[Insight-developers] about shaped neighborhood iterator effiency

[Gaetan Lehmann]

Hi,

I thought to talk about iterator efficiency in my next contribution (a  
moving histogram based filter), but I fail to get good enough performances  
with or without shaped neighborhood iterator.

here is a performance test to show the impact of the size of the  
structuring element on performance. The size of the structuring element  
grow, but there is still only 1 activated neighbor in it (the center pixel)

radius: the radius of the structuring element
rep: number of repetitions for the measures
total: the number of neighbors (activated or not) in the neighborhood
nb: number of activated neighbors
hnb: number of pixels read per translation of the structuring elt (for the  
moving histogram algorithm)
d: mean time to run the dilation with the ITK dilate filter
hd: mean time to run the dilation with the moving histogram filter

#radius rep     total   nb      d       hd
0       5       1       1       2       0.002   0.026
1       5       9       1       2       0.002   0.026
2       5       25      1       2       0.008   0.026
3       5       49      1       2       0.014   0.024
4       5       81      1       2       0.02    0.024
5       5       121     1       2       0.028   0.026
6       5       169     1       2       0.036   0.022
7       5       225     1       2       0.044   0.024
8       5       289     1       2       0.054   0.026
9       5       361     1       2       0.07    0.02
10      5       441     1       2       0.082   0.024
15      5       961     1       2       0.17    0.022
20      5       1681    1       2       0.292   0.024
25      5       2601    1       2       0.456   0.028
30      5       3721    1       2       0.714   0.026
40      5       6561    1       2       1.286   0.022
50      5       10201   1       2       2.108   0.02
100     5       40401   1       2       11.762  0.022


The computation time is almost constant for the moving histogram filters  
(without shaped neighborhood iterator) but grow linearly with the size of  
the structuring element for the itk dilate filter (with shaped iterator).
The problem comes from the implementation of the shaped neighborhood  
iterator which is basically a layer above the neighborhood iterator. The  
data are cached for all the possible neighbors, even if there is only one  
defined.
The computation time is constant without shape iterator, but is also quite  
bad compared to the computation time of the itk dilate filter for small  
structuring elements.

Is there any plan to enhance the implementation of the shaped neighborhood  
iterator ?
Is there an efficient way to get/set the pixel value without using an  
iterator ?

In the moving histogram algorithm, to get the best performances, we need  
to be able to choose on which axe we want to move the iterator, and in  
which direction.
Here is an example of the wanted displacement:

  -------------------\
                     |
  /------------------/
  |
  \------------------\
                     |
  /------------------/
  |
  \------------------>

Is there an efficient solution to do that with an itk image iterator ?

Regards,

Gaetan

-- 
Gaëtan Lehmann
Biologie du Développement et de la Reproduction
INRA de Jouy-en-Josas (France)
tel: +33 1 34 65 29 66    fax: 01 34 65 29 09
http://voxel.jouy.inra.fr