# Improved Image Denoising Algorithm Based on Superpixel Clustering and Sparse Representation
## 2 Basics of Superpixel Clustering and Sparse Representation (SC-SR) Algorithm
### Sparse Subspace Clustering for Noisy Data  
Sparse subspace clustering is an outstanding clustering method based on sparse representation, which is able to handle missing or corrupted data. It is based on the fact that each data point in a union of subspaces can be represented as a linear or affine combination of other points. Points are determined to lie in the same subspace by searching for the sparsest combination, which leads to a sparse similarity matrix [13]. Based on the similarity matrix, spectral clustering is adopted to obtain the final clustering result.  
Given a data matrix \(\mathbf{M}=[\mathbf{m_{1}},\mathbf{m_{2}},\ldots,\mathbf{m_{n}}]\), the sparse representation of each point \(\mathbf{m_{i}}\in R^{d}\) can be obtained by the following optimal problem:  
\[min||\mathbf{\vartheta}_{i}||_{1}\text{ subject to }\mathbf{m_{i}}=\mathbf{M}\mathbf{ \vartheta}_{i} \tag{4}\]  
Matrix \(\mathbf{M_{i}}\in R^{d\times(n-1)}\) is defined as the matrix obtained from \(\mathbf{M}\) by removing its \(i\)-th column, where the subscript \(\hat{i}\) means that there is no \(i\). Point \(\mathbf{m_{i}}\) has a sparse representation with respect to the matrix \(\mathbf{M_{i}}\). Next, the optimal problem is equal to the following problem:  
\[min||\mathbf{c_{i}}||_{1}\text{ subject to }\mathbf{m_{i}}=\mathbf{M_{i}}\mathbf{c_{i}}\text{ and }\mathbf{c_{i}}^{T}\mathbf{I}=1, \tag{5}\]  
where \(\mathbf{I}\) is a unit vector. Taking noise into consideration, let \(\overline{\mathbf{m_{i}}}=\mathbf{m_{i}}+\mathbf{\eta_{i}}\). be the \(i\)-th corrupted data point, where \(||\mathbf{\eta_{i}}||_{2}\leq\varepsilon\) and \(\varepsilon\) are the noise variance. The optimal problem turns to:  
\[min||\mathbf{c_{i}}||_{1}\text{ subject to }||\overline{\mathbf{m_{i}}}-\mathbf{M_{i}}\mathbf{c_{i }}||_{2}\leq\varepsilon\text{ and }\mathbf{c_{i}}^{T}\mathbf{I}=1 \tag{6}\]  
Lasso optimization method [14] is used for recovering the optimal sparse solution from the above equation. With the sparsest representation of each point, a coefficient matrix \(\mathbf{C}\) (\(\mathbf{C}=[\mathbf{c_{1}}\,\mathbf{c_{2}},\ldots,\mathbf{c_{n}}]\) ) can be obtained, which describes the connections between points. Taking the matrix \(\mathbf{C}\) to establish a directed graph \(G=(V,E)\), the vertices of the graph \(V\) are the \(n\) data points and the adjacency matrix is the coefficient matrix \(\mathbf{C}\). Moreover, to make \(G\) balanced, a new adjacency matrix \(\widetilde{\mathbf{C}}\left(\widetilde{C_{ij}}=\left|C_{ij}\right|+\left|C_{ji} \right|\right)\) is built. Subsequently, the Laplacian matrix \(L\) is formed by \(\mathbf{L}=\mathbf{Da}-\widetilde{\mathbf{C}}\), where \(\mathbf{Da}\in R^{N\times N}\) is a diagonal matrix and meets the condition of \(Da_{ii}=\sum_{j}\widetilde{C_{ij}}\). Finally, spectral clustering method is applied to cluster the eigenvector of the Laplacian matrix to obtain the final cluster result for the whole data points.  
In this paper, sparse subspace clustering is adopted to effectively cluster superpixels into regions of similar geometric structure aiming to further learn the NSS prior in mid-level vision cues even in the presence of noise. It is known that better learning of the NSS prior can improve the performance of denoising algorithms based on structure clustering and sparse representation. Instead of clustering  
Figure 1: Segmentation results of simple linear iterative clustering (SLIC).  
size-fixed patches that are inflexibly extracted from images, clustering superpixels takes image edge and structure features into consideration, which leads to a better learning result of the NSS prior.