New Subtract Background Algorithm

[ChristianHeld]

Dear ImageJ Team,

I just did some experiments with the subtract background method written by
Michael Schmid on 09-Oct-2007. Now I'm trying to understand the
implementation.

I know how the standard rolling ball algorithm works (i read the
original paper) and I know that the paraboloid is approximated by using
the 4 main directions. But it is quite hard for me to understand which
conditions the paraboloid has to fulfill?  What is exactly done with the
6th degree polynomial?

Is there perhaps a paper where the modified algorithm is explained?

Thanks for your help!

Yours,
Christian

[Michael Schmid]

Hi Christian,

sorry, there is no paper on this, and I am too busy with
writing papers on my research for writing a paper about this
algorithm.

The reason why I wrote a new algorithm:
- I needed an algorithm that works for float images
- I was unhappy with the artifacts for radii>10
- Adding preview and parallel processing of stack slices on
   multiprocessor machines (OK, this can be done with the
   current algorithm).

The rationale for using a paraboloid instead of a ball is the
following:

For images other than 8-bit images, the pixel values can have a
range that is very different from typical horizontal distances.
So, for a 16-bit image, objects may have pixel values of 50000
and the background 10000, but a ball of say, radius=50 has an
almost negligible extension in the direction of the pixel
values. Looking at it in a "natural" scale, the ball would
appear more like a flat disk.

To mimic the same procedure as the rolling ball algorithm for
an 8-bit image (with the pixel values lower by a factor of 256),
instead of a ball one would need an ellipsiod that is 256*higher
than wide. This would give us not one radius but two, and make
things more complicated.

A paraboloid has the advantage that it has only one scaling
constant. I took the radius of curvature at the apex to describe
the paraboloid. In cases where the previous rolling ball
has touched the "bottom of the image" only near its top, not at
the sides, this results in a similar behavior as the previous
algorithm.

A caveat for 16-bit images: As I said, the ball will behave more
like a disk for these images, so it will touch at the sides,
and its limited lateral dimension will determine what the
previous algorithm does. For my paraboloid algorithm, the
paraboloid has infinite lateral extension. So, usually much
smaller radii will be required for the new algorithm when
processing 16-bit images (radii can be below 1).

Another advantage of a paraboloid: It is not sensitive to adding
a slope - so if the image has a sloping background, the
"sliding paraboloid" algorithm will do exactly the same as for
the same image data without the slope.

How to chose the radius: I would suggest to look at the preview
with "Create Background" to see how well the particles are
leveled out. Another option is using my new Dynamic Profiler
to check a line profile during preview. It is still not finished;
the .class file of the current version is temporarily on
http://www.iap.tuwien.ac.at/www/surface/tmp/Dynamic_Profiler.class

Another way to estimate the radius is to determine the maxixmum
curvature that the background can have and calculate the radius
of a circle with that curvature.

Finally, the 6th-order polynomial: this is for corner correction
only. The reason why corner correction is needed: assume a
particle at a corner (e.g. top right corner of blobs.gif).
A rolling ball or sliding paraboloid can't touch the "bottom
surface" of the image all around the particle because of the
corner - so it will touch the particle at the edge. Thus, the
corner particle will be partly eliminated.

This is a problem because it will make the particle appear smaller
and with less intensity, but it can happen that the particle
won't be recognized as "particle touching edge" any more. When
doing statistics on particles, this may cause problems.

So the algorithm tries to find out whether the edge pixels are
untypical for a background. Here the 6th-order polynomial comes
in: It is assumed that the background at the edges does not fall
off by much more than a 6th-order polynomial. For images
produced by optical systems that show vignetting, I consider this
a reasonable assumption.


By the way, preprocessing of the image before applying the
"sliding parabola" algorithm has been modified in the latest
version of ImageJ (1.39k). It is now less sensitive to small
brightness excursions in the direction opposite to that of the
particles (bright dots in case of dark particles and vice
versa).


Hope this helps,

Michael
________________________________________________________________

On 22 Nov 2007, at 17:30, ChristianHeld wrote:

> Dear ImageJ Team,
>
> I just did some experiments with the subtract background method  
> written by
> Michael Schmid on 09-Oct-2007. Now I'm trying to understand the  
> implementation.
>
> I know how the standard rolling ball algorithm works (i read the  
> original paper) and I know that the paraboloid is approximated by  
> using the 4 main directions. But it is quite hard for me to  
> understand which conditions the paraboloid has to fulfill?  What is  
> exactly done with the 6th degree polynomial?
>
> Is there perhaps a paper where the modified algorithm is explained?
>
> Thanks for your help!
>
> Yours,
> Christian