12 ms·

Generating Coherent Noise Using Fourier Transforms

61 points by achat 5y ago

The_Amp_Walrus 5y ago
What's a situation where noise like this is useful? In any case it's very pretty and nice and I enjoyed the article.
- nightcracker 5y ago
  Game textures often use this kind of noise for terrain heights, smoke, etc. A similar kind of noise known as blue noise can be generated by taking the Fourier transform and not applying a 1/f filter but a high-pass filter instead. You end up with noise that only has high frequencies in it, and not low frequencies. Thus the noise does not have large-scale features, which is ideal for use in dithering. Blue noise (and its DFT) look like this: https://demofox2.files.wordpress.com/2018/08/vc.png https://demofox2.files.wordpress.com/2018/08/vc.png And an example of dithering with white and blue noise: https://demofox2.files.wordpress.com/2019/06/randomvsblue.jpg https://demofox2.files.wordpress.com/2019/06/randomvsblue.jp...
  - littlestymaar 5y ago
    Interestingly enough, in the white noise vs blue noise dithering, I appreciate the white noise one (left) much more because the blue-noise one (right) looks blurry. I guess it depends a lot on the input though, a bit like how nearest-neighbor is a much better algorithm than bi-cubic to scale up pixel art while the result is horrible if you use it on a real-world picture.
    - alejohausner 5y ago
      I see them as both blurry, but the but the one on the left is more grainy.
- cshimmin 5y ago
  There are scientific applications for this kind of procedure. If an experiment has a noise source with a known frequency distribution, you can simulate the experiment by generating many thousands of realizations of noise superimposed with your (expected) signal. The variance in your measurement introduced by the noise can be used to assess the systematic uncertainty of the experiment. For example, in ground-based experiments that measure the cosmic microwave background radiation, there is a substantial foreground noise from the atmosphere that can be modeled as a 1/f distribution. And actually the observations themselves are subject to a random variance (see cosmic variance) due to the fact that we get to observe the early universe from only one point in space. So you can use a similar trick to sample many random realizations of the CMB for given physical constants, and decide if our one-off observation is compatible with the theory.
- pixel_fcker 5y ago
  You’d never do a DFT for generating a fBM, but the same technique using a different noise spectrum is how we’ve been generating ocean waves in the VFX industry since forever: https://people.cs.clemson.edu/~jtessen/reports/papers_files/coursenotes2004.pdf https://people.cs.clemson.edu/~jtessen/reports/papers_files/...
praptak 5y ago
Quote the article: 1. Generate some White Noise. 2. Perform a Fourier transform on the White Noise. Are the two separate steps necessary? It should be possible to directly generate the Fourier Transform of the white noise, rather than applying FFT to the waveform, right?
- nightcracker 5y ago
  At least when using Gaussian white noise, the DFT of the noise is the same distribution with a smaller variance: https://dsp.stackexchange.com/questions/24170/what-are-the-statistics-of-the-discrete-fourier-transform-of-white-gaussian-nois https://dsp.stackexchange.com/questions/24170/what-are-the-s... I don't think the same neat result holds when you use uniform white noise, but I haven't done the math.
  - eutectic 5y ago
    The normal distribution is special in being closed under linear transformation.
- frumiousirc 5y ago
  3. apply filter 4. apply inverse FT It is equivalent to replace 1, 2 and 3 with a proper stochastic but direct sampling of the 1/f function to get the Fourier amplitudes and a uniform sampling for Fourier phase. This would save processing time by avoiding the calculation of one 2D FFT and the application of the filter (a 2D array multiplication).
  - TheOtherHobbes 5y ago
    Even simpler: create your desired amplitude spectrum to match your desired filtered noise profile. This is trivial for any noise spectrum with a simple linear filter - it's just a linear function with the desired slope. It's only slightly less trivial for more complex spectra. Randomise the phases. (i)FFT. Done.
    - 5y ago
