pure old-fashioned math and science

September 6, 2021 1:36 AM

In the process of producing his upcoming book Shift happens, Marcin Wichary (previously) discovers the power of inverse FFT as applied to halftone moiré. (via waxy; moiré previously.)
posted by progosk (24 comments total)

Oh my god, that was intensely satisfying. Seeing the word "Illinois" emerge from illegible dots? Magic. Good post!
posted by Made of Star Stuff at 4:40 AM on September 6, 2021 [2 favorites]

What sorcery is this, and what contract do I sign with whom to get it?
posted by otherchaz at 4:44 AM on September 6, 2021 [1 favorite]

What sorcery is this

Fiji.
posted by progosk at 5:27 AM on September 6, 2021 [3 favorites]

Amazing. Thanks for this.
posted by freakazoid at 5:34 AM on September 6, 2021

Amazing because you'd think that drawing over the FFT would destroy information, but that's the beauty of it, it does! It's destroying the information about the dots, which we don't care about, and preserving the information about the underlying pattern the dots represented, which we do care about.
posted by Mr.Encyclopedia at 5:49 AM on September 6, 2021 [1 favorite]

(I know we're not fans here, but, is he gonna get sued?)
posted by Reasonably Everything Happens at 6:01 AM on September 6, 2021

Fourier transforms are AWESOME.

3blue1brown does an excellent introduction into Fourier Transforms.

It's how, for example, modern spectrometers work. It used to be if we wanted to determine how matter absorbs different frequencies of light, lets say between 2500-25000 nanometers (in the infrared), we would do this:

take a polychromatic source of light
select 2500nm wavelength (using a prism or diffraction grating) shine it thru the sample, see how much is absorbed
select 2501nm wavelength (using a prism or diffraction grating) shine it thru the sample, see how much is absorbed
select 2502nm....

etc.
that took a long time......

now, we just shine all the frequencies at once a few times using an interferometer (basically a fancy moire detector for stuff that works using different lengths that light can travel over) to vary the frequency response and use FTs to extract all of the absorption points.......

Here is the wiki for IR. Watch this video for much more juicy and clear explanations
.

PS: It's also how your MRI scan acquires data so quickly.....
posted by lalochezia at 6:01 AM on September 6, 2021 [6 favorites]

And how MP3 files take up so much less space than CD audio.....
posted by polytope subirb enby-of-piano-dice at 6:23 AM on September 6, 2021 [2 favorites]

And for those who enjoy recursive backronyms, FIJI Is Just ImageJ (batteries included).
posted by polytope subirb enby-of-piano-dice at 6:26 AM on September 6, 2021 [3 favorites]

Huh, I'd never thought about FFT applied to images rather than audio. Very cool.
posted by Foosnark at 6:27 AM on September 6, 2021 [1 favorite]

Oh man, I feel this guy so hard. I used to work in print production and the things authors would submit for publication! And scan/blur/sharpen was a LOT slower 20+ years ago.
posted by rikschell at 7:07 AM on September 6, 2021 [3 favorites]

Yep, 1990s digital prepress guy here (who still owns a couple of the linen testers I used to use for inspecting film separations), and this would have leveled the building where I worked if we had seen it in action, from sheer collective surprise.
posted by wenestvedt at 7:57 AM on September 6, 2021 [3 favorites]

> “You don’t need ML,” Bryan said. “What you need is inverse FFT.”

If there were two facts in the world I wish everyone in the world understood, these might very well be them.
posted by 7segment at 8:15 AM on September 6, 2021 [16 favorites]

So, all those crazy scenes in cop shows where the detective yells at the person sitting at the computer ENHANCE ENHANCE ENHANCE! are coming true?
posted by njohnson23 at 9:06 AM on September 6, 2021 [1 favorite]

(in case there are fellow wizards around...)

So, for audio we have a bunch of perceptual frequency scalings, like Mel scale and Bark scale, which baaasically rescale the frequency avoid because a) much of the useful info is in the lower frequencies, and b) something close to logarithmic frequency scalings matches better with human perception. (One line quasi-empirical half-proof: An octave doubles the frequency.) Q: Why don't we ever use logarithmic frequency scaling when displaying image FFTs? I would imagine a lot more interesting detail should be apparent than a couple diagonal lines.
posted by kaibutsu at 9:24 AM on September 6, 2021 [1 favorite]

