Project 2 Writeup: Image Blending

Basia Korel (bkorel)
February 17, 2010

This project entailed implementing a seamless image blending algorithm using Poisson's equation to solve a large system of linear equations. The basic premise is given a subset of a source image, this region should be seamlessly composited onto a second target image. This project refers to "Poisson Image Editing" by (Perez, et al.). The algorithm is based on solving equation 7 in "Poisson Image Editing". For each pixel under the mask, the pixel value must satisfy this equation; thus each pixel is the average of its neighbors plus the gradient of a pixel and its neighbor in the source image. Solving this problem can either be tackled recursively, or as large series of constraints (the later being the approach taken). I am solving for m*n linear equations with m*n unknowns which can be represented in standard matrix form as Ax=b and solved to get exactly one solution. Ax=b can easily be solved in Matlab as "x=A\b", with x being the resulting image. The bulk of this problem rested in filling in the m*n x m*n A matrix, and the m*n b column vector. In my implementation, I solve a system of linear equations using Ax=b. A is a matrix of m*n linear equations and m*n unknowns. For each pixel p that is not under the mask, A contains the value 1 in the position along the main diagonal. For each pixel p that is under the mask, A contains the number of neighbors of p at the main diagonal for the row, and the value -1 at indices of neighboring pixels to p (this is regardless of if the neighbors are under the mask or not). Since this A matrix is very large, I use a sparse matrix in Matlab. I first find all the coefficient matrix values ahead of time before constructing the sparse matrix A. b is a column vector of known pixel values and calculated values from mixed gradients of the target and source image. I first set the known values in b to the target pixels values for all pixels not under the mask. I have only one for loop that iterates through all of the pixels under the mask. This for loop is essentially computing all the coefficient matrix values for populating matrix A, and calculating gradients to populate vector b. Within this for loop, I check all image edge cases for the set of 4-connected neighboring pixels to p. If a neighbor to pixel p does exist, I add -1 to A at the neighbor index (index is a linear index). I also store the image indices of the neighbor for computing the gradient. For this assignment I did thetransparency extra credit such that I computed mixed gradients, taken from a combination of source and target (refer to equation 13 in the paper). For pixel p and neighbor q, the largest absolute value of the gradient in either the source or target image was taken. This gradient is inserted into vector b for the pixel. As the last command before solving Ax=b, I construct the sparse matrix A.

Results Images