Project 2

In this project, I implemented gradient domain image blending, to reconstruct and merge some images. Every image here was generated by constructing a matrix of gradient and boundary constraints for the output image, which was then solved for a least squares solution.

Toy Example

This approach demonstrates that an image can be reconstructed by its gradients and one pixel value. The image below was encoded into the matrix as constraints such that adjacent pixels in the output would have a difference equal to their gradient along that direction in the input image. Additionally the top left pixel had the added constraint of being equal to its value in the original image. When solved, this linear system produced the source image as shown below.

Poisson Blending

This technique is similar to the above but slightly more elaborate. In this case, in the masked region we solve for an image with gradients matching the source image, however on the boundary we consider the difference between a pixel from the generated region, and the adjacent pixel from the target image. These constraints help to preserve the gradient of the generated patch, while ensuring the boundary between the generated and target pixels matches the gradient along the source image. Below you can see our results from blending the provided image pair.

Target Image	Source	Naive	Blended

Speed Improvements

Originally, my implementation of this algorithm was somewhat slow, taking over a minute for each image. I was able to improve the solution speed to the order of a few seconds by making two changes though. The first change was to make use of a sparse linear solver. Given that each row of the matrix we construct should only have two non-zero entries, a sparse solver such as the one provided in SciPy is much better optimized for this problem. The second change was to note that, as described in the homework writeup, the constraints we add to our matrix for pixels not on the boundary of the masked region involve some duplicates. In particular, the constraint from one pixel to the one to the left of it is equivalent to the constraint from the second pixel to the first. Noting this, I was able to remove all constraints between two internal pixels going either left or up. Removing these roughly decreased the number of constraints by half, which helped the solver to perform about twice as fast.

More Output Cases

The following are some other images I generated using Poisson blending. Note that, in cases like the skydiver image, since the background of the target image roughly matches the color and texture of the background of the source image, the blend is fairly seamless. The only artifacts are around his hand where the background in the source image is less smooth.

Target Image	Source	Naive	Blended

The cat example shows a case where Poisson blending alone doesn't give a satifactory blend of the two images. Since the background of the cat image along the border is white, while the background of the leaf image is green, the cat gets tinted green, rather than its original color. This is most likely due to the fact that the cat is defined in the linear system as the gradient between it and the background in the source image rather than the actual pixel values, so starting from a green pixel rather than white along the boundary will keep that green color throughout the rest of the image.

Another artifact to note from that cat image is that Poisson blending is not a perfect substitute for image matting. Towards the left of the cat's face, a bit more of a border is given on the mask. This means that background pixels from the source image which don't make up the cat are being used there in the output image. Since the cat background is smooth while that area on the leaf has a lot of texture, the resulting combination just looks blurred.

While not perfect for every case, the boundary color artifacts can be useful for some types of image blending, such as the following case where mostly greyscale images of faces are being blended onto colorful fruits. In this case, the color transferring of the blend actually helps to create a better looking output image than if the greyscale inputs had been preserved.

Target Image	Source	Naive	Blended

Say hello to John Lemon, Appaul McCartney, George Pearrison, and Mango Starr.