Inpainting: a users’ guide

Over the past few posts I have introduced the idea of inpainting and the mathematics behind the ability to “intelligently” fill in a region based on the information provided by the rest of the image. The theory was developed by Dr Thomas Maerz, from which he constructed a set of matlab codes that simulated his ideas. Dr Martin Robinson has since developed Thomas’ ideas into a FREE GIMP plugin.

This week I present a guide to using Martin’s plugin.

________________________________________________________________

________________________________________

In its most basic form Martin’s code is extremely easy to use: you select a region; set a few parameters and tell GIMP to run the code. As before, we will use the plugin to remove bee from the following photo. Also, we once again use the GIMP’s extensive suite of selection tools to highlight the region we are interested in.

When you have selected the region you are interested in fire up the inpainting plugin. If it has been installed correctly (see Martin’s documentation for more information) then by default it should be in the “Filters” drop down menu under “Misc”. Once it is opened you should see a box that looks like Figure 1.

First approximation

Figure 1. The general user interface of the inpainting plugin.

In this basic case the text box should automatically be filled in with the correct details. Namely, the image shown at the top should be the area that you selected, the source should be the image you want to inpaint and the mask type should be a selection.

You will then notice that there are four parameters: epsilon, kappa, sigma and rho. These are very important and control various aspects of the inpainting algorithm. Specifically, not only do they influence what colour a chosen pixel will be, but they also influence how details will propagate into the domain. This means if there are straight lines leading into the boundary the parameters will alter how those straight lines are continued. The following box gives more detail on each of the parameters.

epsilon defines the region over which the colour is averaged. If epsilon is large then colours over a larger region are used. If epsilon is small the code only uses local colour detail to paint the new pixel. kappa controls how the level set lines (discussed in a previous post) effect the direction of features that we want to propagate into the region. If we want the picture features to follow the level set line direction we make kappa large, otherwise we make it small. sigma controls how much the input data is smoothed. If sigma is small then small scale features will propagate into the domain, alternatively, if sigma is large then only clear, distinct line features will be taken into the inpainting region. rho controls the averaging of the directional information. This is needed because some of the features may be heavily directional and we may want to propagate these directions into the image. A large rho causes a large amount of information of the boundary to be averaged, leading to more accurate directional information. If there is little directional information in the boundary we make rho small.

In the basic case shown below I set the parameters to epsilon=20, kappa=100, sigma=0.01, rho=20. The way I found these numbers was partly through playing around with the sliders and partly thinking about their definitions. Since the picture is high definition we want the maths to take in detail from a large region, so we make epsilon big. Because there are a number of thin creases in the petals that we want to propagate and carry on the line we set kappa and rho high (to keep the direction) and sigma low (to keep the detail).

As you will see below even this simple approach does a good job. However, by putting in a little extra effort we can make the result so much better.

Advanced inpainting

As you may notice from the image, most of the lines meet up one the bee is removed. However, because the bee covers regions connecting the petals to the central anthers of the plant, some of the central plant detail gets propagated into the inpainted region. To stop details being propagated in to regions we do not want them we use a “stop path”.

We select the path tool from the gimp work box and draw a curve. This curve will represent the points to which the details will propagate. Since the anthers are propagating too far we draw a red line that maps closely to the anther region as seen below. As before, the black and white line represents the region selected to be inpainted.

Once we have the path defined we then go back to the plugin and select “Selection With Stop Path” in the “Mask Type” drop down menu. Once this is selected the “Stop Path” drop down menu should become selectable. In this menu we select the curve that we have drawn and, finally, click apply.

Below we show the base case (left) along with the final image of this advanced version (right), and both of these can be compared with the original (above). Hopefully, you can see that, by just applying a little more work we get a much better result.

________________________________________________________________

________________________________________

Over the last few posts I have introduced the idea of inpainting, met the minds behind it and, hopefully, you’ve had ago yourself. Once again, here are all the links that have mentioned over the last few weeks:

Thomas Maerz’s website

Thomas inpainting code for Matlab

Martin Robinson’s website

Martin’s inpainting plugin for GIMP

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.

Inpainting: automatic mathematical photoshopping

