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.
- the original picture. The lady is called Barbara and this is a
standard image used to test image processing algorithms.
- the picture with noise added. You can change the amount of noise
by entering a different number in the web form at the top of the page.
The noise is a gaussian random function added to the pixel values of
the original image. The parameter you enter in the web form (default:
10) is the standard deviation of the gaussian distribution, taken on a
scale of 0 (for black) to 255 (for white).
- the picture with noise removed by my algorithm.
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 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
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
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.
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:
Peter Selinger /
Department of Mathematics and Statistics /
/ PGP key
Updated Mar 4, 2002