Obligatory XKCD.
posted by Major Clanger at 11:28 AM on September 6, 2021 [2 favorites]

I installed the Fourier plugin into GIMP and played around with an image that Dr. Indexy had to take out of an upcoming publication because it was such a low quality halftone image. The original is followed by different ways of painting bright areas in Fourier space then doing the inverse FFT. I wanted to play with this technique to see what covering different areas in FFT space would do.

Love this! Thank you for posting!
posted by indexy at 12:23 PM on September 6, 2021 [4 favorites]

Artist Takahiro Kurashima has a series of print books called poemotion and moirémotion that use this effect. The books contain printed patterns and come with an acetate sheet that has alternating black and clear lines. Moving the sheet over the page hides and shows different parts of the pattern, which creates an animated effect.
posted by They sucked his brains out! at 12:25 PM on September 6, 2021

Interestingly enough it would be possible to do this in the image domain without FFT: as a consequence of the convolution theorem, the operation of zeroing out some coefficients in frequency domain and then transforming back to image domain corresponds to a particular convolution kernel (a kind of fancy blur). Because of this I think an ML approach would work equally well, since basically the entire mode of operation of convolutional neural networks is to learn convolution kernels.
posted by Pyry at 12:34 PM on September 6, 2021 [2 favorites]

Pattern Suppressor is an open-source plugin for Adobe Photoshop that uses FFT and iFFT for the same purpose. It includes a "star suppressor" option that more nicely automates what the individual in the OP is doing manually with ImageJ/Fiji.
posted by They sucked his brains out! at 1:00 PM on September 6, 2021 [6 favorites]

Sure beats oil-mounting your image at 45° in the drum scanner before spending all afternoon watching the image trickle in … and yes, I'm old enough to remember animating OHP slides with polarized strips and the rotating polarizer doohickey, just like Kurashima's work. My lawn, off.

If you have G'Mic installed in the Open Source Image Editor With The Ableist Slur For a Name, the Grey Descreen filter is pretty neat for removing halftones from B&W scans.

→ an ML approach would work equally well

I'm sure it would, but since an FFT seems quite good at identifying the screen frequency and angle of halftones, it's gonna do it with real science and a lot less faffing about data ‘science’ (aka picking the model that best reinforces your bias without actually knowing how it works).
posted by scruss at 1:18 PM on September 6, 2021 [6 favorites]

Another practical application of FFTs -- for audio, not video -- is separating a mixture of audio -- people speaking at once -- into the individual audio signals from different speakers: cocktail party effect (wikipedia)

There's a few algorithms that roughly proceed by (a) encoding the input mixed audio signal with a short-time fourier transform (wikipedia), (b) using a mask on the coefficients in the frequency domain to allocate each coefficient to one or the other of the speakers, and then (c) decode the two estimated separated signals back into time domain.

With enough training data where you know what the true result is (the original separated audio signals that were mixed together), the mask to separate the mixed audio back into original input signals can be estimated. Here's a nice step by step worked example (mathworks.com, alas, matlab) with lots of plots.

One current algorithm, the SepFormer (archiv), that achieves state of the art performance (paperswithcode.com) on the speech separation problem appears to roughly use the same overall architecture -- albeit where the short-time fourier transform is replaced with some parametrised layer of convolutions -- and something much more sophisticated is going on to estimate and apply the mask.
posted by are-coral-made at 5:13 PM on September 6, 2021 [3 favorites]

Kink-shaming slur, surely?
posted by acb at 4:50 AM on September 7, 2021 [1 favorite]

It's unfortunately applied as a slur to people with mobility disabilities such as CP.
posted by scruss at 4:39 PM on September 7, 2021 [2 favorites]