Project 3: Gradient Domain Fusion

15-463 (15-862): Computational Photography
Project 3: Gradient Domain Fusion

Jun-Yan Zhu

Overview

In this project, I use gradient domain methods to address computational photography problems including Poisson Image Blending, Salience-Preserving Color Removal, Gradient Domain Sharpen Filtering and Non-Photorealistic Rendering. Gradient Domain Fusion was first introduced in high dynamic range compression [Fattal et al. 2002] and image composition [Perez et al. 2003]. This powerful idea provides a different perspective to look at images. Instead of considering and changing the image intensity, we could manipulate the gradient field. This new perspective gives us two advantages [Bhat et al. 2010]:
1) Great for human perception: The difference between intensities (i.e. gradient) is much more noticeable for our human vision system.
2) High-level control over images: A local change in gradient field could affect the global image.

Gradient domain methods have been applied to many problems in both computer vision and computer graphics. The "Gradient Brush" system presented a friendly user interface to paint in gradient domain with real-time feedback on large images [McCann and Pollard. 2008] while "Gradient Shop" provided a gradient domain optimization framework for defining perceptually motivated image and video filters

Approach

The gradient domain framework could be viewed as a energy function optimization problem, The result image f is generated by minimizing the following function:

where p is a pixel in f, E_d is intensity cost function, and E_g is gradient cost function. The energy terms E_d and E_g are quadratic functions defined as follows:

The energy terms E_d and E_g are the squared errors between the desired values (the guidance intensity image d and guidance gradient field g), and the actual values of the final image f. To keep things simple, we do not use weighting scheme described in "Gradient Shop" [Bhat et al. 2010]. We set w_d, w_x and w_y as uniform weights.

For Poisson Blending and Mixed Gradient, we only use gradient cost function. For Salience-Preserving Color Removal, and Gradient Domain Image Filtering, we use both two terms and set the parameter lambda to balance the tradeoff between fidelity to data versus gradient constraints. Since E(f) is a standard least square cost function, we could solve linear equations as the form of Ax=b where A is a sparse matrix. Please refer [Bhat et al. 2010] for details.

Fast Implementation

I developed a fast MATLAB implementation without using any for loop during the generation of A and b. Further, I use parfor to parallelize the gradient domain optimization problems in three channels. The computational time for most applications is less than 0.5 s in original sizes (without downsampling). For toy problem, I developed two versions with and without using for loops. It takes loop version 0.687399 s to run the toy reconstruction problem while it only takes non-loop version 0.069275 s to do the same thing. For the color2gray appalication, it only takes the program 0.055719 s. Vectorization techniques in MATLAB can really make the program 10x faster. Check my code [out] = grayBlend(src, mask, tgt, mode) for the tricks and details.

Failure Examples

I found two situations where Poisson Image Editing might fail:
1) Texture Mixing Problem: The textures between two images are too different (See "Sheep" Example).
2) Discoloration Artifacts: The color differene between two images is too large (See "The Simpson" Example).

Bells and Whistles

Color2Gray: For Salience-Preserving Color Removal, I first convert RGB image to HSV image. I mix the gradient of S channel and V channel, and also use V channel as intensity constraints. I set the parameter lambda as 0.05.

More gradient domain processing: For Gradient Domain Sharpen Filtering, I magnify the image gradients by a scalar factor and use the original image intensity as constraints. For Non-Photorealistic Filtering, I enhance gradients along edges and suppress others, and use this edge-perceiving gradient map as guidance gradient field. Again, I add the original image intensity as constraints. I set the parameter lambda as 0.05 for these two filters.

Toy Example

Poisson Image Blending

Failure Examples

Mixed Gradients

Color2Gray

Image Filtering

Related Papers

[Fattal et al. 2002] "Gradient domain high dynamic range compression"
Raanan Fattal, Dani Lischinski and Michael Werman
ACM Trans. Graph. (Proceedings SIGGRAPH 2002)

[Perez et al. 2003] "Poisson Image Editing"
Patrick PĂ©rez, Michel Gangnet and Andrew Blake
ACM Trans. Graph. (Proceedings SIGGRAPH 2003)

[McCann and Pollard. 2008] "Real-time gradient-domain painting"
James McCann and Nancy S. Pollard
ACM Trans. Graph. (Proceedings SIGGRAPH 2008)

[Bhat et al. 2010] "Gradientshop: A gradient-domain optimization framework for image and video filtering"
Pravin Bhat, C. Lawrence Zitnick, Michael Cohen and Brian Curless
ACM Trans. Graph. (Proceedings SIGGRAPH 2010)