16-726 Learning-Based Image Synthesis

Problem

This assignment focuses on blending a foreground image into a background image seamlessly and naturally. The smooth synthesis is achieved via "Poisson blending". For input, the background image, the foreground image translated to ideal location, and the mask of the foreground image in the background image are provided. The "Poisson blending" algorithm will generate the seamless blending result based on gradient map matching where the foreground image is naturally pasted into the background image at the ideal location.

Quick Detour: The Toy Problem

Before we dive into the real problem, a toy problem is set up to help with understanding and implementing the full Poisson blending algorithm. The toy problem helps to confirm if the lease square problemn is set up correctly such that the solution to the least square problem can successfully recreate the original toy image.

In the toy problem setup, the output image is trying to match the gradient of the entire input image as closely as possible. Since there is no other restricting condition, the optimal solution is to have the output image be exactly the same as the input image. To mimic the gradient of the input image, the algorithm tries to solve the following least square problem: \[ \boldsymbol{v} = \arg\min_{\boldsymbol{v}}\sum_{x,y}((v_{x+1, y} - v_{x, y}) - (s_{x+1, y} - s_{x, y}))^2 + ((v_{x, y+1} - v_{x, y}) - (s_{x, y+1} - s_{x, y}))^2 + (v_{1, 1} - s_{1, 1})^2 \] where \(v\) is the output image, \(s\) is the input image, and \(v_{x, y}\) is the pixel value at \((x, y)\) in the output image. Below is the result of the toy problem.

Poisson Blending Algorithm

With the toy problem laying the foundation, the Poisson blending algorithm only requires a minor modification to the toy problem setup. The blending process consists of three steps.

1. First, in order to perform Poisson blending, we need the input preprocessed so that they are compatible with the problem setup. Thanks to the masking_code.py provided, we can easily align the foreground image to the ideal location in the background image and generate the corresponding mask in the background image.

2. Second, with the input images and mask prepared, we can solve the optimal new image that matches the gradient of the background image at the boundary and average the changes into the editing region such that perceptually the blending is seamless. The algorithm constructs and solves the following least square problem \[ \boldsymbol{v} = \arg\min_{\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 \]

3. Third, the solved new image is then pasted into the background image according to the mask.

Issues and Improvements

• When directly appling the problem setup from the toy problem, since the gradient is calculated in one direction (right-left or bottom-up), the gradient at the left and top boundary is not considered. To solve this problem, the least square problem is implemented slightly differently by computing gradient in all four directions at each pixel in the mask.

• Time complexity of the algorithm is a concern since the algorithm is solving a least square problem of \((h\cdot w)\) variables and \((h\cdot w)\) equations. When the image is large, the algorithm can be extremely slow. Hence all input images are resized to maximum 400px in any dimension before processing.
  Moreover, since solving the least square problem is independent among different channels, the solver is parallelized to speed up the process.

Blending Results

Favorite blending result

The blending result of the Nikola Tesla statuette from RI into a lighting show:

The Poisson blending is very successful comparing to directly pasting as shown above. Although the statuette is too dark to see (yet consistent with the background illumination), surprisingly the bottom of the statuette honestly captures the reflection from the light balls of different colors. Zooming into the top surface of the marble base, we can see the reflection in the correct color as well.
For this particular case, the initial result was not satisfactory as I kept a large margin around the statuette in the source image in the first try, resulting in unrealistic bright blobs in the air after blending. After tightening the margin in the source image, the blending result is much more convincing.

Why does Poisson Blending works

In our lease square problem setup, the term \(\sum_{i\in S, j\in N_i \cap S}((v_i - v_j) - (s_i - s_j))^2\) ensures the new image retain the original source image content by matching the gradients within the mask. This results in the object being honestly kept in the new image.
While trying to preserve the source image as much as possible, the second term \(\sum_{i \in S, j \in N_i \cap\neg S}((v_i - t_j) - (s_i - s_j))^2\) ensures the smoothness of the blending at the boundary by constraining \(v_i - t_j\) to be close to \(s_i - s_j\). In the direct pasting case, \(v_i - t_j\) would be significantly larger than \(s_i - s_j\) which inflicts large loss in the Poisson blending setup. Hence optimizing the Poisson blending least square setup yields the smooth blending boundary which has similar gradient to how the boundary looks in the source.

Other blending results

The blending result of an alarm clock on the table into a floor image:

Not only does the floor color smoothly merge into the target image floor, but also the shadow of the alarm clock is properly blended in to reflect the floor color.

The blending result of the provided bear and swimming pool images:

Failure results

The blending result of birds cropped out of image into a sky image:

The blending result is clearly over-exposed on the birds. The underneath of the bird should be dark due to the shadow. However, in the result image, underneath the bird it is clearly too bright as if the bird is slightly transparent. This is because the Poisson blending algorithm tries to make the dark surrounding of the bird in the source to match the blue sky. However, this brightness change has to propagate to inside the source onto the bird in order to satisfy the gradient constraint.

Then I tried adding a sky background to the bird in the source image with a blue color similar to the sky in the target image. The blending result is shown below:

The result is yet another failure. The added background has a smaller value in the red channel than the original background. This causes the bird to appear red in order for the edge to blend in with the target image smoothly.

After tweaking the artificial background by adding more red color, the blending result is finally satisfactory:

Mixed Gradients

The result after applying mixed gradients is:

As shown in the result, the mixed gradients algorithm is able to blend the covered text from the target image into the source image. Also the source text is blended well with the line in the note page.