# Fast Gaussian Filter Approximations Comparison on SIMD Computing Platforms
## 4 Approximations
### FIR Approximations
#### 4.1.2 Stack Blur and Bell Blur  
The Stack blur algorithm was proposed in [13] to approximate the Gaussian-blurred value of a pixel by a composition of 1D box blurs with increasing radius that simulates the effect of applying the Gaussian kernel. It uses a moving stack of pixels while scanning the image row. The expression of the Stack blur algorithm in one direction is defined as follows:  
\[y_{s}[i]=\sum_{n=i-r}^{i+r}\big{(}r-|n-i|+1\big{)}\,x[n], \tag{7}\]where \(r=r(\sigma)=[C\,\sigma]\) is the radius of the box blur and \(C\) is some constant value. So, the 1D Gaussian kernel (1) is approximated by a piecewise linear function  
\[S_{\sigma}[m]=r-|m|+1=\left\{\begin{aligned} & r-m+1,& \text{if }m>0,\\ & r+m+1,&\text{otherwise}.\end{aligned}\right. \tag{8}\]  
The illustration is provided in Figure 2.  
The idea of fast computation ensues from the following representations:  
\[y_{s}[i]=y_{s}[i-1]-\underbrace{\big{(}x[i-r-1]+x[i-r]+\ldots+x[i-1] \big{)}}_{s_{i}^{out}}+ \tag{9}\] \[+\underbrace{\big{(}x[i]+x[i+1]+\ldots+x[i+r]\big{)}}_{s_{i}^{in}},\]  
\[y_{s}[i+1] =\sum_{n=(i-r)+1}^{(i+r)+1}\big{(}r-|n-i-1|+1\big{)}\,x[n]= \tag{10}\] \[=y_{s}[i]-\underbrace{\big{(}x[i-r]+\ldots+x[i-1]+x[i]\big{)}}_{s _{i+1}^{out}}+\] \[+\underbrace{\big{(}x[i+1]+\ldots+x[i+r]+x[i+r+1]\big{)}}_{s_{i+1} ^{in}},\]  
\[s_{i+1}^{out} =s_{i}^{out}-x[i-r-1]+x[i], \tag{11}\] \[s_{i+1}^{in} =s_{i}^{in}-x[i]+x[i+r+1].\]  
Once we have calculated the value \(y_{s}[i]\) for the \(i\)-th element, the value \(y_{s}[i+1]\) for the \((i+1)\)-th element, due to the form of the kernel, can be obtained just in \(r+1\) subtractions and \(r+1\) additions. Storing the values of \(s^{out}\) and \(s^{in}\), we can obtain the result for \((i+1)\)-th element just by 3 additions and 3 subtractions. Therefore, not considering the initial element in a row (the value for which can be calculated with \(2r+1\) multiplications and \(2r\) additions), computing the Stack blur for a pixel requires 6 additive operations. Note also that the Stack blur result should be normalized by \((r+1)^{2}\).  
Figure 2: Approximation of the Gaussian with \(\sigma=10\) by the Stack blur and Bell blur methods.  
A further extension of the Stack blur idea was described in [14] as Quadratic Stack blur, or Bell blur. It operates as follows:  
\[y_{b}[i+1] =y_{b}[i]-y_{s}[i-r]+y_{s}[i+r+1]= \tag{12}\] \[=y_{b}[i]-\big{(}y_{s}[i-r-1]-s_{i-r}^{out}+s_{i-r}^{in}\big{)}+ \big{(}y_{s}[i+r]-s_{i+r+1}^{out}+s_{i+r+1}^{in}\big{)}.\]  
Computing \(y_{s}[i-r]\) and \(y_{s}[i+r+1]\) according to (9) and (10) requires 6 subtractions and 6 additions in total. Computing the whole result for \((i+1)\)-th element requires 1 more subtraction and 1 more addition, so the total cost is 14 additive operations per element (except for initialization). The result should be normalized by \((2r+1)(r+1)^{2}\).  
The general expression for Bell blur is more complicated:  
\[y_{b}[i]=\sum_{n=i-2r}^{i+2r}\bigg{(}\sum_{m=-r}^{r-|i-n|}\big{(}r-|m|+1\big{)} \bigg{)}x[n], \tag{13}\]  
where \(r=r(\sigma)=[C\,\sigma]\) is the radius of the Stack blur and \(2r\) is the radius of the Bell blur. The kernel (1) is approximated by a piecewise constant function with integer values  
\[B_{\sigma}[n]=\sum_{m=-r}^{r-|n|}\big{(}r-|m|+1\big{)}=\big{(}r+1\big{)}\, \big{(}2r-|n|+1\big{)}-\sum_{m=-r}^{r-|n|}|m|. \tag{14}\]  
The illustration of this approximation is also provided in Figure 2.