Image Denoising: The Min/Max Flow

Explanation/Preview

One illustration of interface methods is the removal of noise from an image. Consider a gray-scale image, made up of pixels which have some value between white (0) and black (255). To make life easy for a second, imagine a black letter on a white background. We'll adopt the usual convention, so that each pixel has a value of either 0 or 255. Now, let's imagine a lot of noise in the image; by noise, we mean pixels that are supposed to be black or white, but in fact have corrupted values somewhere between 0 and 255. As an example, see the figure above.

The idea is to view the pixel values as a topographic map; the intensity (somewhere between white and black) at each pixel is the height of the surface at that point. Suppose we then let each contour undergo motion by curvature. Then very small contours, corresponding to spikes of noise, will disappear quickly. Better yet, the boundaries will remain sharp, since they will not blur under this motion, and instead only move according to their curvature.

Of course, if you let the contours flow under the curvature, Grayson's theorem says that eventually everything will shrink and disappear. Instead we use a min/max flow; which turns the curvature flow on or off depending on the scale of the noise you want to remove. Some advantages of this approach are that:

It stops automatically; if you apply it forever, it will clean the image, and then do nothing.
It requires only local operations on pixels; that means, each pixel value is cleaned or left alone depending only on the basis of the neigboring pixels.

A longer explanation of these ideas is available on the web page about image denoising.

A Java Applet for the Min/Max Denoising Scheme

As illustration, Java applets are available which show how these algorithms work. The idea is to draw a black shape on a white background, then add noise to it, and then try to clean it up and "recover" the original shape.

There are three different Java applets. They have different degrees of resolution; the coarse grain one executes very quickly, and it best for slower machines, while the fine grain one allows one to draw detailed images on a larger pixel area, but executes slower.

Coarse Grain Simulation (Faster): Java Applet
Medium Grain Calculation (Slower): Java Applet
Fine Grain Calculation (Slowest): Java Applet

If you want to learn more:

Malladi, R., and Sethian, J.A., Image Processing via Level Set Curvature Flow , Proceedings of the National Academy of Sciences, Vol. 92(15), pp. 7046--7050, July 1995.

If You Want To Learn More:

An introductory resource about level set methods and applications: