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 to several state-of-the-art denoising algorithms.
Introduction
In the realm of patch-based image denoising, algorithms such as Non-Local Means (NLM) have long relied on the principle of averaging similar pixels across an image. Mathematically, this process is represented by multiplying the noisy image vector by a row-stochastic weight matrix. A curious and previously unexplained phenomenon in this field is that applying a column normalization step prior to the standard row normalization—a process known as symmetrization or Sinkhorn-Knopp balancing—leads to a dramatic and consistent improvement in denoising quality.
As shown in Table 1, this "one-step" symmetrization trick yields significant PSNR improvements across a variety of standard benchmark images. While the empirical benefits were clear, the underlying statistical reason for this gain remained elusive. This paper provides a rigorous foundation for this improvement by reinterpreting symmetric smoothing filters through the lens of Gaussian Mixture Models (GMMs).
A Statistical Learning Perspective
The core contribution of this work is the realization that the Sinkhorn-Knopp algorithm is essentially a restricted version of the Expectation-Maximization (EM) algorithm used to learn a GMM of image patches. Specifically, the column normalization step in Sinkhorn-Knopp corresponds to the E-step in EM, transforming conditional probabilities into posterior probabilities. This serves to "balance" the influence of patches, effectively down-weighting "weak friends"—patches that are somewhat similar but overly numerous and potentially irrelevant.
Standard smoothing filters like NLM are shown to be suboptimal because they implicitly assume a cluster for every single pixel ($k=n$). By contrast, our proposed Gaussian Mixture Model Symmetric Smoothing Filter (GSF) allows for $k < n$, enabling better data aggregation and noise suppression by learning a representative set of clusters directly from the noisy data.
Iterative Symmetrization and Geometric Interpretation
The iterative nature of the Sinkhorn-Knopp algorithm provides a unique geometric view of the denoising process. While initial iterations typically lead to a peak in PSNR improvement, excessive iteration can sometimes lead to a slight degradation as the implicit clustering becomes "too sharp," losing the ability to represent complex textures with a limited number of clusters.
As illustrated in Figure 1, the PSNR improvement typically stabilizes after a few iterations. This behavior confirms that the symmetrization process is not merely a numerical quirk but a principled approach to balancing patch influence within a statistical framework.
The GSF Algorithm and Results
Building on these insights, the GSF algorithm treats denoising as a Maximum-a-Posteriori (MAP) problem. To ensure practicality, we employ Stein’s Unbiased Risk Estimator (SURE) to automatically tune the regularization parameter ($\lambda$) and use cross-validation to determine the optimal number of clusters ($k$).
Experimental results on standard benchmarks (including Lena, Barbara, and Boat) show that GSF consistently outperforms standard NLM and its one-step Sinkhorn-Knopp variants. At high noise levels ($\sigma = 100$), GSF provides a gain of over 2.5 dB compared to NLM. Furthermore, GSF achieves performance levels competitive with state-of-the-art methods like BM3D and NL-Bayes, despite its significantly simpler mathematical structure.
Conclusion
By demystifying the success of symmetric smoothing filters, we have bridged the gap between heuristic matrix balancing and principled statistical learning. The GSF algorithm offers a robust, high-performance alternative to traditional denoising methods. Future work will focus on reducing the computational complexity of the EM clustering process to make GSF even more efficient for real-time applications.
Summary updated