Inpainting

Image Inpainting with Navier-Stokes, Fast Marching and Shift-Map method

Image inpainting involves filling in part of an image or video using information from the surrounding area. The goal is to produce a revised image in which the inpainted region is seamlessly merged into the image in a way that is not detectable by a typical viewer. The algorithm attempts to imitate basic approaches used by professional restorators. The algorithm also introduces the importance of propagating both the gradient direction (geometry) and gray-values (photometry) of the image in a band surrounding the hole to be filled-in.

Fig. 1, Inpainting illustration

Bertalmio et. al.[1] drew an analogy between the image intensity function for the image inpainting problem and the stream function in a two-dimensional (2D) incompressible fluid. An approximate solution to the inpainting problem is obtained by numerically approximating the steady state solution of the 2D NSE (Navier-Stokes Equations) vorticity transport equation, and simultaneously solving the Poisson equation between the vorticity and stream function, in the region to be inpainted. This elegant approach allows one to produce an approximate solution to the image inpainting problem by using techniques from computational fluid dynamics.

Fig. 2, Navier-Stokes method

Telea [2] described a method for image inpainting that is as effective as the method due to Bertalmio et.al.[1], but doesn’t require the implementation of numerically unstable and complex methods like anisotropic diffusion, called "The Fast Marching Method (FMM)". It is a technique for producing distance maps of the points in a region from the boundary of the region. This method combined with a way to paint the points inside the boundary, according to the increasing distance from the boundary of the region.

The FMM maintains a so-called Narrow Band of pixels, which is exactly our inpainting boundary. For every image pixel, we store its value T, its image gray value I (both represented as floating-point values), and a flag f that may have three values: 1) BAND: the pixel belongs to the narrow band. Its T value undergoes update; 2) KNOWN: the pixel is outside inpainting boundary, in the known image area. Its T and I values are known; 3) INSIDE: the pixel is inside inpainting boundary, in the region to inpaint. Its T and I values are not yet known. First, we set T to zero on and outside the boundary of the region to inpaint and to some large value (in practice 10^6) inside, and initialize f over the whole image as explained above. All BAND points are inserted in a heap NarrowBand sorted in ascending order of their T values. Next, we propagate the T, f, and I values using the code shown in Fig. 3. Step 1 extracts the BAND point with the smallest T. Step 2 marches the boundary inward by adding new points to it. Step 3 performs the inpainting: iterate over the KNOWN points in the neighborhood of the current point (i, j) and compute I(i, j) and the image gradient gradI is estimated by central differences. Step 4 propagates the value T of point (i, j) to its neighbors (k, l) by solving the finite difference discretization problem. Finally, Step 5 inserts (k, l) with its new T in the heap.

Fig. 3, Fast Marching method

Fig. 5, Shift Map Results

References

1. M. Bertalmio, A. L. Bertozzi, G. Sapiro, Navier-Stokes, Fluid Dynamics, and Image and Video Inpainting, IEEE CVPR, 2001.

2. A Telea, An image inpainting technique based on the fast marching method , J. GRAPHICS TOOLS, 2004.

3. Y. Pritch, E. Kav-Venaki, and S. Peleg, Shift-Map Image Editing, , IEEE ICCV'09, Kyoto, Sept. 2009.

4. Boykov, Veksler, Zabih, Fast Approximate Energy Minimization via Graph Cuts, IEEE T-PAMI, 2001.