Understanding Symmetric Smoothing Filters: A Gaussian Mixture Model Perspective

Stanley H. Chan, Todd E. Zickler, Yue M. Lu

TL;DR

This paper explains why a seemingly simple column-then-row normalization step can significantly improve image denoising filters. They show this process is equivalent to an Expectation-Maximization (EM) algorithm for learning a Gaussian Mixture Model (GMM) of image patches, leading to a new, effective denoising algorithm called GSF.

What Problem Does This Paper Address?

Many image denoising algorithms rely on smoothing filters, which are often represented as matrices. A standard requirement is that these matrices are "row-normalized," meaning each row sums to one. However, researchers observed that applying an additional "column normalization" before the row normalization could surprisingly boost performance. This phenomenon was linked to the Sinkhorn-Knopp algorithm, which iteratively symmetrizes matrices, but a clear understanding of why this improvement occurred was missing. The authors aim to bridge this gap by providing a statistical learning perspective and developing a more robust denoising method.

Methods

The core of the paper's contribution lies in connecting the Sinkhorn-Knopp algorithm to the Expectation-Maximization (EM) algorithm for learning Gaussian Mixture Models (GMMs).

  • Sinkhorn-Knopp as EM: They demonstrate that the iterative column-row normalization steps of Sinkhorn-Knopp directly correspond to the E-step (estimating cluster assignments) and M-step (updating model parameters) of an EM algorithm applied to image patches.
  • Geometric Interpretation: This connection provides a geometric understanding of the symmetrization process, viewing it as a form of data clustering.
  • Gaussian Mixture Model Symmetric Smoothing Filter (GSF): Based on this insight, they propose GSF. GSF leverages a GMM prior within a Maximum-a-Posteriori (MAP) estimation framework for denoising. It uses the EM algorithm to learn the GMM parameters from the noisy image patches and then solves a derived closed-form solution for denoising.
  • Parameter Estimation: The paper also addresses crucial parameter estimation challenges for GSF, proposing methods for determining the optimal regularization parameter ($\lambda$) using SURE (Stein's Unbiased Risk Estimator) and the number of clusters ($k$) via cross-validation.

Datasets

The paper uses standard, publicly available images for evaluation. Specific datasets are not introduced, but the experiments are conducted on a collection of 10 testing images, including common benchmarks like "Baboon," "Boat," "Barbara," "House," and "Lena." These images are corrupted with synthetic Gaussian noise at various standard deviation levels.

Key Insights and Ideas

  • Symmetrization is Clustering: The most significant insight is that the performance gain from column-row normalization (Sinkhorn-Knopp) is fundamentally a result of applying an Expectation-Maximization (EM) algorithm to learn a Gaussian Mixture Model (GMM) of image patches. This reframes a matrix operation as a statistical learning process.
  • EM Steps Explained: The paper clearly maps the matrix normalization steps to the E and M steps of the EM algorithm, offering a geometric interpretation of how the algorithm clusters similar image patches.
  • GSF as a Generalization: GSF is presented not just as a new algorithm but as a generalization that unifies several existing smoothing filters (like NLM, one-step Sinkhorn-Knopp, and full Sinkhorn-Knopp) under a single EM-based framework.
  • Parameter Sensitivity: The performance gain from one-step Sinkhorn-Knopp is shown to be sensitive to the spatial parameter ($h_s$) and the noise level, suggesting that "weak friends" (similar but not identical patches) are crucial for the improvement.
  • Cross-Validation for Clusters: The proposed cross-validation method for determining the number of GMM clusters ($k$) based on the deviation from standard NLM covariance matrices is a practical contribution.

Key Results

  • Performance Improvement: The proposed GSF algorithm consistently outperforms standard NLM and one-step Sinkhorn-Knopp across various noise levels, showing significant PSNR gains (e.g., 2.5dB or more at high noise levels).
  • Competitive Performance: GSF achieves performance comparable to several state-of-the-art denoising algorithms, including BM3D and EPLL, particularly in challenging low-noise conditions.
  • Parameter Estimation Effectiveness: The SURE-based method for $\lambda$ and the cross-validation for $k$ are shown to yield results close to optimal, demonstrating their practical utility.
  • Comparison with GLIDE: GSF shows at least 0.65dB improvement over GLIDE (which implements full Sinkhorn-Knopp) on average, supporting the idea that a complete EM implementation is beneficial.

Limitations and Future Work

  • Computational Complexity: The paper acknowledges that learning the GMM using the EM algorithm can be time-consuming, especially when the number of clusters ($k$) is large, which can occur in low-noise scenarios. This is a primary limitation for GSF's real-time applicability.
  • Initialization Sensitivity: While GSF is presented as less sensitive than some methods like PLE, the EM algorithm's performance can still be influenced by initial parameter estimates.
  • Future Work: The authors suggest further exploration into complexity reduction techniques for GSF. They also note that the GMM in GSF only involves cluster weights and means, unlike EPLL which also models covariance. Further investigation into how to best incorporate covariance information or other aspects of the EM algorithm could yield more insights. The paper also hints at the potential for GSF to provide a strong direction for future research in clustering-based image denoising.

Summary updated

Abstract

Many patch-based image denoising algorithms can be formulated as applying a smoothing filter to the noisy image. Expressed as matrices, the smoothing filters must be row normalized, so that each row sums to unity. Surprisingly, if we apply a column normalization before the row normalization, the performance of the smoothing filter can often be significantly improved. Prior works showed that such performance gain is related to the Sinkhorn-Knopp balancing algorithm, an iterative procedure that symmetrizes a row-stochastic matrix to a doubly stochastic matrix. However, a complete understanding of the performance gain phenomenon is still lacking. In this paper, we study the performance gain phenomenon from a statistical learning perspective. We show that Sinkhorn-Knopp is equivalent to an expectation-maximization (EM) algorithm of learning a Gaussian mixture model of the image patches. By establishing the correspondence between the steps of Sinkhorn-Knopp and the EM algorithm, we provide a geometrical interpretation of the symmetrization process. This observation allows us to develop a new denoising algorithm called Gaussian mixture model symmetric smoothing filter (GSF). GSF is an extension of the Sinkhorn-Knopp and is a generalization of the original smoothing filters. Despite its simple formulation, GSF outperforms many existing smoothing filters and has a similar performance compared with several state-of-the-art denoising algorithms.
BibTeX
@article{chan2017understanding,
  author = {Stanley H. Chan and Todd E. Zickler and Yue M. Lu},
  title = {{Understanding Symmetric Smoothing Filters: A Gaussian Mixture Model Perspective}},
  journal = {IEEE Trans. Image Process.},
  year = {2017},
  url = {https://openreview.net/forum?id=AlWpUfbV1Y2},
}
Figure