[home]
Image De-noising

Non-linear Image De-noising in Fourier Space

Recently, Steve Desjardins gave a talk in the graduate student seminar here at Ottawa about how to remove noise from images by converting the image to Fourier space, applying a certain linear transformation to the image, and then converting it back to (x,y)-space. This reminded me of some experiments that I had recently done with digitally removing noise from audio data. I thought maybe a non-linear transformation would do a better job.

The interactive demo

Click here for an interactive demo of the de-noising algorithm.

What the images are

The web interface shows six images. The three left images are: The three right images are Fourier transforms of the corresponding left images. Thus, you can see how each transformation affects the image in both the (x,y)-space and in Fourier space. Namely, adding noise in (x,y)-space results in similarly distributed noise in Fourier space. You can see that in Fourier space, the noise is most visible in the areas that were formerly black.

How noise is detected

My algorithm tries to detect areas in Fourier space that were formerly black, and to remove the noise from them, while leaving the white areas untouched. You can see the result in the third picture: the black areas are black again, but many details of the white areas were lost. The corresponding picture in (x,y)-space is less noisy, but also somewhat blurred. Interestingly, the stripes on the woman's clothes and on the tablecloth are much better preserved than edges in the picture.

The algorithm tries to find the black "background" parts of the noisy image in Fourier space by averaging the pixels in a small neighborhood of each point. If the average value is low compared to a certain threshold, then the pixel is set to 0. If the average value is large compared to the threshold, then the pixel is left untouched. If the value is neither very large nor very small, the algorithm smoothly interpolates between the two possibilities. The actual formula used is: 

      f = 1 - ( 1 / (1 + (E c / t))^2 )
Here, E is the average pixel energy near a given point, c is a constant, t is a user-specified threshold, and f is the factor by which the pixel value will be multiplied. Note that 0 <= f <= 1.

Parameters you can change

You can vary the threshold for the amount of noise the algorithm suppresses by entering a different value in the web form. A larger threshold means more lighter areas will be blackened out in Fourier space in the third image. You can also vary the size of the neighborhood of each point that the algorithm looks at. The neighborhood is a little square of 2n+1 by 2n+1 pixels, where n is the "Denoising neighborhood size" entered in the web form.

Explanation of overlapping Fourier Transforms

Instead of converting the entire image to Fourier space, the algorithm divides the image into a grid of overlapping regions. The boundaries of the regions are smoothed where they overlap, in order to avoid discontinuities. The function used to smooth the boundaries is 
      w(x) = sin( sin^2(pi x) * pi/2 )
where x ranges from 0 to 1. The function has the property that w^2(x) + w^2(x+0.5) is constant on [0.5, 1], so the overlapping pieces fit together perfectly.

In our images of Fourier space, we show only every second region, so that the images do not overlap. Thus, the internal calculations use roughly four times as many regions as the web interface displays.

You will also notice that, while the image in (x,y)-space is black-and-white, there is some color in the images of Fourier space. This is not an accident: color is used because the pixels in Fourier space really correspond to complex numbers. The brightness of a pixel is proportional to the absolute value of a complex number, whereas the hue indicates its phase. The complex numbers 1, exp(2i pi/3), and exp(4i pi/3) are displayed as red, green, and blue, respectively. However, the phase of adjacent pixels is rarely related, and thus the sum of the pixels appears to be white from a distance.

You can change the size of the overlapping windows of the Fourier Transform. This will only work if the size is a power of 2; the useful range is 2-512. It is fun to plug in a smaller value, such as 32, or the maximum, which is 512.

High-noise images

The more noise you add to the image, the more difficult it is to get decent output from the de-noising algorithm. Try n=30 for the amount of noise, and a 32x32 fourier window with a denoising threshold of 3000 and a denoising neighborhood size of 1. For even larger amounts of noise, you need extremely large denoising thresholds.

Back to Homepage: [home]
Peter Selinger / Department of Mathematics and Statistics / Dalhousie University
selinger@mathstat.dal.ca / PGP key
Updated Mar 4, 2002