Или я должен спросить - применяется ли свойство поворота для преобразований Фурье к дискретным БПФ?
Я написал консольную программу win32 с использованием VS2015.В моей программе я кэширую массив из 4 DFT поворотов (0, 90, 180 и 270 градусов) входного изображения пользователя.
Эти 4 DFT могут занимать много памяти.Я хочу уменьшить стоимость памяти, вычисляя FT повернутого изображения при необходимости.Чтобы уменьшить временные затраты, я полагаю, что было бы быстрее повернуть FT входного сигнала, чем вычислить FT повернутого изображения.
После долгих экспериментов я не могу выполнить эту работу.Я хотел бы знать, почему ??
Например, рассмотрим вращение против часовой стрелки на 90 градусов, r90.
Почему нет, r90 (FT (in)) = FT (r90 (in))?
Пример - входное изображение 4px4p.
Input image, 'in'
23 87 90 3
39 51 56 95
12 84 47 61
71 18 11 96
Fourier Transform of input, FT_in = FT(in)
844,0 -59,15 -146,0 -59,-15
-1,-45 -66,16 109,19 2,138
-30,0 -145,-229 20,0 -145,229
-1,45 2,-138 109,-19 -66,-16
Centered FT of input, cDC_FT_In = FT(in)
20,0 -145,229 -30,0 -145,-229
109,-19 -66,-16 -1,45 2,-138
-146,0 -59,-15 844,0 -59,15
109,19 2,138 -1,-45 -66,16
Rotated FT of input, r90_FT_In = R90(FT(in))
-145,-229 2,-138 -59,15 -66,16
-30,0 -1,45 844,0 -1,-45
-145,229 -66,-16 -59,-15 2,138
20,0 109,-19 -146,0 109,19
(A) Recentered Rotated FT of input, cDC_r90_FT_In = cDC(r90(FT(in)))
20,0 109,-19 -146,0 109,19
-145,-229 2,-138 -59,15 -66,16
-30,0 -1,45 844,0 -1,-45
-145,229 -66,-16 -59,-15 2,138
Rotated input, r90_in = r90(in)
3 95 61 96
90 56 47 11
87 51 84 18
23 39 12 71
FT of rotated input, FT_r90_in = FT(r90(in))
844,0-1,-45 -30,0 -1,45
15,-59 -138,2 -229,-145 16,-66
146,0 -109,-19 -20,0 -109,19
15,59 16,66 -229,145 -138,-2
(B) Centered FT of rotated input, cDC_r90_FT_In = cDC(FT(r90(in)))
-20,0 -109,19 146,0 -109,-19
-229,145 -138,-2 15,59 16,66
-30,0 -1,45 844,0 -1,-45
-229,-145 16,-66 15,-59 -138,2
Почему (A) повернутый FT входа и (B) FT повернутого входа отличаются?
Вот простая тестовая программа, которая производит распечатку выше.
// DFT Rotn.cpp : Tests the Rotation Property of Discrete Fourier Transforms.
// FFT() & FFT2D() are modified code by Paul Bourke: http://paulbourke.net/miscellaneous/dft/
//
// Prints out to the console and debug output.
// To enable printing to debug output, uncomment lines below containing,
// "// Uncomment to print to debug output"
#include "stdafx.h"
#include <iostream>
//#include <Windows.h> // Uncomment to print to debug output
using namespace std;
const int inD = 4; // Input image W & H
int FFT(int dir, int nn, double *x, double *y);
int FFT2D(double c[4][4][2],int inW,int inH,int dir);
void print2dArray(char str[100], int array[inD][inD]);
void printComplex2dArray(char str[100], double array[inD][inD][2]);
void cyclicShiftComplex2dArray(double inRA[inD][inD][2], double outRA[inD][inD][2],
int xOff, int yOff);
int main() {
int in[inD][inD] =
{ {23, 87, 90, 3},
{39, 51, 56, 95},
{12, 84, 47, 61},
{71, 18, 11, 96} };
print2dArray("\n\nInput image, 'in' ", in);
// Create the Fourier Transform of the input.
double FT_in[inD][inD][2];
for(int y2=0; y2<inD; y2++)
for(int x2=0; x2<inD; x2++){
FT_in[y2][x2][0] = in[y2][x2];
FT_in[y2][x2][1] = 0;
}//for(x3)
FFT2D(FT_in, inD, inD, 1);
printComplex2dArray("\n\nFourier Transform of input, FT_in = FT(in)", FT_in);
// Center the DC point of the FT of the input.
double cDC_FT_In[inD][inD][2];
cyclicShiftComplex2dArray(FT_in, cDC_FT_In, inD/2, inD/2);
printComplex2dArray("\n\nCentered FT of input, cDC_FT_In = FT(in)", cDC_FT_In);
// Create the rotated Fourier Transform of the input.
double r90_FT_In[inD][inD][2];
for(int y3=0; y3<inD; y3++){
for(int x3=0; x3<inD; x3++){
r90_FT_In[y3][x3][0] = cDC_FT_In[x3][inD-1 - y3][0]; // Real compt
r90_FT_In[y3][x3][1] = cDC_FT_In[x3][inD-1 - y3][1]; // Imag compt
}//for(x2)
}//for(y2)
printComplex2dArray("\n\nRotated FT of input, r90_FT_In = R90(FT(in))", r90_FT_In);
// Recenter the DC point of the rotated FT, using a cyclic shift.
double cDC_r90_FT_In[inD][inD][2];
cyclicShiftComplex2dArray(r90_FT_In, cDC_r90_FT_In, 0, 3);
printComplex2dArray("\n\n(A) Recentered Rotated FT of input, cDC_r90_FT_In = cDC(r90(FT(in)))",
cDC_r90_FT_In);
// Create the Input Rotated 90deg CCW.
int r90_in[4][4];
for(int y4=0; y4<inD; y4++)
for(int x4=0; x4<inD; x4++)
r90_in[y4][x4] = in[x4][inD-1 - y4];
print2dArray("\n\nRotated input, r90_in = r90(in)", r90_in);
// Create the Fourier Transform of the rotated input.
double FT_r90_in[inD][inD][2];
for(int y5=0; y5<inD; y5++)
for(int x5=0; x5<inD; x5++){
FT_r90_in[y5][x5][0] = r90_in[y5][x5];
FT_r90_in[y5][x5][1] = 0;
}//for(x3)
FFT2D(FT_r90_in, inD, inD, 1);
printComplex2dArray("\n\nFT of rotated input, FT_r90_in = FT(r90(in))", FT_r90_in);
cyclicShiftComplex2dArray(FT_r90_in, cDC_r90_FT_In, inD/2, inD/2);
printComplex2dArray("\n\n(B) Centered FT of rotated input, cDC_r90_FT_In = cDC(FT(r90(in)))", cDC_r90_FT_In);
return 0;
}//main()
/* This computes an in-place complex-to-complex FFT
x and y are the real and imaginary arrays of 2^m points.
dir = 1 gives forward transform dir = -1 gives reverse transform. */
int FFT(int dir, int nn, double *x, double *y){
long n, m, i, i1, j, k, i2, l, l1, l2;
double c1, c2, tx, ty, t1, t2, u1, u2, z;
// Calculate m where nn = 2^m
for(n = 1, m = 0; n < nn; n *= 2) m++;
// Do the bit reversal.
i2 = nn >> 1; j = 0;
for (i=0; i<nn-1; i++) {
if (i < j) {
tx = x[i]; ty = y[i];
x[i] = x[j]; y[i] = y[j];
x[j] = tx; y[j] = ty;
}//if()
k = i2;
while (k <= j) { j -= k; k >>= 1; }
j += k;
}//for(i)
// Compute the FFT.
c1 = -1.0; c2 = 0.0; l2 = 1;
for (l=0; l<m; l++) {
l1 = l2; l2 <<= 1; u1 = 1.0; u2 = 0.0;
for (j=0; j<l1; j++) {
for (i=j; i<nn; i+=l2) {
i1 = i + l1;
t1 = u1 * x[i1] - u2 * y[i1];
t2 = u1 * y[i1] + u2 * x[i1];
x[i1] = x[i] - t1; y[i1] = y[i] - t2;
x[i] += t1; y[i] += t2;
}//for(i)
z = u1*c1 - u2*c2; u2 = u1*c2 + u2*c1; u1 = z;
}//for(j)
c2 = (double)sqrt((1.0 - c1) / 2.0);
if (dir == 1)
c2 = -c2;
c1 = (double)sqrt((1.0 + c1) / 2.0);
}//for(l)
return 1;
}//FFT()
int FFT2D(double c[4][4][2],int inW,int inH,int dir) {
int i,j;
double *real,*imag;
/* Transform the rows */
real = new double[inW]; imag = new double[inW];
for (j=0; j<inH; j++) {
for (i=0; i<inW; i++) {
real[i] = c[i][j][0];
imag[i] = c[i][j][1];
}
FFT(dir, inW, real, imag);
for (i=0; i<inW; i++) {
c[i][j][0] = real[i];
c[i][j][1] = imag[i];
}
}
delete []real; delete []imag;
/* Transform the columns */
real = new double[inH]; imag = new double[inH];
for (i=0; i<inW; i++) {
for (j=0; j<inH; j++) {
real[j] = c[i][j][0];
imag[j] = c[i][j][1];
}
FFT(dir, inH, real, imag);
for (j=0; j<inH; j++) {
c[i][j][0] = real[j];
c[i][j][1] = imag[j];
}
}
free(real);
free(imag);
return 1;
}//FFT2D()
// Prints the title & 2d array to the console & debugger output
void print2dArray(char str[100], int array[inD][inD]){
cout << str; // Print the title
//OutputDebugStringA(str); // Uncomment to print to debug output
char buffer[100];
for(int y=0; y<inD; y++){ // Print the array
cout << "\n";
//OutputDebugStringA("\n "); // Uncomment to print to debug output
for(int x=0; x<inD; x++){
cout << array[y][x] << " ";
sprintf_s(buffer, "%i ", array[y][x]);
//OutputDebugStringA(buffer); // Uncomment to print to debug output
}//for(x)
}//for(y)
}//print2dArray()
// Prints the title & 3d array to the console & debugger output
void printComplex2dArray(char str[100], double array[inD][inD][2]){
cout << str; // Print the title
//OutputDebugStringA(str); // Uncomment to print to debug output
char buffer[100];
for(int y=0; y<inD; y++){ // Print the array
cout << "\n";
//OutputDebugStringA("\n "); // Uncomment to print to debug output
for(int x=0; x<inD; x++){
cout << (int)array[y][x][0]; cout << ",";
cout << (int)array[y][x][1]; cout << " ";
sprintf_s(buffer, "%i,", (int)array[y][x][0]);
//OutputDebugStringA(buffer); // Uncomment to print to debug output
sprintf_s(buffer, "%i ", (int)array[y][x][1]);
//OutputDebugStringA(buffer); // Uncomment to print to debug output
}//for(x)
}//for(y)
}//printComplex2dArray()
// Cyclically shifts complex 2d array inRA by xOff & yOff to yield outRA.
void cyclicShiftComplex2dArray(double inRA[inD][inD][2], double outRA[inD][inD][2],
int xOff, int yOff){
for(int yOut=0, yIn=yOff; yOut < inD; yOut++, yIn++){
yIn = yIn%inD;
for(int xOut=0, xIn=xOff; xOut < inD; xOut++, xIn++){
xIn = xIn%inD;
outRA[yOut][xOut][0] = inRA[yIn][xIn][0];
outRA[yOut][xOut][1] = inRA[yIn][xIn][1];
}//for(xOut)
}//for(yOut)
}//cyclicShiftComplex2dArray()