@article {14890,
	title = {The space requirements of indexing under perspective projections},
	journal = {Pattern Analysis and Machine Intelligence, IEEE Transactions on},
	volume = {18},
	year = {1996},
	month = {1996/03//},
	pages = {330 - 333},
	abstract = {Object recognition systems can be made more efficient through the use of table lookup to match features. The cost of this indexing process depends on the space required to represent groups of model features in such a lookup table. We determine the space required to perform indexing of arbitrary sets of 3D model points for lookup from a single 2D image formed under perspective projection. We show that in this case, one must use a 3D surface to represent model groups, and we provide an analytic description of such a surface. This is in contrast to the cases of scaled-orthographic or affine projection, in which only a 2D surface is required to represent a group of model features. This demonstrates a fundamental way in which the recognition of objects under perspective projection is more complex than is recognition under other projection models},
	keywords = {2D, complexity;feature, complexity;table, extraction;image, hashing;indexing, image, images;3D, lookup;, lookup;computational, matching;geometric, matching;indexing;object, model, points;feature, process;invariants;object, processing;table, projections;space, recognition;perspective, recognition;stereo},
	isbn = {0162-8828},
	doi = {10.1109/34.485561},
	author = {Jacobs, David W.}
}
@article {14888,
	title = {Space and time bounds on indexing 3D models from 2D images},
	journal = {Pattern Analysis and Machine Intelligence, IEEE Transactions on},
	volume = {13},
	year = {1991},
	month = {1991/10//},
	pages = {1007 - 1017},
	abstract = {Model-based visual recognition systems often match groups of image features to groups of model features to form initial hypotheses, which are then verified. In order to accelerate recognition considerably, the model groups can be arranged in an index space (hashed) offline such that feasible matches are found by indexing into this space. For the case of 2D images and 3D models consisting of point features, bounds on the space required for indexing and on the speedup that such indexing can achieve are demonstrated. It is proved that, even in the absence of image error, each model must be represented by a 2D surface in the index space. This places an unexpected lower bound on the space required to implement indexing and proves that no quantity is invariant for all projections of a model into the image. Theoretical bounds on the speedup achieved by indexing in the presence of image error are also determined, and an implementation of indexing for measuring this speedup empirically is presented. It is found that indexing can produce only a minimal speedup on its own. However, when accompanied by a grouping operation, indexing can provide significant speedups that grow exponentially with the number of features in the groups},
	keywords = {2D, bounds;time, bounds;visual, extraction;grouping, features;model, features;model-based, images;3D, indexing;feature, model, operation;image, pattern, picture, processing;, recognition, recognition;computerised, recognition;space, systems;computerised},
	isbn = {0162-8828},
	doi = {10.1109/34.99235},
	author = {Clemens,D. T and Jacobs, David W.}
}
