Time and Space Efficient Pose Clustering

Clark F. Olson

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-93-755

, 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-755.pdf

Pose clustering is a method of object recognition that determines the transformations that align hypothesized matches of groups of image and model features: an object that appears in an image corresponds to a large cluster of transformations in pose space close to the correct pose of the object. If there are m model features and n image features, then there are O(m^3n^3) transformations to consider for the case of recognition of three-dimensional objects from feature points in two-dimensional images. I show that pose clustering can be equally accurate when examining only O(mn) transformations, due to correlation between the transformations, if we are given two correct matches between model features and image features. Since we do not usually know two correct matches in advance, this property is used with randomization to decompose the pose clustering problem into O(n^2) problems, each of which clusters O(mn) transformations, for a total complexity of O(mn^3). Besides reducing the time necessary to perform pose clustering, this method requires much less memory and makes the use of accurate clustering algorithms less costly. Further time reductions can be gained by using grouping to determine the initial matches.

BibTeX citation:

@techreport{Olson:CSD-93-755,
    Author= {Olson, Clark F.},
    Title= {Time and Space Efficient Pose Clustering},
    Year= {1993},
    Month= {Jul},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6281.html},
    Number= {UCB/CSD-93-755},
    Abstract= {Pose clustering is a method of object recognition that determines the transformations that align hypothesized matches of groups of image and model features: an object that appears in an image corresponds to a large cluster of transformations in pose space close to the correct pose of the object. If there are <i>m</i> model features and <i>n</i> image features, then there are <i>O</i>(<i>m</i>^3<i>n</i>^3) transformations to consider for the case of recognition of three-dimensional objects from feature points in two-dimensional images. I show that pose clustering can be equally accurate when examining only <i>O</i>(<i>mn</i>) transformations, due to correlation between the transformations, if we are given two correct matches between model features and image features. Since we do not usually know two correct matches in advance, this property is used with randomization to decompose the pose clustering problem into <i>O</i>(<i>n</i>^2) problems, each of which clusters <i>O</i>(<i>mn</i>) transformations, for a total complexity of <i>O</i>(<i>mn</i>^3). Besides reducing the time necessary to perform pose clustering, this method requires much less memory and makes the use of accurate clustering algorithms less costly. Further time reductions can be gained by using grouping to determine the initial matches.},
}

EndNote citation:

%0 Report
%A Olson, Clark F. 
%T Time and Space Efficient Pose Clustering
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/CSD-93-755
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6281.html
%F Olson:CSD-93-755