[Insight-developers] Neighborhood iterator refactoring request
for comment
Joshua Cates
cates@sci.utah.edu
Mon, 2 Dec 2002 10:40:38 -0700 (MST)
Hi Luis,
Thanks for the feedback. Yes, I think that these additions, especially of
the shaped iterator, will open up many new fun possibilities for algorithm
development.
Regarding 2c, there could be two signatures for this method, one which
takes a floating point offset and interpolates for the return value. I
was also thinking of adding a floating point offset method of neighbor
value query which interpolates.
The problem with interpolation, however, is that it restricts the type of
data over which a neighborhood iterator can be instantiated. If you want
to iterate over an image of linked lists, for example, interpolation is
undefined. We will need to come up with a way to allow instantiation on
any image type, enabling interpolation only when it makes sense (on scalar
or vector images, or when given a user defined interpolator). It may make
sense to create a subclass of the standard neighborhood iterator to add
this functionality.
Regarding throwing exceptions in 5b, 5c: I was thinking of accesses
specifically through offsets which address neighborhood pixels not
"active" in the iterator. These are technically out of bounds access
attempts, so there is no way for the iterator to return a correct value.
We can always add a method for querying whether an offset location is
active in the neighborhood.
For 5g, I can write a bool IsInNeighborhood(itk::Index) method to allow
for collision checking. Also maybe a method for returning a bounding box
extent of the neighborhood in itk::Index coordinates, something like a
GetNeighborhoodRegion method.
Josh.
______________________________
Josh Cates
School of Computer Science
University of Utah
Email: cates@sci.utah.edu
Phone: (801) 587-7697
URL: www.cs.utk.edu/~cates
On Wed, 27 Nov 2002, Luis Ibanez wrote:
> Hi Josh,
>
> This looks great.
>
>
> Some comments:
>
> (1) Will help to reduce the learning curve for
> using the neighborhood iterator.
>
> (2b) will be quite useful to access neighbors by their offset.
>
> (2c) question: will this distance take spacing into account ?
> maybe we need two of this methods, one measuring in pixels
> and another in space coordinates.
>
>
> (3a,3b) again are useful additions.
>
> (3c) maybe to know if it is inside the requested region.. ?
> altough by having the index from (3a) we could query
> the region directly....
>
>
> (5) Is a powerful addition. Arbitrary shaped neighborhoods
> allow more flexibility in algorithm implementation.
> This will make possible to manage different connectivities.
>
> (5b,5c) I'm not sure about throwing exceptions at the iterator level...
> What could be an scenario for attempting access to an invalid
> location ? maybe when access is made using indices and/or offset ?
>
> (5f) Will be really cool to have. We could implement evolving cellular
> automata with this. Things like region growing algorithms whose
> growth rules depend on the image context. It could also be possible
> to emulate cellular colonies using a neighborhood iterator per
> cell. Cell growth could be simulated by inserting neighbors.
> Also algorithms like curvature flow can be qualitatively
> simulated by cellular automata using simple rules like just
> "voting".
>
> (5g) How about computing collisions between two different neighborhood
> iterators. Something like checking if one index is contained in
> the neighborhood of both iterators. This will facilitate to throw
> N (maybe>1000) neigborhood iterators over an image and make them
> grow and reproduce in order to segment images. It will look a bit
> like the Voronoi2D segmentation but without the restriction to 2D.
>
> For example an iterator could grow its neighborhood if the
> pixels on the boundary satisfy a certain condition (e.g. like
> the ConfidenceConnectedness filter). A neighborhood iterators could
> split in two if it reaches a maximum size or if the pixels
> internally become too diverse. In some way, the FloodFill iterator
> will be the limit case of a growing neighborhood iterator.
>
> So far neighborhood iterators have been used with a single instance
> visiting the whole image following a static pattern. Facilitating
> their use in aggregates could be quite powerful.
>
>
>
>
>
> Luis
>
>
>
> =============================
>
> Joshua Cates wrote:
>
> > Hi Folks,
> >
> > I am refactoring the neighborhood iterators to optimize them with respect
> > to current use and expected future use. I expect to change their
> > implementation slightly (mostly transparent to the user), but also I want
> > to add some new functionality.
> >
> > Below is a summary of the functionality that both exists in the iterators
> > and that I think would be nice to have based on how I've used the
> > iterators and how I've seen others use them.
> >
> > Items which are new or represent changes are marked with +.
> >
> >
> > itk neighborhood iterators
> >
> > (1)+ A single iterator class handles forward, backward, and random access,
> > and automatically enables/disables bounds checking at construction time
> > by analyzing its iteration region. This is different from original
> > design where increasing functionality was added through subclassing.
> >
> > (2) The API supports access of neighbor pixel values through
> > (a) A scalar index into a linear array. it.GetPixel(14)
> > +(b) An itk::Offset from the center index.
> > it.GetPixel(itk::Offset<3>(1,0,0))
> > +(c) A distance and direction along a principle axis. it.GetNext(0, 1)
> > (d) Returning/setting entire neighborhood at once. it.GetNeighborhood()
> >
> > (3) The API supports querying the following information about a neighbor
> > pixel.
> > +(a) Its image index (itk::Index) location.
> > it.GetIndex(14), it.GetIndex(itk::Offset<3>(1,0,0), etc.
> > +(b) Its offset (itk::Offset) from the center of the neighborhood.
> > it.GetOffset(14), etc.
> > +(c) What else do people need to know? Perhaps spatial distance from the
> > center pixel?
> >
> > (4) The API supports querying the following information about the
> > neighborhood
> > (a) Stride lengths along each neighborhood axis. GetStride(1).
> > (b) Extent of the neighborhood (radius)
> > (c) Slices (std::slice) along axes. GetSlice(2)
> > (d) Size of the underlying neighborhood container, i.e. how many
> > pixels are the neighborhood.
> > (e) Image location (itk::Index) of the center of the neighborhood.
> >
> > (5)+ A new iterator class extends (1) to allow the creation of arbitrarily
> > shaped iterators. Shaped neighborhood iterators have the following
> > properties.
> > (a) Iterators are optimized for linear array access, versus indexed
> > lookups, though both should be possible. This means I expect more use
> > for things like neighborhood searching, summation of values, etc.
> > (b) Respond to all access methods in (2). Attempted access
> > of undefined pixel locations throws an exception.
> > (c) Respond to all queries in (3). Querying on an undefined neighbor
> > throws an exception.
> > (d) Responds to a restricted subset of (4). GetSlice and GetStride don't
> > make sense in this context, for example.
> > (e) Active or inactive neighbor locations are specified by offsets from the
> > center of the neighborhood.
> > (f) Neighbor locations can be activated or deactivated after construction
> > to support reshaping the neighborhood on-the-fly?
> > (g) What else?
> >
> > Attached below are some use case scenarios I put together which exercise
> > some of the existing and proposed API. Please send me your additional use
> > cases.
> >
> > I welcome comments from anyone. I plan to start working on these changes
> > next week.
> >
> > Thanks,
> >
> > Josh.
> >
> >
> > --------------------------------------------------------------------------------
> >
> > typedef itk::Image<float, 3> ImageType;
> > ImageType::Pointer image;
> >
> > .
> > .
> > .
> >
> > //
> > // In a 3x3 neighborhood mask, create a shaped neighborhood
> > //
> > ShapedNeighborhoodIterator<ImageType>::RadiusType radius = {1, 1, 1};
> > ShapedNeighborhoodIterator<ImageType> it(radius, image,
> > image->GetRequestedRegion);
> >
> > //
> > // activate the center cell
> > //
> > it->ActivateIndex(itk::Offset<3>(0,0,0));
> >
> > //
> > // activate a list of cells which represent the 6-neighbors
> > //
> > std::list<itk::Offset<3> > active_cells;
> > active_cells.push_back(itk::Offset<3>(0,-1,0));
> > active_cells.push_back(itk::Offset<3>(0,1,0));
> > active_cells.push_back(itk::Offset<3>(-1,0,0));
> > active_cells.push_back(itk::Offset<3>(1,0,0));
> > active_cells.push_back(itk::Offset<3>(0,0,1));
> > active_cells.push_back(itk::Offset<3>(0,0,-1));
> >
> > it->ActivateIndex(active_cells);
> >
> >
> > //
> > // Calculate all z partial derivatives using a non-shaped neighborhood
> > //
> > itk::ConstNeighborhoodIterator<ImageType> it(region, image,
> > image->GetRequestedRegion());
> > itk::NeighborhoodInnerProduct<ImageType> IP;
> > itk::DerivativeOperator<3> d_op;
> > d_op->SetOrder(1);
> > d_op->SetDirection(2);
> > d_op->CreateDirectional();
> > d_op->FlipAxes();
> >
> > std::slice z_slice = it.GetSlice(2);
> > for (; !it.IsAtEnd(); ++it) { float df_dz = IP(z_slice, it, d_op); }
> >
> >
> > //
> > // Calculate "half" forward derivatives in y direction
> > //
> > for (it.GoToBegin(); !it.IsAtEnd(); ++it) { float dy_forward =
> > it.GetNext(2) - it.GetCenter(); }
> >
> >
> > //
> > // Sum pixel values in neighborhoods
> > //
> > for (it.GoToBegin(); !it.IsAtEnd(); ++it)
> > {
> > float sum = 0.0f;
> > for (unsigned i = 0; i < it.Size(); ++i) { sum += it.GetPixel(i); }
> > }
> >
> > //
> > // Search the neighborhood for a value and and find the itk::Offset of that
> > // neighbor from the center of the neighborhood. here used to implement a
> > // "flood fill" type iterator. Can use shaped or non-shaped iterator.
> > //
> > std::list<itk::Index<3> > indicies_to_visit;
> > indicies_to_visit.push_back( itk::Index<3>(x_seed,y_seed,z_seed) );
> >
> > while (! indicies_to_visit.empty() )
> > {
> > itk::Index idx = indicies_to_visit.front()
> > indicies_to_visit.pop_front();
> > this->do_some_stuff(idx);
> >
> > it.SetLocation(idx); // or perhaps: it+=(idx - it.GetIndex());
> > for (unsigned i =0; i < it.Size(); ++i)
> > {
> > if ( it.GetPixel(i) == it.GetCenterPixel() )
> > {
> > if (this->already_visited( it.GetIndex(i) ) == false)
> > indicies_to_visit.push_back( it.GetIndex(i) );
> > }
> > }
> > }
> >
> >
> >
> > ______________________________
> > Josh Cates
> > School of Computer Science
> > University of Utah
> > Email: cates@sci.utah.edu
> > Phone: (801) 587-7697
> > URL: www.cs.utk.edu/~cates
> >
> >
> > _______________________________________________
> > Insight-developers mailing list
> > Insight-developers@public.kitware.com
> > http://public.kitware.com/mailman/listinfo/insight-developers
> >
> >
>
>
>
>