Hacker News Reader

Comment by colanderman | Hacker News Reader

I would think the optimal technique lies somewhere between the two: a convolution kernel optimized to conflate halftone dots with each other as to restore exactly the information possible. (Of course, such a kernel would have to be individually tuned for the orientation/spacing of the dots.)

Literally painting over frequency peaks in the FFT with black circles I imagine would be pretty lossy, and not entirely rid yourself of the pattern (since you're making a new pattern with your dots). Indeed, in the animation, the image does get darker as circles are added, and some of the pattern is still visible.

Perhaps using a blur tool to blur out the peaks in the FFT would serve to maintain original image tone, and further reduce patterning?

View on HN

The ImageMagick documentation for this technique recommends blurring the black circles:

https://legacy.imagemagick.org/Usage/fourier/#noise_removal

GIMP has a wavelet deconstruction option/plugin which breaks frequency bands into separate layers (like a stereo's multiband equilizer). You simply delete the layer corresponding to the frequency component and bam, visual features at that scale vanish, preserving structure at all other scales.

There's even more sophisticated wavelet denoisers out there that effectively do the black circle over peaks trick, but automatically and more precisely.

I used this to remove/reduce scars from some portraits. Many layers and then edit the desired spot (without removing the layers). Works like charm.

https://pixls.us/articles/skin-retouching-with-wavelet-decom... covered nicely here.

I did look at this. It seems pretty coarse though -- wavelets generally divide the spectrum into power-of-two frequency bands, and the Gimp is no exception it seems. Also of course you have to remove all higher-frequency bands as well, since the halftone dots have high frequency content at the edges of the dots.

Trying it out now, I'm able to get a good result (to my eye) by deleting the top two bands, but it looks nearly identical to the article's blurring example.

Upscaling the image first by 141% and deleting the same two bands, the dots start peeking through, but the result looks closer to the article's inverse FFT result -- minus the artificial edge contrast enhancement that came from the author's use of black (rather than grey) circles.

G'MIC (which is available as a gimp plugin) has the exact same reversible fourier transform as a layer in it as the Fiji software he referenced. You can do the exact same operations from the article (or any other edits/blurs/selections to the peaks).

It's a bit cumbersome since you can't preview what you're doing, but quite workable. Was trying it out on his reference image this evening and got (IMO nicer) results fiddling with magic wand/fuzzy select/grow/shrink and various fills.

Huh, interesting, thanks for trying that out! Yeah I forgot about the overtone frequencies of the halftone dots.

Yeah I supposed you'd need a tool with a continuous wavelet transform and potentially a 2D one at that.

Any convolution kernel is equivalent to a FFT (aside from wrapping effects). The advantage of using a convolution kernel (instead of a hand-painted FFT mask) is that it's purely local and doesn't cause halftone dots in one area of the image to affect the rest, and is faster than a full-image FFT (which is O(N log N) in both the width and height).

A halftone dot whose size/shape changes gradually across the image acts like slow PWM in a pulse wave, changing the relative amplitudes of the harmonics (but not their locations). However, steep discontinuous changes can have nastier effects (which aren't handled well by either a convolution kernel or FFT).

I suspect it's possible to handle edges better than a FFT using a specialized algorithm, but I don't know if it's possible without inordinate runtimes, and if the end result is significantly better than a FFT or not.

(Also, FFTs won't work as well for non-uniform hand-drawn halftones, like the charming https://upload.wikimedia.org/wikipedia/commons/a/ac/Julemoti....)

I think often the FFT is used to actually speed up convolution, it isn't slower than computing convolution of your kernel shifted to every pixel position.

https://en.wikipedia.org/wiki/Convolution#Fast_convolution_a...

> [FFT] isn't slower than computing convolution of your kernel shifted to every pixel position.

For a fixed kernel size and sufficiently large images, full-image FFT is slower than naive convolution because FFT scales by O(n log n) by the image size, while naive convolution only scales by O(n) in terms of the image size. This can be avoided by using blocked FFT instead of full-image FFT:

> If one sequence is much longer than the other, zero-extension of the shorter sequence and fast circular convolution is not the most computationally efficient method available.[13] Instead, decomposing the longer sequence into blocks and convolving each block allows for faster algorithms such as the overlap–save method and overlap–add method.[14] A hybrid convolution method that combines block and FIR algorithms allows for a zero input-output latency that is useful for real-time convolution computations.[15]

I see, I wasn't thinking about kernels much smaller than the image itself. So, if you don't use blocked FFT, it only makes sense to use FFT convolution when your kernel size is > log n?

You may be right, but I think in practice, people use direct convolution for small kernels, and FFT convolution for large kernels (blocked FFT if the signal is substantially longer than the kernel). I didn't look into the math behind this intuition though.

The specks on the FFT were hand removed... I thought the following: he had an image obtained after a blur and sharpening filters. By replacing parts of the FFT with black, he was just throwing away information. What would happen if instead of naively replacing the specks on the FFT with black he replaced those parts with the FFT from the blurred and sharpened image?

Indeed by applying the "dark circle" (ideal filter or sinc filter) in the frequency domain would introduce other artifacts. The restored image would contain some "ringing" around sharp edges, which might not be perceivable in the image shown. [1]

As of the darkening in restored image, it depends how the software interpret the band-stopping of dark holes. By dark circling in the frequency domain, energy is taken out from the image. Re-normalizing the image might be desired, but then it would turn dark areas brighter. [1] https://en.wikipedia.org/wiki/Ringing_artifacts

I suspect using black instead of grey is the reason for the edge contrast enhancement in the inverse-FFT image. I.e., that's exactly why the tiny areas in between the small letters are darker, and thus the lettering clearer.

Perhaps the optimal technique would be to write a function which halftones a greyscale image, and then use optimisation to find a greyscale image which reproduces the input image when halftoned. This feels like an expectation–maximization kind of problem, but i can't give a rigorous argument for why.

If you just search for "inverse halftoning" on Google Scholar there are a ton of techniques that are clearly better than this, e.g. MAP estimation.

Reply on news.ycombinator.com