contravariant 5y ago
Up to phase I think this is equivalent to just integrating the noise, so you should get some kind of Brownian function.
- dls2016 5y ago
  Yes integration is a 1/f Fourier multiplier. But if you want to do (1/f)^alpha then it's not so straightforward in the time domain.
  - abnry 5y ago
    In the theoretical PDEs world, non-integer alpha represents a fractional derivative.
    - dls2016 5y ago
      Word. I did my time in the Sobolev spaces.
  - wyager 5y ago
    > Yes integration is a 1/f Fourier multiplier. Can you explain this? I don’t see the connection. I can see how the zero-frequency value would be equal to the integral (well, the average). Edit: figured it out. Derivative operator multiplies each basis function by its index. D exp(inx) = inexp(inx). Apply the inverse operation (divide by index) to get the integral.
ginko 5y ago
Maybe I've been in computer graphics land for too long, but I'm somewhat surprized by the author's initial surprize. Isn't it obvious that you get a fractal surface if you sum up frequencies with 1/f amplitude?
- cycomanic 5y ago
  Nothing about computer graphics, I think everyone who has worked with signal processing would be surprised by the authors initial surprise (I was). The question is more what else would one expect?
  - SuchAnonMuchWow 5y ago
    And for people like me, unfamiliar with it but still knowing what a Fourier transform is, just reading the algorithm I really see no reasons why it particularly "shouldn't work", as the author said.
  - londons_explore 5y ago
    Indeed. I suspect perhaps the author is surprised because squinting/defocussing your eyes at the original noise doesn't much look like the final result. Thats because as well as removing the high frequency components (like squinting), this algorithm also is rescaling the amplitude.
virtualritz 5y ago
The oldest work I'm aware of that uses this approach for producing fractals (clouds in this case) is Gardner's[1], from 1985. I dunno if Gardner's earlier paper from 1979, "Computer-generated texturing to model real-world features", contains the idea already because I could never find a digital version of that one. [1] https://www.cs.drexel.edu/~david/Classes/Papers/p297-gardner.pdf https://www.cs.drexel.edu/~david/Classes/Papers/p297-gardner...
deleted 5y ago
[deleted]
SassyGrapefruit 5y ago
It turns out when you can approximate any function. There is a lot you can do? Who da thunk?
munificent 5y ago
> The only benefit this has over its contemporaries is that it is tileable. Although, it does repeat making this benefit useless considering that Perlin and Simplex noise are non-repeating and infinite. Perlin and Simplex are also easily tileable too. Just make your hash function periodic and the resulting noise while tile at the same period. This is a neat article and a neat technique, but probably not super practical. If you know how synthesizers (like the musical instruments) work, then you can think of Perlin noise as additive synthesize and the article here as subtractive synthesis. Taking the FFT, modifying frequency amplitudes, and then taking the IFFT is one way to implement a filter. A more direct way is to filter in the time (well, space here) domain using something like a FIR or IIR. In spatial terms, that means applying a convolution filter, which is exactly how most blurring algorithms in programs like Photoshop work. So, another way to look at this, is that you can generate pretty terrains by taking white noise and blurring it with the right convolution kernel.
- blacksmythe 5y ago
  >> Taking the FFT, modifying frequency amplitudes Modifying amplitude and phase. In the time domain you can't modify frequency amplitude without modifying the phase. If you modify just the FFT amplitude, you can end up with non-causal impulse responses.
farazzshaikh 5y ago
Hey guys Author here. Thank you all so much for the reads and suggestions. Just some context because I think the article comes across as me being ignorant of a lot of stuff 1. I am a noob at math and the original paper really did surprise me because I find it weird and interesting that you can morph white noise to be coherent. I am sure to the people who know what they’re doing it seems obvious but it wasn’t to me. 2. The article is simply an explanation of what I think is the reason behind the mechanism as explained in the paper. Of course now I know with the help of all of you that there are better ways of doing things and most of the steps are redundant. I’ll make a revised post with the improvements sometime in the future. Thank you again :)
- frumiousirc 5y ago
  One thing that gave me pause is calling this "coherent noise". I'm used to "coherency" being a property between two different "channels" or sources of signal. Here, I guess it is being used to mean coherency between the X and Y dimensions. Is that right? If so, I think this is not truly coherent noise but rather mimicry. We see large "patches" in X-Y because the 1/f increases the relative power in lower frequency. It is thus a "natural accident" to have low frequency in X and Y form some patches somewhere. But, it's not a coherent effect. I'd be curious to learn if I'm misunderstanding the use of the term.

