英文:
What is wrong with this inverse FFT implementation
问题
以下是您要翻译的内容:
"I am using the following implementation of an inverse Fast Fourier transform (FFT) for images in which the image of size N by N is stored in a vector of length N x N (with N a square number). When I feed this implementation a matrix of zeros except two 1s, one a few rows above the center and symmetrically below the center, the inverse is correctly an image with vertical bands whose frequency matches the position of the 1s.
However, when the 1s are on the left and on the right of the center, I get horizontal bands, but they are not perfectly horizontal. They have a very small slope. When I do exactly the same in Mathematica with the build-in InverseFourier
function, the bands are very precisely horizontal.
Is there something wrong in the JavaScript implementation below? The relevant code is given below; a complete MWE is available at this JSFiddle
function invFFT_radix2(out, start, input, N, offset, s ) {
if (N === 1) {
out[start] = input[offset];
} else {
invFFT_radix2(out, start, input, N/2, offset, 2*s);
invFFT_radix2(out, start+N/2, input, N/2, offset+s, 2*s);
for (var k = 0; k < N/2; k++) {
var twiddle = cisExp(2*Math.PI*k/N);
var t = out[start+k];
out[start+k] = t.plus ( twiddle.times(out[start+k+N/2]) );
out[start+k+N/2] = t.minus( twiddle.times(out[start+k+N/2]) );
}
}
}
called with
```javascript
invFFT_radix2(out, 0, input, input.length, 0, 1 )
in which input
is the input vector, and out
contains the result. All the entries are Complex
numbers (as per this response) and the function cisExp
is defined as
function cisExp(x) { // e^ix = cos x + i*sin x
return new Complex(Math.cos(x), Math.sin(x));
}
As a comparision, this is the magnified top of the image with the JSFiddle
The JS image begins on the left with a white line which becomes black on the right.
请告诉我,您需要进一步的帮助或信息吗?
英文:
I am using the following implementation of an inverse Fast Fourier transform (FFT) for images in which the image of size N by N is stored in a vector of length N x N (with N a square number). When I feed this implementation a matrix of zeros except two 1s, one a few rows above the center and symmetrically below the center, the inverse is correctly an image with vertical bands whose frequency matches the position of the 1s.
However, when the 1s are on the left and on the right of the center, I get horizontal bands, but they are not perfectly horizontal. They have a very small slope. When I do exactly the same in Mathematica with the build-in InverseFourier
function, the bands are very precisely horizontal.
Is there something wrong in the JavaScript implementation below? The relevant code is given below; a complete MWE is available at this JSFiddle
function invFFT_radix2(out, start, input, N, offset, s ) {
if (N === 1) {
out[start] = input[offset];
} else {
invFFT_radix2(out, start, input, N/2, offset, 2*s);
invFFT_radix2(out, start+N/2, input, N/2, offset+s, 2*s);
for (var k = 0; k < N/2; k++) {
var twiddle = cisExp(2*Math.PI*k/N);
var t = out[start+k];
out[start+k] = t.plus ( twiddle.times(out[start+k+N/2]) );
out[start+k+N/2] = t.minus( twiddle.times(out[start+k+N/2]) );
}
}
}
called with
invFFT_radix2(out, 0, input, input.length, 0, 1 )
in which input
is the input vector, and out
contains the result. All the entries are Complex
numbers (as per this response) and the function cisExp
is defined as
function cisExp(x) { // e^ix = cos x + i*sin x
return new Complex(Math.cos(x), Math.sin(x));
}
As a comparision, this is the magnified top of the image with the JSFiddle
The JS image begins on the left with a white line which becomes black on the right.
答案1
得分: 1
A 2D [inverse] DFT is the 1D version on one axis then the other, so you could do, for example,
for (let i = 0; i < 2; i++) {
for (let y = 0; y < HEIGHT; y++) {
invFFT_radix2(out, y * WIDTH, ss, WIDTH, y * WIDTH, 1);
}
ss = out.slice();
transpose(ss);
}
where
const WIDTH = 256;
const HEIGHT = 256;
const swap = (arr, i, j) => {
const t = arr[i];
arr[i] = arr[j];
arr[j] = t;
};
const transpose = (ss) => {
for (let i = 1; i < HEIGHT; i++) {
for (let j = 0; j < i; j++) {
swap(ss, i * WIDTH + j, j * WIDTH + i);
}
}
};
英文:
A 2D [inverse] DFT is the 1D version on one axis then the other, so you could do, for example,
for (let i = 0; i < 2; i++) {
for (let y = 0; y < HEIGHT; y++) {
invFFT_radix2(out, y * WIDTH, ss, WIDTH, y * WIDTH, 1);
}
ss = out.slice();
transpose(ss);
}
where
const WIDTH = 256;
const HEIGHT = 256;
const swap = (arr, i, j) => {
const t = arr[i];
arr[i] = arr[j];
arr[j] = t;
};
const transpose = (ss) => {
for (let i = 1; i < HEIGHT; i++) {
for (let j = 0; j < i; j++) {
swap(ss, i * WIDTH + j, j * WIDTH + i);
}
}
};
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论