[ITK] ITK NeighborhoodIterator alternative

[Bradley Lowekamp]

Hello David,

I unfortunately don't see a justification for the huge (~35x) difference between the C and the ITK iterator. 

Switching from indexing via an OffsetType to an scalar IndexType yields an over 2X speed up for the ITK iterator, but that is still unsatisfactory.

As both the C and ITK methods appear to be linear in performance, I don't think line cache misses are a significant factor here.

You also correctly set the Boundary Condition to Off, which should give the best performance. So there would be no performance benefit gain in using a ImageBoundaryFacesCalculator.

I have been meaning to spend some time on the convolution filters which use this iterator.

Brad

On Feb 9, 2015, at 6:11 PM, Matt McCormick <matt.mccormick at kitware.com> wrote:

> Hi Michael and David,
> 
> The way that memory is accessed with a NeighborhoodIterator can make
> it relatively slow.  There are many memory accesses that need to take
> place, and since all pixels from a neighborhood are not in the same
> location in memory, this interferes with cache lines, etc. [1].
> 
> For computing the response of large kernel sizes, FFT-based
> convolution will be much faster [2].
> 
> Since many more checks are at the boundary of an image, working with
> the NeighborhoodIterator can be sped up by using  an
> ImageBoundaryFacesCalculator [3].  This is covered in more detail in
> The Software Guide.
> 
> HTH,
> Matt
> 
> PS. David, your conda recipe for ITK looks great! Would you be
> interested in submitting it to upstream [4]?
> 
> [1] http://arstechnica.com/gadgets/2002/07/caching/
> 
> [2] http://www.itk.org/Doxygen/html/classitk_1_1FFTConvolutionImageFilter.html
> 
> [3] http://www.itk.org/Doxygen/html/structitk_1_1NeighborhoodAlgorithm_1_1ImageBoundaryFacesCalculator.html
> 
> [4] https://github.com/conda/conda-recipes
> 
> 
> On Mon, Feb 9, 2015 at 5:00 PM, David Froger <david.froger.ml at mailoo.org> wrote:
>> Hi,
>> 
>> I have the same question, this benchmark shows that NeighborhoodIterator
>> are very slow for large 2D images:
>> https://github.com/dfroger/quickstart/tree/master/itk/iterators
>> 
>> Did I made something wrong in using NeighborhoodIterator? Is there an efficent
>> alternative?
>> 
>> ITK was built in release mode.
>> 
>> Thanks,
>> David
>> 
>> Quoting Brehler, Michael (2015-01-29 10:15:49)
>>> Hi,
>>> 
>>> 
>>> 
>>> I am using the ITK NeighborhoodIterator to calculate response images of 3D box
>>> filters with varying size on volumetric images. The iterator is very convenient
>>> but especially for large filter sizes (27x27x27 and above) this method is very
>>> slow. Is there an efficient alterative?
>>> 
>>> 
>>> 
>>> Regards,
>>> 
>>> Michael
>>> 
>>> 
>>> 
>> _______________________________________________
>> Community mailing list
>> Community at itk.org
>> http://public.kitware.com/mailman/listinfo/community
> _______________________________________________
> Community mailing list
> Community at itk.org
> http://public.kitware.com/mailman/listinfo/community