Submitted in the scope of ‘Computer Graphics Seminar’ course in Winter-Semester 2011 at the TU Berlin, department of CG.
Implement a seamless image blending algorithm (benefiting from the principles of Poisson Image Editing), which enables copying regions from source image to target image, not simply as pixels themselves, but gradients instead, which achieves better results by adjusting copied pixels to the conditions of the new target image !!
g known function of source
f* known function in target over domain S
f unknown function in target over domain Ω
∂Ω boundary between known and unknown regions
Solution idea is to find f whose gradient is the closest to G, gradient of source g.
This can be formulated into :
whose solution is the solution of Poisson equation
under the condition of Dirichlit-boundary : known pixels at boundaries:
this condition is important, because the known boundary works as a reference to reconstruct gradients into the resulting image. And it also plays a big role in constructing the linear equation system.
The condition is already fulfilled, because pixels at boundaries are read from target image.
From (*): div G is the Divergence Property of gradient field
and ∆ is the Laplacian operator
|1 -4 1|
|0 1 0|
Applying these to (*) equation
We turn into a classical linear equation
With number of Unknowns = N pixels
A: NxN matrix , b: N-elements vector
The problem now is to build both b and A !
Suppose Pi denotes the unknown pixel (i) ; i = 1 .. N
And S(x,y) denotes the corresponding pixel (i) in source image
Where Neighbor(Pi) is the subset of the 4 neighbors of Pi (top, bottom, right, left) that contains only neighbors belonging to the boundary. Consider the following image for example
- Put -4 in its column
- Put 1 in columns referring to its neighbors
- Put 0 elsewhere
=> A : 30,000 x 30,000 = 900,000,000 elements
Problem : How to store and deal with it ?!
Solution : Notice that A is a sparse matrix i.e. populated primarily with zeros, so we benefit from sparse notation in Matlab!
Sparse matrix is stored using Coordinated-list compression method, where a sparse matrix (A) is represented with 3 vectors referring to non-zero elements
- Row : row index
- Column : column index
- Value : value at the index A(row, column)
An example considering the last constructed matrix A, at index (1,1) there’s the value (-4), and at index (1,2) there’s the value (1) .. etc.
Row = [ 1, 1, 1, 2, 2, ..]
Col = [ 1, 2, 4, 1, 2, ..]
Val = [-4, 1, 1, 1,-4, ..]
Number of non-zero elements = O(5xN); 5 = pixel itself + 4 neighbors => store 3x5xN instead of NxN
Once A and b are there, X can be easily computed
The next step is initiated by pressing the “Start Computation” button.
In the next step the position of the source image in the target image needs to be specified. The crosshairs determine the position of the upper left corner of the source image.
Left-click to the desired position shifts the source image’s upper left corner to the position of the crosshairs. Subsequently by right-clicking the position is locked and the computation process initiated
In order to show the possibilities of the algorithm let’s have a look at some examples that work and those that don’t.
Both images have a similar setting and are taken with similar ambient light conditions. That makes it easier for the algorithm to compute a good result.
Also the overall smoothness of the images allows the algorithm to create the illusion of seamless blending.
In this example the background of both the source and the target picture have a very different structure and extremely different color. Additionally the ambient light conditions differ quiet a bit.
The source image is taken under the glaring flood light in a football stadium. While the target image is taken under the very soft and warm artificial ambient light of a restaurant. All these factors lead to a very grainy and discolored result.
The edges of the source image are still visible and not at all blended with the background.
The images share similarities though color and ambient lighting don’t match. Nonetheless the result is seamlessly blended and appears natural.
The structures of the stones around the tracks and the leafs on the forrest floor are alike thus allowing for easy blending.
This example shows the pasting of three source images into one target image. Because of similar ambient lighting and settings as well as homogeneity of the backgrounds a neary perfect result is achieved. All edges seem to blend seamlessly and no discolorations can be found.
You can copy and reuse our source code, but referencing us would be a nice gesture 🙂
Amit Agrawal and Ramesh Raskar, Gradient Domain Manipulation, Cambridge, USA, 2007
Patrick Pèrez, Michel Gangnet and Andrew Blake, Poisson Image Editing, Microsoft Research UK, 2003
I welcome any comment or question 😀