Fast triangular binning kernel approximations for weighted gradient histogram creation

The implementation of weighted gradient histograms are studied. Such histograms are commonly used in computer vision methods, and their creation can make up a significant portion of the computational cost. Further, due to potentially severe aliasing, non-uniform binning kernels are desirable. We show that previously presented fast methods for uniform binning kernels can be extended to non-uniform binning, and that the triangular kernel can be well approximated for common weighting strategies. The approximation is implemented with sums and products of projections of the gradient samples on specially chosen vectors. Consequently, only a few standard arithmetic operations are required, and therefore, the suggested implementation has a significantly lower computational cost when compared with an implementation in which the gradient argument and magnitude are explicitly evaluated. Finally, the frequency components of the different kernels are studied to quantify the fundamental gain achieved by using triangular kernels instead of uniform kernels.