[PYTHON MATRIX-SIG] Re: Two things

[Jim Hugunin]

> From: Charles G Waldman <cgw@pgt.com>

> I've spent a bunch of time optimizing 2D FFT's for image processing 
> applications.  The above code is not terrible, but I would like to 
> offer a few comments.
> 
> First of all, I don't think it will give the traditional normalization. 
> (See, for example, Gonzalez&Wintz, "Digital Image Processing",
Addison-Wesley,
> 1977, page 45)

Could you give me the right function to normalize this with?

> Secondly, it won't be the fastest thing in the world, particulary on
large
> arrays - the efficient way is to take a 1d FFT of each row in a given
array,
> then transpose the array, then do FFT's again down each row - this
eliminates
> a lot of page-faults which you get when doing FFT's down the columns. 
(There
> is an efficient recursive algorithm for matrix transpose.)  Then of
course
> you have to transpose again.  But in my experience, the two transposes
> are faster than all the column-wise accesses - - remember that in an FFT
> you're not always just handling adjacent elements.

This is in fact what will happen here.  The fftpack code only works on
packed vectors, so the fft along the -2 axis will result in the two
expected transpositions.  The transpositions will add a little extra python
overhead, but I'd bet this will be minimal.

> I have some C code I could contribute if you're interested - don't know
how
> well it would integrate into the FFT code you already have, but I'll send
it
> along to you if you want.

I really like the idea of using the standard fftpack code, so lets see how
well my version works for people.  If there are many speed problems I might
take you up on this offer.

-Jim

=================
MATRIX-SIG  - SIG on Matrix Math for Python

send messages to: matrix-sig@python.org
administrivia to: matrix-sig-request@python.org
=================