c++中图像的快速傅立叶变换和快速傅立叶变换

Question

我写了一个程序来加载、保存和执行黑白png图像的fft和ifft。经过许多令人头疼的调试，我终于得到了一些连贯的输出，结果却发现它扭曲了原始图像。

输入：

​

​

fft：

​

​

ifft：

​

​

据我测试，每个数组中的像素数据都被正确地存储和转换。像素存储在两个数组中，包含每个像素的b/w值的'data‘和长度为'data’的两倍的'complex_data‘，并且以交替的索引存储每个像素的实际b/w值和虚部。我的fft算法是在一个类似'complex_data‘结构的数组上运行的。在读取来自用户的命令的代码之后，下面是有问题的代码：

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;
}}

我的ifft是相同的，只是f_or_b设置为-1而不是1。我的程序对每一行调用FFT()，转置图像，再次对每一行调用FFT()，然后转置回来。我的索引可能有错误吗？

Answer 1

不是一个实际的答案，因为这个问题是Debug only，所以应该有一些提示：

你的结果真的很糟糕

它应该看起来像这样：

​

​

第一行是实际的DFFT，result

• Re,Im,Power被常量放大，否则你会看到一个黑色的图像

• 最后一个图像是IDFFT的原始的未放大的Re,IM结果

• 第二行是一样的，但DFFT结果在展位x,y中被半倍大小的图像包裹，以匹配大多数DIP/CV文本

中的常见结果

如你所见，如果你IDFFT返回包装的结果，结果是不正确的(棋盘掩码)

你只有一幅图像作为结果

• 是功率谱吗？
• 还是你忘了包括虚部？要只查看，或者也可以在某处查看计算？

你的1D **还能用吗？**

对于真实数据，结果应该是从我的评论中测试链接，并比较一些样本的结果1D array

• debug/repair你的1D 快速傅立叶变换首先，然后才移动到下一级

• 不要忘记测试真实和复杂的数据...

你的IDFFT看起来像BW (无灰色)饱和

• 那么，您是否放大了DFFT结果以查看图像，并将其用于IDFFT而不是原始的DFFT结果？
• 还要检查在计算过程中是否没有舍入到某个地方的整数

注意(I)溢出/下溢

如果你的图像像素强度太大，图像的分辨率太高，那么你的计算可能会失去精度。较新的人在图像中看到了这一点，但如果您的图像是HDR，那么它是可能的。这是由DFFT计算的大多项式卷积的一个常见问题。

Answer 2

感谢大家的意见。所有关于内存损坏的东西，虽然这是一个观点，但并不是问题的根源。我错位的数据大小并不是太大，并且我将它们释放到了正确的位置。在学习c的同时，我对此进行了大量的练习。问题也不是fft算法，甚至也不是我的2D实现。

我所遗漏的就是ifft代码末尾的1/(M*N)缩放。因为图像是512x512，所以我需要将ifft输出缩放1/(512*512)。此外，我的fft看起来像白噪声，因为像素数据没有重新缩放到0到255之间。

Answer 3

建议你看看这篇文章http://www.yolinux.com/TUTORIALS/C++MemoryCorruptionAndMemoryLeaks.html

克里斯托弗的观点很有道理，但他错了，他认为这与问题无关，因为在现代，使用malloc而不是new()/free()不会初始化内存或选择最佳数据类型，这将导致以下列出的所有问题：

可能的原因是：

当一个数字在某个地方发生变化时，我也看到过类似的问题，比如在上使用了平台调用，而值是通过值而不是引用传递的。这是由于内存不一定是空的，所以当你的图像数据进入时，它将对它的值进行布尔数学运算。我建议您在将图像数据放入内存之前确保内存为空。

1. 内存向右旋转(汇编语言中的ROR)或向左旋转(ROL)。如果使用的数据类型不一定匹配，则会发生这种情况。输入无符号数据类型的有符号值，或者每个变量中的位数不同。由于进入有符号变量的无符号值而导致
2. 数据丢失。结果是1比特丢失，因为它将被用来确定否定或积极，或者在极端情况下，如果发生二进制补码，数字的含义将变得反转，请在维基百科上查找二进制补码。

另请参阅在使用前应如何清除/分配内存。http://www.cprogramming.com/tutorial/memory_debugging_parallel_inspector.html