Assignment 2: Gradient Domain Fusion

Assignment Overview

Background

Lets say I have two images. The first is of 2 penguins, the second of another lone penguin, and I want to place the lone penguin with the other two. Just copying and pasting will result in poor and unrealistic result. That's where gradient-domain processing comes into play. In this assignment will be writing a Poisson blending method.

Poisson image blending will allow us "remove" or blend the seams of a source image when placing it into a target image. Our combined image result utilizes gradients for a smooth blend, we are tyring to preserve the gradients of the cutout image without changing the background. The mathematics of this idea are explained below in the Method section.

Copy & Paste

Poisson

Method

We will write our problem in the form of the following equation.

Let's dig in to what this equation means. First variable definitions.

S: The source image. The image we are trying to paste into our target.

s_i or s_j: The ith or jth pixel in the image S.

T: The target image. The image we are trying to paste the source into.

t_j: The jth pixel in the target image.

v: The resulting image. The image combining S and T using Poisson blending that we are solving for.

v_i or v_j: The ith or jth pixel in the image v.

N: The four neighbor region (above, below, left, right) around pixel i.

Now that we have defined what variables are in the equation, we can describe what each part does. Starting with the left side of the equation. For every pixel i in S we are minimizing the difference in between the gradient of the current pixel in the source image and the gradient of the current pixel in our resulting image. We cover the gradient in multiple directions by also looping over each of the four neighbors in N for every i, so each j is the location directly above, below, to the right or left of i, but only if location j is also in the source image. Note that this does count the y and x gradients twice, simply for computational ease. The right half of the equation handles the edges of the source image. j now covers the neighbors of i NOT in the source image. In this case, position j is not in the source image, so we are using t_j from our target image instead of v_j as they are the same in this case.

Implementation Details

We implemented Poisson image blending in python utilizing OpenCV, Scipy and Numpy. We convert the equation into a format compatible with Scipy's sparse least squares function and solve for v. Pseudocode for the implementation can be seen below. The mask is way to determine if a pixel is in the source image with ease. If the mask is true, or 1, a given pixel is in S.

        
          A = initialize coefficient matrix
          b = initialize dependent variable matrix
          for i in range(pixel amount):
             for each neighbor location (j) in N:
                if mask[i] == 1:
                    # if below pixel in mask
                    if mask[j] == 1:
                        A[e, im2var[i]] += 1
                        A[e, im2var[j]] = -1
                        b[e] +=  si - sj
                    # if below pixel is not in mask
                    else:
                        A[e, im2var[i]] += 1
                        b[e] += si - sj + tj
                else:
                    A[e, im2var[row, col]] = 1
                    b[e] = ti
                    e += 1
        A_sparse_0 = sparse.csr_matrix(A)
        v = scipy.sparse.linalg.lsqr(A_sparse_0, b)
        return v
        
    

For speed we use OpenCV's BoundingRect function to find a bounding box that encompasses the True area of the mask, we then perform least squares on just that subsection of the images to avoid looping through all the pixels in a given image.

Toy Problem

Before jumping into Poisson image blending, we start with a "Toy Problem" where we simply use the image gradients to reconstruct an image. We do this with following 3 objectives:

1) Minimize ((v(x+1,y) - v(x,y)) - (s(x+1,y) - s(x,y)))²

2) Minimize ((v(x,y+1) - v(x,y)) - (s(x,y+1) - s(x,y)))²

3) Minimize (v(0,0) -s(0,0))²

1 & 2 are for the x and y gradients of v to match that of the source image. The third objective to make sure the upper left corners of the S and v are the same to prevent the optimization from finding a constant value as the solution. Expanding on the provided pseudocode and solving the least squares problem yields the following result.

Original

Reconstruction

Poisson Blending Results

Favorite

This result is from preforming Poisson image blending a couple of times to get 3 of me in the same image. Sage, the cat, is a bit blurry in the result, but we will forgive her photo bombing and even add her into the image again.

Source

Target

Copy & Paste

Poisson

Copy & Paste

Poisson

Another Result

Source

Target

Source

Target

Failure

Let's look at where this method fails. Let's use the same couch from my favorite result and plop a group of my friends on it. The couch they are sitting on is different from mine and is not blended in well. The image was also taken at a different angle, this causes the man on the far left to look a bit off. His lower half seems out of proportion to the rest of him. Poisson blending is a simple algorithm and cannot fix source images skewed with respect to the target. This method darkened the source, this can be undesirable when tyring to preserve skin tone and hair color. This may be caused by the matching of image gradient to the background, a dark gray couch, in this case we probably would just want to match the gradients around the edges of the source and not inside the people. It could also be caused by the fact we ignore overall intensity so the color of things can change.

Source

Target

Source

Target

Mixed Gradients

For bonus I also implemented mixed gradients. As shown below, because we choose the image (source or target) with the largest gradient to contribute as our second term in each summation for the least squares equation at any given point, it is easy to ignore low detail/smooth areas of the source image and instead favor the high details of the target image. We can see that the mixed gradient method preserves much more detail from the target image than the Poisson image blending method does.

Source

Target

Copy & Paste

Poisson

Mixed