[Insight-users] RE: itk::SparseImage + binary images in general(BUI XUAN Viet)

[Miller, James V (Research)]

You wouldn't be able to create a sparse image representation and just drop it into an ITK pipeline.  Some early design decisions relative to performance and flexibility preclude this.
 
ITK has such a rich set of iterators for an image. RegionIterators, ReverseRegionIterators, FloodFillIterators, NeighborhoodIterators, ReflectiveIterators, etc. The iterators are not "part" of the Image class but exist outside of the class.  This allows great flexibility and skirts some compiler issues (related to having all these iterators in a single class).  Note that N-dimensional iteration about an image is much more complicated than iterating an STL container. Each of the ITK iterators has to maintain quite a bit of state and cache.
 
The impact of separating the iterators from the Image container classes is that each FILTER decides for itself what type of iterator it wants to use.  For instance, the DiscreteGaussianImageFilter uses a standard NeighborhoodIterator, the ConnectedComponentImageFilter uses a ShapedNeighborhoodIterator, etc. If you passed a SparseImage to an ITK filter, the iterators used by that filter would have to support accessing a SparseImage.
 
For performance reasons, most the image iterators use pointer arithmetic to navigate the N-dimensional image. Pointer arithmetic is also used to converting an interator to an index position.
 
ImageRegionIterator caches a pointer for "start" of the image.  It then keeps track on a 1D offset for the current pixel position.  Pixels are accessed as *(start+offset).  The 1D offset is only converted to an ND itk::Index when the user specifically asks for an index. I
 
ImageRegionIteratorWithIndex always maintains a valid itk::Index internally.  This index is update with every call to operator++.  Internally, pointers are kept to the current pixel being examined.
 
NeighborhoodIterators maintain a collection of pointers to pixels within an image. As an image moves, all the pointers are incremented.
 
A few years ago, I realized that if we had made a slight change to the design (and not exposed a pointer to the image buffer), all the iterators could have been written using a 1D offset.  The iterators would access a pixel via an interface to the PixelContainer via this 1D offset.  This would allow different image organizations using the same set of iterators.  ITK images are contiguous blocks of memory.  If we designed the iterators to use 1D offsets, we could create the illusion of contiguous memory but support SparseImages or images that are only slice contiguous, etc.
 
So to support a SparseImage in ITK completely, the options are to:
 
A) Convert all the image iterators to use a 1D offset approach.  SparseImage could then just subclass off of ImageBase. 
 
B) Create separate iterators for a SparseImage and separate filters to process a SparseImage.  For instance, DiscreteGaussianSparseImageFilter, etc.  This requires duplicating filter code.
 
Option A would be the best option.  But this very invasive and we would have to determine whether there are any performance issues (due to using a function call inplace of a direct memory access).
 
Option B is probably the better short option if there are only a few filters that you want to run on a SparseImage.  If you want to use the breadth of filters in ITK with SparseImages, then something like Option A would have to be explored.  
 
Here is another option:
 
C) Create some mechansism for a filter to request a "class" of iterator from some trait class.  IteratorTraits<ImageType>::ImageRegionIterator would be a typedef to an image region iterator suitable for the particular type of image (dense or sparse image).  IteratorTraits<ImageType>::ShapedNeighborhoodIterator would be a typedef to a shaped neighborhood iterator for the particular type of image. Etc.
 
The approach would require a second set of iterator classes that operate on SparseImages.  However, separate filters for dense and sparse images would NOT be required.  Instead, we would just have to edit EVERY filter to use the IteratorTraits<> to create iterators instead of creating them directly.  We'd have to retrain the developers but this is doable.  We can even write a script to change the existing code.
 
 
 
 

	-----Original Message----- 
	From: insight-users-bounces at itk.org on behalf of Robert Maroon 
	Sent: Wed 4/6/2005 4:45 PM 
	To: insight-users at itk.org 
	Cc: 
	Subject: [Insight-users] RE: itk::SparseImage + binary images in general(BUI XUAN Viet)
	
	

	BUI XUAN Viet wrote:
	
	====================
	1/ Complete "solution" that allows to work with an itk
	pipeline and with iterators to access pixels directly.
	====================
	
	This would be the ideal solution, as you mentioned.
	The question is, is this feasible in ITK? That is, to
	create an alternative "Image" type that could work
	transparently with iterators such that for most
	reasonable algorithms, the "Image" is read from (and,
	for some alternative image types, written to)
	transparently as an ITK-style raster image.
	
	Besides sparse representations, I also imagine this
	could be useful for working with non-raster image
	types (e.g., EPS). (Though, of course, a filter
	couldn't *write* in a raster-wise manner into a vector
	graphic, but the vector graphic could still be used as
	an image source.)
	
	Assuming it is technically possible in the current ITK
	class hierarchy, the other question would be where to
	place the class such that most of Image's methods
	would be exploitable immediately and not need to be
	rewritten.
	
	Robert
	
	
	
	
	               
	__________________________________
	Do you Yahoo!?
	Yahoo! Sports - Sign up for Fantasy Baseball.
	http://baseball.fantasysports.yahoo.com/
	_______________________________________________
	Insight-users mailing list
	Insight-users at itk.org
	http://www.itk.org/mailman/listinfo/insight-users