# Salt and Pepper Noise Removal with Multi-Class Dictionary Learning and L0 Norm Regularizations
## 2 Methods
### Proposed Method
#### 2.2.1 Adaptive Dictionary Learning in Salt and Pepper Noise Removal  
We first introduce the Fast Dictionaries Learning Method on Classified Patches (FDLCP) [13] into salt and pepper noise removal. FDLCP not only inherits fast learning to form orthogonal  
Figure 1: A flowchart of the proposed method on impulse noise removal. dictionaries, but also provides sparser representations by training comprehensive dictionaries for different geometrical image patches. As shown in Figure 2, patches that share the same geometric direction are grouped together to form one class, and then this class is used to learn a specific dictionary. Therefore, the dictionary of each class effectively captures the underlying image structures (Figure 2c). Mathematically, within a class of patches \(\mathbf{X}_{\omega}\) that shares a same geometric direction \(\omega\), an orthogonal dictionary is trained by solving the optimization problem [15]:  
\[\min_{\mathbf{D}_{\omega},\mathbf{Z}}\|\mathbf{X}_{\omega}-\mathbf{D}_{\omega}\mathbf{Z}\|_{F}^{2} +\eta^{2}\|\mathbf{Z}\|_{0}\quad s.t.\quad\mathbf{D}_{\omega}^{T}\mathbf{D}_{\omega}=\mathbf{I} \tag{3}\]  
where \(\mathbf{D}_{\mathrm{w}}\) is the dictionary and \(\left\|\cdot\right\|_{F}\) is the Frobenius norm. We choose the orthogonal dictionary learning because it enables the significant reduction of computation [13,15] than the commonly redundant dictionary trained in the K-SVD. For example, it has been shown that the computational time of learning orthogonal dictionary will be approximately 1% than that of the redundant dictionary in K-SVD [13]. Equation (3) can be fast solved by alternatively computing the sparse coding \(\mathbf{Z}\) and updating the dictionary \(\mathbf{D}_{\omega}\) in each iteration [13,15] as follows:  
(1) Given the current dictionary \(\mathbf{D}_{\omega}\), update sparse coefficients \(\mathbf{Z}\) via hard thresholding:  
\[\mathbf{Z}=H_{c}\Big{(}\mathbf{D}_{\omega}^{T}\mathbf{X}_{\omega}\Big{)} \tag{4}\]  
where the hard threshold \(H_{c}(\mathbf{Q})\) for a matrix \(\mathbf{Q}\) is an element-wise operator that performs on the element \(\mathbf{Q}_{ij}\) according to \(H_{c}(\mathbf{Q}_{ij})=\left\{ \begin{array}{cc}0,\;if\;abs(\mathbf{Q}_{ij})\leq c&\\ \mathbf{Q}_{ij},if\;abs(\mathbf{Q}_{ij})>c&\end{array} \right.\) with a threshold \(c\). (2) Given the coefficients \(\mathbf{Z}\), compute dictionary \(\mathbf{D}_{\omega}\) according to:  
\[\min_{\mathbf{D}_{\omega}}\|\mathbf{X}_{\omega}-\mathbf{D}_{\omega}\mathbf{Z}\|_{F}^{2}\quad s.t.\quad\mathbf{D}_{\omega}^{T}\mathbf{D}_{\omega}=\mathbf{I}, \tag{5}\]  
where \(\eta\) is a parameter to decide the sparsity and \(I\) is an identity matrix. The solution of Equation (5) is:  
\[\mathbf{D}_{\omega}=\mathbf{PV}^{T}, \tag{6}\]  
where \(\mathbf{P}\) and \(\mathbf{V}\) are orthogonal matrices of the following singular value decomposition:  
\[\mathbf{X}_{\omega}\mathbf{Z}^{T}=\mathbf{P}\mathbf{\Lambda}\mathbf{V}^{T}, \tag{7}\]  
Figure 2: Adaptive representations learnt with FDLCP. (**a**) Geometric directions estimated from the Barbara image, (**b**) one class of image patches that share the same geometric direction, (**c**) one dictionary learnt from the class of patches in (**b**). Note: red lines in (**a**) indicate geometric directions of image patches. where \(T\) denotes the matrix transpose. The solutions in Equations (7) and (8) are called the orthogonal Procrustes solutions, which were first considered in dictionary learning before [35]. In our implementation, the parameter \(\eta\) is set to 0.2 in all experiments. A good feature of the FDLCP [15] is that it balances the fast learning via orthogonal dictionary, comparing with the relatively slow learning in the classic K-SVD [12], and sparse representation for each classes, comparing with the sole orthogonal dictionary for all image patches [13]. FDLCP has been observed to outperform K-SVD in the medical image reconstruction [15], but not yet applied to impulse denoise so far.