[Insight-developers] FloodFilledSpatialFunctionIterator

[Damion Shelton]

> The idea here is that these filters and your iterators share a common
"technique".  Perhaps these
> filters and your iterators could both use some the same helper class (or
more likely these filters
> would use something derived from a helper class and your iterator would
probably inherit from this
> helper class).  It might even be possible for your iterator to be used
directly by these algorithms.

Ok... I think I see it. Part of the problem is that I'm not really all that
familiar with the fuzzy connectedness or fast marching algorithms, and
therefore not completely sure how to best integrate
FloodFilledSpatialFunctionIterator.

I'm going to ramble for a bit:

In the context of this iterator, the spatial function is any function that
determines whether the pixel being examined by the flood algorithm is part
of the "structure of interest" or not (<=0 means "inside the
structure/function" and > 0 means outside). I'm using simple shape functions
that give you results which mean "inside a sphere", "inside a torus", etc.
but I don't see any reason why these couldn't be more complex energy
functions or the like (presuming they were derived from itkSpatialFunction).

Incidentally, generalized SpatialFunctions don't neccessarily provide info.
about "insidedness" or "outsidedness"; it's a matter of interpretation. The
only parts of a SpatialFunction that are enforced (subject to change) are:

1) EvaluateFunctionValue - function to get the function value, a double, at
a point specified by a vnl_vector_fixed of doubles

2) EvaluateFunctionGradient - function to get the function's gradient (a
vnl_vector_fixed of doubles) at a point specified by a vnl_vector_fixed of
doubles

Therefore, the short answer is that I think - maybe - that the fuzzy
connectedness and fast marching algorithms could _use_ a
FloodFilledSpatialFunctionIterator rather than share a base class with it.
It's just a matter of specifying the functions that they use to determine
connectedness in a way that fits in with the SpatialFunction API.

> On an implementation note: I would avoid keeping a link list of the
indices to visit (you mentioned
> having operator++ move through this list).  That would be extremely memory
intensive.  I would
> suggest encapsulating operator++ algorithmetically. So, operator++
performs one step in the flood
> fill algorithm to determine the next index.

It seems there's a tradeoff of memory and computational efficiency. In the
current implementation the iterator is built once, and can then be used
multiple times with very little computational cost. If the operator++ were
implemented algorithmetically the flood would have to be recalculated each
time the iterator were re-used (by re-use I mean a complete walk from start
to end).

Of course, this could be left up to the user - if you're going to be
performing the iteration multiple times you'd build the list externally and
save it for future reference. With the size images I've been playing with
the size of the list hasn't been an issue, but I suppose with very large
volumes in high dimensions it could get unwieldy.

A few changes would be:

End() is undefined, since we no longer know the end until we get to it
IsAtEnd() is defined as a ++ call where no new pixels can be identified

I'll try it your way and see what happens - thanks for the tip.

-Damion-