ChapterZero

Lately, I’ve been thinking a lot about inpainting. Well, ‘a lot’ is a relative term, so maybe not.

I first ran into the concept of inpainting while looking frantically for papers on directional representations to write up my NSF fellowship application. Classically, inpainting is a technique for using information from the surrounding region to fill in missing regions of a painting— in some way, painters would transfer/propagate/diffuse ‘information’ into the corrupted region. Mathematically, inpainting refers to techniques that do the same thing, but automatically, without human intervention. The most common kind of inpainting is done using PDEs, as I tried to suggest by my choice of words.

Here’s a somewhat mathematical formulation of the inpainting problem that lends itself to a PDE approach. Let indicate the -th image generated by an iteration through the inpainting algorithm, with being the original image. Then define

where , the corrupted region, controls the rate of improvement, and is the -th update term. The hope is that as , , some reasonable image.

Of course, the most important term in this equation is , because it incorporates information from outside the region, and determines what can be reached. Here’s where the PDE formulations come in: you can define according to a PDE with boundary conditions that correspond to the values in the surrounding regions. That’s where the actual math comes in, and I start getting fuzzy.

Inpainting clearly has many applications besides image restoration: it can be used to coherently remove portions of an image in a hopefully more intelligent manner than Photoshop’s clone tool, to resize images smoothly, to compensate for the artifacts of JPEG encodings, etc… But one significant drawback of the naieve PDE-based inpainting algorithms is that they can’t be used on areas with significant texture or large areas, because of their diffusive, smoothing nature. There are hybrid algorithms designed to compensate for this shortcoming: ones that adaptively switch between variational and purely (stochastic?) texture-based inpainting, and ones that somehow merge the two. I don’t know anything about them, other than that they exist.

Today a professor visited UH, who had been one of Papadakis’ students, and mentioned an inpainting method he and someone else devised, based on the diffusion of framelet coefficients. I didn’t understand too much of what he talked about, but I got the impression that his is the only inpainting method with a proven convergence. Viz., other inpainting algorithms have great empirical performance, but nothing is known about their convergence. Something like that.

I’ve actually been giving a little thought to the design of an inpainting algorithm myself, based on wavelet coefficients. In my concocted scheme, you would decompose the image into several subbands, and mark the coefficients which correspond to areas overlapping with the corrupted region. Then you would perform a standard inpainting method on the subbands, and recombine them. This seems like such a simple method that someone must have thought of it before me.