Lacking documentation that I can find, I have been trying to figure out the relationship between the centered and uncentered Image.FFT's.
I had assumed that they were related by a simple shift of inputs/outputs between corner and center. But this does not seem to be the case. By trial and error I found that, at least with the shift as I envision it, an extra sign flip is needed, where the sign flip is row/col index mod 2 related. This script shows this flip, which is required to make the outputs identical.
Is this expected behavior? Maybe I am not doing the corner/center shift properly? Is there a simpler way to understand the centered/uncentered relationship?
Thanks,
Mike
#include <pjsr/ColorSpace.jsh>
#include <pjsr/SampleType.jsh>
function FFT(complexData, centered) {
var rows = complexData.real.rows;
var cols = complexData.real.cols;
var image = new Image(cols, rows, 1, ColorSpace_Gray, 32, SampleType_Complex);
var c = new Complex;
for (var row = 0; row != rows; ++row) {
for (var col = 0; col != cols; ++col) {
c.real = complexData.real.at(row, col);
c.imag = complexData.imag.at(row, col);
image.setSample(c, col, row);
}
}
image.FFT(centered);
var newComplexData = {real: new Matrix(rows, cols), imag: new Matrix(rows, cols)};
var c = new Complex;
for (var row = 0; row != rows; ++row) {
for (var col = 0; col != cols; ++col) {
c = image.sample(col, row);
newComplexData.real.at(row, col, c.real);
newComplexData.imag.at(row, col, c.imag);
}
}
image.free();
return newComplexData;
}
function FFTShiftReal(realData) {
var rows = realData.rows;
var cols = realData.cols;
var rows2 = rows >> 1;
var cols2 = cols >> 1;
var newRealData = new Matrix(rows, cols);
for (var row = 0; row != rows; ++row) {
for (var col = 0; col != cols; ++col) {
newRealData.at(row, col, realData.at((row + rows2) % rows, (col + cols2) % cols));
}
}
return newRealData;
}
function FFTShiftComplex(complexData) {
return {real: FFTShiftReal(complexData.real), imag: FFTShiftReal(complexData.imag)};
}
function FFTFlipReal(realData) {
var rows = realData.rows;
var cols = realData.cols;
var rows2 = rows >> 1;
var cols2 = cols >> 1;
var newRealData = new Matrix(rows, cols);
for (var row = 0; row != rows; ++row) {
for (var col = 0; col != cols; ++col) {
newRealData.at(row, col, (row % 2) == (col % 2) ? -realData.at(row, col) : realData.at(row, col));
}
}
return newRealData;
}
function FFTFlipComplex(complexData) {
return {real: FFTFlipReal(complexData.real), imag: FFTFlipReal(complexData.imag)};
}
function maximumAbsoluteDifference(complexData1, complexData2) {
function square(x) {
return x * x;
}
var rows = complexData1.real.rows;
var cols = complexData1.real.rows;
var error = 0;
for (var row = 0; row != rows; ++row) {
for (var col = 0; col != cols; ++col) {
error = Math.max(error, Math.sqrt(
square(complexData1.real.at(row, col) - complexData2.real.at(row, col)) +
square(complexData1.imag.at(row, col) - complexData2.imag.at(row, col))
));
}
}
return error;
}
function randomRealData(rows, cols) {
var newRealData = new Matrix(rows, cols);
for (var row = 0; row != rows; ++row) {
for (var col = 0; col != cols; ++col) {
newRealData.at(row, col, Math.random());
}
}
return newRealData;
}
function main() {
for (var size = 1; size <= 1024; size *= 2) {
var complexData = {real: randomRealData(size, size), imag: randomRealData(size, size)};
//console.writeln("complexData.real: ", complexData.real.toArray());
//console.writeln("complexData.imag: ", complexData.imag.toArray());
var centeredFFT = FFT(complexData, true);
//console.writeln("centeredFFT.real: ", centeredFFT.real.toArray());
//console.writeln("centeredFFT.imag: ", centeredFFT.imag.toArray());
var shiftComplexData = FFTShiftComplex(complexData);
//console.writeln("shiftComplexData.real: ", shiftComplexData.real.toArray());
//console.writeln("shiftComplexData.imag: ", shiftComplexData.imag.toArray());
var shiftUncenteredFFT = FFT(shiftComplexData, false);
//console.writeln("shiftUncenteredFFT.real: ", shiftUncenteredFFT.real.toArray());
//console.writeln("shiftUncenteredFFT.imag: ", shiftUncenteredFFT.imag.toArray());
var uncenteredFFT = FFTShiftComplex(shiftUncenteredFFT);
//console.writeln("uncenteredFFT.real: ", uncenteredFFT.real.toArray());
//console.writeln("uncenteredFFT.imag: ", uncenteredFFT.imag.toArray());
var flipUncenteredFFT = FFTFlipComplex(uncenteredFFT);
//console.writeln("flipUncenteredFFT.real: ", flipUncenteredFFT.real.toArray());
//console.writeln("flipUncenteredFFT.imag: ", flipUncenteredFFT.imag.toArray());
var error = maximumAbsoluteDifference(centeredFFT, flipUncenteredFFT);
console.writeln("size: ", size, ", error: ", error);
}
}
main();
