Abstract
Despite their ubiquitous presence, little has been investigated about the scale variability—the relative variations in the spatial extents of local structures—of 3D geometric data. In this paper we present a comprehensive framework for exploiting this 3D geometric scale variability in range images that provides rich information for characterizing the overall geometry. We derive a sound scale-space representation, which we refer to as the geometric scale-space, that faithfully encodes the scale variability of the surface geometry, and derive novel detectors to extract prominent features and identify their natural scales. The result is a hierarchical set of features of different scales which we refer to as scale-dependent geometric features. We then derive novel local shape descriptors that represent the surface structures that give rise to those features by carving out and encoding the local surface that fall within the support regions of the features. This leads to scale-dependent or scale-invariant local shape descriptors that convey significant discriminative information of the object geometry. We demonstrate the effectiveness of geometric scale analysis on range images, and show that it enables novel applications, in particular, fully automatic registration of multiple objects from a mixed set of range images and 3D object recognition in highly cluttered range image scenes.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Akagunduz, E., & Ulusoy, I. (2007). Extraction of 3D transform and scale invariant patches from range scans. In IEEE int’l conf. on computer vision and pattern recognition (pp. 1–8).
Bariya, P., & Nishino, K. (2010). Scale-hierarchical 3D object recognition in cluttered scenes. In IEEE conf. on computer vision and pattern recognition.
Brady, M., Ponce, J., Yuille, A., & Asada, H. (1985). Describing surfaces (Technical Report AIM-822). MIT Aritificial Intelligence Laboratory Memo.
Bro, R., Acar, E., & Kolda, T. G. (2008). Resolving the sign ambiguity in the singular value decomposition. Journal of Chemometrics 22, 135–140.
Carmo, M. P. D. (1976). Differential geometry of curves and surfaces. Prentice Hall: New York.
Chang, K. C., Ding, W., & Ye, R. (1992). Finite-time blow-up of the heat flow of harmonic maps from surfaces. Journal of Differential Geometry, 36(2), 507–515.
Chen, C., Hung, Y., & Cheng, J. (1999). RANSAC-based DARCES: a new approach to fast automatic registration of partially overlapping range images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(11), 1229–1234.
Chua, C., & Jarvis, R. (1997). Point signatures: a new representation for 3D object recognition. International Journal of Computer Vision, 25(1), 63–85.
Cohen, R., Hardt, R., Kinderlehrer, D., Lin, S., & Luskin, M. (1987). Minimum energy configurations for liquid crystals: computational results (pp. 99–121). New York: Springer.
Coron, J. M. (1990). Nonuniqueness for the heat flow of harmonic maps. Annales de l’Institut Heri Poincaré, 7(4), 335–344.
Dinh, H. Q., & Kropac, S. (2006). Multi-resolution spin-images. In IEEE int’l conf. on computer vision and pattern recognition, Washington, DC, USA (pp. 863–870). Los Alamitos: IEEE Comput. Soc.
Fischler, M. A., & Bolles, R. C. (1981). Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6), 381–395.
Flynn, P., & Jain, A. (1991). Bonsai: 3D object recognition using constrained search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(10), 1066–1075.
Freire, A. (1995). Uniqueness for the harmonic map flow in two dimensions. Calculus of Variations and Partial Differential Equations, 3(1), 95–105.
Frome, A., Huber, D., Kolluri, R., Bulow, T., & Malik, J. (2004). Recognizing objects in range data using regional point descriptors. In European conf. on computer vision.
Gelfand, N., Mitra, N., Guibas, L., & Pottmann, H. (2005). Robust global registration. In Symposium on geometry processing.
Grimson, W. (1988). The combinatorics of object recognition in cluttered environments using constrained search. In IEEE int’l conf on computer vision (pp. 218–227).
Grimson, W., Lozano-Perez, T., & Huttenlocher, D. (1990). Object recognition by computer: the role of geometric constraints. Cambridge: MIT Press.
ter Haar, F., & Veltkamp, R. (2007). Automatic multiview quadruple alignment of unordered range scans. In IEEE shape modeling and applications, Washington, DC, USA (pp. 137–146). Los Alamitos: IEEE Comput. Soc.
Hardt, R. (1991). Singularities of harmonic maps. Bulletin of the American Mathematical Society, 34, 15–34.
Huber, D., & Hebert, M. (2003). Fully automatic registration of multiple 3d data sets. Image and Vision Computing, 21(7), 637–650.
Johnson, A. (1997). Spin-images: a representation for 3-D surface matching. Ph.D. thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
Johnson, A., & Hebert, M. (1999). Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(5), 433–449.
Johnson, A., Carmichael, O., Huber, D., & Hebert, M. (1998). Toward a general 3-D matching engine: multiple models, complex scenes, and efficient data filtering. In Proceedings of the 1998 image understanding workshop (IUW) (pp. 1097–1107).
Kazhdan, M., Bolitho, M., & Hoppe, H. (2006). Poisson surface reconstruction. In Eurographics symp. on geometry processing, Eurographics Association, Aire-la-Ville, Switzerland (pp. 61–70).
Kimmel, R. (1997). Intrinsic scale space for images on surfaces: the geodesic curvature flow. In Scale-space theory in computer vision (pp. 212–223).
Kimmel, R., & Sethian, JA (1998). Computing geodesic paths on manifolds. In Proceedings of national academy of sciences USA (pp. 8431–8435).
Koenderink, J. (1984). The structure of images. Biological Cybernetics, 50, 363–370.
Lab QURCV (2009). Queen’s range image and 3-D model database. http://rcvlab.ece.queensu.ca/~qridb/
Lalonde, J., Unnikrishnan, R., Vandapel, N., & Hebert, M. (2005). Scale selection for classification of point-sampled 3-D surfaces. In Int’l conf. on 3-D digital imaging and modeling.
Li, X., & Guskov, I. (2005). Multi-scale features for approximate alignment of point-based surfaces. In Symposium on geometry processing.
Li, X., & Guskov, I. (2007). 3D object recognition from range images using pyramid matching. In IEEE int’l conf. on computer vision workshop on 3D representation for recognition (pp. 1–6).
Lindeberg, T. (1994). Scale-space theory in computer vision. Dordrecht: Kluwer Academics.
Lindeberg, T. (1998). Feature detection with automatic scale selection. International Journal of Computer Vision, 30, 77–116.
Makadia, A., Patterson, A., & Daniilidis, K. (2006). Fully automatic registration of 3D point clouds. In IEEE int’l conf. on computer vision and pattern recognition, Washington, DC, USA (pp. 1297–1304). Los Alamitos: IEEE Comput. Soc.
MeshLab (2010). http://meshlab.sourceforge.net/.
Mian, A., Bennamoun, M., & Owens, R. (2004). From unordered range images to 3D models: a fully automatic multiview correspondence algorithm. In Theory and practice of computer graphics, Washington, DC, USA (pp. 162–166). Los Alamitos: IEEE Comput. Soc.
Mian, A., Bennamoun, M., & Owens, R. (2006). Three-dimensional model-based object recognition and segmentation in cluttered scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10), 1584–1601.
Mokhtarian, F., Khalili, N., & Yuen, P. (2001). Curvature computation on free-form 3-D meshes at multiple scales. Computer Vision and Image Understanding, 83, 118–139.
Morita, S., Kawashima, T., & Aoki, Y. (1992). Hierarchical shape recognition based on 3D multiresolution analysis. In European conf. on computer vision.
Nishino, K., & Ikeuchi, K. (2002). Robust simultaneous registration of multiple range images. In Proc. of fifth Asian conference on computer vision, ACCV 02 (pp. 454–461).
Novatnack, J., & Nishino, K. (2007). Scale-dependent 3D geometric features. In IEEE int’l conf. on computer vision.
Novatnack, J., & Nishino, K. (2008). Scale-dependent/invariant local 3D shape descriptors for fully automatic registration of multiple sets of range images. In European conference on computer vision (pp. 440–453).
Pauly, M., Kobbelt, L. P., & Gross, M. (2006). Point-based multi-scale surface representation. ACM Transactions on Graphics, 25(2), 177–193.
Ponce, J., & Brady, M. (1985). Toward a surface primal sketch. The International Journal of Robotics Research, 2, 420–425.
Schlattmann, M. (2006). Intrinsic features on surfaces. In Central European seminar on computer graphics (pp. 169–176).
Skelly, L. J., & Sclaroff, S. (2007). Improved feature descriptors for 3-d surface matching. In: Proc. SPIE conf. on two- and three-dimensional methods for inspection and metrology (Vol. 6762, pp. 63–85).
Stein, F., & Medioni, G. (1992). Structural indexing: efficient 3-D object recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2), 125–145.
Struwe, M. (1985). On the evolution of harmonic mappings of riemannian surfaces. Commentarii Mathematici Helvetici, 60(1), 558–581.
Sun, Y., & Abidi, M. (2001). Surface matching by 3D point’s fingerprint. In IEEE int.’l conf. on computer vision (Vol. 2, pp. 263–269).
Taati, B. (2009). Generation and optimization of local shape descriptors for point matching in 3-D surfaces. Ph.D. thesis, Queen’s University, Ontario, Canada.
Taati, B., Bondy, M., Jasiobedzki, P., & Greenspan, M. (2007). Variable dimensional local shape descriptors for object recognition in range data. In IEEE int’l conf. on computer vision workshop on 3D representation for recognition. Los Alamitos: IEEE Comput. Soc.
Tang, B., Sapiro, G., & Caselles, V. (2000). Diffusion of general data on non-flat manifolds via harmonic maps theory: the direction diffusion case. International Journal of Computer Vision, 36(2), 149–161.
Taubin, G. (1995). A signal processing approach to fair surface design. In ACM SIGGRAPH (pp. 351–358).
Umeyama, S. (1991). Least-squares estimation of transformation parameters between two point patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(4), 376–380.
Unnikrishnan, R., & Hebert, M. (2008). Multi-scale interest regions from unorganized point clouds. In IEEE int’l conf. on computer vision and pattern recognition: workshop on search in 3D (S3D).
Weickert, J., Ishikawa, S., & Imiya, A. (1999). Linear scale-space has first been proposed in Japan. Journal of Mathematical Imaging and Vision, 10(3), 237–252.
Witkin, A. (1984). Scale-space filtering: a new approach to multi-scale description. In IEEE int’l conf. on acoustics, speech, and signal processing (pp. 150–153).
Zhang, D., & Hebert, M. (1999). Harmonic maps and their applications in surface matching. In IEEE int’l conf. on computer vision and pattern recognition (Vol. 2).
Zou, G., Hua, J., Lai, Z., Gu, X., & Dong, M. (2009). Intrinsic geometric scale space by shape diffusion. IEEE Transactions on Visualization and Computer Graphics, 15, 1193–1200.
Author information
Authors and Affiliations
Corresponding author
Additional information
This material is based in part upon work supported by the National Science Foundation under CAREER award IIS-0746717 and IIS- 0803670. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
Rights and permissions
About this article
Cite this article
Bariya, P., Novatnack, J., Schwartz, G. et al. 3D Geometric Scale Variability in Range Images: Features and Descriptors. Int J Comput Vis 99, 232–255 (2012). https://doi.org/10.1007/s11263-012-0526-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-012-0526-7