Maximum-Likelihood Template Matching

This algorithm features a robust measure of matching and an efficient search technique.

An improved algorithm for detecting gray-scale and binary templates in digitized images has been devised. The greatest difference between this algorithm and prior template-detecting algorithms stems from the measure used to determine the quality or degree of match between a template and given portion of an image. This measure is based on a maximum-likelihood formulation of the template- matching problem; this measure, and the matching performance obtained by use of it, are more robust than are those of prior template-matching algorithms, most of which utilize a sum-of-squared-differences measure. Other functions that the algorithm performs along with template matching include subpixel localization, estimation of uncertainty, and optimal selection of features. This algorithm is expected to be useful for detecting templates in digital images in a variety of applications, including recognition of objects, ranging by use of stereoscopic images, and tracking of moving objects or features. (For the purpose of tracking, features or objects recognized in an initial image could be used as templates for matching in subsequent images of the same scene.)

For the sake of computational simplicity, the present version of the algorithm involves two-dimensional edge and intensity templates, the pose space of which is restricted to translations in the image plane; however, it is possible, in principle, to extend the algorithm to more complex cases. The basic image-matching technique used in the algorithm utilizes a prior maximum-likelihood formulation of edge template matching that has been extended to include matching of grayscale templates. In this formulation, one generates a function that assigns a likelihood to each of the possible positions of a template. In an application in which a single instance of the template appears in the image, (e.g., tracking or stereoscopy), one accepts the template position with the highest likelihood if the matching uncertainty is below a specified threshold. In other recognition applications, one accepts all template positions with likelihoods greater than some threshold value.

The search for the template position( s) is performed according a variant of a multiresolution technique that makes it unnecessary to consider all pos- sible template positions explicitly, yet makes it possible to find the best template position(s) in a discretized search space. In this technique, the space of model positions is divided into rectilinear cells and the cells are tested to determine which (if any) contain positions that satisfy a likelihood-based acceptance criterion. The cells that pass the test are divided into subcells, which are examined recursively, and the rest are pruned.

Inasmuch as the likelihood function measures the probability that each position is an instance of the template, error and uncertainty cause the likelihoodfunction peak that corresponds to that position to be spread over some volume of the pose space. Integration of the likelihood function under the peak yields an improved measure of the quality of the peak as a location of the template. Subpixel localization and estimation of uncertainty are performed by fitting the likelihood surface with a parameterized function at the locations of the peaks. In a stereoscopic or tracking application, the probability of failure to detect the correct position of the template is estimated in a procedure that includes a comparison of the integral of the likelihood under the most likely peak to the integral of the likelihood in the remainder of the pose space.

This work was done by Clark F. Olson of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.nasatech.com/tsp under the Information Sciences category. NPO-21026