# Fast Gaussian Filter Approximations Comparison on SIMD Computing Platforms
## 5 Complexity and Accuracy Comparison  
The comparison of the methods in terms of computational complexity, accuracy, and extra memory is summarized in Table 1. The complexity is the number of required operations per pixel for 2D image filtering with a Gaussian kernel. Note that the number of required arithmetic operations is presented per pixel. For several methods, it depends on  
Figure 6: Approximation of Gaussian transfer function with \(\sigma=10\) by the second-order and the third-order VYV filters.  
their internal parameters, the meaning of which can be clarified in the subsection with a description of the corresponding approximation.  
The accuracy of methods was computed by us independently by minimizing the mean square error (MSE) provided by the expression  
\[\text{MSE}=\frac{1}{S}\sum_{n=1}^{S}\big{(}g_{\sigma_{0}}[n]-h[n]\big{)}^{2} \tag{59}\]  
for \(S=500\) points uniformly taken on the interval \([-3\sigma_{0};\,3\sigma_{0}]\) with \(\sigma_{0}=10\). The original [PERSON] paper contained values of error provided by (34) for the second-order filter and \(\sigma=100\), so we re-estimated its error. The PcParab method is the only method that did not require any parameter adjustment by minimizing any function because the coefficients of the parabolas were obtained by solving a system of linear equations. As a result, the obtained \(h[n]\) was just substituted into expression (59) for this method.  
The third-order VYV filter proved to be the most accurate of all the approximations considered. The second-order VYV and the second-order Deriche ones, as well as the PcParab method, were slightly less accurate. At the same time, these approximations are the most computationally expensive. Running sums method with \(k=5\) has almost identical computational complexity but shows an order of magnitude lower accuracy. The first-order Deriche and second-order VYV filters require few operations but show lower accuracy than the others. The Stack and Bell blur approximations do not require multiplicative operations, while the accuracy is acceptable. Among the approximations with piecewise constant functions, the accuracy of Bell blur was higher than all the running sums ones since the number of steps used in Bell blur notation is not limited and is shown (Figures 2 and 3) to be significantly greater than for running sums. Nevertheless, for \(k=5\), the accuracy of the running sums method is very close to Bell blur.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Method** & \# + & \# : & **Error (FP)** & **Error (Quant.)** & **Extra Memory** \\ \hline Direct Gaussian & \(2(K-1)\) & \(2K\) & depends on \(K\) & depends on \(K\) & \(O(1)\) \\ \hline DFT-based convolution (FFT) & \(O(\log K^{2})\) & \(O(\log K^{2})\) & depends on \(K\) & - & impl. defined \\ \hline Stack blur & 12 & 0 & \(9.35\times 10^{-6}\) & \(9.35\times 10^{-6}\) & \(O(1)\) \\ \hline Bell blur & 28 & 0 & \(4.40\times 10^{-6}\) & \(4.40\times 10^{-6}\) & \(O(1)\) \\ \hline Running sums, \(k=3\) & 12 & 6 & \(1.43\times 10^{-5}\) & \(1.43\times 10^{-5}\) & \(O(\max\{h;w\})\) \\ \hline Running sums, \(k=4\) & 16 & 8 & \(7.91\times 10^{-6}\) & \(7.91\times 10^{-6}\) & \(O(\max\{h;w\})\) \\ \hline Running sums, \(k=5\) & 20 & 10 & \(5.11\times 10^{-6}\) & \(5.11\times 10^{-6}\) & \(O(\max\{h;w\})\) \\ \hline PcParab & 22 & 16 & \(1.92\times 10^{-7}\) & \(5.22\times 10^{-6}\) & \(O(\max\{h;w\})\) \\ \hline Deriche (1 st order) & 6 & 8 & \(1.39\times 10^{-5}\) & - & \(O(1)\) \\ \hline Deriche (2 nd order) & 14 & 16 & \(1.80\times 10^{-7}\) & - & \(O(1)\) \\ \hline VYV (2 nd order) & 8 & 12 & \(1.39\times 10^{-7}\) & - & \(O(1)\) \\ \hline VYV (3 rd order) & 12 & 16 & \(5.01\times 10^{-8}\) & - & \(O(1)\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison of the considered methods for Gaussian filtering image with size \(h\times w\) in terms of the number of additions (# +) and multiplications (# ) per pixel, error, and extra memory. For FIR filters, we use kernel of size \(K\times K\).