Image colorization¶

$$ \newcommand{\eg}{{\it e.g.}} \newcommand{\ie}{{\it i.e.}} \newcommand{\argmin}{\operatornamewithlimits{argmin}} \newcommand{\mc}{\mathcal} \newcommand{\mb}{\mathbb} \newcommand{\mf}{\mathbf} \newcommand{\minimize}{{\text{minimize}}} \newcommand{\argmin}{{\text{argmin}}} \newcommand{\diag}{{\text{diag}}} \newcommand{\cond}{{\text{cond}}} \newcommand{\rank}{{\text{rank }}} \newcommand{\range}{{\mathcal{R}}} \newcommand{\null}{{\mathcal{N}}} \newcommand{\tr}{{\text{trace}}} \newcommand{\dom}{{\text{dom}}} \newcommand{\dist}{{\text{dist}}} \newcommand{\E}{\mathbf{E}} \newcommand{\var}{\mathbf{var}} \newcommand{\R}{\mathbf{R}} \newcommand{\B}{\mathbf{B}} \newcommand{\SM}{\mathbf{S}} \newcommand{\ball}{\mathcal{B}} \newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}} $$

Jong-Han Kim (jonghank@khu.ac.kr)

A color image is represented by an $m\times n \times 3$ matrix of RGB intensities, so each pixel $p_{ij}$ can be represented by a three dimensional vector,

$$ p_{ij}=\bmat{r_{ij} \\ g_{ij} \\ b_{ij} }\in\R^3 $$

A natural grayscale intensity $w_{ij}$ can be obtained from the $r_{ij}$, $g_{ij}$, $b_{ij}$ intensities by the following relations, i.e., the grayscale intensity can be interpreted as a linear combination of the R/G/B intensity values.

\begin{align*} w_{ij} &= 0.299r_{ij} + 0.587g_{ij} + 0.114b_{ij} \\ &= \bmat{0.299 & 0.587 & 0.114}p_{ij} \end{align*}

In this problem you will be given an $m\times n \times 3$ image, most of whose color information is lost, and you will work on reconstructing the lost color information.

The following describes how those full color information or grayscale information are represented: Each pixel in a color image consists of a three dimensional vector whose components describes the R/G/B intensities, however in this mostly colorless image, approximately 2% pixels contain those color information,

$$ p_{ij} = \bmat{r_{ij} \\ g_{ij} \\ b_{ij}} $$

while the rest 98% pixels contain three dimensional vectors whose three components are the grayscale intensity.

$$ p_{ij} = \bmat{w_{ij} \\ w_{ij} \\ w_{ij}} $$

So by looking at the three components in each pixel, you can identify whether the corresponding pixel contains the correct color information, or not. If a pixel contains a three dimensional vector with all different components, that means the pixel contains the correct color information. If a pixel contains a three dimensional vector with identical components, that means the pixel's color information is lost.

Your job is to reconstruct the color information for those 98% pixels.

The following loads an $m\times n \times 3$ mostly colorless PNG image.

The image pretty much looks like a grayscale image. However if you zoom in, you will see some of them actually contain the color information.

Identify the pixels with full color information, by comparing R/G/B intensities. In other words, find $m_\text{known}$, the row indices, and $n_\text{known}$, the column indices for the pixels with full color information, so that

$$ p_{ij} = \bmat{r_{ij} \\ g_{ij} \\ b_{ij}}, \qquad \text{if } i\in m_\text{known} \text{ and } j\in n_\text{known} $$

and $p_{ij} = \bmat{w_{ij} & w_{ij} & w_{ij}}^T$ otherwise.

Now find the grayscale intensities for all the pixels, i.e., compute $w_{ij}$ for all $i$ and $j$.

Now paint the image with appropriate colors, by reconstructing the lost color information. So more formally, find

$$ p_{ij} = \bmat{r_{ij} \\ g_{ij} \\ b_{ij}}, \qquad \text{for } i\notin m_\text{known} \text{ or } j\notin n_\text{known} $$

that minimizes the $\ell_2$ total variation of the image defined by

$$ \text{tv}(p) = \sum_i^{m-1} \sum_j ^{n-1} \left\| \bmat{p_{i+1,j}-p_{ij} \\ p_{i,j+1}-p_{ij} } \right\|_2 $$

You may refer to the TV inpainting example page from the cvxpy tutorials at https://www.cvxpy.org/examples/applications/tv_inpainting.html, for handling color images for cvxpy.tv() function.

Also, your choice of objective function is not limited to the above total variation function. You can change it, or you can add regularizers, or you can do whatever you want. The job is just to find a natural color image that (somehow) matches the given information.

Compare your painting with the original color image which can be downloaded from http://jonghank.github.io/ee786/files/khu_entrance.png. The original file is provided just for comparison; you are not allowed to use anything from it.