| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Indexing without Invariants in 3D Object Recognition
October 1999 (vol. 21 no. 10)
pp. 1000-1015
Abstract—We present a method of indexing three-dimensional objects from single two-dimensional images. Unlike most other methods to solve this problem, ours does not rely on invariant features. This allows a richer set of shape information to be used in the recognition process. We also suggest the $k$d-tree as an alternative indexing data structure to the standard hash table. This makes hypothesis recovery more efficient in high-dimensional spaces, which are necessary to achieve specificity in large model databases. Search efficiency is maintained in these regimes by the use of Best-Bin First search, a modified $k$d-tree search algorithm which locates approximate nearest-neighbors. Neighbors recovered from the index are used to generate probability estimates, local within the feature space, which are then used to rank hypotheses for verification. On average, the ranking process greatly reduces the number of verifications required. Our approach is general in that it can be applied to any real-valued feature vector. In addition, it is straightforward to add to our index information from real images regarding the true probability distributions of the feature groupings used for indexing. In this paper, we provide experiments with both synthetic and real images, as well as details of the practical implementation of our system, which has been applied in the domain of telerobotics.
[1] 1000 E. Barrett,P. Payton,N. Haag,, and M. Brill,“General methods for determining projective invariants in imagery,” CVGIP:IU, vol. 53, pp. 45-65, 1991.[2] J.B. Burns, R.S. Weiss, and E.M. Riseman, "View Variation of Point-Set and Line-Segment Features," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 1, pp. 51-68, Jan. 1993.[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. Forsyth, J.L. Mundy, A. Zisserman, and C.M. Brown, “Invariance—A New Framework for Vision,” Proc. Int'l Conf. Computer Vision '90, pp. 598-605, 1990.[5] 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.[6] 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.[7] C.A. Rothwell, A. Zisserman, J.L. Mundy, and D.A. Forsyth, “Efficient Model Library Access by Projectively Invariant Indexing Functions,” Proc. Computer Vision and Pattern Recognition '92, pp. 109-114, 1992.[8] P. Wayner, "Efficiently using invariant theory for model-based matching," Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 473-478, 1991.[9] J.S. Beis, “Indexing without Invariants in Model-Based Object Recognition,” PhD thesis, Univ. of British Columbia, June 1997.[10] M.D. Wheeler and K. Ikeuchi, “Sensor Modelling, Probabilistic Hypothesis Generation, and Robust Localization for Object Recognition,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 3, pp. 252-265, Mar. 1995.[11] I. Shimshoni and J. Ponce, “Probabilistic 3D Object Recognition,” Proc. Int'l Conf. Computer Vision '95, pp. 488-493, 1995.[12] W.E.L. Grimson and D.P. Huttenlocher,“On the sensitivity of geometric hashing,” Proc. Int’l Conf. Computer Vision, pp. 334-338, 1990.[13] F. Stein and G. Medioni, "Structural Indexing: Efficient 2D Object Recognition," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 12, pp. 1,198-1,204, Dec. 1992.[14] F. Stein and G. Medioni, “Structural Indexing: Efficient 3-D Object Recognition,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 2, pp. 125–145, 1992.[15] J.S. Beis and D.G. Lowe, “Shape Indexing Using Approximate Nearest-Neighbor Search in High-Dimensional Spaces,” Proc. Computer Vision and Pattern Recognition '97, pp. 1,000-1,006, June 1997.[16] A. Califano and R. Mohan, "Multidimensional Indexing for Recognizing Visual Shapes," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 4, pp. 373-392, 1994.[17] S.J. Dickinson, A.P. Pentland, and A. Rosenfeld, "3D Shape Recovery Using Distributed Aspect Matching," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 2, pp. 174-198, Feb. 1992.[18] S.J. Dickinson, A.P. Pentland, and A. Rosenfeld, “From Volumes to Views: An Approach to 3D Object Recognition,” CVGIP: Image Understanding, vol. 55, no. 2, pp. 130-154, Mar. 1992.[19] R.C. Nelson and A. Selinger, “Large-Scale Tests of a Keyed, Appearance-Based 3-D Object Recognition System,” Vision Research, vol. 38, no. 15, pp. 2,469-2,488. 1998,[20] C. Schmid and R. Mohr, “Local Grayvalue Invariants for Image Retrieval,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 5, pp. 530-535, May 1997.[21] H. Murase and S.K. Nayar, “Visual Learning and Recognition of 3-D Objects from Appearance,” Int'l J. Computer Vision, vol. 14, pp. 5-24, 1995.[22] B. Schiele and J. Crowley, “Probabilistic Object Recognition Using Multidimensional Receptive Field Histograms,” Proc. 13th Int'l Conf. Pattern Recognition, vol. B, pp. 50-54, 1996.[23] D.G. Lowe, “Similarity Metric Learning for a Variable-Kernel Classifier,” Neural Computation, vol. 7, no. 1, pp. 72-85, 1995.[24] J.H. Friedman, J.L. Bentley, and R.A. Finkel, "An Algorithm for Finding Best Matches in Logarithmic Expected Time," ACM Trans. on Math. Software, vol. 3, no. 3, pp. 209-226, Sept. 1977.[25] H. Samet, The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990.[26] R.F. Sproull, “Refinements to Nearest-Neighbor Searching in k-Dimensional Trees,” Algorithmica, vol. 6, pp. 579-589, 1991.[27] J. Ben-Arie, "The Probabilistic Peaking Effect of Viewed Angles and Distances With Application to 3D Object Recognition," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 8, pp. 760-774, August 1990.[28] R. Malik and T. Whangbo, “Angle Densities and Recognition of 3D Objects,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 1, pp. 52-57 Jan. 1997.[29] R. Duda, P. Hart, and D. Stork, Pattern Classification. New York: John Wiley&Sons, 2001.[30] D.G. Lowe, "Fitting Parameterized Three-Dimensional Models to Images," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 5, pp. 441-450, May 1991.[31] J.E. Lloyd, J.S. Beis, D.K. Pai, and D.G. Lowe, “Model-Based Telerobotics with Vision,” Proc. ICRA '97, pp. 1,297-1,304, Apr. 1997.[32] J.E. Lloyd and V. Hayward, “Multi-RCCL User's Guide,” technical report, Center for Intelligent Machines, McGill Univ., Apr. 1992.[33] J. Canny, “A Computational Approach to Edge Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679-698, June 1986.
Index Terms:
Model-based object recognition; indexing; kd-tree algorithm; nearest-neighbors algorithm.
Citation:
Jeffrey S. Beis, David G. Lowe, "Indexing without Invariants in 3D Object Recognition," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21, no. 10, pp. 1000-1015, Oct. 1999, doi:10.1109/34.799907
