Image in-painting¶

$$ \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@inha.ac.kr)

You are given an $m \times n$ corrupted image

$$X\in \R^{m\times n}$$

some of whose pixel values are missing, and your job is to in-paint the image by guessing the missing pixel values.

The missing pixels can be represented by an $m\times n$ binary matrix

$$B\in\B^{m\times n}$$

where $B_{ij}=1$ implies that $X_{ij}$ is known, and $B_{ij}=0$ means $X_{ij}$ is unknown. Note that this matrix $B$ is given in some lucky cases, but it doesn't always happen in which cases you have to identify which pixels are reliable and which are not. In this problem, we assume that $B$ is given, or at least can be identified reliably.

Then your job is to reconstruct, by using $X$ and $B$, the corrupted image by filling appropriate pixel values into the unknown pixels where $B_{ij}=0$, so that your reconstructed image looks natural.

We first download a black and white image from the course webpage. The image was corrupted by white characters written on top. So we will try to in-paint the image by guessing the missing pixel values at those white pixels.

So the missing pixels can be found by searching for the white pixels.

Let $p$ be the number of known pixels and $q$ be the number of unknown pixels, so $mn = p+q$.

We first let $x\in\R^{mn}$ be the vectorized version of the image, $X\in\R^{m\times n}$,

\begin{align*} x &=\text{vec}\left(X\right) \\ X &=\text{vec}^{-1}\left(x\right) \end{align*}

so the vectorization is nothing but stacking all the columns into a single long column, and the inversion is just going backwards. Note that the vectorization is linear and explicitly represented by

$$ {\displaystyle {\text{vec}}({X} )=\sum _{i=1}^{n} e_i\otimes X e_i} $$

where $e_i$ is the $i$-th unit vector in $\R^n$, and $\otimes$ represents the Kronecker product.

We then separate the image into two parts, the known part and the unknown part, since we know which are which from ${B}$. Let $x_\text{k}$ is the $p$-vector containing the known pixel values, and $x_\text{u}$ be the $q$-vector of unknown pixel values that we will have to find.

\begin{align*} x_\text{k}&\in\R^{p} \\ x_\text{u}&\in\R^{q} \end{align*}

We will define some operators to build the image from these two vectors.

\begin{align*} Z_\text{k}&\in\R^{mn \times p} \\ Z_\text{u}&\in\R^{mn \times q} \end{align*}

so that

$$\text{vec}(X) = Z_\text{k}x_\text{k} + Z_\text{u}x_\text{u}$$

For example, $Z_\text{k}$ is a lifting operator that maps a $p$-vector $x_\text{k}$ to a $mn$-vector by zero-padding appropriately, and a similar but complementary operation is done by $Z_\text{u}$. Note that $Z_\text{k}$ and $Z_\text{u}$ are made of columns exclusively taken from the $mn\times mn$ identity matrix.

For example, the known part of the corrupted image (with zeros on the unknown pixels) can be formed from

$$ \text{vec}^{-1}(Z_\text{k}x_\text{k}) $$

Note that the image $X$ is a simple linear function of the unknown variable $x_\text{u}$, and the inpainting problem boils down to finding some good $x_\text{u}$ satisfying the linear relation. Once you have it, the reconstructed image can be obtained from

$$ X_\text{recon} = \text{vec}^{-1} ( Z_\text{k}x_\text{k} + Z_\text{u}x_\text{u} ) $$

We define a function that quantifies "roughness" of rectangular images.

$$ \text{TV}(X) = \sum_{i=1}^{m-1}\sum_{j=1}^{n-1} \left( |X_{ij}-X_{i+1,j}|^p + |X_{ij}-X_{i,j+1}|^p \right) $$

Note that this can be written as follows

$$ \text{TV}(X) = \left\| \begin{bmatrix}{D_x \\ D_y}\end{bmatrix} \text{vec}(X) \right\|_p^p $$

with $D_x\in\mathbb{R}^{m(n-1) \times mn}$

$$ D_x = \bmat{ -1 & & & & 1 & & & & & & & & & & & &\\ & -1 & & & & 1 & & & &\\ & & \ddots & & & & \ddots & & &\\ &} $$

returning the $m(n-1) \times mn$ column-wise differences and $D_y\in\mathbb{R}^{(m-1)n\times mn}$

$$ D_x = \bmat{ -1 & 1 & & & & & & & & & & & & & &\\ & \ddots & \ddots & & & & &\\ & & -1& 1 & & & & & & & \\ & & & & -1& 1& & & & & & &\\ & & & & & \ddots & \ddots & \\ & & & & & & & & & &} $$

returning the $(m-1)n\times mn$ row-wise differences.

Now the inpainting problem is finding $x_\text{u}$ that minimizes $\text{TV}(X_\text{recon})$, in other words,

$$ \underset{x_\text{u}}{\text{minimize}}\quad \left\| \begin{bmatrix}{D_x \\ D_y}\end{bmatrix} \Big( Z_\text{k}x_\text{k} + Z_\text{u}x_\text{u} \Big) \right\|_p $$

First, the 2-norm reconstruction via ordinary least squares solution.

The 1-norm reconstruction can be obtained by numerically solving the problem via cvxpy with the SCS solver.

Now compare your reconstructed images with the clean original image.

Can you tell the difference?