Most of us take bad photos. I know I do. There is always a random guy in the background of my landscape shots, or part of my image is obscured by bars as I try to photograph animals in zoos. Moreover, I’ve plenty of old non-digital photos that have various scuffs and scratches on.

Of course, photoshop gives us the ability to cure all these ills by adding, removing and changing any detail we should wish. However, a well photoshopped image takes time, patients and a lot of skill, somethings that few of us have now-a-days.

Thankfully, due to the work of Dr Thomas Maerz and implementation by Dr Martin Robinson (post doctoral researchers in the Oxford Mathematical Institute), any novice image manipulator can now quickly and simply remove details from their images, through a process known as “inpainting”. The idea behind inpainting is to create a rigorous mathematical approach that will fill in a section of an image, based on the information from the rest of the image. Examples of this process are shown below. No doubt you will think that they are too good to be true. However, I assure you that all the inpainted images are generated automatically through Thomas’ incredible work. Not only is this work impressive theoretically, but Martin has actually created a FREE GIMP plugin that you can use to produce your own incredible inpainted images.

Figure 1. The left image is a vandalised image that has data removed. The right image is the result of applying Thomas’ automatic inpainting theory to the vandalised image [1].

On 2nd February 2014 I sat down with Thomas and Martin to discuss the ideas behind inpainting. This week I introduce them, the problem of inpainting and demonstrate the codes abilities.

________________________________________________________________

________________________________________

Thomas and Martin, could you give me a brief idea of your mathematical backgrounds?

Figure 2. Coffee capsules created by mathematicians, for mathematicians.

Martin: I did computer systems and engineering in Brisbane, where I specialised in generating 3D structures from 2D images. The techniques I worked on where actually going to be applied to the tourist industry. The idea being that you would be able to recreate a 3D representation of a beach, or the inside of church.

I then moved to Monash University in Melbourne and did my Phd in fluid mixing. This led me to work with Nestle on granular and fluid mixing with the aim of understanding what processes happen inside their coffee capsules. I now work on implementing multiscale theories behind coupling probabilistic events with deterministic events.

Thomas: I studied mathematics and achieved my Masters and Phd in Munich under the supervision of Prof. Dr Folkmar Bornemann. Both of my degrees have been focused on the application of numerical analysis to image analysis and particularly inpainting. My Master’s project was coming up with the implementation of the original framework and my Phd was more on the analysis of the model.

So you created the method… and then checked it worked?

Thomas: Exactly [grinning]. Now I’m working more on the “closest point method” [a way of solving differential equations on very general surfaces, see here for details].

Why would we want to use inpainting?

Martin: I think the main two uses would be for removal and repair. Most people would immediately think they would be able to use this technique to get rid of someone in their photos, but I would suggest it would be better suited to removing specific features, such as a grating over an image. The other reason you may want to use it to repair old photographs that may have degraded.

Figure 3. Uncaging a parrot. The left image is the original. The middle image shows the area which is to be inpainted and the right image is the result [1].

Are there many other people working on inpainting?

Thomas: Oh yes, very many. There are people who use methods based on partial differential equations. However, different groups use different differential equations. Other mathematicians using wavelet transforms, Fourier transforms and harmonic analysis. Engineers tend to use very different techniques. They primarily focus on discrete, pixel based methods. On the other hand optimisation people tend to think of an image as a graph.

If there are so many people working on inpainting why should we use your technique rather than any other?

Thomas: We compared our method with some of the other more complex partial differential techniques and we found that our results where comparable in quality, whilst being much faster in terms of processing time.

Martin: The plugin was made to be free and as user friendly as possible in order to get people to start using it.

Why make the plugin free?

Martin: I try to primarily use open source software in my research, which is useful when you are working in a university, which often does not have the money buy big commercial software packages. So it is nice to give something back to the community.

Thomas: It also encourages future development. The plugin is a great gateway to get people interested in my research.

________________________________________________________________

________________________________________

For those of you who are interested the website with the plugin can be found here. Next time I will a brief guide to the mathematics [1,2] that makes the code work. Below are a couple more examples demonstrating the power of inpainting.

Figure 4. Left: 70% of the image of a tram has been removed, so only the information on a square lattice is left. Right: inpainting recovers the pictures beautifully.

