Image in-painting

  • guess pixel values in obscured/corrupted parts of image
  • total variation in-painting: choose pixel values $x_{i,j} \in \mathbf{R}^3$ to minimize $$ \mbox{TV}(x) = \sum_{i,j} \left\| \left[ \begin{array}{c} x_{i+1,j}-x_{i,j}\\ x_{i,j+1}-x_{i,j} \end{array}\right]\right\|_2 $$
  • a convex problem

Example

  • $512 \times 512$ color image
  • denote corrupted pixels with $K \in \{0,1\}^{512 \times 512}$

    • $K_{ij} = 1$ if pixel value is known
    • $K_{ij} = 0$ if unknown
  • $X_\mathrm{corr} \in \mathbf{R}^{512 \times 512 \times 3}$ is corrupted image

  • 60 seconds to solve with CVXPY and SCS on a laptop

In [1]:
import matplotlib.pyplot as plt
import matplotlib.cbook as cbook
image_file = cbook.get_sample_data('lena.png')

X_orig = plt.imread(image_file)
plt.imshow(X_orig)


Out[1]:
<matplotlib.image.AxesImage at 0x103c9e110>

In [2]:
from PIL import Image, ImageDraw, ImageFont
import itertools, textwrap
from itertools import cycle, islice

def drawText(image, fontsize, length):
    text = 'Lorem ipsum dolor sit amet, consectetuer adipiscing elit, \
sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna \
aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud \
exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea \
commodo consequat. Duis autem vel eum iriure dolor in hendrerit in \
vulputate velit esse molestie consequat, vel illum dolore eu feugiat \
nulla facilisis at vero eros et accumsan et iusto odio dignissim qui \
blandit praesent luptatum zzril delenit augue duis dolore te feugait \
nulla facilisi. Nam liber tempor cum soluta nobis eleifend option \
congue nihil imperdiet doming id quod mazim placerat facer possim'
    
    imshape = (image.shape[0], image.shape[1])
    dmg = Image.new("L",imshape)
    draw = ImageDraw.Draw(dmg)

    #fontsize = 80
    font = ImageFont.truetype("/Library/Fonts/Georgia.ttf", fontsize)
    text = "".join(islice(cycle(text),length))
    lines = textwrap.wrap(text, width = 40)
    w, h = dmg.size
    y_text = 0
    for line in lines:
        width, height = font.getsize(line)
        draw.text((0, y_text), line, font = font, fill = 255)
        y_text += height
    
    return (np.array(dmg) == 0).astype(int)

In [3]:
K = drawText(X_orig,40,600)
rows, cols, colors = X_orig.shape

X_corr = np.ones((rows,cols,colors))
X_corr[K==1,:] = X_orig[K==1,:]
plt.imshow(X_corr)


Out[3]:
<matplotlib.image.AxesImage at 0x104ca4150>

In [4]:
%%time
from cvxpy import *
variables = []
constr = []
for i in range(colors):
    X = Variable(rows, cols)
    variables += [X]
    constr += [multiply(K, X - X_corr[:, :, i]) == 0]

prob = Problem(Minimize(tv(*variables)), constr)
prob.solve(verbose=True, solver=SCS)


----------------------------------------------------------------------------
	scs v1.0 - Splitting Conic Solver
	(c) Brendan O'Donoghue, Stanford University, 2012
----------------------------------------------------------------------------
Method: sparse-direct, nnz in A = 3998488
EPS = 1.00e-03, ALPHA = 1.80, MAX_ITERS = 2500, NORMALIZE = 1, SCALE = 5.00
Variables n = 1047553, constraints m = 2614279
Cones:	primal zero / dual free vars: 786432
	linear vars: 0
	soc vars: 1827847, soc blks: 261121
	sd vars: 0, sd blks: 0
	exp vars: 0, dual exp vars: 0
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj |  kappa  | time (s)
============================================================================
     0| 1.04e+00  2.63e+00  1.00e+00 -7.08e+04  3.00e+04  4.52e-08  8.94e-01 
   100| 8.78e-05  7.99e-04  2.21e-05  1.22e+04  1.22e+04  0.00e+00  2.49e+01 
----------------------------------------------------------------------------
Status: Solved
Timing: Solve time: 2.50e+01s, setup time: 1.13e+01s
	Lin-sys: nnz in L factor: 35153634, avg solve time: 1.78e-01s
	Cones: avg projection time: 4.85e-03s
