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.
--
Helmut Jarausch
Lehrstuhl fuer Numerische Mathematik
RWTH - Aachen University
D 52056 Aachen, Germany
_______________________________________________
Gimp-developer mailing list
Gimp-developer@xxxxxxxxxxxxxxxxxxxxxx
https://lists.XCF.Berkeley.EDU/mailman/listinfo/gimp-developer
