c++fftifftcimg

C++ Image 2D Fast Fourier Transform


I have to implement 2D FFT transform on the image (I cannot use library to do it for me - part of the course). I use CImg to load and save images. I have made the following code:

CImg<Complex> FastFourier(CImg<unsigned char> &originalImage)
{
    //check size in the main.cpp
    CImg<Complex> resultantImage = TransformToComplex(originalImage);
    vector< vector< vector< Complex > > > vectorImage = imageToVector(resultantImage);
    //cout << "Transform to complex" << endl;
    int size = originalImage.width();

    for(int i = 0; i < size; i++)
        FastFourier1D(vectorImage[i], false);

    vectorImage = rotateVector(vectorImage);

    for(int i = 0; i < size; i++)
       FastFourier1D(vectorImage[i], false);

    vectorImage = rotateVector(vectorImage);

    resultantImage = vectorToImage(vectorImage);

    return resultantImage;
}

And:

void FastFourier1D(vector< vector< Complex > > &input, bool inverse)
{
    int size = input.size();
    double angle;

    if(size <= 1)
        return;

    int channels = input[0].size();
    vector< vector< Complex > > even;
    vector< vector< Complex > > odd;

    for(int i = 0; i < size; i+=2)
    {
        vector< Complex > tempEven;
        vector< Complex > tempOdd;
        for(int channelIterator = 0; channelIterator < channels; channelIterator++)
        {
            tempEven.push_back(input[i][channelIterator]);
            tempOdd.push_back(input[i + 1][channelIterator]);
        }

        even.push_back(tempEven);
        odd.push_back(tempOdd);
    }

    FastFourier1D(even, inverse);
    FastFourier1D(odd, inverse);

    for(int channelIterator = 0; channelIterator < channels; channelIterator++)
    {
        for(int i = 0; i < size / 2; i++)
        {
           if(inverse == false)
               angle = -2.0 * (double)PI * (double)i / (double)size;
           else
               angle = 2.0 * (double)PI * (double)i / (double)size;

           double real = cos(angle);
           double imaginary = sin(angle);

           Complex W;
           W.setRP(real);
           W.setIP(imaginary);

           W = W * odd[i][channelIterator];

           input[i][channelIterator] = even[i][channelIterator] + W;
           input[(size / 2) + i][channelIterator] = even[i][channelIterator] - W;
       }
    }
}

However the results are not good. Input image: Input image

FFT (without any transform): FFT (without any transform)

Inverse FFT:

Inverse FFT

As you can see, it has colors of lena, but does not look like lena. Could you help me? Is there any mistake?


Solution

  • I found out that the answer was an incorrect implementation of multiplication operator in my Complex class.

    Complex Complex::operator*(const Complex& a)
    {
        Complex number;
        double RP = realPart * a.getRP() - imaginaryPart * a.getIP(); // this line was wrong
        double IP = realPart * a.getIP() + imaginaryPart * a.getRP();
        number.setRP(RP);
        number.setIP(IP);
        return number;
    }
    

    In real part, I forgot about minus. Now the whole implementation is working and fourier successfully converts an image into frequency domain and makes inverse into spatial domain as well.