[Insight-developers] Proposed requirements for convolution filters in ITK

[Gaëtan Lehmann]

Hi Dirk,

Le 2 juin 11 à 19:07, Padfield, Dirk R (GE Global Research) a écrit :

>
> "VNL operates only on images whose sizes are powers of two."
> This is not entirely true; VNL requires that the image size be  
> multiples
> of 2s, 3s, and 5s, and this is far less restricting (and much faster).

So VNL based FFT filters in ITK are too restrictive when then impose  
to use sizes which are power of two?
This is a great news!


> It also turns out that, even though FFTW handles any size, it is much
> faster when the images are multiples of 2s, 3s, and 5s.

According to FFTW's documentation,

   "FTW is best at handling sizes of the form 2a 3b 5c 7d 11e  
13f,where e+f
    is either 0 or 1, and the other exponents are arbitrary. Other  
sizes are
    computed by means of a slow, general-purpose algorithm (which
    nevertheless retains O(n log n)"

This is easily verified in practice, as shown in figure 7 of

   http://hdl.handle.net/10380/3154


>  In my
> implementation, I wrote a function that calculates the next largest
> image size in each dimension that is a multiple of 2s, 3s, and 5s and
> then pads the image with zeros before doing the Fourier domain
> computation.

It seems that we have done something very similar again.
We should work more often together :-)

>  Thus, the padding size should not be a parameter.

The padding size can be useful to let the user to let the user choose  
the trade off between memory efficiency and better plan computation  
with fftw's wisdoms.
Padding size is expressed as the greatest prime factor to achieve for  
the image sizes.
- greater prime factors help to reduce memory usage.
- smaller prime factors enhance the chances to get a size which match  
a size already used, making FFTW's wisdoms more efficients

Gaëtan

-- 
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  http://www.itk.org
http://www.mandriva.org  http://www.bepo.fr

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 203 bytes
Desc: Ceci est une signature ?lectronique PGP
URL: <http://www.itk.org/mailman/private/insight-developers/attachments/20110603/c72ea61d/attachment-0001.pgp>