15463-Computational Photography



cm cleop



Final Project: Automatic Colorization

Varun Ramakrishna





Introduction

For my final project I chose to explore techniques to automatically colorize black and white images. There exists a huge archive of Black and White photography taken ever since the camera was invented. It would be interesting to see how some of these images might look in color. However for a particular B&W picture, though there are certainly "incorrect" colorizations, there might exist multiple "correct" colorizations. To reduce the ambiguity, a similar color image is provided to act as a reference for the colorization procedure. The approach followed were the methods implemented in the following two papers, with a few modifications of my own


1. Colorization by Example, - R.Irony, D.Cohen-Or, and D.Lischinski, Eurographics symposium on Rendering (2005)

2. Colorization using Optimization, - Anat Levin, D.Lischinski,  Yair Weiss, SIGGRAPH (2004)

Overview





                                                                                                                         Colorization by Example, - R.Irony, D.Cohen-Or, and D.Lischinski


The reference image is segmented according to the different regions in the image. Each region is assigned a label and is used in the subsequent supervised classification scheme for segmentation of the input image. Features are extracted from the input and reference image. The input image regions are classified using a two step process, voting in image space and voting in feature space. Finally the colors with a high computed "confidence" are transferred from the reference image to the input image, and then fed as input to the optimization step.

    Input & Segmentation
    Feature Extraction
    Classification
    Color transfer
    Colorization by Optimization


Input & Segmentation

The following images were chosen as the input and reference image respectively:

leop1             leopref                               


The reference image was first converted to LUV color space and then segmented using a mean-shift clustering algorithm based on the LUV values. The LUV color space is used because similar colors are perceived to be close together in this space. The basin of attraction and trajectory of the clustering algorithm needed to be fine-tuned based on the image to obtain a meaningful segmentation. For the above reference image  the segmentation image was as shown below:

leopseg

Feature Extraction   


For each pixel in the reference and input images a feature vector was computed for classification. I used the responses to the Maximal Response 8 Filter bank as a feature set. The MR8 filter bank is commonly used in texture classification applications. The reason behind choosing these features is because it was desired to match similar texture regions in the input and reference image, based on the assumption that similar texture regions had similar color.  The MR8 Filter bank consists of Laplacians and Gaussians of varying orientaions and scales as shown below:

mr8


Classification

Each reference feature vector is associated with a label as computed in the segmentation stage. Now the feature vectors corresponding to the input image are classified using a K-nearest neighbours algorithm. However the resulting segmentation of the input image might have a lot of pixels which have been misclassified. We would like to apply something like a median filter to smooth out the noisy misclassifications, however the labels do not have any ordering, hence we need to approach it differently. We proceed by computing a confidence value of the classification of each pixel in each label

cpl

Where N(p,l) denotes the pixels in the neighbourhood of p with a label l. W denotes the weighting, which is calculated as :

cpl2
Where D(q, Mq) is the euclidean distance between q and it's best match Mq. To obtain the new segmentation we replace each pixel label with the label with the highest confidence value. Shown below are the rough segmentation, the new segmentation and the confidence map for the above input image:

lseg1    lsegnewcm

It can be observed that the confidence values are high in uniform regions and lower at boundaries between objects where the color usually changes.



Color Tranfer

Once the input image has been segmented and the confidence map computed, we transfer color between the reference image and the input image. Color is transferred only between regions having a confidence (as computed previously) above a certain threshold. This results in an image with certain regions marked with color ( or scribbles) .
scrib


Colorization using Optimization

To propagate color throughout the image, the approach described by Levin et al was used. The basic assumption of this method is that neighbouring pixels with similar luminance values should have similar colors. We seek to minimize the difference between the color assigned to a pixel and the weighted average of it's neighbours. The weights being determined by the similarity of their luminance. The objective function used is :

cpl3
Where the ws are the weight computed based on the similarity of the luminance of pixels p and q, and C(p) is the color (UV values) of the pixel. The result after optimization is shown below:

cleop

Issues

I ran into a few issues in my implementation of the project. The main problems were :

  1. Misclassification of regions: I found that the main reason behind some of the bad results were some regions being misclassified. This was possibly a limitation of the feature set used and also a result of the fact that I am using a very simple KNN classifier. Perhaps with a more discriminating feature space this problem could be overcome
  2. Time of computation: My implementation of the KNN classifier took very long to run. Perhaps speedups like using the approx. Nearest neighbour algorithm would help improve the run time of the algorithm

Examples


m                         m


s             ss

Future Work

We could use data-driven methods to improve the colorization technique, and to automate the process of selecting a similar reference image. This could be done in a manner similar to that in IM2GPS (Hays/Efros) by finding similar images using a large image database such as flickr. Also exploring different feature sets that would improve matching between regions would improve the colorization.