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
       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

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

- 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 Jarausch

Lehrstuhl fuer Numerische Mathematik
RWTH - Aachen University
D 52056 Aachen, Germany
Gimp-developer mailing list

Reply via email to