# Effective Implementation of Edge-Preserving Filtering on CPU Microarchitectures
## 1 Introduction  
Edge-preserving filters [1; 2; 3; 4; 5] are the basic tools for image processing. The representatives of the filters include bilateral filtering [1; 2], non-local means filtering [3] and guided image filtering [4; 5; 6]. These filters are used in various applications, such as image denoising [3; 7], high dynamic range imaging [8], detail enhancement [9; 10; 11], free viewpoint image rendering [12], flash/no-flash photography [13; 14], up-sampling/super resolution [15; 16], alpha matting [5; 17], haze removal [18], optical flow and stereo matching [19], refinement processing in optical flow and stereo matching [20; 21] and coding noise removal [22; 23]. The kernel of the edge-preserving filter can typically be decomposed into range and/or spatial kernels, which depend on the difference between the value and position of reference pixels. Bilateral filtering has a range kernel and a spatial kernel. Non-local means filtering has only a range kernel. The shape of the spatial kernel is invariant across all pixels. By contrast, that of the range kernel is variant; thus, the range kernel is computed adaptively for each pixel. The adaptive computation is expensive. Several acceleration algorithms have been proposed for the bilateral filtering [8; 24; 25; 26; 27; 28; 29; 30; 31; 32] and non-local means filtering [33; 34; 24]. These algorithms reduce the computational order of these filters. The order of the naive algorithm is \(O(r^{2})\), where \(r\) is the kernel radius. The order of the separable approximation algorithms [24; 25] is \(O(r)\), and that of constant-time algorithms [27; 28; 29; 30; 31; 32; 33; 34; 35; 36] is \(O(1)\). The separable approach is faster than the naive; however, the approximation accuracy is low. The constant-time algorithms are faster than the \(O(r^{2})\) and \(O(r)\) approaches in large kernel cases. In the case of multi-channel image filtering with intermediate-sized kernels, the method tends to be slower than the naive algorithms owing to the curse of dimensionality [27], which indicates that the computational cost increases exponentially with increasing dimensions. Furthermore, when the kernel radius is small, the naive algorithm can be faster than the algorithms of the order \(O(r)\) or \(O(1)\) owing to the offset times, which refers to pre-processing and post-processing such as creating intermediate images. In the present study, we focus on accelerating the naive algorithm of the edge-preserving filtering based on the characteristics of computing hardware. The edge-preserving filter usually involves denormalized numbers, which are special floating-point numbers defined in IEEE Standard 754 [37]. The definition of the denormalized numbers is discussed in Section 3. The formats are supported by various computing devices, such as most central processing units (CPUs) and graphics processing units (GPUs). The denormalized numbers represent rather small values that cannot be expressed by normal numbers. Although the denormalized numbers can improve arithmetic precision, their format is different from the normal numbers. Therefore, the processing of the denormalized numbers incurs a high computational cost [38; 39; 40]. The edge-preserving filters have small weight values, where a pixel is across an edge. The values tend to be the denormalized numbers. Figure 1 shows the occurrence of the denormalized numbers in various edge-preserving filtering. The denormalized numbers do not influence the eventual results, because these values are almost zero in the calculations. Hence, we can compute edge-preserving filtering with high-precision even by omitting the denormalized numbers. Moreover, the omission would be critical for accelerating the edge-preserving filtering. Figure 1: Occurrence status of denormalized numbers: (**a**) original image; (**b**) bilateral filter; (**c**) non-local means filter; (**d**) Gaussian range filter; (**e**) bilateral non-local means filter. (**b–e**) present heat maps of the occurrence frequency of denormalized numbers in each kernel.