# Mapping a Guided Image Filter on the HARP Reconfigurable Architecture Using OpenCL
## 5 Guided Image Filtering
### Algorithm  
A guided filter uses a guidance image \(G\), to transform an input image \(I\) into an output image \(O\). The output pixels are a linear transform of the guidance image pixels in a square window \(\omega_{k}\) surrounding each pixel:  
\[O_{i}=a_{k}G_{i}+b_{k} \tag{1}\]  
The coefficients \(a_{k}\) and \(b_{k}\) are calculated such that the difference between the input image \(I\) and output image \(O\) is minimized according to the following criterion: minimize \(E(a_{k},b_{k})\) where  
\[E(a_{k},b_{k})=\sum_{i\in\omega_{k}}((O_{i}-I_{i})^{2}+\epsilon a_{k}^{2}) \tag{2}\]  
and \(O_{i}\) is given by (2). \(\epsilon\) is chosen to constrain the values of \(a_{k}\). The solution of (1) subject to minimizing (2) is  
\[a_{k} = \frac{\frac{1}{|\omega|}\sum_{i\in\omega_{k}}G_{i}I_{i}-\mu_{k} \overline{I}_{k}}{\sigma_{k}^{2}+\epsilon}\] \[b_{k} = \overline{I}_{k}-a_{k}\mu_{k}\]  
where \(\mu_{k}\) and \(\sigma_{k}^{2}\) are the mean and variance of \(G\) in region \(\omega_{k}\) and \(\overline{I}_{k}\) is the mean of the input pixels in \(\omega_{k}\)[15].  
To obtain the same linear transformation for all pixels in \(\omega_{k}\) of Equation (1), the coefficients \(a_{k}\) and \(b_{k}\) are averaged in \(\omega_{k}\), leading to  
\[O_{i}=\frac{1}{|\omega|}\sum_{k|i\in\omega_{k}}(a_{k}G_{i}+b_{k}) \tag{3}\]  
or  
\[O_{i}=\overline{a}_{i}G_{i}+\overline{b}_{i} \tag{4}\]  
with \(\overline{a}_{i}=\frac{1}{|\omega|}\sum_{k\in\omega_{i}}a_{k}\) and \(\overline{b}_{i}=\frac{1}{|\omega|}\sum_{k\in\omega_{i}}b_{k}\).  
The gray-scale filter readily extends to color images. In that case, the pixel and coefficients \(a_{i}\) and \(b_{i}\) become \(3\times 1\) vectors, and due to the linearity, the color output is calculated as  
\[\mathbf{O_{i}}=\mathbf{a}_{i}^{\mathsf{T}}\mathbf{G}_{i}+\mathbf{b_{i}}, \quad\forall i\in\omega_{k} \tag{5}\]  
The guided image filter algorithm consists of five steps, which are displayed in pseudo-code in Algorithm 1. The algorithm has four input parameters, filtering input \(I\), guidance input \(G\), filtering radius \(r\) and a regularization parameter \(\epsilon\), and has one output, the filtering output \(O\)[15].  
In a first step, the function \(f_{mean,r}\) is applied. \(f_{mean,r}\) calculates the mean of all pixels within a square window of size \((2r+1)\times(2r+1)=5\times 5\), where \(r=2\) is the radius of the window. A radius of 2 leads to a square window in which all values within a distance of 2 pixels of the central pixel are considered. This function is applied to the filtering input, the guidance input, the filtering input multiplied by the guidance input, and the guidance input multiplied by itself. The multiplication of two images is executed pixel-wise, as denoted by the point-wise multiplication \(.*\). Based on the values calculated in Step 1, the variance of the guidance input, \(var_{G}\), and the covariance of the filtering input multiplied by the guide input, \(cov_{IG}\), is calculated for each pixel in Step 2. In Step 3, images \(a\) and \(b\) are calculated using the previously calculated \(var_{G}\) and \(cov_{IG}\), and using the regularization parameter \(\epsilon\). Then, in Step 4, images \(a\) and \(b\) are filtered using the same \(f_{mean,r}\) as used in Step 1, which results in images \(mean_{a}\) and \(mean_{b}\). Finally, in Step 5, the filtering output is calculated as \(mean_{a}\cdot*G+mean_{b}\).  
The number of floating-point operations is given in Table 2.