The 3D Indexing Problem
Type of publication:  IdiapRR 
Citation:  breuel93.04 
Number:  IdiapRR081993 
Year:  1993 
Institution:  IDIAP 
Abstract:  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 offline preprocessing 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 wellknown pointlocation 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 (nearlinear) complexity in the number of 3D models, or require a superpolynomial amount of space to represent the result of the precomputation. Such computational limitations are illustrated by a discussion of several commonly used approaches to 3D indexing (viewbased 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 highdimensional 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 constantfactor speedups. 
Userfields:  ipdmembership={vision}, 
Keywords:  3D~model base indexing, 3D~object recognition, algebraic varieties, arrangements, computational complexity, computational geometry, computer vision., geometric hashing, invariants, point location algorithms, view sets, visual object recognition 
Projects 
Idiap 
Authors  
Added by:  [UNK] 
Total mark:  0 
Attachments


Notes


