Week 4: Poisson Editing

Goal

This week we wanted to solve the image editing problem of cloning areas from one images and adapting them to another one. We implement a method that uses the Poisson partial differential equation with Dirichlet boundary conditions to achieve a seamless clone.

src (girl.png)

dst (lena.png)

dst with src eyes & mouth

Mandatory Tasks

Implementation

We study the method described in “Poisson Image Editing” by Patrick Pérez et al. and implement it in two different ways in order to fit src eyes and mouth into dst eyes and mouth seamlessly.

	Set of connected neighbors of pixel p (in our case, 4).
	Value of f at p within unknown area.
	Value of f at q (where q is an element of Np) within unknown area.
	Value of f at q within known area (src - dst, which includes the boundary)
	Difference between value of g at pixel p and value of g at neighbor q

Rearranging the equation above taken from Pérez, we can see that in order to obtain the value for a pixel p, we need to compute the sum of all the nearest neighbours in the border, in the domain, and the difference between the pixels in g and their 4-neighbours.

G4_PoissonEditing_GS

This function uses the Gauss Seidel scheme to solve the discrete Poisson pixel by pixel iteratively.  We crop the masks and images at their corresponding location,

Resulting image using Gauss-Seidel

Within this function, we call G4_gaussSeidel for each color channel.

   

G4_gaussSeidel

This function iteratively solves the equation

as such:

G4_PoissonEditing_CG

This function instead uses the preconditioned gradients method to solve the Poisson equation in the form Ax = b.  A is the matrix created by G4_createA (explained below). b is the laplacian of the source image with the destination boundaries, and x if the resulting image f.

Resulting image using PCG

G4_createA

Creates the matrix A for solving the discrete Poisson equation with the pcg method. This is a sparse matrix of the form:

In G4_PoissonEditing_CG we create a matrix A of dimensions 990x990px (for the eyes). We modify in this matrix the corresponding values in order to conserve the lenna crop borders information. It looks like the following:

Full 990x990px Poisson matrix.

Close-up of pattern (white = 4, black = -1, gray =1, background = 0))

The rows having only one gray pixel (value = 1), like the first ones and the last ones, correspond to the boundaries, and will let us assign directly the value of B to f . The other rows apply the Laplacian operator to each pixel.