NYU CSCI-UA 9473 Introduction to ML

Unsupervised Learning (Part III)

Exercise 1. Dictionnary learning and image inpainting.

We consider the popular Lena image below which was corrupted by the overlaying of some text

In [1]:
from PIL import Image

img = Image.open('lena.png').convert('LA')
img.save('greyscale.png')
In [2]:
import cv2
import numpy as np
import matplotlib.pyplot as plt
image = cv2.imread('greyscale.png')  
texted_image =cv2.putText(img=np.copy(image), text="hello", org=(200,200),fontFace=3, fontScale=3, color=(0,0,255), thickness=5)
plt.imshow(texted_image)
plt.show()
In [5]:
im = Image.fromarray(texted_image)
img = im.convert('LA')
plt.imshow(img)
plt.show()

Using the grayscale image above (or if you want to your implementation to be faster, on a downsampled version of this image), decompose the image into a series of overlapping patches (e.g. of size 8x8), store those patches as a list of vectors. Center the list and scale it (divide by the std). Once we have a first dictionnary, we can try to compute the recovered image by first expressing each of the patches from the original image as

\begin{align*} \underset{\mathbf{s}}{\operatorname{argmin}} \left\|\mathbf{y} - \mathbf{D}\mathbf{s}\right\| + \lambda \|\mathbf{s}\|_1 \end{align*}

This minimization can be solved for example through Matching Pursuit

In [ ]:
# implement the minimization step here

Once the decomposition of the image in the dictionnary has been found, we can the update this dictionnary as \begin{align*} \underset{\mathbf{D}}{\operatorname{argmin}} \left\|\mathbf{Y} - \mathbf{D}\mathbf{S}\right\| \end{align*} which can be solved in closed form through the steps \begin{align*} \mathbf{D} = \mathbf{Y}\mathbf{S}^T\left(\mathbf{S}\mathbf{S}^T\right)^{-1} \end{align*} followed by the normalization of the atoms (colums of the dictionnary).

In [ ]:
# add the dictionnary learning step below