Signal Processing in Communications
João Marcos Travassos Romano, Charles C. Cavalcante · 2015
Template matching is a technique widely used for finding patterns in digital images. It is very desirable that template matching should be able to detect template instances that have undergone geometric transformations like rotation and scaling. The obvious “brute force” solution executes a series of conventional template matchings between the search image and the query template rotated by every angle, translated to every position, and scaled by every factor. Clearly, this takes too long and thus is not practical. In this chapter, we describe two rotation and scale invariant template matchings that substantially accelerate this process. The first is called Ciratefi and consists of three cascaded filters that successively exclude pixels that have no chance of matching the template. This algorithm is especially suited for parallel implementations, because similar sequence of operations is applied to all pixels. The second is called Forapro and uses the complex coefficients of the discrete Fourier transform of circular and radial projections to efficiently compute rotation-invariant local features. Once the local features are computed, many different templates can be quickly localized in the search image. Thus, this algorithm is suitable for: multi-scale searching; searching many different query templates in a search image; and partial occlusion-robust template matching.