Assignment #2 - Gradient Domain Fusion

Background

This project explores gradient-domain processing, a simple technique with a broad set of applications including blending, tone-mapping, and non-photorealistic rendering. For the core project, we will focus on “Poisson blending”; tone-mapping and NPR will be investigated as bells and whistles.

The primary goal of this assignment is to seamlessly blend an object or texture from a source image into a target image. The simplest method would be to just copy and paste the pixels from one image directly into the other. Unfortunately, this will create very noticeable seams, even if the backgrounds are well-matched. How can we get rid of these seams without doing too much perceptual damage to the source region?`

Here we take the following approach: The insight we will use is that people often care much more about the gradient of an image than the overall intensity. So we can set up the problem as finding values for the target pixels that maximally preserve the gradient of the source region without changing any of the background pixels. Note that we are making a deliberate decision here to ignore the overall intensity! So a green hat could turn red, but it will still look like a hat.

We can formulate our objective as a least squares problem. Given the pixel intensities of the source image “s” and of the target image “t”, we want to solve for new intensity values “v” within the source region “S”:

v = \arg \min_{v} \sum_{i \in S, j \in N_{i} \cap S} {((v_{i} - v_{j}) - (s_{i} - s_{j}))}^{2} + \sum_{i \in S, j \in N_{i} \cap \neg S} {((v_{i} - t_{j}) - (s_{i} - s_{j}))}^{2}

Here, each “i” is a pixel in the source region “S”, and each “j” is a 4-neighbor of “i”. Each summation guides the gradient values to match those of the source region. In the first summation, the gradient is over two variable pixels; in the second, one pixel is variable and one is in the fixed target region.

The method presented above is called “Poisson blending”. Check out the Perez et al. 2003 paper to see sample results, or to wallow in extraneous math. This is just one example of a more general set of gradient-domain processing techniques. The general idea is to create an image by solving for specified pixel intensities and gradients.

Part 1.1 Toy Problem

The goal of this part of the assignment is to compute the x and y gradients from an image s, then use all the gradients, plus one pixel intensity, to reconstruct an image v.

Approach

We use the following formulation for this problem. Denote the intensity of the source image at (x, y) as s(x,y) and the values of the image to solve for as v(x,y). For each pixel, then, we have three objectives:

Minimize $((v (x + 1, y) - v (x, y)) - (s (x + 1, y) - s (x, y)))^{2}$ , so the x-gradients of v should closely match the x-gradients of s.
Minimize $((v (x, y + 1) - v (x, y)) - (s (x, y + 1) - s (x, y)))^{2}$ , so the y-gradients of v should closely match the x-gradients of s. Note that these could be solved while adding any constant value to v, so we will add one more objective:
Minimize $(v (1,1) - s (1,1))^{2}$ The top left corners of the two images should be the same color

Via this formulation, we are able to reconstruct the original grayscale image using least-squares equations. We use scipy.sparse.linalg.lsqr since the "A" matrix is sparse. Some reconstructions are shown below.

Results

Here are the results after running the least-squares optimization on some grayscale inputs.

Toy Problem
(Buzz and Woody)

Toy Problem
(Lightning McQueen)

Toy Problem
(Minions)

Part 1.2 Poisson Blending

This part aims to seamlessly blend a cutout from a source image into a target image by creating a new image whose gradient values are guided to match those in the source image, and whose boundary gradient values are guided to match those in the target image. The least squares solver will then take any hard edges of the cutout at the boundary and smooth them by spreading the error over the gradients inside “S”.

Approach

The approach we take here is to first get the bounding box of the source mask, then crop all of source, target, and mask to that bounding box (we also expand the bounding box by one pixel on all sides since we need the 4-neighbour of every source region pixel). This is for computational efficiency's sake, since we are only changing the part of the image that is masked out, and thus we only need to generate an image of at most the size of the bounding box of the mask (imagine if the target image was huge compared to the source mask, we would have a lot of computational savings in this case). We then iterate over this bounding box, and add the blending constraints in the form of matrices, making sure we respect the boundary conditions by doing bounds checking (the number of constraints is less than equal to bounding box area * 4, since we iterate over all pixels' 4-neighbours). Lastly, we pass our matrices into the least squares solver. We use scipy.sparse.linalg.lsqr since the "A" matrix is sparse.

Below are the results after running Poisson Blending on some images:

Sample Image Results

Source

Target

Bear in Pool

Favourite Image Results

Source

Target

Happy Feet

Extra Image Results

Source

Target

WALL-E in space

Failure Image Results

Source

Target

Godzilla Building Blend

Possible Reasons for Bad Results

Examining the failure case (Godzilla image), we see that one possible factor that leads to bad blending is the background having too much detail/texture that the foreground does not have. The edges around Godzilla are very blurred out and look like the average between the buildings and its own gray, featureless background. We also see that the Poisson blending process can badly affect the intensity of pixels in the source image, a phenomenon that is particularly prominent in the bear and godzilla images, where we see the dark regions go even darker. The cause of this may be that the background's and foreground's gradient distributions are too different, or that the lighting conditions of the two images are too dissimilar, leading to suboptimal blending.

Bells and Whistles

Mixed Gradients

I followed the same steps as Poisson blending, but use the gradient in source or target with the larger magnitude as the guide, rather than the source gradient: $v = \arg \min_{v} \sum_{i \in S, j \in N_{i} \cap S} {((v_{i} - v_{j}) - d_{i j})}^{2} + \sum_{i \in S, j \in N_{i} \cap \neg S} {((v_{i} - t_{j}) - d_{i j})}^{2}$ , where $d_{i j}$ refers to the value of the gradient from the source or the target image with larger magnitude.

Here's a sample result from using mixed blending:

Source

Target

The Cake is a Happy Lie

Color2Gray

Sometimes, in converting a color image to grayscale (e.g., when printing to a laser printer), we lose the important contrast information, making the image difficult to understand (see rgb2gray examples in the images below). One way to solve this problem is to use mixed gradients to preserve the contrast of the original RGB image.

To create a gray image that has similar intensity to the rgb2gray output but has similar contrast to the original RGB image, I used a similar formulation to that of Part 1. As per Part 1, I use the grayscale image (mean of the 3 channels) as the guide, but I also add extra least square constraints by converting the image to the HSV color space and using the larger gradient between saturation and value channels as the guide.

Here are some examples: