Retrieving 3D shapes based on their appearance

ABSTRACT

In this paper, we propose an algorithm for shape-similarity comparison and retrieval of 3D shapes defined as polygon soup. One of the issues in comparing 3D shapes is the diversity of shape representations used to represent these "3D" shapes. While a solid model is well-defined and is easier to handle, others such as polygon soup poses many problems. In fact, a polygon soup 3D model most often does not define a 3D shape, but merely an illusion of "3D shape-ness" by its collection of independent polygons, lines, and manifold meshes. The most significant feature of our 3D shape similarity comparison method is that it accepts polygon soup and other ill-defined 3D models. Our approach is to use the rendered appearance only of the model as the basis for shape similarity comparison. Our method removes scale and positional degrees-of-freedom by using normalization, and the three rotational degrees of freedom by using a combination of discrete sampling of solid angles and a rotation-invariant 2D image similarity comparison algorithm. Evaluation experiments showed that, despite its simplicity, our approach worked quite well despite its simplicity.

REFERENCES

• 1: 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
• 2: J. Corney, H. Rea, D. Clark, John Pritchard, M. Breaks, R. MacLeod, Coarse Filter for Shape Matching, IEEE CG&A, pp. 65--73, May/June, 2002.
• 3: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 4: Michael Elad , Ayellet Tal , Sigal Ar, Content based retrieval of VRML objects: an iterative and interactive approach, Proceedings of the sixth Eurographics workshop on Multimedia 2001, p.107-118, September 08-09, 2001, Manchester, UK
• 5: 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]
• 6: Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001 [doi>10.1145/383259.383282]
• 7: Takeo Igarashi , Satoshi Matsuoka , Hidehiko Tanaka, Teddy: a sketching interface for 3D freeform design, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.409-416, July 1999 [doi>10.1145/311535.311602]
• 8: Daniel A. Keim, Efficient geometry-based similarity search of 3D spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.419-430, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 9: D. McWherter, M. Peabody, W. Regli, A. Shokoufandeh, Transformation Invariant Shape Similarity Comparison of Solid Models, Proc. ASME DETC `2001, September 2002, Pittsburgh, Pennsylvania.
• 10: Patrick Min , John A. Halderman , Michael Kazhdan , Thomas A. Funkhouser, Early experiences with a 3D model search engine, Proceeding of the eighth international conference on 3D Web technology, March 09-12, 2003, Saint Malo, France [doi>10.1145/636593.636595]
• 11: Shinji Mukai , Susumu Furukawa , Mitsuru Kuroda, An algorithm for deciding similarities of 3-D objects, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566334]
• 12: Marcin Novotni , Reinhard Klein, A Geometric Approach to 3D Object Comparison, Proceedings of the International Conference on Shape Modeling & Applications, p.167, May 07-11, 2001
• 13: Ryutarou Ohbuchi , Tomo Otagiri , Masatoshi Ibato , Tsuyoshi Takei, Shape-Similarity Search of Three-Dimensional Models Using Parameterized Statistics, Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, p.265, October 09-11, 2002
• 14: Ryutarou Ohbuchi , Takahiro Minamitani , Tsuyoshi Takei, Shape-Similarity Search of 3D Models by using Enhanced Shape Functions, Proceedings of the Theory and Practice of Computer Graphics 2003, p.97, June 03-05, 2003
• 15: Ryutarou Ohbuchi , Tsuyoshi Takei, Shape-Similarity Comparison of 3D Models Using Alpha Shapes, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.293, October 08-10, 2003
• 16: Robert Osada , Thomas Funkhouser , Bernard Chazelle , David Dobkin, Matching 3D Models with Shape Distributions, Proceedings of the International Conference on Shape Modeling & Applications, p.154, May 07-11, 2001
• 17: Robert Osada , Thomas Funkhouser , Bernard Chazelle , David Dobkin, Shape distributions, ACM Transactions on Graphics (TOG), v.21 n.4, p.807-832, October 2002 [doi>10.1145/571647.571648]
• 18: E. Paquet , M. Rioux, Nefertiti: a query by content software for three-dimensional models databases management, Proceedings of the International Conference on Recent Advances in 3-D Digital Imaging and Modeling, p.345, May 12-15, 1997
• 19: E. Paquet, A. Murching, T. Naveen, A. Tabatabai, M. Roux. Description of shape information for 2-D and 3-D objects, Signal Processing: Image Communication, 16:103--122, 2000.
• 20: W. Regli, V. Cicirello, Managing Digital Libraries for Computer-Aided Design, Computer Aided Design, pp. 110--132, Vol. 32, No. 2, 2000.
• 21: Motofumi T. Suzuki , Toshikazu Kato , Hideo Tsukune, 3D Object Retrieval based on Subjective Measures, Proceedings of the 9th International Workshop on Database and Expert Systems Applications, p.850, August 26-28, 1998
• 22: M. T. Suzuki, T. Kato, N. Otsu. A similarity retrieval of 3D polygonal models using rotation invariant shape descriptors. IEEE Int. Conf. on Systems, Man, and Cybernetics (SMC2000), Nashville, Tennessee, pp. 2946--2952, 2000.
• 23: Remco C. Veltkamp, Shape Matching: Similarity Measures and Algorithms, Proceedings of the International Conference on Shape Modeling & Applications, p.188, May 07-11, 2001
• 24: D. V. Vranić, D. Saupe, and J. Richter. Tools for 3D-object retrieval: Karhunen-Loeve Transform and spherical harmonics. Proc. IEEE 2001 Workshop on Multimedia Signal Processing, Cannes, France, pp. 293--298, October 2001.
• 25: T. Zaharia, F. Préteux, Three-dimensional shape-based retrieval within the MPEG-7 framework, Proc. SPIE Conference 4304 on Nonlinear Image Processing and Pattern Analysis XII, San Jose, CA, January 2001, pp. 133--145.
• 26: T. Zaharia, F. Préteux, Shape-based retrieval of 3D mesh models, Proc. IEEE ICME 2002, Lausanne, Switzerland, August 2002.
• 27: D. S. Zhang, G. Lu, Shape-based image retrieval using generic Fourier descriptor, Signal Processing: Image Communication, 17(10), pp. 825--848, (November, 2002).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis

General Terms:
Algorithms, Experimentation

Keywords:
depth map, geometric modeling, polygon soup, polygonal mesh, shape similarity search, three-dimensional models