Using approximation and randomness to speed-up intensive linear filtering

This paper investigates the usefulness of approximation and randomness in linear filtering in order to decrease computation time. Pouring inspiration from Compressive Sensing techniques, we implement the convolution product operation using a fewer number of samples from the convolution kernel. Depending on the use case, either the higher values of the kernel or a random subset of them are used. Three applications of the principle are used to illustrate the approach: Gabor filters, quick-look production and disparity map estimation by linear correlation.