The Most Informative Order Statistic and its Application to Image Denoising

Alex Dytso, Martina Cardone, Cynthia RusharXiv 2021 · OpenReview

Abstract

We consider the problem of finding the subset of order statistics that contains the most information about a sample of random variables drawn independently from some known parametric distribution. We leverage information-theoretic quantities, such as entropy and mutual information, to quantify the level of informativeness and rigorously characterize the amount of information contained in any subset of the complete collection of order statistics. As an example, we show how these informativeness metrics can be evaluated for a sample of discrete Bernoulli and continuous Uniform random variables. Finally, we unveil how our most informative order statistics framework can be applied to image processing applications. Specifically, we investigate how the proposed measures can be used to choose the coefficients of the L-estimator filter to denoise an image corrupted by random noise. We show that both for discrete (e.g., salt-pepper noise) and continuous (e.g., mixed Gaussian noise) noise distributions, the proposed method is competitive with off-the-shelf filters, such as the median and the total variation filters, as well as with wavelet-based denoising methods.

Introduction

In statistics and signal processing, order statistics—the values of a sample sorted from smallest to largest—are fundamental tools. While the median is widely used for robust filtering and the minimum/maximum are critical in reliability engineering, a formal theoretical framework to justify the preference of one order statistic over another for a specific distribution has been lacking. This research addresses this gap by asking: if we can only observe a subset of sorted data, which subset reduces our uncertainty about the original sample the most? This question is particularly pertinent for image denoising, where the optimal selection of filter weights can significantly impact image quality.

Information-Theoretic Framework

The core of this work leverages Mutual Information (MI) to quantify how much knowing an order statistic reduces uncertainty about the entire sample. For discrete random variables, such as Bernoulli trials, the authors define a direct measure $r_1$. However, for continuous variables, the MI between a sample and its order statistic is technically infinite. To address this, the paper introduces regularized measures ($r_2$ and $r_3$) by analyzing the behavior of MI as a small amount of Gaussian noise is added and then vanished.

Figure 2: The informativeness metric $r_1(i, X^n)$ plotted alongside the probability mass function (pmf) for a discrete sample.

A key insight from this framework is the "switch point" phenomenon. For Bernoulli samples (0s and 1s), the most informative statistic is not at a fixed position but is located where the sequence is expected to transition from 0 to 1. Furthermore, while the median is most informative for Uniform distributions, this is not a universal rule; the "best" statistic shifts according to the underlying noise distribution.

Application to Image Denoising: The L-Estimator

The authors apply these metrics to design a custom L-estimator filter. In this filter, the output is a weighted sum of ordered pixels within a local window. Unlike the standard median filter, which assigns a weight of 1 to the middle value and 0 elsewhere, the proposed L-estimator assigns weights based on the calculated informativeness of each position in the sorted list.

The weighting strategy adapts to the noise level:

  • Low-noise regimes: Weights are assigned inversely to informativeness.
  • High-noise regimes: Weights are assigned directly proportional to informativeness.

Experimental Results

The L-estimator was evaluated against standard benchmarks, including Total Variation (TV), Wavelet-based denoisers (SURE, FDR), and the standard Median filter, using various noise models like salt-and-pepper, mixed Gaussian, and heavy-tailed Cauchy noise.

Figure 5: Visual comparison of image denoising performance using the proposed L-estimator.

The results demonstrate that the L-estimator is particularly superior in high-noise environments (e.g., 80% corruption). Qualitatively, it preserves edges and geometric shapes better than the Median filter. For Cauchy noise, which typically breaks standard filters due to its infinite variance, the L-estimator achieved top performance across metrics like MSE, PSNR, and SSIM.

Conclusion and Future Work

This framework provides a nuanced method for selecting filter coefficients that often aligns better with human visual perception than traditional MSE minimization. Current limitations include the requirement for prior knowledge of the noise distribution and the computational overhead of calculating informativeness metrics. Future research will focus on extending the theory to non-i.i.d. cases to better account for the high correlation between pixels in real-world images.

Summary updated

Abstract

We consider the problem of finding the subset of order statistics that contains the most information about a sample of random variables drawn independently from some known parametric distribution. We leverage information-theoretic quantities, such as entropy and mutual information, to quantify the level of informativeness and rigorously characterize the amount of information contained in any subset of the complete collection of order statistics. As an example, we show how these informativeness metrics can be evaluated for a sample of discrete Bernoulli and continuous Uniform random variables. Finally, we unveil how our most informative order statistics framework can be applied to image processing applications. Specifically, we investigate how the proposed measures can be used to choose the coefficients of the L-estimator filter to denoise an image corrupted by random noise. We show that both for discrete (e.g., salt-pepper noise) and continuous (e.g., mixed Gaussian noise) noise distributions, the proposed method is competitive with off-the-shelf filters, such as the median and the total variation filters, as well as with wavelet-based denoising methods.
BibTeX
@misc{dytso2021most,
  author = {Alex Dytso and Martina Cardone and Cynthia Rush},
  title = {{The Most Informative Order Statistic and its Application to Image Denoising}},
  year = {2021},
  eprint = {2101.11667},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.11667},
}
Figure