| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
The Space Requirements of Indexing Under Perspective Projections
March 1996 (vol. 18 no. 3)
pp. 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 3-D model points for lookup from a single 2-D image formed under perspective projection. We show that in this case, one must use a 3-D 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 2-D surface is required to represent a group of model features [[3]], [[10]]. This demonstrates a fundamental way in which the recognition of objects under perspective projection is more complex than is recognition under other projection models.
[1] 330 T. Breuel, "The 3D indexing problem," IDIAP Memo 93-08, 1993.[2] J. Burns, R. Weiss, and E. Riseman, "The non-existence of general-case view-invariants," Geometric Invariance in Computer Vision, J. Mundy, and A. Zisserman, eds., Cambridge: MIT Press, 1992.[3] D. Clemens and D. Jacobs, "Space and time bounds on model indexing," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 10, pp. 1,007-1,018, 1991.[4] D. Cyganski and J.A. Orr, "Applications of tensor theory to object recognition and orientation determination," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 7, no. 6, pp. 662-673, 1985.[5] O. Faugeras, "What can be seen in three dimensions with an uncalibrated stereo rig?" Second European Conf. Computer Vision, pp. 563-578, 1992.[6] D. Forsyth, J.L. Mundy, A. Zisserman, C. Coelho, A. Heller, and C. Rothwell, "Invariant descriptors for 3-D object recognition and pose," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 10, pp. 971-991, 1991.[7] D. Jacobs, "Space efficient 3D model indexing," IEEE Conf. Computer Vision and Pattern Recognition, pp. 439-444, 1992.[8] D. Jacobs, "Recognizing 3-D objects using 2-D images," MIT AI TR-1416, 1992.[9] D. Jacobs, "2-D Images of 3-D oriented points," IEEE Conf. Computer Vision and Pattern Recognition, pp. 226-232, 1993.[10] D. Jacobs, "Matching 3-D models to 2-D Images," Int'l J. Computer Vision. forthcoming [11] Y. Lamdan, J.T. Schwartz, and H.J. Wolfson, "Affine invariant model-based object recognition," IEEE Trans. Robotics and Automation, vol. 6, pp. 578-589, 1990.[12] Y. Lamdan and H.J. Wolfson, "Geometric hashing: A general and efficient model-based recognition scheme," Second Int'l Conf. Computer Vision, pp. 238-249, 1988.[13] Y. Moses and S. Ullman, "Limitations of non model-based recognition schemes," Second European Conf. Computer Vision, pp. 820-828, 1992.[14] C. Rothwell, D. Forsyth, A. Zisserman, and J. Mundy, "Extracting projective structure from single perspective view of 3D point sets," Proc. Fourth Int'l Conf. Computer Vision, pp. 573-582, 1993.[15] A. Shashua, "On geometric and algebraic aspects of 3D affine and projective structures from perspective 2D views," Proc. Second Workshop on Applications of Invariance in Computer Vision, pp. 87-112, 1993.[16] A. Tuller, A Modern Introduction to Geometries.Princeton: D. Van Nostrand Company, Inc., 1967.[17] A. Wallack and J. Canny, "Efficient indexing techniques for model based sensing," IEEE Conf. Computer Vision and Pattern Recognition, pp. 259-266, 1994.[18] I. Weiss, "Projective invariants of shape," DARPA IU Workshop, pp. 1,125-1,134, 1988.[19] M. Werman and D. Weinshall, "Complexity of indexing: Efficient and learnable large database indexing," Hebrew Univ. Tech. Report No. 95-7, 1995.
Index Terms:
Indexing, invariants, perspective projection, geometric hashing, 3-D objects, 2-D images, object recognition, space, complexity.
Citation:
David W. Jacobs, "The Space Requirements of Indexing Under Perspective Projections," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 3, pp. 330-333, Mar. 1996, doi:10.1109/34.485561
