Filling a roi using Laplace diffusion equation

[Gabriel Landini]

I found this interesting thread in the usenet,

http://groups.google.com/group/sci.image.processing/browse_thread/thread/5f97aceac1c3efa0/972290c79200d05c?lnk=raot

To make it short, a roi is filled from the boundary pixels interpolating
inwards, using Laplace diffusion equation.
Any suggestions on how this could be computed?

Here is the example mentioned in that thread:

http://www.mathworks.com/access/helpdesk/help/toolbox/images/index.html?/access/helpdesk/help/toolbox/images/roifill.html

Cheers

Gabriel

[Michael Schmid]

Hi Gabriel,

a plugin like this is one of the points in my wishlist since a long  
time!

There is an easy but extremely slow algorithm: replace each pixel by  
the average of its neighbors, i.e., run 'smooth' repeatedly until it  
converges. For rois larger than a couple of pixels in the shortest  
direction it will take ages.

One can start with a coarser grid and then refine it, but  
nevertheless, this is slow. Also, for arbitrary roi shapes, there  
will be some effort to determine where to put the initial points.
There are many other methods, including finite elements (probably the  
fastest way to do it), but I don't know a simple one that works for  
arbitrary roi size.

Since we have no reasonable plugin for it, my current workaround is  
first filling the selection with the mean value of the near-border  
pixels or bilinear fit. Then I run a few iterations of Gaussian Blur  
with a large radius (large sigma) comparable to the roi size and  
refine it in steps until I have a small sigma of 1 or so; with a few  
Gaussian iterations at each step.

This method has one slight advantage over an exact solution of the  
Laplace equation: I usually apply it to remove particles. My method  
averages over a larger range at the boundary, so it does not matter  
if the boundary includes a few pixels influenced by the unsharp edge  
of the particle.

Best wishes,

Michael
________________________________________________________________

On 17 Apr 2009, at 12:45, Gabriel Landini wrote:

> I found this interesting thread in the usenet,
>
> http://groups.google.com/group/sci.image.processing/browse_thread/ 
> thread/5f97aceac1c3efa0/972290c79200d05c?lnk=raot
>
> To make it short, a roi is filled from the boundary pixels  
> interpolating
> inwards, using Laplace diffusion equation.
> Any suggestions on how this could be computed?
>
> Here is the example mentioned in that thread:
>
> http://www.mathworks.com/access/helpdesk/help/toolbox/images/ 
> index.html?/access/helpdesk/help/toolbox/images/roifill.html
>
> Cheers
>
> Gabriel

[Gabriel Landini]

On Friday 17 April 2009, Michael Schmid wrote:
> a plugin like this is one of the points in my wishlist since a long
> time!

:-)
> There is an easy but extremely slow algorithm: replace each pixel by
> the average of its neighbors, i.e., run 'smooth' repeatedly until it
> converges. For rois larger than a couple of pixels in the shortest
> direction it will take ages.

Some time ago I wrote a macro that does something similar by averaging the
pixels which are at the border of the area to be filled in a 3x3 window and
ignoring white pixels (which mark the area to be inpainted). I reduce the
number of tests by doing a 3x3 connectivity analysis first (so the mean is
only computed on those pixels surrounded by less than 8 to-be-inpainted
pixels). The number of tests gets smaller as the process advances.
This works surprisingly well for a 1-2 pixels thick areas/lines but it looks
awful for large ones. I am now realising that perhaps this might be similar to
what the Matlab code does, but  what I have not done is the convergence
iteration...
Indeed if from one side of the area-to-inpaint there is a large difference in
grey level, there is a very noticeable step, at the centre of the filled area
which I guess would disappear by the sequential averaging.

> Since we have no reasonable plugin for it, my current workaround is
> first filling the selection with the mean value of the near-border
> pixels or bilinear fit. Then I run a few iterations of Gaussian Blur
> with a large radius (large sigma) comparable to the roi size and
> refine it in steps until I have a small sigma of 1 or so; with a few
> Gaussian iterations at each step.

Thanks I will try implementing something like this and see if this improves
the results.
Cheers,

Gabriel

[Burger Wilhelm]

I am not sure if I understand the problem right, but what comes to my mind here is the "Kriging" technique used for geological surface interpolation between known elevation points (see e.g. http://people.ku.edu/~gbohling/cpe940/Kriging.pdf).
 
An alternative might be to calculate a Delaunay triangulation and linear interpolation within each segment ...
 
--Wilhelm

________________________________

Von: ImageJ Interest Group im Auftrag von Michael Schmid
Gesendet: Fr 17.04.2009 18:12
An: [hidden email]
Betreff: Re: Filling a roi using Laplace diffusion equation



Hi Gabriel,

here is another idea that I once had for an interpolating plugin:

One could use linear interpolation between the edge pixels (maybe
taking more than one edge pixel especially for calculating the pixels
further inwards, far from the edge).
This can be done for horizontal and vertical lines; the output value
would be a weighted average of the two, with the weight depending on
the distance from the edges along the respective line.

Then, less smoothing would be required; maybe starting with larger
kernel size and restricted to the inner pixels far from the edge,
then approaching the edge as the kernel size gets reduced (in most
cases, the near-edge pixels will be rather close to the final value
anyhow).

When changing kernel sizes by factors of ?1.6 or less between the
iteration steps it would be enough to use simple 'mean' smoothing
with a square kernel, which is about twice as fast as the Gaussian
blur in ImageJ (see my 'fast filters' on the documentation wiki); and
even faster if no checking for image bounds is needed.

Whatever the algorithm, it will be difficult to handle rois touching
the edge of the image. There won't be a linear interpolation in one
direction. Also for a true Laplacian, one would have to find a
suitable boundary condition at the edge.

Still, I have no really perfect algorithm in the back of my head,
otherwise I would have written the plugin already...

Best wishes,

Michael
________________________________________________________________

[Gabriel Landini]

On Friday 17 April 2009, Burger Wilhelm wrote:
> I am not sure if I understand the problem right, but what comes to my mind
> here is the "Kriging" technique used for geological surface interpolation
> between known elevation points (see e.g.
> http://people.ku.edu/~gbohling/cpe940/Kriging.pdf).
>
> An alternative might be to calculate a Delaunay triangulation and linear
> interpolation within each segment ...

The only points are the boundary points. So this is filling inwards from the
boundary. I suspect that the Kriging and the DT would expect points inside the
region (which is empty in our case).

I also wondered about fractal interpolation, but there seems to be more
talking than implementations.

Cheers

G