Combinatorial Geometry for Shape Representation and Indexing

Abstract

Combinatorial geometry is the study of order and incidence properties of groups of geometric features. Ordering properties for point sets in 2-D and 3-D can be seen as a generalization of ordering properties in 1-D and incidences are configurations of features that are non-generic such as collinearity of points. By defining qualitative shape properties using combinatorial geometry we get a common framework for metric and qualitative representations. Order and incidence form a natural hierarchy together with metric representations in terms of increasing abstraction $Metric = = > Order = = > Incidence$ The problem of recognition can be structured in a similar hierarchy ranging from the recognition of specific objects from specific viewpoints, using calibrated cameras to that of calibration free, view independent recognition of generic objects. Order and incidence relations have invariance properties that make them especially interesting for general recognition problems. We present an algorithm for 3-D object hypothesis generation from single images. The combinatorial properties of triplets of line segments are used to define an index to a model library. This library consists of line segment triplets for object model views. Every indexing of a model triplet by an image triplet is accumulated into a matching matrix between image and model line segments. From this matrix we can evaluate the strength of an hypothesis that a specific object is present.