Inpainting: how does it work?

Last time I introduced the idea of inpainting, which is an automatic way of “intelligently” filling in a region of an image. Dr Thomas Maerz has worked on a technique which is not only computationally quick, but can produce astounding results. Incredibly, Thomas is allowing his ideas to be made freely available by Dr Martin Robinson who has implemented them in a simple to use GIMP plugin, which can be downloaded from here.

This week we take a look at the theory behind the code.

If you are interested in discovering more about the mathematics of inpainting then Thomas' papers can be found here and here, whilst an original version of Thomas' matlab code can be found on github.

________________________________________________________________

________________________________________

1) Select the image.

You begin with an image, in which there is a region you want to remove, or repair. As an example, let’s take the image below and try to remove the bee from the flower.

2) Select the region.

Select the region using the many tools available in gimp such as the rectangle box, colour selection, or, as I used here, the simple free hand tool. You do not have to delete the area, but since the interior is ignored I will delete it to clearly show the region we are working with.

3) Create level sets.

For all of the pixels in the selected area the plugin calculates the nearest distance to the boundary. In the image below the lines represent contours that are the same distance away from the boundary. For example, the black line represents the white pixels that are 10 pixels away from the nearest boundary; the red line represents the white pixels that are 20 pixels away from the nearest boundary, etc. The colour of the lines are for visualisation purposes only and serve no function in the mathematics.

These contours then form what are known as level sets. Essentially this means that a certain function has a constant value on them. In our case the function is the distance to the boundary.

4) Process the curves.

The curves are processed sequentially, working our way in from the boundary. The boundary is the last region of colour before we enter the cleared region. This boundary gives us all the initial data we need and it is propagated into the region.

Since this curve is coloured we step to the next contour, for example the black contour in the above picture. We choose a pixel on this contour and consider all the previously coloured pixels. This new pixel is filled in with a colour value that is a weighted average of the previously coloured pixels. Namely, coloured pixels that are close to the white pixel we are considering are given more weight when it comes to choosing the appropriate colour for the white pixel. Once the colour is chosen we move to the next white pixel on our current contour. Once all the pixels on the contour are coloured we move into the next contour.

This provides gimp with an algorithm allowing it to automatically fill in the white region, as shown above.

5) Enjoy the result.

The bee (in the original image on the left) has been completely removed in the processed image on the right.

________________________________________________________________

________________________________________

Although the final image on the right was produced in approximately 30 seconds it can still be improved upon as there are clearly regions where the creases in the petals do not line up. Next time I will present a user guide to Martin’s implementation of Thomas’ work and show that this can be improved upon.