17 ms·
Why can’t you design noise in frequency space?
- wg-throw-away 5y agoFor what it's worth, in digital communications, OFDM you could say "is designed in frequency space" and then passed through a FFT/IFFT and the output time-domain signal is what is sent over the air.
- LargoLasskhyfv 5y agoI wonder if he ever heard of the (·) https://en.wikipedia.org/wiki/ANS_synthesizer https://en.wikipedia.org/wiki/ANS_synthesizer and its modern implementation (:) https://warmplace.ru/soft/ans/ https://warmplace.ru/soft/ans/ ?
- deleted 5y ago[deleted]
- im3w1l 5y agoFourier theory is built on the assumption of everything being linear, and I suspect it can be hard to fit the constraint of 0 <= v <= 1 into that framework. In audio they solve this by having headroom (not applicable here) or using dynamic range compression (might work), but that will change the frequencies a little bit. Histogram equalization could be something to try. It forces the values to be uniformly 0 to 1. This could also solve the issue of > the problem with the IDFT method is though… you get gaussian distributed values, not uniform, and the noise seems to be lower quality as well. If these issues could be solved, or if this noise has value as is, I think that’d be a real interesting and useful result
- cjfd 5y agoI studied physics when I was young and my first reaction was 'sure you can!' and 'I have done that kind of stuff some 20 years ago or so'. What looks to be the problem is that he wants a rather non-physical kind of noise. The noise is supposed to be between 0 and 1 distributed uniformly. Now, that really is not the kind of noise one expects or wants in physics in most cases. The values that are distributed in a gaussian way would seem to be much more sensible. O well, I suppose the thing he calls 'blue noise texture' really cannot be generated very well in frequency space....
- whatshisface 5y agoIf you do the phases wrong you will get pulses instead of noise. Obviously if you do the phases right you can do anything, because the Fourier transform is one to one.
- deleted 5y ago[deleted]
- ssfrr 5y agoSure for any specific signal x you can craft the corresponding signal X so that ifft(X)==x, but the idea here is to generate a random signal with certain properties (blue spectrum and uniformly-distributed time-domain values). This is the tricky bit.
- a9h74j 5y agoEven physical noise? I don't imagine you could create a random walk in frequency space, say if the steps taken had to be integer-valued.
- stochtastic 5y agoThere is an interesting relationship between frequency domain filtering and the distributional properties of a signal, which I believe the author encounters: So interestingly, the IDFT method makes noise that is gaussian distributed. This kind of makes sense because we are filling out frequencies as uniform random white noise, which are turning into uniform random white noise sinusoids that are being summed together, which will tend towards a gaussian distribution as you sum up more of them. In contrast, the void and cluster method makes uniform distributed values which are perfectly uniform. One of the papers I'm most proud of co-authoring explains some aspects of this phenomenon [0] through the use of higher order spectra (the bispectrum, trispectrum, etc...) and how the geometry of frequency-domain filters affects skewness and excess kurtosis. [0] https://s3-us-west-2.amazonaws.com/arpdfs/Publications/Proistosescu_2016.pdf https://s3-us-west-2.amazonaws.com/arpdfs/Publications/Prois...
- a9h74j 5y agoFWIW, in looking up higher-order spectra, I see that work at LIGO has resulted in an interesting toolkit and documentation: https://labcit.ligo.caltech.edu/~rana/mat/HOSA/HOSA.PDF https://labcit.ligo.caltech.edu/~rana/mat/HOSA/HOSA.PDF
- anotheryou 5y agoTrevor Wishart works in the spectral space quite a bit when editing. One of his sound art pieces (I'm sure many cuts and similarity matching were done automatic and spectrum based): https://youtu.be/DWkxPP6Ndng?t=473 https://youtu.be/DWkxPP6Ndng?t=473 Showcasing the sounds of his software: https://youtu.be/f9swWsGgLB4 https://youtu.be/f9swWsGgLB4 The "Composers Desktop Project" also exists standalone with a paid front-end I think. Not sure anyone but him can use it well though :). It also has a loooong history (starting 1986) https://www.composersdesktop.com/history.html https://www.composersdesktop.com/history.html edit: his UI, sound loom, in "use" (at least you see how transforming to spectral space and re-synthesis are a thing, not much else though :).) : https://youtu.be/LypM6-WDjL8?t=620 https://youtu.be/LypM6-WDjL8?t=620
- ta988 5y agoThat was a great discovery, thanks!
- Lichtso 5y agoTwo things which seem to be overlooked here: - When working with frequencies alone and ignoring the phases you kill half of the entropy of the signal. - Further more, when only the positive half of the frequencies is used and the negative half is mirrored with the complex conjugate, you kill half of the remaining entropy of the signal.
- sdenton4 5y agoTo add a DIFFERENT point on handling phase: Overlap-add STFT actually has phase dependencies between adjacent patches. So generating independent random phase in frequency space tends to produce incompatible phase in adjacent patches. In audio the audio domain, this leads to audible distortion. What's (often) used in the audio domain is Griffin-Lim, in which you apply the ISTFT and STFT repeatedly to 'smooth out' the phase inconsistencies. It typically takes a long time to converge and is still not quite right. The main alternatives for audio are the new neural vocoders. But they are expensive to train, and it's not terribly clear to me that it's any better than using an existing blue noise algorithm for this specific problem.
- anon_123g987 5y agoYour first point is spot on, but the second is not: for the signal to be real valued in the time domain, the negative and positive frequencies have to be redundant in the complex valued frequency domain. Edited to add a link to a simple Matlab solution of this problem: https://www.mathworks.com/matlabcentral/fileexchange/42919-pink-red-blue-and-violet-noise-generation-with-matlab https://www.mathworks.com/matlabcentral/fileexchange/42919-p... (click on the Functions tab to see the source code)
- omegalulw 5y agoI'm confused about the first point. Is it simply restating that Fourier coefficients are complex numbers?
- anon_123g987 5y agoBasically yes, but his statement is mixing up things a bit. The Discrete Fourier Transform transforms a complex vector of length N to another complex vector of length N. In the latter, each of the N elements corresponds to a frequency "bin" and, like complex numbers in general, can be represented either by a real and an imaginary part (like Cartesian coordinates), or by a phase (==atan(Im/Re)) and a magnitude (==sqrt(Re^2+Im^2)) (like polar coordinates). Obviously, whichever you choose, you need both components for unambiguous representation.
- ajot 5y agoWhat are the use cases of generating different kind of noises (e.g. white, blue and red)? I've only heard about them as background noises to fall asleep or focus while working/studying. Is there something ininformation or signal theory that benefits from creating truly random (or random but with some structure to it like blue noise not having lower frequencies) noise? As a chemist, I always model real-world noise with a gaussian distribution, so I don't really get where this could br used.
- dnautics 5y agoChemist here too but my ex was an sound consultant for an architectural firm. Iirc, different kinds of noises essentially are defined by the average amplitude (energy) vs frequency function of the rng. For architects, it can be important to model noise to ensure your structure complies with for example OSHA regulations. There can be code regulations too if you're in an urban place and say putting residential on top of street level commercial spaces, especially bars that might be open late. Finally, for gathering/events spaces you want to have a situation where a PA/presentation system doesn't have to work hard to go over conversation noise. The energy profiles for all of these scenarios is empirically determined and "well known" in the community. The ex helped model the "death star" auditorium space at the academy of motion picture arts and sciences in LA. IIRC it sounds really aquarium-ey during normal times and during events they roll out strategically placed dampeners.
- mzs 5y agoblue noise dither: http://www.imaging.org/site/PDFS/Papers/1999/RP-0-93/1786.pdf http://www.imaging.org/site/PDFS/Papers/1999/RP-0-93/1786.pd...
- the__alchemist 5y agoI'm using pink noise in an audiogram, to determine if users can hear sounds with it as background.
- iamwil 5y agoBlue noise is useful in games for generating more natural looking scenes. Here's an example of how to algorithmically place grass in the game "The Witness". https://youtu.be/Ge3aKEmZcqY?t=965 https://youtu.be/Ge3aKEmZcqY?t=965 So if you use white noise, it looks unnaturally clustered with patches. This is the part that discusses the noise. https://youtu.be/Ge3aKEmZcqY?t=1385 https://youtu.be/Ge3aKEmZcqY?t=1385
- goblin89 5y agoMetaSynth is a pretty cool riff on a visual frequency-based DAW. (Paid, macOS only.)
- cozzyd 5y agoNo time to play with this at the moment but I suspect the problem is that the author didn't try generating the real and imaginary parts. You can't treat the magnitude the same way you treat amplitudes. Also I don't see if the DC and Nyquist terms are forced to be real (otherwise the IFT won't be real)?
- madengr 5y ago
- mistercow 5y ago> First we make N complex values from polar coordinates that have a random angle 0 to 2pi and a random radius from 0 to 1. This is what jumped out to me as suspicious. This looks just like a naive (and wrong) algorithm for generating random points in a circle. The simplest correct way to do this in the circle case is rejection sampling. In this context, that would mean: generate a random real and imaginary part to get z, and retry until |z| ≤ 1.
- midjji 5y agoThen simplest way to do so is to sample a normal distribution twice and normalize the length. Its significantly faster too.
- ssfrr 5y agoThe goal is not well-defined here. If the goal is to generate uniformly-distributed points in a circle then this algorithm is wrong, but it’s not clear that’s actually what they want. Generating a spectrum with a given magnitude distribution and uniform phase distribution is pretty common (at least in audio).
- enriquto 5y agoNo need for gradient descent or stuff. For these simple disributions you can design a target histogram and a target spectral decay and sample it.
- ssfrr 5y agoCan you clarify? It’s not clear to me how to target a particular distribution in time and frequency domain simultaneously.
- enriquto 5y agoThink about the direct problem: you start with white noise with a distribution g such that you can compute its power spectrum (e.g. if g is Gaussian) , and then convolve it with a positive kernel k. You can write down explicitly the histogram and the power spectrum of the result, in terms of g and k. Now work backwards from it. I can find a reference if you need it.
- ssfrr 5y agoBut after you convolve in the time domain it will change the distribution, right? Every point in the convolved signal will be the sum of a bunch of points in the original signal multiplied by the kernel, which would make their distributions more gaussian, right?
- nobodywillobsrv 5y agoDidn't read in detail and had a hard time understanding what their goal was but there are important things to understand regarding Fourier features (eigenfunctions, sin, cos, etc) and the Gaussian Kernel Start with something like this https://arxiv.org/pdf/1611.06740.pdf https://arxiv.org/pdf/1611.06740.pdf and reading links might help.
- onos 5y agoNewbie here trying to follow. The prior post I link below suggests that what’s going on here is we are trying to find good points to sample an image. A challenge here is that the algorithms to generate the blue noise distributed sample points are slow. This motivates using an FT signal constructed by hand and then inverting this somehow to get sample points more quickly. But… he’s finding that the result doesn’t place sample points uniformly throughout an image. Is that right? How does one construct discrete sample points from the inverted FT? https://blog.demofox.org/2017/10/20/generating-blue-noise-sample-points-with-mitchells-best-candidate-algorithm/ https://blog.demofox.org/2017/10/20/generating-blue-noise-sa...
- dahart 5y agoYep, you’ve got the right idea - the implied goal of trying to use the FT is to make blue noise texture generation faster, but it doesn’t seem to work using the DFT. (Or maybe there are unmet constraints on how you need to generate the frequency space texture.) > How does one construct discrete sample points from the inverted FT? This is a good question! So one example the author has (in a different post) is how to use blue noise textures for ray traced shadows. The idea is at every pixel of your output image, trace a ray into the scene, then when it hits something, trace a ray toward the light to see if the pixel is lit or shadowed. Normally, you’d use a random number generator to pick a random sample on the hemisphere of the surface the first ray hits, and shoot a new ray in this random direction. You can instead grab your two random values from the red and green channels of a blue noise texture. The blue noise texture could have the same size as your desired output image, and you would use the same pixel id in the blue noise texture as the pixel id of your output image. That example is pretty easy, but I found out it can be surprisingly tricky to use blue noise textures in other ways, there are a limited number of ways you can use a blue noise texture effectively, and it’s not always an easy drop-in replacement for a white noise random number generator. It’s much harder to use blue noise for multiple samples per pixel, for example. It’s harder to create a sequence of blue-distributed random numbers for use in a single integral. Another way to say that is that it would be difficult to generate your camera rays using blue noise.
- onos 5y ago
- henrikf 5y agoAuthor seems to be looking to generate a blue noise texture for image sampling. I'm not familiar with them but it seems to be blue noise which also has uniformly distributed values in time domain. Generating white noise in frequency domain and multiplying with a frequency shape mask can generate noise with any frequency distribution, but it does not fill the uniform distributed values in time-domain requirement. If there are no other requirements than the frequency spectrum then generating the noise in frequency domain works fine.
- ssfrr 5y agoYeah I think that uniform time(space)—domain distribution constraint is the one that the author identifies as the main problem here.
- amelius 5y agoIf you view the IFFT as a random number generator, how do you change the seed of it? I.e., white noise has a flat spectrum. So if you take a flat spectrum back to noise (using IFFT), what determines the seed of this process?
- nitrogen 5y agoIt's the seed of whatever source you use to randomize the phases.
- ssfrr 5y agoI wonder if there’s some iterative algorithm that would work here. When synthesizing audio from the short-time Fourier transform (STFT) sometimes you have unknown or noisy phase, and there’s an algorithm called Griffey-Lim that’s pretty common for finding the corresponding time-domain signal. You start in the STFT-domain and continually swap between time and STFT domains, each time fixing the STFT magnitudes. Eventually the phase tends to converge (but not sure if that’s guaranteed). Maybe there’s something similar here where you keep swapping back and forth while applying the blue spectrum and uniform sample histogram constraints (or partially applying them in a gradient-descent fashion). (Side note that there are other/better phase estimation algos for this problem, but Griffin-Lim is simple and relatively common)
- nitrogen 5y agoCan you link to a paper, summary, or textbook with this algorithm? I'd like to learn more, but searching for "Griffey-Lim" only returns this HN thread, and a bunch of very unrelated news items about money laundering.
- raphlinus 5y agoPretty sure it's this paper: https://ieeexplore.ieee.org/document/1164317 https://ieeexplore.ieee.org/document/1164317 That is Griffin-Lim, which matches the second mention but not the first. It's a fairly well known algorithm for reconstructing speech from spectrum, though I believe is largely superseded these days by vocoders based on neural techniques. (Actually I just checked and the original Tacotron paper cites Griffin-Lim; I do think newer neural TTS approaches have gone beyond it, however)
- nyanpasu64 5y agoSo frequency-domain blue noise has a higher crest factor than void-and-cluster? Also I'm interested to see how closely the mean intensity (at each radius) of void-and-cluster blue noise actually matches a sinc or sinc-squared subtracted from a constant.
- anon_123g987 5y agoAlthough the author couldn't do it, the problem is obviously solvable, and not even that difficult. Theory: https://rjav.sra.ro/index.php/rjav/article/view/40/29 https://rjav.sra.ro/index.php/rjav/article/view/40/29 [PDF] Matlab code (under the Functions tab): https://www.mathworks.com/matlabcentral/fileexchange/42919-pink-red-blue-and-violet-noise-generation-with-matlab https://www.mathworks.com/matlabcentral/fileexchange/42919-p... This is for the 1D case, but since the Fourier transform is separable, it works identically in 2 (and any N) dimensions by performing the transform sequentially in every dimensions.
- lapinot 5y agoYou're pointing to something saying that power-law distributed noise can be generated by filtering white noise (and doing the filtering in the frequency domain, but that's really an implementation detail). OP actually wants to only do the inverse transform, generating the noise in the frequency domain already.
- anon_123g987 5y agoThe Fourier transform of white noise is white noise, so that doesn't matter.
- ssfrr 5y agoDoes that approach end up with a uniform distribution if values in the time domain? That seemed like the difficult part here.
- RicoElectrico 5y agoI thought this was straightforward like in the audio domain? [1] Now, not all noises of the same amplitude spectrum are created equal. For instance LFSR sequences are only ±1 yet they have a white spectrum. The difference lies in phase. I wonder if generating random phases, then putting it through an optimizer to find lowest crest factor could work. Oh, and can someone chime in whether void-and-cluster masks guarantee that all values are covered, just like in Bayer mask? [1] https://zynaddsubfx.sourceforge.io/doc/PADsynth/PADsynth.htm https://zynaddsubfx.sourceforge.io/doc/PADsynth/PADsynth.htm