# Fast Gaussian Filter Approximations Comparison on SIMD Computing Platforms
## 3 Gaussian Filtering
### Basic Optimizations  
One can see that the values of the Gaussian kernel decrease as the argument moves away from zero, and this kernel goes to zero at infinity. However, an infinite-size mask cannot be used in computations. For very large positive or negative arguments, the values of the Gaussian kernel become so small that they can be ignored, and the computations can be focused only in the neighborhood of zero; such an optimization is called \"truncation of the tails\". A three-sigma rule of thumb states that, if the mask is of size \(K\times K\), then \(K\) should roughly equal \(2\pi\sigma\approx 6\sigma\). That would capture about 99.73% of the non-zero values of the Gaussian function. Then, convolution will have the following form:  
\[y[i,j]=\sum_{m=-M}^{M}\sum_{n=-M}^{M}g_{\sigma}[m,n]\,x[i-m,j-n], \tag{2}\]where \(x[i,j]\) denotes the value of \((i,j)\)-th pixel of image \(x\), \(y[i,j]\) is the resulting value of \((i,j)\)-th pixel of output image \(y\), and \(K=2M+1\). The illustration of how discrete convolution works is provided below (Figure 1).  
Applying this operation to each image pixel \(x\), we obtain the values of output image \(y\), the convolution result. There will be a problem related to boundary pixels: the closer a pixel is to the image boundaries, the more of the mask lies outside the image. There are two standard solutions to deal with such a border issue. The first variant ignores border pixels and performs convolution only for those pixels for which this is possible. The second one is to define boundary pixel neighborhoods or by some extrapolation. It can be set to constant values, mirrored, etc.  
The important thing that makes the Gaussian mask attractive is the fact that it is separable. It is illustrated by the following expression:  
\[y[i,j] =\frac{1}{2\pi\sigma^{2}}\sum_{m=-M}^{M}\sum_{n=-M}^{M}e^{-\frac{1 }{2}\left(\frac{m^{2}\sigma^{2}}{\sigma^{2}}\right)}x[i-m,j-n]= \tag{3}\] \[=\sum_{m=-M}^{M}\frac{1}{\sqrt{2\pi\sigma}}e^{-\frac{1}{2}\left( \frac{m^{2}}{\sigma^{2}}\right)}\cdot\sum_{n=-M}^{M}\frac{1}{\sqrt{2\pi\sigma} }e^{-\frac{1}{2}\left(\frac{m^{2}}{\sigma^{2}}\right)}x[i-m,j-n]=\] \[=\sum_{m=-M}^{M}g_{\sigma}[m]\cdot\sum_{n=-M}^{M}g_{\sigma}[n]\,x [i-m,j-n].\]  
So, the convolution with a 2D Gaussian kernel can be decomposed into a pair of convolutions with 1D Gaussian kernels: one vertical and one horizontal. It is important to note that this decomposition is not itself an approximation and still provides an exact result.  
The representation provided by (3) renders applying the Gaussian filtering much computationally cheaper. If we do not consider the Gaussian kernel's separability, we will perform \(K^{2}\) multiplications and \(K^{2}-1\) additions per pixel to convolve a 2D image with a 2D kernel. Convolution with a 1D kernel requires \(K\) multiplications and \((K-1)\) additions per pixel, and filtering with a separable 2D kernel only doubles the cost of the 1D case. So, utilizing the separability property, the computational cost is reduced to \(2K\) multiplications and \(2(K-1)\) additions per pixel. The kernel separability already allows us to reduce the computational complexity by one order.  
In the following, we will use the separability property throughout, so all further description is limited to the consideration of one-dimensional filters.