61 points by achat 5y ago

The_Amp_Walrus 5y ago

What's a situation where noise like this is useful? In any case it's very pretty and nice and I enjoyed the article.

nightcracker 5y ago
Game textures often use this kind of noise for terrain heights, smoke, etc. A similar kind of noise known as blue noise can be generated by taking the Fourier transform and not applying a 1/f filter but a high-pass filter instead. You end up with noise that only has high frequencies in it, and not low frequencies. Thus the noise does not have large-scale features, which is ideal for use in dithering. Blue noise (and its DFT) look like this: https://demofox2.files.wordpress.com/2018/08/vc.png https://demofox2.files.wordpress.com/2018/08/vc.png And an example of dithering with white and blue noise: https://demofox2.files.wordpress.com/2019/06/randomvsblue.jpg https://demofox2.files.wordpress.com/2019/06/randomvsblue.jp...
- littlestymaar 5y ago
  Interestingly enough, in the white noise vs blue noise dithering, I appreciate the white noise one (left) much more because the blue-noise one (right) looks blurry. I guess it depends a lot on the input though, a bit like how nearest-neighbor is a much better algorithm than bi-cubic to scale up pixel art while the result is horrible if you use it on a real-world picture.
  - alejohausner 5y ago
    I see them as both blurry, but the but the one on the left is more grainy.
cshimmin 5y ago
There are scientific applications for this kind of procedure. If an experiment has a noise source with a known frequency distribution, you can simulate the experiment by generating many thousands of realizations of noise superimposed with your (expected) signal. The variance in your measurement introduced by the noise can be used to assess the systematic uncertainty of the experiment. For example, in ground-based experiments that measure the cosmic microwave background radiation, there is a substantial foreground noise from the atmosphere that can be modeled as a 1/f distribution. And actually the observations themselves are subject to a random variance (see cosmic variance) due to the fact that we get to observe the early universe from only one point in space. So you can use a similar trick to sample many random realizations of the CMB for given physical constants, and decide if our one-off observation is compatible with the theory.
pixel_fcker 5y ago
You’d never do a DFT for generating a fBM, but the same technique using a different noise spectrum is how we’ve been generating ocean waves in the VFX industry since forever: https://people.cs.clemson.edu/~jtessen/reports/papers_files/coursenotes2004.pdf https://people.cs.clemson.edu/~jtessen/reports/papers_files/...

praptak 5y ago

Quote the article: 1. Generate some White Noise. 2. Perform a Fourier transform on the White Noise. Are the two separate steps necessary? It should be possible to directly generate the Fourier Transform of the white noise, rather than applying FFT to the waveform, right?

nightcracker 5y ago
At least when using Gaussian white noise, the DFT of the noise is the same distribution with a smaller variance: https://dsp.stackexchange.com/questions/24170/what-are-the-statistics-of-the-discrete-fourier-transform-of-white-gaussian-nois https://dsp.stackexchange.com/questions/24170/what-are-the-s... I don't think the same neat result holds when you use uniform white noise, but I haven't done the math.
- eutectic 5y ago
  The normal distribution is special in being closed under linear transformation.
frumiousirc 5y ago
3. apply filter 4. apply inverse FT It is equivalent to replace 1, 2 and 3 with a proper stochastic but direct sampling of the 1/f function to get the Fourier amplitudes and a uniform sampling for Fourier phase. This would save processing time by avoiding the calculation of one 2D FFT and the application of the filter (a 2D array multiplication).
- TheOtherHobbes 5y ago
  Even simpler: create your desired amplitude spectrum to match your desired filtered noise profile. This is trivial for any noise spectrum with a simple linear filter - it's just a linear function with the desired slope. It's only slightly less trivial for more complex spectra. Randomise the phases. (i)FFT. Done.
  - 5y ago

contravariant 5y ago

Up to phase I think this is equivalent to just integrating the noise, so you should get some kind of Brownian function.

dls2016 5y ago
Yes integration is a 1/f Fourier multiplier. But if you want to do (1/f)^alpha then it's not so straightforward in the time domain.
- abnry 5y ago
  In the theoretical PDEs world, non-integer alpha represents a fractional derivative.
  - dls2016 5y ago
    Word. I did my time in the Sobolev spaces.
