Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Probabilistic Indexing: Recognizing 3D Objects from 2D Images Using the Probabilistic Peaking Effect

Clark F. Olson

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-93-733
May 1993

http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-733.pdf

Recent papers have shown that indexing is a promising approach to fast model-based object recognition because it allows most of the possible matches between image point groups and model point groups to be quickly eliminated from consideration. Current indexing systems for the problem of recognizing three-dimensional objects from single two-dimensional images require groups of four points to generate a key into the table of model groups and each model group must be represented over an infinite subspace of a multi-dimensional table. We present a system that is capable of indexing using groups of three points by taking advantage of the probabilistic peaking effect. Each model group need only be represented at one point in the index table. To be able to index using groups of three points, we must allow false negatives for point group matches. If there are n model points present in the image, there are O( n^3) groups of three correct model points, so we can withstand negatives by examining information from multiple groups. Since we are able to index on smaller groups of points, indexing can be used with an additional set of algorithms with lower computational complexity. This system can utilize larger point groups to increase accuracy in discriminating between correct and incorrect matches. Results are given on real and synthetic data.


BibTeX citation:

@techreport{Olson:CSD-93-733,
    Author = {Olson, Clark F.},
    Title = {Probabilistic Indexing:  Recognizing 3D Objects from 2D Images Using the Probabilistic Peaking Effect},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {May},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6028.html},
    Number = {UCB/CSD-93-733},
    Abstract = {Recent papers have shown that indexing is a promising approach to fast model-based object recognition because it allows most of the possible matches between image point groups and model point groups to be quickly eliminated from consideration. Current indexing systems for the problem of recognizing three-dimensional objects from single two-dimensional images require groups of four points to generate a key into the table of model groups and each model group must be represented over an infinite subspace of a multi-dimensional table. We present a system that is capable of indexing using groups of three points by taking advantage of the probabilistic peaking effect. Each model group need only be represented at one point in the index table. To be able to index using groups of three points, we must allow false negatives for point group matches. If there are <i>n</i> model points present in the image, there are <i>O</i>(<i>n</i>^3) groups of three correct model points, so we can withstand negatives by examining information from multiple groups. Since we are able to index on smaller groups of points, indexing can be used with an additional set of algorithms with lower computational complexity. This system can utilize larger point groups to increase accuracy in discriminating between correct and incorrect matches. Results are given on real and synthetic data.}
}

EndNote citation:

%0 Report
%A Olson, Clark F.
%T Probabilistic Indexing:  Recognizing 3D Objects from 2D Images Using the Probabilistic Peaking Effect
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/CSD-93-733
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6028.html
%F Olson:CSD-93-733