# Improved Image Denoising Algorithm Based on Superpixel Clustering and Sparse Representation
## 3 Proposed SC-SR Algorithm
### Learning Sub-Dictionaries for Each Cluster of Superpixels  
In the similar superpixel regions, we extracted overlapping patches centering on each pixels, where the overlapping patches were all \(b\times b\) size (\(b\) is odd). As for the pixels on the boundary of the image, we extended them by \(b/2\) pixels in a horizontal and vertical direction by mirroring pixels to gain the patches centering on them. As shown in Figure 2, the matrix \(Ma_{1}\) was extended by two elements in a horizontal and vertical direction by mirroring extension, and the matrix \(Ma_{2}\) was obtained. After every patch was transformed into a column vector, \(K\) sub-datasets \(\{\mathbf{M}_{k}\}_{k=1}^{K}\) were formed for training sub-dictionaries.  
Since the number of patches in each cluster was limited and patches in \(M_{k}\) had similar patterns, it was not necessary to learn an over-complete dictionary for each cluster [16]. Therefore, we used the principal component analysis (PCA) method to learn the compact sub-dictionary for each cluster.  
For each sub-dataset \(\mathbf{M}_{k}\), the proposed algorithm applied PCA to compute the principal components, with the purpose of constructing the sub-dictionaries \(\{\mathbf{D}_{k}\}_{k=1}^{K}\). \(\mathbf{D}_{k}\) can be constructed by the optimal solution for the following formulation:  
\[\big{(}\mathbf{D}_{k},\mathbf{A}_{k}\big{)}=\underset{\mathbf{D}_{k},\mathbf{A}_{k}}{\arg\min} \Big{\{}||\mathbf{M}_{k}-\mathbf{D}_{k}\mathbf{A}_{k}||_{2}^{2}+\lambda||\mathbf{A}_{k}||_{1} \Big{\}}, \tag{16}\]  
where \(\mathbf{A}_{k}\) is the sparse coefficient matrix of \(\mathbf{M}_{k}\) over \(\mathbf{D}_{k}\) The rank of \(\mathbf{M}_{k}\) is denoted by \(r\) and the co-variance matrix of \(\mathbf{M}_{k}\) is denoted by \(\mathbf{\psi}_{k}\) We obtained the result of matrix factorization \(\mathbf{\psi}_{k}=\mathbf{P}_{k}^{T}\mathbf{\Lambda}_{k}\mathbf{P}_{k}\), where \(\mathbf{P}_{k}=[\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{r}]\) is the orthogonal transformation matrix and \(\mathbf{\Lambda}_{k}\) is a diagonal matrix taking \(r\) eigenvalues of \(\mathbf{\psi}_{k}\) as its diagonal elements. If we regard \(\mathbf{P}_{k}\) as the dictionary and set \(\mathbf{E}_{k}=\mathbf{P}_{k}^{T}\mathbf{M}_{k}\), we obtain \(||\mathbf{M}_{k}-\mathbf{P}_{k}\mathbf{E}_{k}||_{2}^{2}=||\mathbf{M}_{k}-\mathbf{P}_{k}\mathbf{P}_{k}^ {T}\mathbf{M}_{k}||_{2}^{2}=0\) Therefore, Equation (16) is only determined by the sparsity regularization term \(\mathbf{E}_{k1}\), which is constant in this case. To obtain better sub-dictionaries for sparse representation, we extracted the first \(\tau\in[1,r]\) most important eigenvectors in \(\mathbf{P}_{k}\) to form a dictionary \(\mathbf{D}_{k}^{\tau},\mathbf{D}_{k}^{\tau}=[\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{\tau}]\), instead of regarding \(\mathbf{P}_{k}\) as the dictionary. The sparse coefficient matrix is denoted by \(\mathbf{A}_{k}^{\tau}\) It is known that \(\mathbf{E}_{k1}\) increases when \(\tau\) increases, while \(||\mathbf{M}_{k}-\mathbf{D}_{k}^{t}\mathbf{A}_{k}^{t}||_{2}^{2}\) decreases. The optimal solution can be obtained by solving the following problem:  
\[\hat{\tau}=\underset{\tau}{argmin}\Big{\{}||\mathbf{M}_{k}-\mathbf{D}_{k}^{\tau}\mathbf{A }_{k}^{\tau}||_{2}^{2}+\lambda||\mathbf{A}_{k}^{\tau}||_{1}\Big{\}}. \tag{17}\]  
Consequently, we obtained \(K\) sub-dictionaries \(\{\mathbf{D}_{k}\}_{k=1}^{K}\) for the \(K\) sub-datasets \(\{\mathbf{M}_{k}\}_{k=1}^{K}\). In Equation (17), it was verified that some noise can be successfully removed during computing the local PCA transform of each image patch. In this paper, PCA was applied to each sub-dataset to construct the dictionary, which was able to reduce not only the computational cost consumed by dictionary training, but also the noise introduced into the dictionary.  
Figure 2: Matrix mirroring extension.