[Insight-users] Silly Question!!

Thu, 20 Mar 2003 16:31:14 -0500

Hi Zein,

Why is that the silly questions turn
out to be the hardest to answer right ?

---

I was about to say:

  No, the number of initial seeds shouldn't matter,...

but...

  then looking closer at the algoritm used
  by the region growing filters like ConnectedThreshold,
  which is implemented in the class

      itkFloodFillFunctionConditionalConstIterator

It happens that it works based on a stak of pixels
"to be visited".

This class was designed and implemented by Damion Shelton,
at CMU. So, I hope he will correct me if any description
here is incorrect or missleading.

--

The basic algorithm goes as follows:

- You have a stak of indices corresponding
   to pixels "to be visited".

- You have a mask image that will have
   values 0,1,2 depending on:

   0 = pixel not visited yet
   1 = pixel visited and not satisfying condition
   2 = pixel visited and satisfying condition

The stack of pixels to be visited is filled with
the initial list of 'seeds' that you provide.

Then in a big loop, the pixel on the top of the stack
is tested in the mask image,

if it is an unvisited pixel, its condition is tested,
and the result is marked in the mask image,

then it is taken out of the stack. Finally all its
neighborhood are tested in the mask, and those that
have not been visited are inserted in the stack.

The big loop ends when the stack is empty.

So....

Let's consider the hypotetical case in which you have
a spherical shape that you plan to flood fill.

If you start with a single seed, conveniently placed
in the center of the shape, the region will start
growing from the seed. First the 6 nearest neighbors
will be inserted in the stack, then one of them will
be analyzed and some of its 6 neearest neighbors will
be tested... and so on.

At a particular time, the stack should containg the
pixels in the external 'surface' of the region.

since the std::stack is a LIFO structure,
http://www.sgi.com/tech/stl/stack.html

the growth of the region will be concentrated in a
particular section of the region. That means that instead
of generating a spherical wavefront, this algorithm will
grow by protuding extensions. This extension will tend to
grow linearly getting farther and farthere from the
seed point, until they reach the boundary of the
condition defining the object. At that point, the
'active' region of growth will be the zone of immediate
contact between the region and the boundary of the
object. In our hypotetical case, this active region
will be a circle. Again, the circle will grow a
protrusion, that will be squeezed against the object
boundary. ...

This seems to indicate that a long time will pass before
the algorithm can go back and take out of the stack the
pixels that were at the other side of the original seed.

So we could describe this as a directed growth that
then procedess as 'adherent' to the object boundaries.
Imagine the way in which frost will appear inside
a refrigerator. It should also tend to create
filamentous structures like the plants that grow only
at the buds.

By growing close to the boundaries, a lot of time
will be passed testing points that are not in the
object.  If the algorithm developed by generating
a wave front (by using a FIFO structure), most of
the time, the tests will result in points that are
inside the object and hence result in actual region
growth.

This could be achieved by using a std::queue which
is a FIFO container,
http://www.sgi.com/tech/stl/queue.html

or maybe even better with a
std::priority_queue
http://www.sgi.com/tech/stl/priority_queue.html

(altought it is not clear if the overhead of sorting
will take over the advantage of ordered growth)

---

So,....

If you start from multiple seeds instead of using
a single one, the current algorithm will not be
much different since the additional seeds you
provided will not be visited until the whole
structure connected to the first seed has been
flooded. Very likely the flooding of the first
seed will surround the other seeds before they
have a chance to start growing on their own.

If the growth was organized in wave fronts by
using a FIFO container, multiple seeds will
make a difference since the growth will be
done in pallallel, one pixel at a time per
seed.  That is, first the region of the first
seed will gain a neighbor, then the second
seed will gain a neighbor... and so on.
Only when the last seed has gained its first
neighbor, will the first seed have a chance
to make its second neighbor.

That being said, the wave-front approach will
have the disadvantage of breaking locality in
memory access and probably result in many
cache misses. Which will certainly reduce
performance...

----

So, to be honest,

I don't know the answer to your not-so-silly question,

but I certainly think that it is worth to investigate
the  issue, and that could probably give you enough
material for publishing a paper in a decent journal.

 From the fact side. We know that something like the
FastMarchingLevelSet method will run faster than the
current flood fill implementation, and we probably say
that both things are 'region growing' methods.

Regards,

     Luis

-----------------------------
salah wrote:
> Hi all,
> 
> would a region-growing segmentation filter (Connected threshold for example) work faster if it 
> is fed with many seed points, rather than only one??
> 
> Thanks,
> Zein
> 
> 
> ->8<------------->8<------------->8<------------->8<------------->8<------------->8<-
> Zein I. Salah 
> University of Tübingen, WSI-GRIS, Sand 14, 72076 Tübingen 
> Email: salah@gris.uni-tuebingen.de
> Tel.: (07071) 29 75465 (GRIS),           Fax: (07071) 29 54 66
> 
> _______________________________________________
> Insight-users mailing list
> Insight-users@public.kitware.com
> http://public.kitware.com/mailman/listinfo/insight-users
> 