Project 2: Image Blending Writeup

Travis Webb (jtwebb)
Feb. 17, 2010

The Algorithm

I implemented poisson image blending. The given photos are the first 5 in the table. The following 5 are my own creations taken from the internet and/or photos that I had (The wagon and tiger photos are my attempt at approximating Calvin and Hobbes).

Poisson blending works by solving a system of linear constraints on a region of unknown pixels. A mask is used to specify pixels in the "target" image that are to be modified (either replaced or blended). The mask also specifies pixels in the "source" image that will be put in the target image. Pixels in the "target" that fall under the mask are considered unknown. The value of those unknown pixels are computed by poisson blending.

To begin, pixel is assumed to be the average of its neighbors even if those neighbors are unkown. We can think of this as the system Ax = b. Where x is a vector with elements that are pixels in the output image. Each row of A holds an equation for a pixel in the output image (an element in x). To begin, each element in b is either the value of the pixel if it is outside the mask or 0 if it is under the mask. To begin, a row of A has 1 on the diagonal and a 0 everywhere else if the pixel is known (and thus a correct value in b). This means that equation will be x_i = b_i which is exactly what we want. Other rows in A have neighborCount in the diagonal and -1 at the column corresponding each neighbor. For example a given non edge pixel will have four nieghbors and its equation will be 4x_i - x_n1 - x_n2 - x_n3 - x_n4 = 0. This is exactly what we want for basic poisson blending. This will take each unknown pixel and compute its value to be the average of its neighbors.

The next step is to draw information from the source image into the target. Now each unknown pixel will be computed based on the average of its neighbors and the data from the source image. The only change we need to make is to replace the 0s in b with the sum of a pixel to its gradients in the source image. For example a given non edge pixel will have four nieghbors and its equation will be 4x_i - x_n1 - x_n2 - x_n3 - x_n4 = sum j=1to4 source_i - source_nj.

Implementation Details

I implemented the alogrithm two ways. First I implemented it with loops and if statements. This solution is incredibly slow. Next I vectorized everything and it is almost instantaneous. However in the vector implementation assumes that everything has 4 valid neighbors so it will not work in the case where an unknown pixel is on the edge (or corner of an image). The slow version works just fine on that image, but the fast version crashes. It was handy to have the fast version around to align images and use in the general case, but if you are desperate for those corner pixels you are stuck with loops.

Some discussion of results

My Calvin and Hobbes tigers suffer from having to cover up the girl in the picture so they are obviously oversized. I'm not sure what's causing the night sky whale to be shifted red so strongly. The forest orchestra is just semantically off so it doesn't look right.

Results Images

Source Target Result