Partial matching of 3D shapes with priority-driven search

ABSTRACT

Priority-driven search is an algorithm for retrieving similar shapes from a large database of 3D objects. Given a query object and a database of target objects, all represented by sets of local 3D shape features, the algorithm produces a ranked list of the c best target objects sorted by how well any subset of k features on the query match features on the target object. To achieve this goal, the system maintains a priority queue of potential sets of feature correspondences (partial matches) sorted by a cost function accounting for both feature dissimilarity and the geometric deformation. Only partial matches that can possibly lead to the best full match are popped off the queue, and thus the system is able to find a provably optimal match while investigating only a small subset of potential matches. New methods based on feature distinction, feature correspondences at multiple scales, and feature difference ranking further improve search time and retrieval performance. In experiments with the Princeton Shape Benchmark, the algorithm provides significantly better classification rates than previously tested shape matching methods while returning the best matches in a few seconds per query.

REFERENCES

• 1: {AFP00} Audette M. A., Ferrie F. P., Peters T. M.: An algorithmic overview of surface registration techniques for medical imaging. Medical Image Analysis 4, 3 (2000), 201--217.
• 2: Mihael Ankerst , Gabi Kastenmüller , Hans-Peter Kriegel , Thomas Seidl, 3D Shape Histograms for Similarity Search and Classification in Spatial Databases, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.207-226, July 20-23, 1999
• 3: {BB76} Barrow H., Burstall R.: Subgraph isomorphism, matching relational structures and maximal cliques. Inf. Process. Lett. 4 (1976), 83--84.
• 4: Alexander C. Berg , Tamara L. Berg , Jitendra Malik, Shape Matching and Object Recognition Using Low Distortion Correspondences, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, p.26-33, June 20-26, 2005 [doi>10.1109/CVPR.2005.320]
• 5: Benjamin Bustos , Daniel A. Keim , Dietmar Saupe , Tobias Schreck , Dejan V. Vranić, Feature-based similarity search in 3D object databases, ACM Computing Surveys (CSUR), v.37 n.4, p.345-387, December 2005 [doi>10.1145/1118890.1118893]
• 6: {BKS*06} Bustos B., Keim D., Saupe D., T. Schreck, Vranić D.: An experimental effectiveness comparison of methods for 3D similarity search. International Journal on Digital Libraries, Special issue on Multimedia Contents and Management in Digital Libraries 6, 1 (2006), 39--54.
• 7: Paul J. Besl , Neil D. McKay, A Method for Registration of 3-D Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.2, p.239-256, February 1992 [doi>10.1109/34.121791 ]
• 8: {BMP01} Belongie S., Malik J., Puzicha J.: Matching shapes. ICCV (2001).
• 9: Chin Seng Chua , Ray Jarvis, Point Signatures: A New Representation for 3D Object Recognition, International Journal of Computer Vision, v.25 n.1, p.63-85, Oct. 1997 [doi>10.1023/A:1007981719186 ]
• 10: {COTS03} Chen D.-Y., Ouhyoung M., Tian X.-P., Shen Y.-T.: On visual similarity based 3D model retrieval. Computer Graphics Forum (2003), 223--232.
• 11: {CR00} Chui H., Rangarajan A.: A new algorithm for non-rigid point matching. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2000), 44--51.
• 12: Martin A. Fischler , Robert C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, v.24 n.6, p.381-395, June 1981 [doi>10.1145/358669.358692]
• 13: {FHK*04} Frome A., Huber D., Kolluri R., Bulow T., Malik J.: Recognizing objects in range data using regional point descriptors. In European Conference on Computer Vision (ECCV) (May 2004), pp. 224--237.
• 14: Thomas Funkhouser , Patrick Min , Michael Kazhdan , Joyce Chen , Alex Halderman , David Dobkin , David Jacobs, A search engine for 3D models, ACM Transactions on Graphics (TOG), v.22 n.1, p.83-105, January 2003 [doi>10.1145/588272.588279]
• 15: Ran Gal , Daniel Cohen-Or, Salient geometric features for partial shape matching and similarity, ACM Transactions on Graphics (TOG), v.25 n.1, p.130-150, January 2006 [doi>10.1145/1122501.1122507]
• 16: Kristen Grauman , Trevor Darrell, The Pyramid Match Kernel: Discriminative Classification with Sets of Image Features, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1458-1465, October 17-20, 2005 [doi>10.1109/ICCV.2005.239]
• 17: Natasha Gelfand , Niloy J. Mitra , Leonidas J. Guibas , Helmut Pottmann, Robust global registration, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
• 18: {HKSV02} Heczko M., Keim D., Saupe D., Vranić D.: Methods for similarity search on 3D databases. In Datenbank-Spektrum (2002), vol. 2, pp. 54--63. (In German).
• 19: {IJL*05} Iyer N., Jayanti S., Lou K., Kalyanaraman Y., Ramani K.: Three dimensional shape searching: State-of-the-art review and future trends. Computer-Aided Design 37, 5 (2005), 509--530.
• 20: Andrew E. Johnson , Martial Hebert, Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.5, p.433-449, May 1999 [doi>10.1109/34.765655 ]
• 21: Michael Kazhdan , Thomas Funkhouser , Szymon Rusinkiewicz, Rotation invariant spherical harmonic representation of 3D shape descriptors, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 22: {KPNK03} Kortgen M., Park G.-J., Novotni M., Klein R.: 3D shape matching with 3D shape contexts. In 7th Central European Seminar on Computer Graphics (April 2003).
• 23: Xinju Li , Igor Guskov, Multi-scale features for approximate alignment of point-based surfaces, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
• 24: {LW88} Lamdam Y., Wolfson H.: Geometric hashing: a general and efficient model-based recognition scheme. In Proc. ICCV (December 1988).
• 25: {MBM01} Mori G., Belongie S., Malik J.: Shape contexts enable efficient retrieval of similar shapes. In IEEE Computer Vision and Pattern Recognition (CVPR) (December 2001).
• 26: Patrick Min , John A. Halderman , Michael Kazhdan , Thomas A. Funkhouser, Early experiences with a 3D model search engine, Proceedings of the eighth international conference on 3D Web technology, March 09-12, 2003, Saint Malo, France [doi>10.1145/636593.636595]
• 27: {NDK05} Novotni M., Degener P., Klein R.: Correspondence Generation and Matching of 3D Shape Subparts. Tech. Rep. CG-2005-2, ISSN 1610--8892, Friedrich-Wilhelms-Universität Bonn, June 2005.
• 28: Philip Shilane , Thomas Funkhouser, Selecting Distinctive 3D Shape Descriptors for Similarity Retrieval, Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, p.18, June 14-16, 2006 [doi>10.1109/SMI.2006.34]
• 29: The Princeton Shape Benchmark, Proceedings of the Shape Modeling International 2004, p.167-178, June 07-09, 2004 [doi>10.1109/SMI.2004.63]
• 30: {SMS*04} Shan Y., Matei B., Sawhney H. S., Kumar R., Huber D., Hebert M.: Linear model hashing and batch ransac for rapid and accurate object recognition. In IEEE International Conference on Computer Vision and Pattern Recognition (2004).
• 31: A Survey of Content Based 3D Shape Retrieval Methods, Proceedings of the Shape Modeling International 2004, p.145-156, June 07-09, 2004 [doi>10.1109/SMI.2004.10]
• 32: {Vra06} Vranić D.: Tools for 3d model retrieval, 2006. http://merkur01.inf.uni-konstanz.de/3Dtools/.
• 33: Sameh M. Yamany , Aly A. Farag, Surfacing Signatures: An Orientation Independent Free-Form Surface Representation Scheme for the Purpose of Objects Registration and Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.8, p.1105-1120, August 2002 [doi>10.1109/TPAMI.2002.1023806 ]