[Insight-developers] FloodFill Iterator : Stack vs Queue : Re
placement done.
Luis Ibanez
luis.ibanez@kitware.com
Thu, 03 Apr 2003 09:23:22 -0500
Hi Daniel,
Yes, please take a look at the constructor,
it is good to have a second check in case
my modifications are not correct.
I think the GoToBegin() method is a fair
Practice. STL iterators are not initialized
either. You have to do something like
typedef std::vector<float> VectorType;
Vector vv;
VectorType::iterator it; // <----Constructor ***
it = vv.begin(); // <--- Initialization
while( it != vv.end() )
{
++it;
}
(***) Note that the constructor of the
STL iterator does not initialize it at all,
not even to a null value.
It is up to the programmer to initialize the
iterator to vv.begin() (or anything else).
The forgetful is going to have a hard time
finding bugs in his STL code too. :-/
----
If we want to push for Self-initialization
of the iterator, we may have to replicate
code in the constructors of the derived
classes of the FloodFill iterator. That may
be a reasonable trade-off.
Just for the record,
The flood fill is not the only iterator that
requires GoToBegin() to be invoked.
Documentation on the Iterators is clear
enough about the importance of calling
GoToBegin().
BTW, Josh just added a chapter on iterator
to the SoftwareGuide. This chapter will
show up in the web soon.
Luis
-----------------------------------------
Blezek, Daniel J (Research) wrote:
> 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
>