Please refer to my slides for more info.

For my final project, I re-implement the algorithm described in "Colorization Using Optimization" by Levin, Lischinski, and Weiss.

The goal for the algorithm is to colorize a grayscale image given a user's scribble on the image indicating the color of different regions in the image. The key concept of the algorithm is that neighboring pixels with similar intensities should have similar color. This means that we want to minimize the different between the color at each pixel and the weight average of the color of its surrounding pixels.

The weight for each neighbor pixel is calculated based on its intensity compared to the intensity of the center pixel. I chose to use the first weighting function suggested by the paper.

In order to solve the optimization problem, we first set up a weight matrix A. Each row of A represents the weights for 1 pixel and its neighbors, with column i holding the weight for pixel i. We fill the diagonal of A with 1 to represent the fact that each pixel should get a weight of 1. Then we proceed to fill in the weights for each pixel's neighbors in each pixel's row. Note that if a pixel has been labeled by the user, then we leave its neighbor's weights as 0 since we'll be using its row as a constraint in our system of equations.

We then set up a vector b representing all pixels in the image. If pixel i has been labeled by the user, then the ith row of b will contain the value of the color. Otherwise, b contains 0.

Given A and b, we used MATLAB's backslash function (A\b) to solve the equations. The resulting vector represents each pixel in the color image.

In order to compensate for the fact that the user might draw large blobs of color on the grayscale image that might match the intensity level poorly, we performed an extra step after colorization. We replaced all the pixels labeled by the user with the corresponding pixels in the original grayscale image and re-ran the optimization algorithm using the newly obtained colorized image as the set of labeled pixels.

I've also implemented a website that allows a user to label an image and see the colorization result.

Grayscale Image:

Colorized Image:

• sky: http://www.givingwhatwecan.org/sites/givingwhatwecan.org/files/Krisztina%20Csortea/Create%20Story/blue_sky.jpg
• flower: http://imageretouchingblog.com/wp-content/uploads/2009/05/YellowFlowerCloseUp1.jpg
• road: http://www.roadsafetyfoundation.org/media/2853/road-homepage-1-small.jpg
• micky: https://www2.bc.edu/alaina-beyar/images/micky.jpg
• river: http://imgs.sfgate.com/blogs/images/sfgate/hawaii/2011/03/30/wailua_river612x459.jpg
• grass: http://m.rgbimg.com/cache1nNuYq/users/s/sc/scottmliddell/600/mjQnA4A.jpg
• child: http://www.cs.huji.ac.il/~yweiss/Colorization/