[Insight-developers] Neighborhood Tools

[Joshua Cates]

Hello all,

Over the past few days I have checked in a number of classes that comprise
a toolkit for manipulating itk::Images at the neighborhood level.
These neighborhood tools are specifically designed to work efficiently
with itk::Image buffers and the streaming environment.

I've included an introductory overview to the tools below.

I am hoping that other algorithm developers will find these tools useful
and participate in their continued development.

Please read on for more...

OVERVIEW OF THE NEIGHBORHOOD TOOLS

* WHAT ARE THE NEIGHBORHOOD TOOLS?
 The neighborhood tools are a set of container classes, algorithms, and
iterators that provide an API for developing itk::Image filters.

* WHY WERE THE NEIGHBORHOOD TOOLS CREATED?
  We need tools to prototype and build our algorithms.  These tools need
to support streaming.  Low level tools are necessary for achieving
reasonable speed and optimizing the use of memory.

* HOW DO THE NEIGHBORHOOD TOOLS WORK?
  The neighborhood tools extend the classic, zero-dimensional
iterator-container relationship to arbitrary dimensions.  A "neighborhood
iterator" class contains a geometry that defines the size and shape
(scope) of a neighborhood around a pixel.  As a neighborhood iterator
moves from pixel to pixel in an image, it is able to reference all the
surrounding pixels that lie within its scope.
  A new container class called an itk::Neighborhood was defined to hold
the values and the geometry of a dereferenced neighborhood iterator.  
Common mathematical operations are defined on the neighborhood container.  
These operations either manipulate the values contained in the
neighborhood, produce new neighborhoods of values, or return scalar
products.
  A second container class called an itk::NeighborhoodOperator was created
as a subclass of itk::Neighborhood.  A neighborhood operator is a
specialized neighborhood of coefficients that can be applied to another
neighborhood to perform some user-defined operation.  For example, a
convolution kernel or a morphological structuring element might be
encapsulated in a neighborhood operator. A neighborhood operator may be
given the ability to generate its own coefficients from user-defined
parameters.

* AN EXAMPLE OF USING THE NEIGHBORHOOD TOOLS TO FILTER AN IMAGE
  The process of convolution filtering is a good, generalized example.
Convolution filtering at a low level (the algorithm-developer's
perspective), can be done in three steps.

1. Create an itk::NeighborhoodOperator that generates the appropriate
convolution kernel (or create an itk::Neighborhood and fill it with the
appropriate coefficients).

2. Set up an itk::NeighborhoodIterator on the itk::Image region that you
want to filter.

3. Iterate across the region and take the inner product of the
neighborhood referenced by the iterator with the (mirrored) operator at
each step.

Note that multiple convolution operations can be combined into one by
pre-convolving all of the operators in step 1.

Separable convolution can be accomplished by successive applications of
operators with length in only one dimension.

* SOME FEATURES OF THE NEIGHBORHOOD TOOLS
- Iteration is optimized for speed. 
- Iteration is customizable and several types of iterators exist,
including an iterator that moves only along region boundaries.
- Iteration automatically wraps across region boundaries so there is no
need to keep track of the image buffer size.
- Boundary conditions and detection are automatically handled by some
iterators.
- Iterators can be subclassed to incorporate different boundary
conditions.
- Iteration uses "loop counters" to handle region boundary wrapping and to
detect out-of-bounds conditions.
- Predefined algorithms for common tasks.
- Operators that are modular and customizable. 
- The more people using a common API for itk::Image access, the more
community support is available for algorithm development and optimization
of the infrastructure.

* KNOWN PROBLEMS
 We are currently in the process of developing our first filters with
these tools.  Since the tools have not been extensively tested, there are
almost certainly be some bugs here and there.  Also, as the pipeline
infrastructure evolves, there will be necessary changes to the API and
internals of the tools.
 These tools have not been tested on the microsoft compiler since I don't
currently have access to one.

* POSSIBLE ENHANCEMENTS

- Support for arbitrarily shaped (non-rectangular) neighborhoods and
iterators.
- Support for morphological structuring elements and operations.
- Increased support for separable filtering in predefined operators..
- API for applying multiple operators at once at the neighborhood level.

* WHICH CLASSES ARE PART OF THE NEIGHBORHOOD TOOLS?
itkNeighborhoodBase
itkNeighborhood
itkNeighborhoodIterator
itkRegionNeighborhoodIterator
itkSmartRegionNeighborhoodIterator
itkRegionBoundaryNeighborhoodIterator
itkSliceIterator
itkDerivativeOperator
itkGaussianOperator
itkDerivativeHalfBackwardOperator
itkDerivativeHalfForwardOperator
itkNeighborhoodOperatorList
itkNeighborhoodAlgorithm
itkFilterImageSingleOperator
itkFilterImageMultipleOperator

* WHERE TO GET MORE INFORMATION

More complete documentation will follow soon in
/Documents/itkNeighborhoodDocumentation.pdf

For now you can see the inline doxygen documentation on the Insight web
pages.

Examples will come in the following weeks in the form of filters that we
will create with these tools.

Please email me with any questions, comments, concerns, miscellaneous
feedback, or whatever.  Our hope is to make this stuff useful for
everyone.

Thanks,

Josh.

+--+--+--+--+--+--+--+--+--+--+--+--
 Josh Cates			
 Department of Computer Science	
 University of Utah
 Email: cates at cs.utah.edu
 Phone: (801) 587-7697
 URL:   www.cs.utk.edu/~cates
--+--+--+--+--+--+--+--+--+--+--+---