# Effective Implementation of Edge-Preserving Filtering on CPU Microarchitectures
## 6 Effective Implementation of Edge-Preserving Filtering  
In the edge-preserving filtering, weight calculation accounts for the largest share of processing time. Thus, we consider the implementation of the weight calculation. There are three approaches for the arithmetic computation of the weight function [47]: direct computation, by using LUTs and a combination of both [47]. Computing of usual arithmetic functions has lower cost than the transcendental functions, i.e., exp, log, sin and cos, or heavy algebraic functions, e.g., sqrt. For the high-cost function, the LUT is effective when arithmetic computing is a bottleneck. By contrast, computing is valid when memory I/O is a bottleneck. We can control the trade-off by using the LUT and computation. In the bilateral filter, the possible types of implementation are as follows:  
* RCSC: range computing spatial computing; range and spatial kernels are directly and separately computed. * MC: merged computing; range and spatial kernels are merged and directly computed. * RCSL: range computing spatial LUT; the range kernel is directly computed, and LUTs are used for the spatial kernel. * RLSC: range LUT spatial computing; LUTs are used for the range kernel, and the spatial kernel is directly computed. * RLSL: range LUT spatial LUT; LUTs are used for both range and spatial kernels. * ML: merged LUT; LUTs are used for the merged range and spatial kernels;
* RqLSL, RLSqL: range (quantized) LUT spatial (quantized) LUT; LUTs are quantized for each range and spatial LUT in RLSL. * MqL: merged quantized LUT; range and spatial kernels are merged, and then, the LUTs are quantized. In the non-local means filtering process, the possible types of implementation are reduced, because the filter does not contain the spatial kernel. The possible types of implementation are as follows:  
* RC: range computing; the range kernel is directly computed. * RL: range LUT; LUTs are used for the range kernel. * RqL: range quantized LUT; quantized LUTs are used for the range kernel. We consider five types of implementation for bilateral filtering, namely, MC, RCSL, RLSL, RqLSL and MqL. Notably, we did not implement the RCSC, RLSC, RLSqL and ML, because the cost of computing the spatial kernel is lower than that of computing the range kernel, and the size of the range/merged LUT is larger than that of the spatial LUT. We also implement three types for non-local means filtering, such as RC, RL and RqL. Note that the pairs of MC/RC, RLSL/RL and RqLSL/RqL are similar without spatial computation. In the MC/RC implementation, weights are directly computed for each iteration. In the bilateral and bilateral non-local means filtering, two exponential terms are computed as one exponential term considering the nature of the exponential function. The implementation is computationally expensive because it involves weight calculation every time. However, this point is not always a drawback. The calculation increases arithmetic intensity, which is the ratio of the number of float-number operations per the amount of the accessed memory data. When the arithmetic intensity is low, the computational time is limited by memory reading/writing [48]. In image processing, arithmetic intensity tends to be low, but the MC/RC implementation improves the arithmetic intensity. Therefore, the MC/RC implementation may be practical in a few cases. RCSL can be applied to filters, which contain a spatial kernel. These filters include the bilateral and bilateral non-local means filters. The exponential term of the range kernel is computed every time, and LUTs are used as the weights of the spatial kernel. The size of the spatial LUT is the kernel size.