January 29, 2010

I have implemented a poisson image blending algorithm. The algorithm first generates an array the same size as the image, wherein the value at cell (i,j,k) is the sum of the differences of pixel (i,j,k) from its neighbors in the source image. This is equivalent to the gradient at pixel (i,j,k). The number of neighbors at (i,j,k) is then computed. A sparse matrix A of size ((image width)*(image height)*3)^2 is constructed, such that each row R represents the constraints on the value of the pixel at linear index R. For pixels not in the mask, the row R contains 1 at column R. b(R) is set to the value of the pixel in the target image. For pixels in the mask, the value for the pixel in row R is set to the number of neighbors, and each neighbor is assigned a value of -1 in row R. b(R) is set to the gradient of the pixel with linear index R. The matrix A is constructed in one line, so as to avoid indexing into a large, sparse matrix. This sped up execution time considerably. Solving A*x=b for x gives the pixel values for the output image.

While I am extremely thankful for the support code provided in fix_images.m, by enclosing the source image inside a larger image, it became difficult to determine where the edges of the source image where. If the mask included an edge of the source image, then my calculations for gradient would include the difference between an edge pixel and the black space surrounding it. This gave some strange results. My "hacky" solution to this was to insert the source image into a copy of the source image that was one pixel larger in each dimension.

Source Gradient | Source Gradient With Hack |
---|---|

Without Hack | With Hack |

- Mixed Gradient Poisson Blending
I followed the extension explained in Pérez et. all. For each pixel, and for each neighbor of that pixel, I choose the gradient in the source image, or that in the target image, whichever magnitude was larger. The gradient at that pixel was set to the sum of these four values.

Source | Mask | Target | Result |
---|---|---|---|

This implementation does not deal with transparency or images with holes. The trees in the rainbow image are blurred, and the texture of the brick wall image is lost near the writing. Some bleeding also occurs near the bottom left edge of Nicolas Cage's face, as well as the top of the Polar Bear's face, but these could be fixed with tighter masks. The strangest glitch is that the question marks on Matthew Lesko's shoulders take on the features of the pavement behind them. This might be explainable due to the low gradient between these question marks and the background in the source image.

Source Gradient Blending | Mixed Gradient Blending |
---|---|

A mixed gradient seamless insertion is better for the jet, rainbow, and wall images. The difference for the ceiling cat and ufo images is negligable. Using mixed gradient blending on faces yields some interesting results. When the faces in both images are roughly the same, the resulting blur looks similar to a morph between the two. When the faces are not in similar positions, such as for the bear statue, both faces appear. This ghostly double image is also evident in the images of the Gonk Droid, Matthew Lesko, and to a lesser extent the bear in the pool. It is apparent that, for many pixels, the source images used in these three images had a lower absolute value for gradient than did the target image. I can conclude that the multi gradient approach is not always superior to the single gradient one, as it tends to add transparency where a user would not.