Project 2: Poisson Image Editing
cs195-g: Computational Photography Patrick Doran
Spring 2010 pdoran
High level description of the algorithm.
1 Reshape the source, mask, and target so they all have the same dimensions.
2 Create a sparse matrix that is #pixels x #pixels and initialize the diagonal to 1s (MATLAB optimization). This is the coefficient matrix. Also initialize the solution vector values for those pixels not in the mask. Their final values will be their value in the target.
3 Iterate over indices of white pixels in the mask and determine the system of equations:
Coefficient matrix
-1 for neighbor pixels within the mask
0 for neighbor pixels outside the mask
N Number of neighbors the pixel has (4 except at image edges)
Solution vector
f* pixels not in the mask (these pixels will be the same as their input values)
sum(v) + sum(f*) sum(gradient(Current-Neighbor in source image)) + (sum(Neighbors in target) if neighbor is not in the mask)
4 Solve the system of equations
5 Repeat for each color channel and combine.
General Comments

The algorithm assumes that the color of the source image is close to that of the target. This assumption means that when the colors don't match, the source image color gets tinted toward the color of the target image.

The big-O speed of the algorithm depends on the system of equations solver implementation as well as how long it takes to set up the equations. In MATLAB, the biggest time-waster is indexing into a large sparse matrix. I've managed to bring the indexing down to the number of white pixels in the mask, but it is still very slow. Possible speed improvements lie within having a sparse matrix be smaller in size, though the overhead for that appears difficult compared to the current implementation.

Bells and Whistles

Preserve transparencies by taking the stronger of the source and target gradients at each pixel. Compare the magnitude of the gradients of the pixel to the neighbor. Take the stronger of the two. An individual pixel may take some of the gradients from the source and some from the target. The plane and rainbow use this gradient mixture model.

There is a tendency of the results to blur the target image around the source image mask. This is not desirable, however there is no distinctly visible seam. There is also a tendency of the source image to absorb the color of the target image underneath. In the case of the bear in water, the bear became blue tinted; in the case of the plane, it became dark like the mountains in the background.
Source Mask Target Result