Reshuffling: a fast algorithm for filtering with arbitrary kernels

A novel method to accelerate the application of linear filters that have multiple identical coefficients on arbitrary kernels is presented. Such filters, including Gabor filters, gray level morphological operators, volume smoothing functions, etc., are widely used in many computer vision tasks. By taking advantage of the overlapping area between the kernels of the neighboring points, the reshuffling technique prevents from the redundant multiplications when the filter response is computed. It finds a set of unique coefficients, constructs a set of relative links for each coefficient, and then sweeps through the input data by accumulating the responses at each point while applying the coefficients using their relative links. Dual solutions, single input access and single output access, that achieve 40 % performance improvement are provided. In addition to computational advantage, this method keeps a minimal memory imprint, which makes it an ideal method for embedded platforms. The effects of quantization, kernel size, and symmetry on the computational savings are discussed. Results prove that the reshuffling is superior to the conventional approach