For my final project I implemented part of a 2004 SIGGRAPH paper by Levin et. al. titled "Colorization using Optimization." The authors demonstrate a technique for colorizing black and white images by taking input in the form of a user's colored markings on the image.
In this paper, images are handled in YUV space, where one channel (Y) indicates the intensity of a pixel and the two remaining channels (U and V) determine the color. The algorithm, then, takes as input a normal Y channel and two mostly-empty U and V channels. It then attempts to solve for the mising U and V values. It does so by creating a sparse linear system of equations relating each pixel and finding the lowest-cost solution. The main insight of the algorithm is that adjacent pixels with similar intensity values should also have similar color values. Thus, the color at each pixel is driven by a weighted sum of the colors of the pixels around it, where the weights are given by a function that sums to 1 across all neighbors, is large when the intensities of the two pixels are similar, and small when they are different. This relationship, when anchored by the user-selected colors at certain pixels, yields a large sparse matrix of equations and solutions which can be solved as in project 2.
To test my algorithm, I wanted to remove as much human influence as possible. Thus, rather than draw on black-and-white images, I took color photos and randomly discarded 99% of their color information. I then attempted to recolor them using my algorithm. The results can be seen below.
| Original | 99% color removed | Recolorized |
|
|
|
Knowing my algorithm worked, I then attempted to do as the authors had done and colorize black and white photos by drawing on them. The results can be seen below.
| Original | With markup | Colorized |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
The results are generally pretty convincing, although color can sometimes bleed across boundaries if they are not well-marked. The original paper makes the markup process seem relatively easy. In reality, it is a fairly error-prone process that requires some trial and error to achieve desirable results. However, as the decolorized images show, given accurate markup the algorithm will produce excellent results.