You may not be impressed by Figure 4 as you can still make out the train in the top left image. However, take a look at Figure 5. Here, 56% of the image has been randomly destroyed, yet once again inpainting works like magic.

Figure 5. Left: Image with 56% of the image randomly is destroyed. Right: The reconstructed image.

[1] Images taken from Fast Image Inpainting Based on Coherence Transport

[2] Thomas' second paper on this work can be found  here: Image Inpainting Based on Coherence Transport with Adapted Distance Functions 

What makes a good mathematical biologist?

Last time I presented the life and times of Prof. Jim Murray FRS. Jim is actually my academic grandfather as he supervised Philip Maini (the current director of the Wolfson Centre for Mathematical Biology) and Philip supervised me.

Figure 1. Three generations of mathematical biologists. From left to right: Me, Philip Maini and Jim Murray. When I showed the picture to my wife she said that she loved the gradient in beard colour :).

The extended mathematical family tree can be seen in one of my previous posts.

This week we discuss Jim's work.

________________________________________________________________

________________________________________

What field of maths did you start in?

I was working on various types of fluid mechanics, such as magnetohydrodynamics and a theory of fluidisation but, except for the latter, nothing really caught my imagination. The last paper I wrote on fluids was on Burgers equation [an equation related to turbulence modelling]. I once met Burgers. I was giving a talk and he was sitting there seemingly asleep in the front row all during the lecture. At the end everyone applauded, he woke up and proceeded to ask a highly relevant question.

How did you get into mathematical biology?

A professor of botany approached the department and asked if they could recommend anyone who could help him quantify how oxygen got into pea nodules. When the guy phoned me up he thought I was a graduate student and said he could offer me $5 an hour! So, that was my introduction into mathematical biology: oxygen diffusion in pea nodules. After writing a few papers on it I found it quite interesting even though there was nothing too difficult about the mathematics as it was just singular perturbation analysis of the diffusion equation

I don’t know how, but someone from anatomy heard about me and got in touch. His problem was on pilot ejection seat injuries.

Please do expand on this problem. I’ve heard it involved dropping corpses down lift shafts.

I got interested and the model consisted of a one-dimensional compressible material on one end of which we applied a force to simulate the chair lifting rapidly. This lead to a wave travelling up the rod, but the wave equation was nonlinear and so a shock developed [shocks form when the solution tries to become multivalued. It’s like a wave breaking on the shore. See here for a simulation of the shock forming]. We then hypothesised that the shock might actually split the vertebrae.

We took this to the anatomist who wanted to test the theory. I asked him how he’d do this and he said that they strap a cadaver to a lift and dropped them. On stopping the lift suddenly they mimic the effect of an ejector seat and we can see what happens to the spine. He suggested that I come along to see how they do it, but I passed on that offer.

What has been your favourite experiment and what has been your favourite piece of mathematics?

Oh I don’t know. There have been so many and so diverse. I think animal coat patterns have been the most enjoyable. However, I’ve never thought that the model had anything to do with biology. It was phenomenological. I feel that the mechanochemical theory of morphogenesis (developed with George Oster from Berkeley) is much more relevant to biology since it made real biological predictions which were confirmed experimentally. Reaction-diffusion theory was taken over by mathematicians for the past 50 years: a morphogen was only found last year [click here to see my posts on Alan Turing’s chemical theory of morphogenesis].

In fact the person who should really be given credit for much of reaction-diffusion patterning is Daniel Thomas (university of Compiegne). He did experiments that produced reaction-diffusion spatial patterns, long before others in the early 1970s. It was his experimental reactions that I used for my animal coat patterning work. Yet no one has heard of him in the field, which is a real shame.

You are best known for being able to create models that are incredibly simple, yet are able to be strong enough to capture the relevant biology. How do you do it?

Well I would always start by talking to the biologist. Unless I get an intuitive argument to test from them I wouldn’t know what to do with the idea. I always want the mathematics to be as simple as possible. Then you can start adding in extra bits, if you need it to get closer to the biology.

