# 2D Fourier Transform invertibility [closed]

Edit: I found an error in my C++ code. -(rand()&1)) is either 0 or -1 rather than -1 or 1 as I intended. Changing this to (0.5-(rand()&1))*2 seems to solve the problem. Does anyone know why only zeroes and positive values in the power spectrum would cause peaks in the corners of the terrain?

For context, I'm working on a program that procedurally generates variable, tileable terrain with spectral synthesis, but I don't think I entirely understand the concept of the Fourier transform (I've taken calculus, but have been reading online about the transform).

I'm using Mathematica currently but I'm hoping to move into C++, which is enormously faster for the filtering. I came here since this seemed much more of a math problem than a programming one, but I'll post my code to help explain my algorithm:

f[d_] := (1/(1000 d + 1))^2.4 (* filtering function *)
r = 128; (* resolution *)
noise = Fourier@RandomComplex[{-1 - I, 1 + I}, {r, r}];
(* generates a 2d array of random complexes, then takes the Fourier transform *)
For[x = 1, x <= r, x++,
For[y = 1, y <= r, y++,
d = EuclideanDistance[{x, y}, {r/2 - .5, r/2 - .5}]/r;
(* calculates distance to center *)
noise[[x, y]] = f@d*noise[[x, y]];
(* applies filtering function to each point *)
]
]


This produces decent-looking terrain that is the goal of the algorithm. However, the filtering (inside the For loops) takes a long time (about 1 second for the above code for 128^2 points), while my C++ implementation of the filter takes under a second for the 512^2 terrain linked below.

Produced with ImageAdjust@Image@Log@Abs@noise:

http://i.stack.imgur.com/ip6bM.png

Produced with ReliefImage@Abs@InverseFourier@noise:

http://i.stack.imgur.com/9MKNV.png

Earlier I said I applied a low-pass filter to the power spectrum, and that was incorrect. I apply a filter to the white noise by attenuating the power spectrum in proportion to the distance to the center. This is implemented in Mathematica above by f[d] which represents the factor of attenuation as a function of distance from the center.

I'm happy with the results but not the execution speed. I've implemented the random complex generation and the filter in C++. The Fourier transform of white noise appears to be simply more white noise, so I figured I didn't need to compute the forward transform before filtering. Here is the relevant C++ code:

for(int i=0; i<RESOLUTION*RESOLUTION; i++){
int x = i/RESOLUTION;
int y = i%RESOLUTION;
double distance=sqrt(pow(((double)RESOLUTION/2-0.5-x),2)+pow((double)RESOLUTION/2-0.5-y,2))/(double)RESOLUTION;
double f = pow(DISTANCE_LIN*distance+1,-DISTANCE_EXP);
realnoise[i] = f * ((double)(rand()%RAND_MAX))/((double)RAND_MAX) * -(rand()&1));
imagnoise[i] = f * ((double)(rand()%RAND_MAX))/((double)RAND_MAX) * -(rand()&1));
// Random positive double                 // Random sign
}


Right now I just export the contents of realnoise and imagnoise to CSV files and import them into Mathematica for viewing (creating the noise variable with noise = realnoise + imagnoise*I;). The result contains oddities I can't seem to remove by filtering. Specifically, the four corners of the resultant terrain have very high values.

Produced with ReliefImage@Abs@InverseFourier@noise:

(not letting me do more than two hyperlinks) http:// i.stack.imgur.com/zx2YA.png

The power spectrum after importation from C++ contains zeroes, so I can't show a logarithmic power spectrum. Produced with ImageAdjust@Image@Abs@Noise:

http:// i.stack.imgur.com/Sit53.png

From what I know of the Fourier transform, the top left corner of the terrain represents the mean of all values of the power spectrum. I subtracted this mean from all filtered noise values before transforming (noise=noise-Mean@noise), and afterwards every leftmost pixel of the terrain was equal to zero. Nothing else was affected. I suppose it makes sense that only the "zero-frequency" points would be affected, but then why wasn't the top edge affected as well? What is causing the upwards slope around the corners? Is there something special about the Fourier transform of white noise versus regular white noise, or am I misunderstanding the invertibility of the transform?

-
I'd like to try to help you with this, but I'm finding it a bit difficult to follow your description of the problem. For a start, could you indicate more precisely what refers to what? (E.g. "the mean of all the values" -- which values? You "subtracted the mean from all filtered noise values before transforming" -- in which direction?) Also, the second image seems to show only black with a white smudge in the middle -- is this what it's supposed to show? If this really shows the power spectrum of the other image, perhaps you could colour it differently so the values can be distinguished? –  joriki Oct 24 '11 at 14:12
Also it might help if you tell us something about how you're doing the transform, so we can try to assess how likely the problem is to be in the software, your use of the software, your understanding of the transform or whatever. For instance, there could be problems with values automatically being reordered or not, with normalization, with arrangement of real and complex values in memory, etc. etc., almost none of which we can say anything useful about at the current level of detail of your question. –  joriki Oct 24 '11 at 14:13
You should try to understand/test all this concepts firts in 1D –  leonbloy Oct 24 '11 at 14:23
"it applies a low-pass filter to both the imaginary and real parts and takes the inverse Fourier " Sounds rather arbitrary to me (why apply a low pass filter in the transformed domain? are you sure you didn't misunderstand the algorithm?) –  leonbloy Oct 24 '11 at 14:34
To apply a low-pass filter in the "time" domain, is the same as multiplying in the frequency domain by almostr-rectangular-window. Dually, applying a low pass filter in the "frequency domain" (??) would amount to multiply in the "time" (here, the pixel) domain by a rectangular window. I doubt you want that. –  leonbloy Oct 24 '11 at 14:37