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

[Blezek, Daniel J (Research)]

Luis,

  I thought I had re-worked the FloodFill iterator to do the equivalent of
GoToBegin in the constructor.  I had to duplicate some of the code because
of the virtual method call that you mentioned.  If not, I'll have an
additional look at the FloodFill interator, because requiring a GoToBegin()
call could perhaps induce some nasty and hard to find bugs in people's code
(if they don't call it).  To help the forgetful, we could set an
initialization flag in the class, and check it during the call to IsAtEnd(),
this would add some time to code that needs to be highly efficient.

  My take is that iterators should be self-initalizing.  Not being an STL
expert, but I think STL iterators are initialized to the beginning right?
Shouldn't we follow this model as much as possible?

-dan

-----Original Message-----
From: Luis Ibanez [mailto:luis.ibanez@kitware.com]
Sent: Wednesday, April 02, 2003 8:17 PM
To: insight-developers@public.kitware.com
Cc: Joshua Cates; Andy Cedilnik; Damion Shelton
Subject: Re: [Insight-developers] FloodFill Iterator : Stack vs Queue :
Replacement done.



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
> 



_______________________________________________
Insight-developers mailing list
Insight-developers@public.kitware.com
http://public.kitware.com/mailman/listinfo/insight-developers