In Oxford most of these interdisciplinary conversations have started as discussions over high table dinner in various Oxford colleges. So my advice on becoming a good mathematical biologist is to have haute cuisine dinners with as many interesting people as possible.

________________________________________________________________

________________________________________

Whilst Jim was in Oxford. Philip Maini got the chance to do a fuller interview that was recorded and is hosted by the Mathematical Institute of University of Oxford. It is called "Jim Murray - Reflections on a Life in Academia" and can be watched below.

Prof. James Murray FRS: The founder of mathematical biology in Oxford

Although in the last post I said I would discuss rotational symmetric Venn diagrams we're going to take a short break in order to bring you an interview with one of the greats of mathematical biology.

On Tuesday 4th of March Prof. Jim Murray FRS came to Oxford to deliver the first annual Hooke lecture. When it comes to mathematical biology Jim, quite literally, wrote the book. Two books in fact! Not only has he had an extremely varied, interesting and hilarious career (dealing with everything from marriage to cannibalism and even having time to win the University of St Andrews first blue in table tennis and was captain of the university’s billiard team) but he founded Oxford’s Centre for Mathematical Biology.

Although he had a packed schedule I managed to catch up with him for a quick interview about his work, hoping that I could try and glean what makes a great mathematical biologist. This week we get a little bit of his background and biography

________________________________________________________________

________________________________________

How are you?

Doing fine, just not as physically active as I used to be.

Still active on the lecture circuit though?

Oh yes, I still do a bit of teaching in Princeton and give colloquia around. My mind is still very much active.

Could you give me a brief overview of your early academic career?

Figure 1. Jim Murray.

I started in Moffat, a very rural and isolated part of Scotland, where there was only one non private school and you only attended until you were 14. After that everyone left to get a job. However, there were two of us that went off to Dumfries Academy. At the end of my three years there were only two of us who went on to university. The number going on to higher education back then was minute.

I was actually the first person in St Andrews University to get a PhD in Applied Mathematics. My supervisor, Ron Mitchell, who was also a professional footballer (known as “Elbows” Mitchell), wanted me to do numerical analysis on shear flow past shapes and in pipes. It was all associated with how aeroplanes measure their speed. Thankfully, I wriggled out of that by obtaining analytical solutions.

Based on this I did a summer internship in an aircraft industry, Fairey Aviation Company, near London. I worked in the theoretical division, but they had me doing the most boring jobs you could imagine. No wonder the company went bust! So, I decided against going into industry.

So did you go through this knowing that you wanted to be an academic?

Oh no. It was simply that from having polio I knew I was never going to be a plumber. I remember our maths teacher coming around the classroom giving his opinion on whether we would be able to do maths at university and he said,

“No, no, no Murray. You’d never make it”.

Well, I didn’t know any better back then and, so, I started doing chemistry at St Andrews. Thankfully, in the Scottish system you didn’t have to specialise at the beginning, which was good, as I found the field to be totally unexciting. By the end of that year I switched to physics. However, I also found that to be boring. Alongside this I did keep up the mathematics and found I kept getting prizes and medals in it. This, of course, made me think that perhaps the teacher hadn’t been right.

What did you do after your PhD?

I actually finished my thesis and had it all approved after two years, but I couldn’t graduate until after the third year. Thankfully, the university let me take a job for that third year at King’s College in Newcastle (then part of Durham University). I then got a post-doc and later a lectureship at Harvard University.

I came back to England, to University College London and two years later was elected Mathematics Fellow in Hertford College, Oxford. I actually got the position by mistake. The college fellow in charge of the appointment was a physicist who said to me that any person who gets a strong recommendation from Goldstein, must be good. It turns out the Goldstein he was thinking of was not the same Goldstein that had written my reference!

Who have you really admired?
Oh there are so many. For example, many of my students and postdocs are now major international figures in the field of mathematical biology. Several of the people I’ve collaborated with such as Jeffries Wyman (a biologist) just missed getting a Nobel prize (his collaborators did, however). I’ve always thought of these people as friends rather than just collaborators. I’m particularly fond of my extended collaboration with George Oster (Berkeley) a close friend with whom I worked for several years with on the mechanochemical theory of biological development. There are, of course, many many others.

________________________________________________________________

________________________________________