----------------------------------------------------------------------------
Error metrics:
|Ax + s - b|_2 / (1 + |b|_2) = 8.7766e-05
|A'y + c|_2 / (1 + |c|_2) = 7.9909e-04
|c'x + b'y| / (1 + |c'x| + |b'y|) = 2.2127e-05
dist(s, K) = 0, dist(y, K*) = 0, s'y = 0
----------------------------------------------------------------------------
c'x = 12215.7252, -b'y = 12216.2658
============================================================================
CPU times: user 46.3 s, sys: 2.39 s, total: 48.7 s
Wall time: 49.3 s

In [7]:
# the recovered image
X_rec = np.zeros((rows,cols,3))
for i,x in enumerate(variables):
    X_rec[:,:,i] = x.value

In [8]:
def showImgs(im1,im2,labels,filename=None):
    fig, ax = plt.subplots(1, 2, sharex=True, sharey=True, figsize=(10, 5))
    matplotlib.rcParams.update({'font.size': 14})
    fig.tight_layout()
    ax[0].imshow(im1)
    ax[1].imshow(im2)

    ax[0].axis('off')
    ax[1].axis('off')

    ax[0].set_title(labels[0])
    ax[1].set_title(labels[1])

    if filename:
        fig.savefig(filename, bbox_inches='tight')

In [9]:
showImgs(X_orig,X_corr,['Original','Corrupted'],filename='inpaint_text1.pdf')



In [10]:
showImgs(X_orig,X_rec,['Original','Recovered'],filename='inpaint_text2.pdf')



In [11]:
showImgs(X_corr,X_rec,['Corrupted','Recovered'],filename='inpaint_text_cr.pdf')


Random pixels


In [10]:
rows, cols, colors = X_orig.shape
K = (np.random.rand(rows,cols) < .2).astype(int)

X_corr = np.ones((rows,cols,colors))
X_corr[K==1,:] = X_orig[K==1,:]
plt.imshow(X_corr)


Out[10]:
<matplotlib.image.AxesImage at 0x10236ea10>

In [11]:
%%time
from cvxpy import *
variables = []
constr = []
for i in range(colors):
    X = Variable(rows, cols)
    variables += [X]
    constr += [multiply(K, X - X_corr[:, :, i]) == 0]

prob = Problem(Minimize(tv(*variables)), constr)
prob.solve(verbose=True, solver=SCS)


----------------------------------------------------------------------------
	scs v1.0 - Splitting Conic Solver
	(c) Brendan O'Donoghue, Stanford University, 2012
----------------------------------------------------------------------------
Method: sparse-direct, nnz in A = 3551632
EPS = 1.00e-03, ALPHA = 1.80, MAX_ITERS = 2500, NORMALIZE = 1, SCALE = 5.00
Variables n = 1047553, constraints m = 2614279
Cones:	primal zero / dual free vars: 786432
	linear vars: 0
	soc vars: 1827847, soc blks: 261121
	sd vars: 0, sd blks: 0
	exp vars: 0, dual exp vars: 0
----------------------------------------------------------------------------
 Iter | pri res | dua res | rel gap | pri obj | dua obj |  kappa  | time (s)
============================================================================
     0| 1.11e+00  2.88e+00  1.00e+00 -3.42e+04  3.47e+04  2.54e-08  7.84e-01 
   100| 6.21e-05  6.63e-04  3.08e-05  8.60e+03  8.60e+03  6.36e-09  3.00e+01 
----------------------------------------------------------------------------
Status: Solved
Timing: Solve time: 3.01e+01s, setup time: 1.18e+01s
	Lin-sys: nnz in L factor: 35172450, avg solve time: 2.18e-01s
	Cones: avg projection time: 6.17e-03s
----------------------------------------------------------------------------
Error metrics:
|Ax + s - b|_2 / (1 + |b|_2) = 6.2088e-05
|A'y + c|_2 / (1 + |c|_2) = 6.6253e-04
|c'x + b'y| / (1 + |c'x| + |b'y|) = 3.0850e-05
dist(s, K) = 0, dist(y, K*) = 0, s'y = 0
----------------------------------------------------------------------------
c'x = 8599.3132, -b'y = 8599.8438
============================================================================
CPU times: user 50.6 s, sys: 2.54 s, total: 53.2 s
Wall time: 54.7 s

In [12]:
# the recovered image
X_rec = np.zeros((rows,cols,3))
for i,var in enumerate(variables):
    X_rec[:,:,i] = var.value

In [13]:
showImgs(X_orig,X_corr,['Original','Corrupted'],filename='inpaint80_1.pdf')



In [14]:
showImgs(X_orig,X_rec,['Original','Recovered'],filename='inpaint80_2.pdf')



In [ ]: