The 3D Indexing Problem


Thomas M. Breuel
IDIAP
C.P. 609, 1920 Martigny, Switzerland
tmb@idiap.ch


This paper discusses the problem of 3D indexing.  That is, given a
collection of 3D object models (CAD models, formalized as collections
of labeled 3D points), an indexing algorithm may perform off-line
pre-processing to generate a data structure that allows it to decide
quickly whether a given 2D image was contains any of the objects
represented by the 3D models.

We first review and develop some mathematical machinery.  Next, the
indexing problem is related to well-known point-location and search
problems in computational geometry.  Based on such relationships, a
number of asymptotically optimal indexing algorithms are discussed.

We then observe that all algorithms related to this problem that have
been developed in computer vision as well as in computational geometry
show either suboptimal (near-linear) complexity in the number of 3D
models, or require a super-polynomial amount of space to represent the
result of the pre-computation.

Such computational limitations are illustrated by a discussion of
several commonly used approaches to 3D indexing (view-based indexing,
indexing by invariants).

We conclude with the speculation that, ultimately, the situation for
3D indexing algorithms is likely to remain analogous to that of
high-dimensional geometric query problems: while asymptotically
efficient algorithms are known even in high dimensions, most practical
applications use linear time algorithms and are content with methods
that give significant constant-factor speedups.


Keywords: 3D~model base indexing, view sets, point location
algorithms, algebraic varieties, arrangements, visual object
recognition, invariants, geometric hashing, 3D~object recognition,
computational complexity, computational geometry, computer vision.