- wyager 5y ago
  > Yes integration is a 1/f Fourier multiplier. Can you explain this? I don’t see the connection. I can see how the zero-frequency value would be equal to the integral (well, the average). Edit: figured it out. Derivative operator multiplies each basis function by its index. D exp(inx) = inexp(inx). Apply the inverse operation (divide by index) to get the integral.

ginko 5y ago

Maybe I've been in computer graphics land for too long, but I'm somewhat surprized by the author's initial surprize. Isn't it obvious that you get a fractal surface if you sum up frequencies with 1/f amplitude?

cycomanic 5y ago
Nothing about computer graphics, I think everyone who has worked with signal processing would be surprised by the authors initial surprise (I was). The question is more what else would one expect?
- SuchAnonMuchWow 5y ago
  And for people like me, unfamiliar with it but still knowing what a Fourier transform is, just reading the algorithm I really see no reasons why it particularly "shouldn't work", as the author said.
- londons_explore 5y ago
  Indeed. I suspect perhaps the author is surprised because squinting/defocussing your eyes at the original noise doesn't much look like the final result. Thats because as well as removing the high frequency components (like squinting), this algorithm also is rescaling the amplitude.

virtualritz 5y ago

The oldest work I'm aware of that uses this approach for producing fractals (clouds in this case) is Gardner's[1], from 1985. I dunno if Gardner's earlier paper from 1979, "Computer-generated texturing to model real-world features", contains the idea already because I could never find a digital version of that one. [1] https://www.cs.drexel.edu/~david/Classes/Papers/p297-gardner.pdf https://www.cs.drexel.edu/~david/Classes/Papers/p297-gardner...

deleted 5y ago

[deleted]

SassyGrapefruit 5y ago

It turns out when you can approximate any function. There is a lot you can do? Who da thunk?

munificent 5y ago

> The only benefit this has over its contemporaries is that it is tileable. Although, it does repeat making this benefit useless considering that Perlin and Simplex noise are non-repeating and infinite. Perlin and Simplex are also easily tileable too. Just make your hash function periodic and the resulting noise while tile at the same period. This is a neat article and a neat technique, but probably not super practical. If you know how synthesizers (like the musical instruments) work, then you can think of Perlin noise as additive synthesize and the article here as subtractive synthesis. Taking the FFT, modifying frequency amplitudes, and then taking the IFFT is one way to implement a filter. A more direct way is to filter in the time (well, space here) domain using something like a FIR or IIR. In spatial terms, that means applying a convolution filter, which is exactly how most blurring algorithms in programs like Photoshop work. So, another way to look at this, is that you can generate pretty terrains by taking white noise and blurring it with the right convolution kernel.

blacksmythe 5y ago
>> Taking the FFT, modifying frequency amplitudes Modifying amplitude and phase. In the time domain you can't modify frequency amplitude without modifying the phase. If you modify just the FFT amplitude, you can end up with non-causal impulse responses.

farazzshaikh 5y ago

Hey guys Author here. Thank you all so much for the reads and suggestions. Just some context because I think the article comes across as me being ignorant of a lot of stuff 1. I am a noob at math and the original paper really did surprise me because I find it weird and interesting that you can morph white noise to be coherent. I am sure to the people who know what they’re doing it seems obvious but it wasn’t to me. 2. The article is simply an explanation of what I think is the reason behind the mechanism as explained in the paper. Of course now I know with the help of all of you that there are better ways of doing things and most of the steps are redundant. I’ll make a revised post with the improvements sometime in the future. Thank you again :)

frumiousirc 5y ago
One thing that gave me pause is calling this "coherent noise". I'm used to "coherency" being a property between two different "channels" or sources of signal. Here, I guess it is being used to mean coherency between the X and Y dimensions. Is that right? If so, I think this is not truly coherent noise but rather mimicry. We see large "patches" in X-Y because the 1/f increases the relative power in lower frequency. It is thus a "natural accident" to have low frequency in X and Y form some patches somewhere. But, it's not a coherent effect. I'd be curious to learn if I'm misunderstanding the use of the term.