An Image Inpainting Technique Based on the Fast Marching Method

Introduction:

The paper by Alexandru Telea of the Eindhoven University of Technology describes a method for image inpainting that is as effective as the method due to Bertalmio et.al., but doesn’t require the implementation of numerically unstable and complex methods like anisotropic diffusion.

The Fast Marching Method 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.

Algorithm:

The convention that we follow is given below:

1. ∂Ω denotes the boundary of the region Ω to be inpainted.

2. Bε( p) is the ε- ball of the known image around some unknown point p.

For ε small enough, we consider a first order approximation Iq (p ) of the image in point p , given the image I (q ) and gradient ∇I (q ) values of point q.

Iq( p) = I( q) + ∇ I( q)( p − q) .

Next, we inpaint point p as a function of all points q in Bε (p ) by summing the estimates of all points q , weighted by a normalized weighting function w (p, q ):

I(p,qi )= w(p,qi)[ I( q) + ∇ I( q)( p − q)]

I(p) is the sum of I(p,qi) over all qi belonging to the epsilon ball Bε(p) about point p which is to be inpainted. The values of w(p,qi) depends on the image to be inpainted and hence has to be computed for each point to be inpainted.

Pseudocode:

Let ∂Ω denote the boundary of the region to be inpainted. The pseudocode implementing inpainting is as follows:

1. p = pixel of deltaΩ closest to deltaΩi

2. inpaint p using Eqn.2

3. advance deltaΩ into Ω

4. if ( deltaΩ != empty) goto 1 else exit

Results:

Original Image

The mask

Reconstructed Image