问题描述:

I wrote a program that loads, saves, and performs the fft and ifft on black and white png images. After much debugging headache, I finally got some coherent output only to find that it distorted the original image.

input:

fft:

ifft:

As far as I have tested, the pixel data in each array is stored and converted correctly. Pixels are stored in two arrays, 'data' which contains the b/w value of each pixel and 'complex_data' which is twice as long as 'data' and stores real b/w value and imaginary parts of each pixel in alternating indices. My fft algorithm operates on an array structured like 'complex_data'. After code to read commands from the user, here's the code in question:

`if (cmd == "fft")`

{

if (height > width) size = height;

else size = width;

N = (int)pow(2.0, ceil(log((double)size)/log(2.0)));

temp_data = (double*) malloc(sizeof(double) * width * 2); //array to hold each row of the image for processing in FFT()

for (i = 0; i < (int) height; i++)

{

for (j = 0; j < (int) width; j++)

{

temp_data[j*2] = complex_data[(i*width*2)+(j*2)];

temp_data[j*2+1] = complex_data[(i*width*2)+(j*2)+1];

}

FFT(temp_data, N, 1);

for (j = 0; j < (int) width; j++)

{

complex_data[(i*width*2)+(j*2)] = temp_data[j*2];

complex_data[(i*width*2)+(j*2)+1] = temp_data[j*2+1];

}

}

transpose(complex_data, width, height); //tested

free(temp_data);

temp_data = (double*) malloc(sizeof(double) * height * 2);

for (i = 0; i < (int) width; i++)

{

for (j = 0; j < (int) height; j++)

{

temp_data[j*2] = complex_data[(i*height*2)+(j*2)];

temp_data[j*2+1] = complex_data[(i*height*2)+(j*2)+1];

}

FFT(temp_data, N, 1);

for (j = 0; j < (int) height; j++)

{

complex_data[(i*height*2)+(j*2)] = temp_data[j*2];

complex_data[(i*height*2)+(j*2)+1] = temp_data[j*2+1];

}

}

transpose(complex_data, height, width);

free(temp_data);

free(data);

data = complex_to_real(complex_data, image.size()/4); //tested

image = bw_data_to_vector(data, image.size()/4); //tested

cout << "*** fft success ***" << endl << endl;

void FFT(double* data, unsigned long nn, int f_or_b){ // f_or_b is 1 for fft, -1 for ifft

unsigned long n, mmax, m, j, istep, i;

double wtemp, w_real, wp_real, wp_imaginary, w_imaginary, theta;

double temp_real, temp_imaginary;

// reverse-binary reindexing to separate even and odd indices

// and to allow us to compute the FFT in place

n = nn<<1;

j = 1;

for (i = 1; i < n; i += 2) {

if (j > i) {

swap(data[j-1], data[i-1]);

swap(data[j], data[i]);

}

m = nn;

while (m >= 2 && j > m) {

j -= m;

m >>= 1;

}

j += m;

};

// here begins the Danielson-Lanczos section

mmax = 2;

while (n > mmax) {

istep = mmax<<1;

theta = f_or_b * (2 * M_PI/mmax);

wtemp = sin(0.5 * theta);

wp_real = -2.0 * wtemp * wtemp;

wp_imaginary = sin(theta);

w_real = 1.0;

w_imaginary = 0.0;

for (m = 1; m < mmax; m += 2) {

for (i = m; i <= n; i += istep) {

j = i + mmax;

temp_real = w_real * data[j-1] - w_imaginary * data[j];

temp_imaginary = w_real * data[j] + w_imaginary * data[j-1];

data[j-1] = data[i-1] - temp_real;

data[j] = data[i] - temp_imaginary;

data[i-1] += temp_real;

data[i] += temp_imaginary;

}

wtemp = w_real;

w_real += w_real * wp_real - w_imaginary * wp_imaginary;

w_imaginary += w_imaginary * wp_real + wtemp * wp_imaginary;

}

mmax=istep;

}}

My ifft is the same only with the f_or_b set to -1 instead of 1. My program calls FFT() on each row, transposes the image, calls FFT() on each row again, then transposes back. Is there maybe an error with my indexing?

Thank you everyone for your opinions. All that stuff about memory corruption, while it makes a point, is not the root of the problem. The sizes of data I'm mallocing are not overly large, and I am freeing them in the right places. I had a lot of practice with this while learning c. The problem was not the fft algorithm either, nor even my 2D implementation of it.

All I missed was the scaling by 1/(M*N) at the very end of my ifft code. Because the image is 512x512, I needed to scale my ifft output by 1/(512*512). Also, my fft looks like white noise because the pixel data was not rescaled to fit between 0 and 255.

Not an actual answer as this question is Debug only so some hints instead:

**your results are really bad**

it should look like this:

- first line is the actual
**DFFT**result `Re,Im,Power`

is amplified by a constant otherwise you would see a black image- the last image is
**IDFFT**of the original not amplified`Re,IM`

result - the second line is the same but the
**DFFT**result is wrapped by half size of image in booth`x,y`

to match the common results in most**DIP/CV**texts

As you can see if you **IDFFT** back the wrapped results the result is not correct (checker board mask)

**You have just single image as DFFT result**

- is it power spectrum?
- or you forget to include imaginary part? to view only or perhaps also to computation somewhere as well?

**is your 1D **DFFT** working?**

- for real data the result should be symmetric
- check the links from my comment and compare the results for some sample 1D array
- debug/repair your 1D
**FFT**first and only then move to the next level - do not forget to test Real and complex data ...

**your IDFFT looks BW (no gray) saturated**

- so did you amplify the
**DFFT**results to see the image and used that for**IDFFT**instead of the original**DFFT**result? - also check if you do not round to integers somewhere along the computation

**beware of (I)DFFT overflows/underflows**

If your image pixel intensities are big and the resolution of image too then your computation could loss precision. Newer saw this in images but if your image is **HDR** then it is possible. This is a common problem with convolution computed by **DFFT** for big polynomials.

Suggest you look at the article http://www.yolinux.com/TUTORIALS/C++MemoryCorruptionAndMemoryLeaks.html

Christophe has a good point but he is wrong about it not being related to the problem because it seems that in modern times using malloc instead of new()/free() does not initialise memory or select best data type which would result in all problems listed below:-

Possibly causes are:

Sign of a number changing somewhere, I have seen similar issues when a platform invoke has been used on a dll and a value is passed by value instead of reference. It is caused by memory not necessarily being empty so when your image data enters it will have boolean maths performed on its values. I would suggest that you make sure memory is empty before you put your image data there.

Memory rotating right (ROR in assembly langauge) or left (ROL) . This will occur if data types are being used which do not necessarily match, eg. a signed value entering an unsigned data type or if the number of bits is different in one variable to another.

Data being lost due to an unsigned value entering a signed variable. Outcomes are 1 bit being lost because it will be used to determine negative or positive, or at extremes if twos complement takes place the number will become inverted in meaning, look for twos complement on wikipedia.

Also see how memory should be cleared/assigned before use. http://www.cprogramming.com/tutorial/memory_debugging_parallel_inspector.html

您可能感兴趣的文章：

- c - Memory error and leaks with detached and exited thread?
- what type of object should be used for a match-3 game (ios)
- android - Calabash step to check if application is being run for the first time
- python - Data and histogram do not collide in matplotlib?
- outlook - Find out Conflicting Events using office365 Rest Calendar API
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial