Fast Alignment by Eliminating Unlikely Matches

Clark F. Olson

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-92-704

, 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-704.pdf

The alignment method is a model-based object recognition technique that determines possible object transformations from three hypothesized matches of model and image points. In the absence of grouping, the alignment method must examine each possible matching of three model points with three image points. Thus, if m is the number of model features and n is the number of image features, this method requires O(m^3n^3) transformations to be computed. Each of these transformations must then be tested to determine whether it is correct, a time consuming step itself. For images and/or models with many features, the running time of the alignment method is not satisfactory, even in the presence of current grouping techniques. This paper presents methods of reducing the number of matches that must be examined. The techniques we describe are: 1) using the probabilistic peaking effect to eliminate unlikely matches, 2) examining the algorithm used to produce the transformation and eliminating model groups likely to produce large errors, 3) eliminating image groups likely to produce large errors. Results are presented that show we can achieve a speedup of over two orders of magnitude faster while still finding the best transformation.

BibTeX citation:

@techreport{Olson:CSD-92-704,
    Author= {Olson, Clark F.},
    Title= {Fast Alignment by Eliminating Unlikely Matches},
    Year= {1992},
    Month= {Oct},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6254.html},
    Number= {UCB/CSD-92-704},
    Abstract= {The alignment method is a model-based object recognition technique that determines possible object transformations from three hypothesized matches of model and image points. In the absence of grouping, the alignment method must examine each possible matching of three model points with three image points.  Thus, if <i>m</i> is the number of model features and <i>n</i> is the number of image features, this method requires <i>O</i>(<i>m</i>^3<i>n</i>^3) transformations to be computed. Each of these transformations must then be tested to determine whether it is correct, a time consuming step itself. For images and/or models with many features, the running time of the alignment method is not satisfactory, even in the presence of current grouping techniques. <p>This paper presents methods of reducing the number of matches that must be examined. The techniques we describe are: 1) using the probabilistic peaking effect to eliminate unlikely matches, 2) examining the algorithm used to produce the transformation and eliminating model groups likely to produce large errors, 3) eliminating image groups likely to produce large errors. Results are presented that show we can achieve a speedup of over two orders of magnitude faster while still finding the best transformation.},
}

EndNote citation:

%0 Report
%A Olson, Clark F. 
%T Fast Alignment by Eliminating Unlikely Matches
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-704
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6254.html
%F Olson:CSD-92-704