Discrete Universal Denoiser (DUDE)

The DUDE is a new denoising algorithm for discrete sources corrupted by discrete memoryless channels. The algorithm takes as inputs a noisy data sequence, the channel transition probabilities, and a distortion metric, and produces an estimate of the clean signal. We can show through a theoretical analysis that the quality of the estimate, as measured by the specified distortion metric, is asymptotically at least as good as what can be achieved by any finite window denoiser, including the best such denoiser for the clean and noisy signals at hand. The DUDE is eminently practical as its running time and storage requirements are linear in the data size.

Below are links to demonstrations of the empirical effectiveness of the DUDE in the denoising of binary images and to an HP Labs Technical Report presenting the DUDE and its analysis.   The journal version of this report, published in the January 2005 issue of the IEEE Transactions on Information Theory, received the 2006 IEEE ComSoc and Information Theory Joint Paper Award.

Demonstrations:

Here the DUDE is seen to be effective in denoising two radically different types of binary images corrupted by a binary symmetric channel.

• Scanned text. For this setting the conventional approaches are median and morphological filtering, which are both finite window denoisers. As stated in the report, on this example, the DUDE achieves a lower bit error rate than both of these denoisers.
• Halftone. In this setting, a good off-the-shelf denoiser is not available. Median and morphological filtering actually amplify the noise. The DUDE, on the other hand, achieves a significant reduction in the bit error rate.

These examples are good illustrations of the "universality" of the DUDE. It should be apparent that the best denoisers for the above image types have radically different structures. The "universality" of the DUDE is embodied in its ability to learn about the underlying image type from just the noisy observation and to automatically apply what it has learned to arrive at a fairly close approximation of the appropriate image type dependent denoiser.

References:

Universal discrete denoising: known channel
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J. Weinberger 
HP Labs Tech. Report HPL-2003-29, February 2003 and IEEE Trans. Inform. Theory, Vol. 51, No. 1, Jan. 2005, pp. 5 – 28.

For more details, contact marcelo@hpl.hp.com.