Fast matching techniques utilizing integral images.
详细信息
文摘
Many applications in computer vision require finding a particular pattern or shape in images and video sequences. This problem is sometimes referred to as pattern matching. A standard approach is to scan the entire image and evaluate a match measure between the pattern and a local sub-window in the image. Due to the fact that this naive approach is very time-consuming, many speedy algorithms have been proposed in the literature. This dissertation focuses on utilizing a sophisticated data structure called integral image to speed up matching techniques. Rejection schemes have been used to accelerate the matching process. These techniques compute either a lower or an upper bound on the match measure. We generalize this idea and show how to utilize both lower and upper bounds to further improve the performance. Specifically, we describe an algorithm that uses such bounds to detect the k best matches for any value of k provided by the user. Its runtime compares favorably with existing methods. We show that this approach can be used for pattern detection according to the l2 norm and according to the classic normalized cross-correlation criterion. Our approach to accelerate the speed of exact matching algorithms requires patterns to be specified over rectangular regions. This assumption is also common in other studies. However, in some cases it is desirable to define patterns over more complex regions. We describe an extension of our work for patterns of irregular shapes. Identifying patterns, irrespective of their orientation and scale, is an important component of many practical computer vision systems. The standard approach is to detect multiple copies of the original patterns, which further reduces the speed of the matching process. We propose an algorithm that can be applied to detect patterns at arbitrary scales and rotations without generating multiple patterns. It requires modification of the classic integral image data structure to enable good performance in very large images. Many recent studies on template matching employ fast transforms, in particular the Walsh-Hadamard Transform WHT). These techniques use a small number of Walsh transform coefficients at multiple image locations. We have improved the current state of the art by showing how to efficiently compute such coefficients based on the integral image technique.