Hi,

can somebody, please, point me to some information on how a selection is represented (internally) within Gimp and how one can access this. Is it represented by a matrix of bits? If the selection has many holes it's not sufficient to have a lower and upper bound for each pixel row. I need the selection exactly for my attempt at a new healing tool.

Many thanks for a pointer,

Helmut Jarausch.

On 30 Mar, Kevin Cozens wrote:

It is good to have another person around who is interested in working on a healing tool for GIMP.

Before you start, are you aware that a healing tool was added to the current development version of GIMP? It was created by Kevin Sookocheff as part of the 2006 Google Summer of Code program.

The healing tool has a couple of bugs filed against it. You may find your time would be better spent fixing and polishing the existing healing tool instead of starting a new one. On the other hand, if you have an idea for a different or better approach to a healing tool that what is in the current development release, I'm sure the GIMP developers would be interested to hear about your ideas for a new version of a healing tool.

We had some discussions here 5 weeks, ago. I had a look at the current implementation (in the development version). There I found the reference to a paper by T. Georgiev (from Adobe). The current implementation fails in some fundamental aspects. (Only) to explain the problems I'll make the simplifying assumption that the region to be healed ("destination area") is the interior of a circle, which I'll call the boundary below. Georgiev's algorithm proceeds in 2 steps:

step 1 is identical to the clone tool, i.e. some source area of identical shape to the destination area is copied into the interior of the destination area (interior of the circle)

setp 2 Now, at each pixel at the boundary we have 2 values: the previous value of the destination area and the new value of the source area which has not yet been copied. Georgiev tries to fit the area in the interior of the circle (which has just been copied from the source area) to the (old) outside of the circle. To do that he computes the quotients of the old values at the boundary divided by the new values there (for each color separately). Then he suggests to "pull" these factors smoothly into the interior of the circle - see below. Once he has got all these factors, he multiplies all values in the interior by the corresponding factors. Thus, we get a perfect fit on the boundary and hopefully a pleasing one in the interior. Note that it is absolutely essential that the (old) boundary doesn't contain a single "defective" pixel since this defective value would have been "pulled" into the interior of the circle.

To "pull" the factors at the boundary smoothly into the interior he suggests to solve a so-called Poisson equation (= Laplace equation). Unfortunately the solution of this equation is very expensive unless one uses the right (a bit complicated) algorithm called multi-grid. The current implementation use a very simple iterative algorithm (called Gauss-Seidel relaxation) which is not suitable for more than say a few hundreds of pixels. Even then it would take a significant time to solve the equation. The current implementation just puts a fixed upper bound on the number of iterations.
So, it simply doesn't solve this equation in all but trivial cases. For thousand and more pixels (which is still a tiny part of a 10 Megapixel image) this algorithm could take hours or more to complete.

My current plan encompasses a few steps outlined below. Perhaps I'll add a quick mode which would be similar to the clone tool lateron.

- In step 1 the user creates a selection which selects the area to be healed paying attention to the boundary of that selection to contain good (i.e. typical) values of the image. The user can use any of Gimp's selection tools including the quick mask for that purpose. Once finished (e.g. signaled by pressing a button) the heal tool will remember that selection.

- In step 2 one invokes the Move Tool to move the selection into a suitable "source area". I'll try to copy the source to the destination on the fly so the user can see the effect (of the clone tool) immediately. Satisfied with the source region the user proceeds to step 3 - again by pressing a button (somewhere)

- In step 3 the healing tool starts working. For that it applies a given number of iterations of the so-called multi-grid algorithm. The nice thing about this algorithm is its speed independent(!) of the number of unknowns (= unknown factors). Probably less than 5 iterations will do even for millions of unknowns. I think I'll let the user select the number of iterations calling it the "strength" (or a similar word) of the healing tool. Strength 0 will give results identical to the clone tool. Strength 5 (?) will give the full effect of the healing tool as described by Georgiev. Let's see if an intermediate strength gives interesting (noticeably different) results.

For the "quick mode" the user starts by specifying a point somewhere within his source area. Then - exactly like the clone tool - he paints the destination area. BUT, once he/she releases the mouse button or lifts the pen, the healing algorithm would be started. It will give bad results if the boundary of the destination area still contains "defective" pixels.

I am looking forward to your comments, Helmut.