The graph Laplacian operator, which originated in spectral graph theory, is commonly used for learning applications such as spectral clustering and embedding. In this paper we explore the Laplacian distance, a distance function related to the graph Laplacian, and use it for visual search. We show that previous techniques such as Matching by Tone Mapping (MTM) are particular cases of the Laplacian distance. Generalizing the Laplacian distance results in distance measures which are tolerant to various visual distortions. A novel algorithm based on linear decomposition makes it possible to compute these generalized distances efficiently. The proposed approach is demonstrated for tone mapping invariant, outlier robust and multimodal template matching.

We present an efficient and noise robust template matching method based on asymmetric correlation (ASC). The ASC similarity function is invariant to affine illumination changes and robust to extreme noise. It correlates the given non-normalized template with a normalized version of each image window in the frequency domain. We show that this asymmetric normalization is more robust to noise than other cross correlation variants, such as the correlation coefficient. Direct computation of ASC is very slow, as a DFT needs to be calculated for each image window independently. To make the template matching efficient, we develop a much faster algorithm, which carries out a prediction step in linear time and then computes DFTs for only a few promising candidate windows. We extend the proposed template matching scheme to deal with partial occlusion and spatially varying light change. Experimental results demonstrate the robustness of the proposed ASC similarity measure compared to state-of-the-art template matching methods.

This paper presents a simple and efficient method to convolve an image with a Gaussian kernel. The computation is performed in a constant number of operations per pixel using running sums along the image rows and columns. We investigate the error function used for kernel approximation and its relation to the properties of the input signal. Based on natural image statistics we propose a quadratic form kernel error function so that the SSD error of the output image is minimized. We apply the proposed approach to approximate the Gaussian kernel by linear combination of constant functions. This results in a very efficient Gaussian filtering method. Our experiments show that the proposed technique is faster than state of the art methods while preserving similar accuracy.

Non uniform kernels is important for many image processing algorithms. However, for large kernel sizes the filtering can become computationally expensive. We introduce cosine integral images (CII) which represent a large set of spatial and range filters, based on their frequency decomposition. The filtering requires a constant number of operations per image pixel, independent of filter size. We make use of CII to compute the Gabor filters, whose complexity is for the first time a constant O(l) operations per image pixel. We also improve previous constant time approximations of spatial Gaussian smoothing and bilateral filtering.