Computer Science Department
CS 520: Assignment 4 – Colorization
The purpose of this assignment is to demonstrate and explore some basic techniques in supervised learning and
The Problem: Consider the problem of converting a picture to black and white.
Figure 1: Training Data – A color image and its corresponding greyscale image.
Typically, a color image is represented by a matrix of 3-component vectors, where Image[x][y] = (r, g, b) indicates
that the pixel at position (x, y) has color (r, g, b) where r represents the level of red, g of green, and b blue respectively,
as values between 0 and 255. A classical color to gray conversion formula is given by
Gray(r, g, b) = 0.21r + 0.72g + 0.07b, (1)
where the resulting value Gray(r, g, b) is between 0 and 255, representing the corresponding shade of gray (from
totally black to completely white).
Note that converting from color to grayscale is (with some exceptions) losing information. For most shades of gray,
there will be many (r, g, b) values that correspond to that same shade.
However, by training a model on similar images, we can make contextually-informed guesses at what the shades of
grey ought to correspond to. In an extreme case, if a program recognized a black and white image as containing
a tiger (and had experience with the coloring of tigers), that would give a lot of information about how to color it
Figure 2: Trained on the Color/Grayscale image in Fig.1, recovers some green of the trees, and distinguishing blues
between sea and sky. But there are definitely some obvious mistakes as well.
You have a lot of freedom in your approach to this, but carefully formulate each of the following in outlining your
solution to the problem, expressing your design choices, the math, and the algorithms behind your solution:
Computer Science Department – Rutgers University Fall 2018
• Representing the Process: How can you represent the coloring process in a way that a computer can
handle? What spaces are you mapping between? What maps do you want to consider? Note that mapping
from a single grayscale value gray to a corresponding color (r, g, b) on a pixel by pixel basis, you do not have
enough information in a single gray value to reconstruct the correct color (usually).
• Data: Where are you getting your data from to train/build your model? What kind of pre-processing might
you consider doing?
• Evaluating the Model: Given a model for moving from grayscale images to color images (whatever spaces
you are mapping between), how can you evaluate how good your model is? How can you assess the error of
your model (hopefully in a way that can be learned from)? Note there are at least two things to consider when
thinking about the error in this situation: numerical/quantified error (in terms of deviation between predicted
and actual) and perceptual error (how good do humans find the result of your program).
• Training the Model: Representing the problem is one thing, but can you train your model in a computationally tractable manner? What algorithms did you draw on? How did you determine convergence? How did
you avoid overfitting?
• Assessing the Final Project: How good is your final program, and how can you determine that? How
did you validate it? What is your program good at, and what could use improvement? Do your program’s
mistakes ‘make sense’? What happens if you try to color images unlike anything the program was trained on?
What kind of models and approaches, potential improvements and fixes, might you consider if you had more
time and resources?
Some Possible Approaches
Some possible approaches you might take to the problem include the following (and where used to generate the small
• While mapping from gray 7→ (r, g, b) cannot reliably reconstruct the true color of a pixel, not having enough
information in a single gray value, consider looking at a small 3 × 3 pixel window of gray values, and mapping
this set of nine gray values to a single (r, g, b) color vector, which could for instance be the color of the middle
pixel in this window. In this case, the surrounding eight gray values give additional context and information
to build a color for the central pixel. With such a map, a grayscale image could be colored by simply taking
every 3 × 3 pixel patch, and determining what color the central pixel should be.
• To further simplify things, the problem can be shifted from a regression problem to a discrete classification
problem in the following way: consider building an initial palette of K representative colors, and instead of
trying to reconstruct the true color of a pixel, determine which of these K colors should best be applied to a
given pixel. How can you determine which K colors are best to use, however? And be careful as well – how
should you assess error and the quality of a model when coloring in this way?
• It may also be useful to reduce the input space as well as the output space – consider for instance the set of
all possible 3 × 3 pixel patches that occur in a given image, much like overlapping jigsaw puzzle pieces. Do
all possible jigsaw puzzle pieces occur in representing a given image, or could the overall space be reduced to
consider only a set of ‘representative’ puzzle pieces?