[HN Gopher] Moire No More
___________________________________________________________________
Moire No More
Author : stock_toaster
Score : 366 points
Date : 2021-09-26 19:17 UTC (3 hours ago)
(HTM) web link (www.getrevue.co)
(TXT) w3m dump (www.getrevue.co)
| NKosmatos wrote:
| Well written, good flow, interesting read and reminded me of the
| lessons we had at the university some decades ago (should have
| paid more attention). Why isn't this offered as an option in
| photoshop or other commercial image editing packages?
| amelius wrote:
| The author probably missed that the first F in FFT refers to a
| very specific (but efficient) algorithm, and that the effects he
| achieved are due to the properties of the (2D) Fourier transform,
| which can be computed using other algorithms as well.
| arriu wrote:
| Fantastic read, thanks!
| geoduck14 wrote:
| >Imagine being able to edit the nutrition label and see the food
| transform in front of you.
|
| This is a surprisingly good description of an FFT.
| asnt wrote:
| The Fast Food Transform?
| GekkePrutser wrote:
| That tool is broken, it only transforms belly size :(
| [deleted]
| marzell wrote:
| Been using this technique for a long time, great to see an in-
| depth look at it.
|
| This is great for other types of regular patterns, not just
| moire. For instance, if you scan old 60s/70s photos on
| textured/fiber paper, you can use this to smooth out the texture
| if desired.
| beowulfey wrote:
| I use Fiji every day, and I love the first impressions from
| someone who does not use it regularly (all correct too).
|
| FFTs are amazing. In xray crystallography, you can use them to
| recapture the original image of a crystallized protein from the
| scatter of dots left by passing through it--essentially acting as
| the role of lens. They never cease to amaze me with their
| usefulness!
| shrimpx wrote:
| When I saw the link named "explaining [FFT's] ingenuity in more
| detail" I was nearly certain it would be a 3B1B video, and it
| was:
|
| https://www.youtube.com/watch?v=spUNpyF58BY
| spockz wrote:
| Awesome read! Is this in use by any software already? I can
| imagine someone at Adobe already implementing this in photoshop.
| Can we apply this quickly enough to let everyone where whatever
| stripes they want on television?
| johndough wrote:
| With GIMP:
|
| https://www.youtube.com/watch?v=30XaCfM2QGg
|
| https://www.youtube.com/watch?v=se9I3uGITR0
|
| With Photoshop:
|
| https://www.youtube.com/watch?v=vb4XFNC4MvU
|
| I am sure there are more tools for it. Good search terms seem
| to be "FFT Moire".
|
| Fourier transforms can be easily computed in realtime at full
| HD resolution these days since GPUs are very fast at that kind
| of math.
| mdre wrote:
| It's implemented in affinity photo. You get realtime feedback-
| it's pretty amazing.
| dylan604 wrote:
| Things you can do to a single image that look good do not
| directly scale to the same results to video, especially
| something in motion.
|
| Also, this would be a good example of just because you can
| doesn't mean you should, especially with stripes.
| megous wrote:
| If you mean DFT, then yes. It's basis for image/video
| compression, for example. ;)
| hikarudo wrote:
| That would be DCT - Discrete Cosine Transform.
| smusamashah wrote:
| Someone has made this http://turbomaze.github.io/JS-Fourier-
| Image-Analysis/. I am sure a web version where you can
| manipulate the FFT and see the image reconstruction live should
| already exist somewhere.
|
| EDIT: This fork allows drawing over FFT
| https://geeklogan.github.io/JS-Fourier-Image-Analysis/
| Sharlin wrote:
| This is not a general-moire-removal technique. It's basically a
| band-stop filter that removes those frequencies from an image
| that correspond to the size of halftone dots both horizontally
| and vertically. Nifty use case for FFT though, would probably
| make a good homework assignment on an undergrad DSP course.
| carlob wrote:
| > removes those frequencies from an image that correspond to
| the size of halftone dots both horizontally and vertically
|
| And all the harmonics that make out the circle shape.
|
| I'm pretty sure that making the circle repeat horizontally
| and vertically is some kind of convolution product and that
| has some nifty properties under Fourier transform.
| timthorn wrote:
| This reminded me of when film photography processors went from
| printing using a photographic process to digital printing. The
| digital process introduced a regular grid to the print which
| reduced the quality of the print. When prints were made using an
| enlarger onto photographic paper, the grain was random and the
| resulting images had a much nicer character.
| a_c wrote:
| The blurring and then sharpening in spatial domain is equivalent
| to applying a band-pass filter, or rather a band-stop in the
| article's case, in the frequency domain. Blurring requires a lot
| of parameter tuning, in particular the size of the mask and the
| weight of each the mask element. The choice of parameter can be
| mapped to particular filter in the frequency domain, e.g. a
| gaussian filter or an ideal filter. Same for sharpening.
| Operating in the frequency domain allows you to skip all the
| trial and error of parameters, by eye-balling the frequency of
| interest, and suppress its presence.
|
| > what you did is still the best out there
|
| It still is.
|
| I worked with a printing company before. The company impart anti-
| forgery pattern to packaging material by tuning the half tone-ing
| angle of the printer. The printing company then offer a seemingly
| transparent film, with special pattern printed on it, to company
| requiring brand protection. By overlaying the film on top of
| packaging material, a specifically designed moire pattern would
| occur. If you squint your mind enough, it is like public-private
| key encryption in the physical world. Whenever the brand receive
| dispute over authenticity of purchased items, a special team, a
| team having that transparent film, will be summoned to verify the
| authenticity of item in question. It is one of the many ways the
| brand in question protect their goods. The printing company was
| looking for a mobile solution instead of delivery the transparent
| film, that's where I get to learn more about the printing
| industry.
| lbotos wrote:
| are you at liberty to share the printing company here? I'm
| looking for something like this. If not, my email is in my
| profile and would appreciate info so I can reach out and maybe
| give them business!
| mceachen wrote:
| 20 years ago you could just type in the rotation angle you
| wanted for each color separation into your film plotter.
|
| If you ask your printer, they should be able tell you what
| lpi/dpi they can resolve on the media you're printing onto
| (you may be limited due to dot gain on uncoated stock).
| a_c wrote:
| Thing is a bit complicated. I actually worked with a
| middleman, this middleman act as the "certificate authority"
| - signing up brands and dispatching orders to printing
| company(ies). So the printing companies don't know what the
| matching pattern is. It was five years ago and I have since
| moved on.
| a_c wrote:
| > It still is.
|
| It is a relatively well defined problem - removing periodic
| pattern due to physical arrangement of printing device. This is
| where algorithmic approach shines over ML approach. I think
| nowadays a lot of ML is an attempt to outsource the problem
| understanding part. These are hot dogs, these are not hot dogs.
| I don't know what defines a hot dog, but is this picture a hot
| dog?
|
| Hyperbole, of course.
|
| On second thought, I think the author shouldn't remove the
| periodic noise at all. He was preserving "a copy of history",
| not the first occurrence of history. It is a property worth
| preserving. It is a beauty of itself imo.
| II2II wrote:
| The moire is an artifact of the scanning or scaling process,
| and is by no means historic. Removing it is certainly
| legitimate. That is particularly true since scaling the image
| can make it worse.
|
| If you are talking about preserving the halftone in an
| original scan, then yes I agree that it should be preserved.
| Yet you must also accept that the periodic pattern will have
| to be removed prior to publishing the image since it will be
| scaled at some point.
| imoverclocked wrote:
| It would be cool if the photo could be printed in a similar
| way to re-create the effect from the recovered image.
| derefr wrote:
| The halftone pattern itself might look lovely and
| "historical" on you screen, but the book would not present
| the image "as-is" (i.e. with all halftone detail from the
| original photo losslessly captured on the page), but rather
| through the lens of _another_ halftone printing process, one
| whose DPI is low-enough that it would arbitrarily interfere
| with the original photo's to create a garbled mess. The final
| product wouldn't be halftone dots encoding a picture, but
| rather halftone dots encoding moire stripes from an attempt
| to replicate _other_ halftone dots from a "sample grid" that
| doesn't line up with them.
|
| It'd be a bit like taking one of those game emulators that
| displays the game with a "scanline"-effect filter... and then
| hooking the computer running the emulator up to an old TV
| that has a natural built-in scanline effect. You won't get
| the pretty scanlines from the emulator, nor will you get the
| pretty scanlines from the TV; you'll just get a mess.
|
| (To put it in technical terms: to accurately show the
| halftone "information" from the original photo in the book,
| the print resolution of the book would need to be double the
| Nyquist frequency of said halftone information. But it very
| likely won't be.)
| MihaiSandor wrote:
| "I have had my results for a long time: but I do not yet know
| how I am to arrive at them" - C.F Gauss. Nice job a_c
| robocat wrote:
| I tried the image[1] on one of the ML super-resolution online
| image sharpeners[2] and the result was: https://ibb.co/S53Lt0X
| (click button to look at it in full resolution).
|
| The generated image does not have the same global problem with
| moire patterns. The dot patterns remain in the image, randomly
| dithered or converted into lines. The FFT solution worked better
| than that particular ML model, although I presume a ML model
| could be trained specifically to remove printing dots.
|
| [1]
| https://s3.amazonaws.com/revue/items/images/010/787/862/orig...
|
| [2] https://deepai.org/machine-learning-model/torch-srgan
|
| Edited: added link to output image.
| rcthompson wrote:
| I wonder, is it better to black out the relevant parts of the FFT
| image, or is it better to adjust them to be the same as the
| "background" shade surrounding them?
| nialse wrote:
| Cool! I wrote a similar script to automate removing rasters some
| ten years ago using G'MIC[1]. It was open sourced[2] and made
| available as a plugin of some sort. (Maybe through GIMP? Can't
| really remember.) The use case was enhancing page size scans of
| Babar childrens books which it worked great for. YMMV though,
| it's a bit rough around the edges.
|
| [1] https://github.com/dtschump/gmic [2]
| https://github.com/dtschump/gmic-community/blob/master/inclu...
| linuxlizard wrote:
| Another great use of an FFT and filtering.
| https://www.edn.com/buenos-notches-the-filter-wizard-vs-the-...
| Filtering out vuvuzela noise. Same sort of idea, targeting the
| frequency peak of an obnoxious interference.
| skatanski wrote:
| Well written and really interesting. Its really cool to see an
| FFT usage example, afaik its also being used by Shazam for
| matching sound samples. I have fond memories of FFT, from the
| time I attempted to use it for generating stereo-pairs for
| obstacle detection using a two camera system. In my case
| specifically I was using it to find a particular pixel in the
| second image of a pair and calculate the shift. In the end at the
| time using FFT for something like that was much slower, than
| using a correlation window based algorithm. It was very
| interesting though and very different, than the latter.
| nyanpasu64 wrote:
| Fun fact: large correlations (hundreds or thousands of samples
| in 1D, unsure in 2D) can be efficiently computed using FFTs (if
| the needle is smaller than the haystack, you can use chunked
| algorithms like overlap-add/save).
| chmod775 wrote:
| That's amazing.
|
| Reading this I actually got excited about something I already
| knew and had used now and then, when I never felt about it that
| way before.
| vermarish wrote:
| Same. I think it's something to do with the writing style, the
| familiarity of the problem, and the sheer flexibility of FFT.
| poxwole wrote:
| FFTs are amazing! Also throwing ML at any problem is the root of
| all evil.
| colanderman wrote:
| 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?
| [deleted]
| a_c wrote:
| 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
| nyanpasu64 wrote:
| 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/wikip
| edia/commons/a/ac/Julemoti....)
| kortex wrote:
| 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.
| twic wrote:
| 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.
| marcodiego wrote:
| 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?
| mrob wrote:
| The ImageMagick documentation for this technique recommends
| blurring the black circles:
|
| https://legacy.imagemagick.org/Usage/fourier/#noise_removal
| Darthy wrote:
| Since the halftone dots are in a matrix that is at an angle,
| can't you just write a small program that measures the size of
| each halftone dot and stores that measurement? Then map the
| measured size to a grey value (supersmall = near white, big =
| black), and you have recovered all the information in that image.
|
| Then just counter the rotation of the matrix to get the best
| possible right-side-up scan.
| carlob wrote:
| Or better yet: figure out the average dot, replicate it all
| over the image, and run its Fourier transform. I think that
| subtracting it from the original image Fourier transform and
| then inverse transforming the result should also work.
| nyanpasu64 wrote:
| Subtracting the Fourier transform of a dot pattern from the
| Fourier transform of a photo is equivalent to (but slower
| than) subtracting a dot pattern from the photo. Subtracting
| an average-sized dot from a random dot would leave behind a
| ring, and subtracting a cone from a random dot would instead
| leave behind odd sloped shapes. It might be a good first step
| though.
| carlob wrote:
| Right right... linearity
| hardmath123 wrote:
| If you liked this, you might enjoy this little trick you can do
| with moire patterns -- near the end of the post, I talk a little
| bit about the math behind the FFT connection.
| https://hardmath123.github.io/moire.html
| dongping wrote:
| Or for those who studied electrical engineering (or anyone one
| who took a _Signal and System_ course):
|
| https://en.wikipedia.org/wiki/Nyquist%E2%80%93Shannon_sampli...
|
| https://matthews.sites.wfu.edu/misc/DigPhotog/alias/
| mxfh wrote:
| An increadibly well explained piece on the magic that is the
| frequency domain visualized as power spectrum.
|
| HN please, make a _FFT of the Day_ tag to not miss those, just on
| the title.
| vermarish wrote:
| This article is very well written! I remember having a similar
| experience creating a bandpass filter by computing FFT,
| multiplying by a Gaussian, and inverting the result. I swear
| Gaussian functions are just one of those things that you can
| insert anywhere and it'll just work out.
| sedatk wrote:
| > All the demoireing guides tell you to apply a sharpening filter
| after [blurring] to compensate, but that's like reheating cold
| pizza.
|
| What a fantastic analogy. I wanted to stand up and applaud the
| author.
| bambax wrote:
| Good writing, yes. But there are ways to properly re-heat old
| pizza and it's almost as good as fresh. One way (the best way)
| is to put it in a skillet with the pizza slice on one side and
| a little bit of water on the other side (not touching!) and
| cover it, and put over medium heat for 2-4 minutes. Another is
| to use an air-dryer (if you have one). You may need to test
| temperature and durations but once you find the proper settings
| it's perfect.
| thrdbndndn wrote:
| I don't think what the author did here (descreening) has anything
| to do with Moire _per se_. Sure, due to the nature of halftone,
| it often introduce Moire as the author said. But if you scan your
| document /photo at high enough resolution (sampling theorem
| anyone?) it isn't an issue in the descreening process later
| (which is the main topic of this article.)
|
| Also, using inverse fourier transform to descreen is already the
| basis of lots of popular commercial denoise plugins (for
| Photoshop etc.). Most of them will automatically measure the
| angle and resolution of halftone matrix too.
| DantesKite wrote:
| Fun read. Apparently the author is going to be coming out with a
| book on the history of keyboards and the people involved in them.
|
| Sounds promising.
___________________________________________________________________
(page generated 2021-09-26 23:00 UTC)