In this post I will show how to smooth a halftone image using the fast Fourier Transform (FFT). You can try this out yourself by downloading my Matlab code on the bottom of the article.
The halftone technique is a general printing method used to reproduce photos with continuous tones using a limited number of colors. The technique works by putting dots in patterns of various sizes. This creates the illusion of smooth shades of colors.
The method was first used in the first daily tabloid in the United States called Daily Graphic. The article was published in December 2, 1873 (Picturing the past: media, history, and photography). The reason it works is because the human eye has a resolution limit, so the dots are effectively blurred together, forming the illusion of a continuous gradient.
The method is not only used for reproducing grayscale imagery, it can also be used to create color photos by using different overlaying patterns and a couple of carefully chosen colors. What is interesting with this technique is that the dots were initially relatively large, the patterns also need to be rotated, otherwise distracting effects called Moiré patterns will occur.
The same method is still used today in magazines and newspapers. A similar illusion can be seen in a ordinary (non-digital) photographs where the dots are grains, microscopic in size. Another difference is that the placement of the grains are not following any pattern as they are the result of a chemical process.
A first observation: can we use blur to remove the dots?
-A blur filter will not only smooth the dots, but also the sharp details which we wish to preserve. There may be more sophisticated kernels that can blur only the dots…
How about median filter, the dots are like salt-and-pepper noise?
-The median filter is good for reducing salt-and-pepper noise, but it will too reduce the quality of the photo. We can do better.
We will use the Fourier Transform. One of the most important algorithms, ever.
Here is how it works:
If we transform the image using the 2d fast Fourier Transform, we basically arrange the data by frequency, making it easy to see the dots, because they follow a pattern. Read more about FFT (Wiki on FFT).
First, to make it even easier to analyse, we shift the frequency spectrum using the Matlab command fftshift. The ‘frequency spectrum’ or ‘frequency domain’ now maps the low frequency data to the center of the matrix. What we see is usually stars, the large star in the center, which contains low frequency data the higher frequencies, which show the periodic higher-frequency data. The patterns will fall into the category of higher frequency, because they are periodic. Also note the symmetry of the stars. What is nice about the Fourier Transform is that the different patterns will be concentrated to a couple of areas, separate from the other frequencies. By setting these frequencies to zero, we effectively suppress the dots.
To accomplish this I wrote a simple code in Matlab where you can read in an image and draw in the frequency spectrum the parts you want to erase. The code saves the filled in points in a mask, then erases the points from the complex matrix, shifts back and applies the inverse FFT and views the result. It is simple to create a blur filter using FFT by simply erasing everything but the low frequency data.
Please notice that I use the log of the FFT2 for visualisation only. For the actual reconstruction I use both the real and imaginary elements of the FFT.
So, by erasing these off-center stars, we suppress the halftone patterns which gives us a kind of interpolated color for each pixel. See below for the frequency spectrum (magnitude of FFT2 of image).
An interesting fact is, by looking at different halftone photos, if the patterns of dots are the same, they will also look the same in their frequency spectrum. This means that we can filter those halftone images using the same mask and it also means that we can identify halftone patterns using FFT. If we for some reason want to see the printing pattern of a set of photos, we can identify which ones used the same halftone pattern.
I have an example of a halftone photo of Stefan Berggren, a member of GMK (Göteborgs Magiska Klubb). The photo was scanned from the club’s paper called ‘Tricks’. This specific photo was from September 1984, as part of a set of photos of a performance.
It can be difficult to see the smoothing effect the FFT method has, so I created a closeup of Stefans right arm to show that the background actually has a texture that cannot be seen in the halftone photo. The patterns we erase are both the bright ones and the dark ones. The intensity of all the dots are equalized.
While looking around using Google search, I found a Photoshop plugin by Alex V. Chirokov that actually does what I just did. See Photoshop FFT plugin. If you have Matlab and you don’t want to buy Photoshop, just give my code a try ;-)
The method of using the frequency spectrum to manipulate the image data is not new, but it is still very interesting. The most important part of this technique is that the original image is not degraded as with a blur filter. The sharp features seems to be preserved quite well considering.
Maybe I will add a smoothing filter to the drawing code, so it resembles the Photoshop plugin more. I might also remove the symmetry, so I only have to draw half of the frequency spectrum. Also, a real time preview would be really helpful.