Next time we discuss Jim's mathematics. Trust me, this is something that you don't want to miss, as we will be discussing the relationship between mathematics and dropping corpses down lift shafts. Also Jim shares his secret on how to be a great mathematical biologist.

In the mean time you can watch Jim's Hooke lecture "Why there are no 3-headed monsters, resolving some problems with brain tumours, divorce prediction and how to save marriages" below. This was recorded and is hosted by the Mathematical Institute of University of Oxford.

Rotationally symmetric Venn diagrams

No doubt you will have seen a Venn diagram. They are a wonderful way of presenting logical information. For example, they allow us to illustrate the fact that centaurs lie in the union of objects with male torsos and horse legs (Figure 1).

Figure 1. Not all male torsos are connected to horse legs and vice versa. However, we see that centaurs do lie in the intersection.

Recently there has been an upsurge in using Venn diagrams as way of illustrating jokes, or song titles. My personal favourite explains where the platypus fits in the animal kingdom (Figure 2).

Figure 2. Although not scientifically sound it does show that the keyboard guitar and platypus can be defined as the intersection of two other sets.

Of course you are not restricted to two sets of objects. A Venn diagram can be made of any number of sets. For example Figure 3 illustrates the some of the lyrics from the song “The Joker” by the Steve Miller Band.

Figure 3. A seven set intersection diagram illustrating the characteristics of certain famous people.

Technically, Figure 3 illustrates an Euler diagram and not a Venn diagram. A Venn diagram contains every single possible intersection between all combinations of the sets, whereas an Euler diagram only shows the intersections you are interested in. For example, in Figure 3 there is no section where only grinners and jokers intersect (this could possible contain Heath Ledger).

When dealing with two or three sets the obvious Euler diagram is also a Venn diagram (Figure 4). Interestingly, they both also have rotational symmetry. This will be considered in more detail in the next article.

Figure 4. Two and three set Venn diagrams.

However, when we get to four circles, things are not so easy anymore and the basic Euler diagram (Figure 5, left) is no longer a Venn diagram. However, by removing the restriction that the groups have to be circles we can once again produce a four set Venn diagram (Figure 5, right). Sadly though, we have lost the pleasing rotational symmetry.

Figure 5. If only circular shapes are used we cannot create a Venn diagram, only an Euler diagram (left). However, by generalizing the set's shape, we can produce a Venn diagram once more (right).

Next time I will present another part of the discussion with Barry Cipra and we will see under what conditions Venn diagrams can have rotational symmetry.

Sol LeWitt Solution

Last time I introduced the Sol LeWitt’s problem, devised by the eminent mathematical reporter Barry Cipra. The challenge was to take the tiles, as presented in the left image of Figure 1 and rearrange them such that all the lines form continuous rows, columns and diagonals across the grid. As I revealed there are many solutions, one such solution is presented in the right image of Figure 1.

Figure 1. Left: the original Sol LeWitt tiles. Right: an arrangement in which all lines cross the entire grid.

I also mentioned that there were some special relationships between certain solutions. For example rotating a solution through 90 degrees, reflecting it, or performing a combination of these two operations generates another, related solution. Furthermore, we can take the topmost row (or the leftmost column) and moving it all the way to the bottom (or to the right). Explicitly, a set of solutions can be drawn on the surface of a torus.

This leaves us with a new question. Are there any solutions which cannot be generated in such a way? Namely, starting from one solution are their other “distinct” solutions, which cannot be created through rotations, reflections or row/column operations. Each distinct solution will then generate a different solution set, which will lead to different to tori.

The famous mathematician John Conway demonstrated that there are actually three distinct solutions, from which all others can be derived. One has been given above. Can you find the other two possible distinct solutions?

As I was talking to Barry about this puzzle he told me a nice anecdote, where he had used this puzzle in a workshop involving maths teachers and maths researchers that had been paired together. He said that the teachers were constantly moving the pieces around, effectively using trial and error, whilst their researcher partner would sit back and think about the pieces. Eventually, one researcher claimed that the puzzle was impossible, not a moment later his partner produced a working solution! Let this be a lesson to any mathematician. Theory is all well and good, but practical intuition is invaluable.