[Insight-developers] FloodFill Iterator : Stack vs Queue : Replacement done.

[Luis Ibanez]

Hi

The

               "std::stack"

has been replaced with a

               "std::queue"


in the "itkFloodFillFunctionConst iterator.

-----

Some rewriting of the DoFloodStep() method was required.

The API of the iterator was not modified. However it is
now important to enforce the rule that iterators must
call GoToBegin() before start iterating.  In the case of
this iterator, an important initialization process is
performed in the GoToBegin() method.

This initialization process cannot be done in the constructor
because it requires access to a virtual method and virtual
methods are not overloaded in constructor.
(due to ICS = "Identity Crisis Syndrome"  :-) ).

The ConfidenceConnectedness, IsolatedConnected and
ConnectedThreshold filters were checked to ensure that
they are invoking GoToBegin() as required.

The use of the queue data structure dramatically reduces the
computational time for large images as well as the memory
comsumption.

----

Next modification scheduled for the FloodFill iterator is to
replace its 2N-connectedness with a generic ND-neighborhood.

This will allow to produce 6-connected, 18-connected or
26-connected (among many others) regions.  The modification
should not change much the API. The idea will be to use the
new ShapedNeigborhod iterator as a parameter of the FloodFill
iterator. The Shaped iterator will define which neighbor
pixels to visit when looking for candidates to be inserted
in the queue.

This would probably be done next week,...


Josh:

The Flood Fill algorithms are not multithreaded.
It could be interesting to do so, the tricky aspect is to
get a valid seed for every subregion sent to a different
process.


---

Luis




--------------------------
Joshua Cates wrote:
> Hi Luis, et al.
> 
> Are the flood fill algorithms multithreaded?  If so, it would be
> worthwhile to investigate the memory allocation strategies of STL linked
> list implementations for possible problems like heap-contention.
> 
> Josh.
> 
> ______________________________
>  Josh Cates			
>  School of Computer Science	
>  University of Utah
>  Email: cates@sci.utah.edu
>  Phone: (801) 587-7697
>  URL:   http://www.sci.utah.edu/~cates
> 
> 
> On Wed, 2 Apr 2003, Luis Ibanez wrote:
> 
> 
>>Hi,
>>
>>As we discussed in one of the recent Tcons, the FloodFill
>>iterator is using the STL stack container for holding the
>>pixels to be visited.
>>
>>However,  the queue is more appropriate for this task
>>
>>
>>Andy Cedilnik just made a very convincing test of the
>>advantge of using the Queue instead of the Stack.
>>
>>His test is a python script that implements both
>>approaches for flood fill and display their evolution.
>>
>>The test prints out both the computing time and the
>>maximum depth of the container (queue or stack).
>>
>>
>>Andy's  script is attached.
>>
>>I'll give it a shot at replacing the std::stack container with
>>the std::queue container in the itkFloodFill iterator.
>>
>>
>>    Luis
>>
>>
>>BTW
>>Andy is joking about rewriting ITK in Python,
>>at least I think it was a joke...    :-)
>>
> 
> 
> _______________________________________________
> Insight-developers mailing list
> Insight-developers@public.kitware.com
> http://public.kitware.com/mailman/listinfo/insight-developers
>