# FFT of irregular shaped data

I have an irregular shaped 3D image that I want to do frequency domain filtering on. Currently I simply zero-pad the data to make it a cube, then do an fft.

I was wondering if this was a valid approach and what effects this may have. Are there any alternate (better ways) to do this, and if so could you point me in the direction of some literature?

• The simplest way is to interpolate your data onto a uniform coordinate grid. Another way is to develop your own algorithm of Fourier transform that will work on a non-uniform grid: en.wikipedia.org/wiki/Non-uniform_discrete_Fourier_transform. – Eddy_Em Jul 10 '13 at 10:16
• OK, interpolation might be a good way to go about it. However, I don't know about doing a non-uniform sampling scheme, as the data within the 3D 'cloud' is still uniform in the spatial domain. Another solution I was thinking about is if I could take the segments (i.e each row), do the fft on each, and then combine the results. But I don't know how I'd go about doing this either. – user1531177 Jul 10 '13 at 11:18
• 3D-FFT is a sequence of 1D-FFTs. As long as your image is rectangular there is no padding necessary, the x, y and z dimensions can all be different lengths. You do 1D FFTs to each row-vector in the original image. Then you do 1D FFTs to each column-vector from the result of the first set of FFTs. Finally you do 1D FFTs to each "depth"-vector from the result of the second set of FFTs. (The DFT is separable.) The FFTW library will do this for you, as will the fftn function in matlab. – Wandering Logic Jul 10 '13 at 12:07
• As I say, however, the image is not simply rectangular. It is an irregular ill-defined shape, and so I am looking for a way to do the fft, only incorporating points in the 3D object, and nothing outside. – user1531177 Jul 10 '13 at 12:28
• For the FFT basis vectors to be orthogonal and comparable across your shape, you will have to zero pad each axis to at least the same max length for that axis. – hotpaw2 Jul 10 '13 at 14:40