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:
FFT (without any transform):
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?
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.