Assignment #2 - Gradient Domain Fusion

Overview

In this project, the goal is to leverage gradient domain methods to tackle image blending problem. Particularly, instead of changing pixels' intensities directly, we manipulate the gradient field of images.

Effect Preview (From Course Assignment webpage)

Part1.1 Toy Problem

For toy problem, we are solving a least square problem where we try to minimize the gradient difference between synthesized image and source image in both the x and y direction. Assuming the size of source image is H*W, we'll got 2*H*W+1 equations in total. Notice here we need to add scale constraint to the synthesized image otherwise its value will explode. The equations comprise following parts:
1. For each pixel, we minimize gradient in x direction: \(((v[x+1,y]-v[x,y]) - (s[x+1,y]-s[x,y]))^2\), which brings H*W equations;
2. For each pixel, we minimize gradient in y direction: \(((v[x,y+1]-v[x,y]) - (s[x,y+1]-s[x,y]))^2\), which brings H*W equations;
3. For first pixel (top left corner), we minimize the pixel difference of it between source: \((v[0,0]-s[0,0])^2\), which brings 1 equation;

To solve this least squares problem I reformulate the above equations into: \(Av=b\), where b is the gradient from source image and A is a sparse matrix arranged based on above equations. I apply Scipy.sparse.linalg.lsqr function to get v.

Part1.2 Poisson Blending

Similar to the toy problem, but in this part, we are dealing with two different images, the source image and the target image. The task is that we want to crop a certain part from source image, do some modification and clone it into target image seamlessly. To achieve "seamless", we adopt similar strategy as toy problem.
We use gradient of source image as guidance field, but on the boundary, we force the pixel to be consistent with the target image. In this way, we can obtain an image which have consistent texture and color with target image while pertain the shape in the original source image.
Mathematically, the problem can be defined as an optimization problem:
$$\text{min}\iint_{\Omega}|\nabla f - \mathbf{v}|^2, $$ $$f|_{\partial \Omega} = f^*|_{\partial \Omega}$$ where \(\mathbf{v}\) is the guidance field and here a reasonable choice would be the gradient from source image: \(\mathbf{v}=\nabla s\). And f is the image we want to create.
For image, the discretized version of above problem is: $$\boldsymbol{v} = \text{argmin}_{\boldsymbol{v}} \sum_{i\in S, j\in N_i \cap S}((v_i - v_j) - (s_i - s_j))^2 + \sum_{i \in S, j \in N_i \cap\neg S}((v_i - t_j) - (s_i - s_j))^2$$ The unique solution for above Poisson equation with Dirichlet boundary conditions is: $$\Delta f = \text{div} \mathbf{v} = \Delta s,$$ where \(\Delta\) denotes Laplacian operator.
Therefore, the blending process is quite straighforward, we build a discretized Laplacian filter \(A\) (Refer to the code for implementation detail), then we solve the following linear system \(Av=b, (b=As)\), where v is the blended image and s is the source image.
Some results are listed as below.

Although Poisson blending is fast and efficient for simple blending, it is likely to fail on some extreme cases. In general, for images that have very different textures (e.g. wood floor vs grass land, or very different lighting) and colorization (e.g. cute cartoon vs foggy and dark theme), Poisson blending cannot give satisfiable results. (See below)