CODEWITHSUNDEEP
pythonimage-processingfft
bistaumanga
bistaumanga

Reputation: 1496

How to extend 1D FFT code to compute FFT of Images (2D) in python?

I am trying to extend the fft code that works fine for 1D arrays in python for images. Actually i know the problem is in logic in extension. I don't know much about FFTs and i have to submit assignments for Image Processing. I will be thankful for any hints or solutions

Here is the code, Actually, I'm trying to create a module for FFT in python, and it already worked fine for 1D with helps from rosetta Code's site. 

from cmath import exp, pi
from math import log, ceil

def fft(f):
    N = len(f)
    if N <= 1: return f
    even = fft(f[0::2])
    odd =  fft(f[1::2])
    return [even[k] + exp(-2j*pi*k/N)*odd[k] for k in xrange(N/2)] + \
           [even[k] - exp(-2j*pi*k/N)*odd[k] for k in xrange(N/2)]

def pad(f):
    n = len(f)
    N = 2 ** int(ceil(log(n, 2)))
    F = f + [0] * (N - n)
    return F, n 

def unpad(F, n):
    return F[0 : n]

def pad2(f):
    m, n = len(f), len(f[0])
    M, N = 2 ** int(ceil(log(m, 2))), 2 ** int(ceil(log(n, 2)))
    F = [ [0]*N for _ in xrange(M) ]
    for i in range(0, m):
        for j in range(0, n):
            F[i][j] = f[i][j]
    return F, m, n

def fft1D(f):
    Fu, n = pad(f)
    return fft(Fu), n

def fft2D(f):
    F, m, n = pad2(f)
    M, N = len(F), len(F[0])
    Fuv = [ [0]*N for _ in xrange(M) ]
    for i in range(0, M):
        Fxv = fft(F[i])
        for j in range(0, N):
            Fuv[i][j] = (fft(Fxv))[j]
    return Fuv, [m, n]

I called this module with tis code:

from FFT import *
f= [0, 2, 3, 4]
F = fft1D(f)
print f, F
X, s = fft2D([[1,2,1,1],[2,1,2,2],[0,1,1,0], [0,1,1,1]])
for i in range(0, len(X)):
    print X[i]

It's output is : 

[0, 2, 3, 4] ([(9+0j), (-3+2j), (-3+0j), (-3-2j)], 4)
[(4+0j), (4-2.4492935982947064e-16j), (4+0j), (8+2.4492935982947064e-16j)]
[(8+0j), (8+2.4492935982947064e-16j), (8+0j), (4-2.4492935982947064e-16j)]
[0j, -2.33486982377251e-16j, (4+0j), (4+2.33486982377251e-16j)]
[0j, (4+0j), (4+0j), (4+0j)]

The first one for 1d is fine as i verified result with Matlab's output but for 2nd one the Matlab's output is:

>> fft([1,2,1,1;2,1,2,2;0,1,1,0;0,1,1,1])

ans =

   3.0000             5.0000             5.0000             4.0000          
   1.0000 - 2.0000i   1.0000                  0 - 1.0000i   1.0000 - 1.0000i
  -1.0000             1.0000            -1.0000            -2.0000          
   1.0000 + 2.0000i   1.0000                  0 + 1.0000i   1.0000 + 1.0000i

The output is different ,which means i'm doing something wrong in the code's logic.Please help without bothering as i have not studied FFT formally till now so i'm not able to understand the mathematics copmpletely, maybe after i studied it, i may figure the problem out.

Upvotes: 1

Views: 3479

Answers (2)

toylas
toylas

Reputation: 437

I agree with isedev that you should use numpy. It already has a great fft package that can do transforms in n-dimensions.

http://docs.scipy.org/doc/numpy/reference/routines.fft.html

http://docs.scipy.org/doc/numpy-1.4.x/reference/generated/numpy.fft.fft.html

Upvotes: 1

tacaswell
tacaswell

Reputation: 87376

Your code is a little hard to follow, but it looks like you are taking the FFT along the same direction both times. Look up the integral from of the FT, you will see that the x and y integrations are independent. That is (sorry, this notation is awful, ' indicates a function in Fourier space)

FT(f(x, y), x) -> f'(k, y)
FT(f'(k, y), y) -> f''(k, w)

So what you want to do is take the FFT of each row (than is do N 1D FFTs) and shove the results into a new array (which takes you from f(x, y) -> f'(k, y)). Then take the FFT of each column of that result array (doing M 1D FFTs) and shove those results into another new array (which takes you from f'(k, y) -> f''(k, w).

Upvotes: 3

Related Questions