# A Shearlets-Based Method for Rain Removal from Single Images
## 4 The Proposed Method
### Solving the Proposed Model  
To solve the proposed model, the split Bregman algorithm is utilized [27], and the split step is implemented by introducing new variables:  
\[ \begin{pmatrix}v_{1}\\ v_{2}\\ v_{3}\end{pmatrix} = \begin{pmatrix}S_{r}(o-r)\\ S_{b}r\\ r\end{pmatrix}  \tag{14}\]  
as the \(\ell_{1}\)-norm is not differentiable, thus (13) has the following equivalent form  
\[ \begin{split}\min&\gamma_{1}\|v_{1}\|_{1}+\gamma_{2}\|v_{2}\|_{ 1}+\gamma_{3}\|v_{3}\|_{1}\\ s.t.&v_{1}=S_{r}(o-r),\quad v_{2}=S_{b}r,\quad v_{3}=r;\quad r\geq 0; \quad b\geq 0;\end{split}  \tag{15}\]  
for non-negative constrains of \(r\) and \(b\), they can be implemented by a projection operator. The corresponding Bregman iterations can be given as  
\[\left\{ \begin{split}(v_{1}^{k+1},v_{2}^{k+1},v_{3}^{k+1},r^{k+1} )&=\arg\min_{v_{1},v_{2},v_{3},r}\gamma_{1}\|v_{1}\|_{1}+ \gamma_{2}\|v_{2}\|_{1}+\gamma_{3}\|v_{3}\|_{1}+\frac{\alpha_{1}}{2}\|S_{r}(o -r)\\ &-v_{1}-b_{v_{1}}^{k}\|_{2}^{2}+\frac{\alpha_{2}}{2}\|S_{b}r-v_{ 2}-b_{v_{2}}^{k}\|_{2}^{2}+\frac{\alpha_{3}}{2}\|r-v_{3}-b_{v_{3}}^{k}\|_{2}^ {2};\\ b_{v_{1}}^{k+1}&=b_{v_{1}}^{k}+S_{r}(o-r)-v_{1};\\ b_{v_{2}}^{k+1}&=b_{v_{2}}^{k}+S_{b}r-v_{2};\\ b_{v_{3}}^{k+1}&=b_{v_{3}}^{k}+r-v_{3};\end{split} \right. \tag{16}\]Then the \(v_{i}\)-sub-problem \(i=1,2,3\) can be given as  
\[ \begin{cases}v_{1}^{k+1}=\arg\min_{v_{1}}\gamma_{1}\|v_{1}\|_{1}+\frac{\alpha_{1} }{2}\|S_{r}(o-r)-v_{1}-b_{v_{1}}^{k}\|_{2}^{2};\\ v_{2}^{k+1}=\arg\min_{v_{2}}\gamma_{2}\|v_{2}\|_{1}+\frac{\alpha_{2}}{2}\|S_{b }r-v_{2}-b_{v_{2}}^{k}\|_{2}^{2};\\ v_{3}^{k+1}=\arg\min_{v_{3}}\gamma_{3}\|v_{3}\|_{1}+\frac{\alpha_{3}}{2}\|r-v_ {3}-b_{v_{3}}^{k}\|_{2}^{2};\end{cases}  \tag{17}\]  
they can be solved accurately by soft-thresholding strategy as follows  
\[ \begin{cases}v_{1}^{k+1}=\text{Sh}\Big{(}(S_{r}(o-r^{k})+b_{v_{1}}^{k})(r), \frac{\gamma_{1}}{\alpha_{1}}\Big{)};\\ v_{2}^{k+1}=\text{Sh}\Big{(}(S_{b}r^{k}+b_{v_{2}}^{k})(r),\frac{\gamma_{2}}{ \alpha_{2}}\Big{)};\\ v_{3}^{k+1}=\text{Sh}\Big{(}(r^{k}+b_{v_{3}}^{k})(r),\frac{\gamma_{3}}{ \alpha_{3}}\Big{)};\end{cases}  \tag{18}\]  
for \(r=1,...,N\), \(N\) represents the total number of pixels, where  
\[\text{Sh}(x,y)=\text{sign}(x)\max(|x|-y,0); \tag{19}\]  
with  
\[\text{sign}(x)= \begin{cases}1,&x>0;\\ 0,&x=0;\\ -1,&x<0.\end{cases}  \tag{20}\]  
The \(r\)-sub-problem can be given by minimizing the following equation  
\[r^{k+1}=\arg\min_{r}\frac{\alpha_{1}}{2}\|S_{r}(o-r)-v_{1}^{k}-b_{v_{1}}^{k}\| _{2}^{2}+\frac{\alpha_{2}}{2}\|S_{b}r-v_{2}^{k}-b_{v_{2}}^{k}\|_{2}^{2}+\frac {\alpha_{3}}{2}\|r-v_{3}^{k}-b_{v_{3}}^{k}\|_{2}^{2}, \tag{21}\]  
since the \(\ell_{2}\) norm is differentiable, we have the following closed-form solver for \(r\)-sub-problem  
\[(\alpha_{1}S_{r}^{*}S_{r}+\alpha_{2}S_{b}^{*}S_{b}+\alpha_{3}I)r=\alpha_{2}S_ {b}^{*}(v_{2}^{k}+b_{v_{2}}^{k})+\alpha_{3}(v_{3}^{k}+b_{v_{3}}^{k})-\alpha_{1 }S_{r}^{*}(v_{1}^{k}-b_{v_{1}}^{k}-S_{r}o), \tag{22}\]  
where \(I\) is the identity matrix. From [28], the Shearlets transform is constructed to be a Parseval frame, which implies that \(S_{r}^{*}S_{r}=I\), then the \(r\)-sub-problem above can be solved by Fast Fourier Transform (FFT, \(\mathcal{F}\)) efficiently. \[r^{k+1}=\mathcal{F}^{-1}\Big{(}\frac{\alpha_{1}\mathcal{F}(S_{r}^{*}S_{r})+ \alpha_{2}\mathcal{F}(S_{b}^{*}S_{b})+\alpha_{3}\mathcal{F}(I)}{\alpha_{2} \mathcal{F}(S_{b}^{*}(v_{2}^{k}+b_{v_{2}}^{k}))+\alpha_{3}\mathcal{F}(v_{3}^{k }+b_{v_{3}}^{k})-\alpha_{1}\mathcal{F}(S_{r}^{*}(v_{1}^{k}-b_{v_{1}}^{k}-S_{r }o))}\Big{)}, \tag{23}\]  
where \(\mathcal{F}^{-1}\) represents the Fast Inverse Fourier Transform. In the end, the constrains for \(r\geq 0\) and \(b\geq 0\) can be projected by the following formula:  
\[ \begin{split} r^{k+1}&=\min(o,\max(r^{k+1},0));\\ b^{k+1}&=\min(o,\max(o-r^{k+1},0));\end{split}  \tag{24}\]  
Having explained the main idea of our method, the final resulting algorithm is displayed in Algorithm 1.