Project 3

Toy Problem

This is just an example for how to set up constraints and construct output images by solving linear least square problems.

Here is the sample image:

Setting up the following constraints on the ouput image:

1. minimize $(v(x + 1, y) - v(x, y) - (s(x + 1, y) - s(x, y)))^2 $
2. minimize $(v(x, y + 1) - v(x, y) - (s(x, y + 1) - s(x, y)))^2$
3. minimize $(v(1, 1) - s(1, 1))^2$

We can now construct linear least square $Av = b$, where v is the pixel values of the output image, A is the coefficient matrix of equations and b is the vector of constants in the equations.

Take $(v(x + 1, y) - v(x, y) - (s(x + 1, y)-s(x, y)))^2$ as an example. Since we want to minimize the value of it, we can write it as $v(x + 1, y) - v(x, y) = s(x + 1, y) - s(x, y)$. Suppose $i$ correspond to the index of $v(x + 1, y)$ and $j$ correspond to the index of $v(y, x)$ in vector $b$. Then we can insert a new row $k$ into $A$ and $b$, where $A(k, i) = 1, A(k, j) = -1, B(k) = s(x + 1, y) - s(x, y)$ and rest of $A(k)$ will all be $0$.

Then solve $ A$ \ $ b $ to obtain the pixel values of the output image, which is almost the same as the input image (with error of about $9e^{-14}$).

Poisson Blending

In this part, we will be blending two images - one as the foregorund and the other as the background.

A simple solution is to copy paste the foreground image onto the background image:

Obviously, this can not even fool people in 1800s.

Fortunately, we have an alternative approach - Possion blending, which can significantlty improve the result of blending.

For every pixel $s(y, x)$ in the foreground, for its neighboring pixels at $(y + j, x + i)$, $i \in \{1, -1\}, j \in \{1, -1\}$, try to maintain the gradient between them.

Setting up the following constraints on the ouput image:

1. minimize $$\sum_{i \in S, j \in N_i \cap S} ((v_i - v_j) - (s_i - s_j))^2$$
2. minimize $$\sum_{i \in S, j \in N_i \cap \neg S} ((v_i - t_j) - (s_i - s_j))^2$$

Similarly, solve $ A$ \ $ b $ to obtain the output image.

Here is the result:

This is much better than the copy-paste approach.

Here is another result, which is not quite ideal:

As is shown in the reuslt image, the color of the lion is way too greenish, which is a result of maintaining the gradient between the greenish pixel in the background image and the margin of the foreground image.

Here is another good result

Mixed Gradient

This approach is pretty similar to Possion blending in the previous part except that instead of only using the gradient of the foreground image, we are comparing it to the gradient of the background image and select the one with greater absolute value.

Setting up the following constraints on the ouput image:

1. minimize $$\sum_{i \in S, j \in N_i \cap S} ((v_i - v_j) - d_{ij})^2$$
2. minimize $$\sum_{i \in S, j \in N_i \cap \neg S} ((v_i - t_j) - d_{ij})^2$$

, where $d_{ij} = s_i - s_j$ if $|s_i - s_j| > |t_i - t_j|$, otherwise $d_{ij} = t_i - t_j$

Similarly, solve $ A$ \ $ b $ to obtain the output image.

Here is the result:

As a result of using mixed gradient, some of the patterns and color of the background image are been preserved in the result image, which makes the rainbow look more transparent. In this example, using mixed gradient improved the result.

However, the transparent-ish foreground image may also result in relatively poor result:

Poisson Blending:

Mixed Gradient:

Color2Gray

In the process of converting colored image into grayscale image, we may lose important gradient information. As is shown in the following images

In this approach, we are trying to preseve the gradient of the original image as well as to have similar intensity of the grayscale image.

Setting up the following constraints on the ouput image(let $g$ be the grayscale image):

1. minimize $$\sum_{i \in S} (v_i - g_i)^2$$
2. minimize $$\sum_{i \in S, j \in N_i} ((v_i - v_j) - (s_i - s_j)))^2$$

Similarly, solve $ A$ \ $ b $ to obtain the output image.

Here is the result:

In comparison to the grayscale image, the numer "4" is still slightly noticiable in the result image