Shape distributions

ABSTRACT

Measuring the similarity between 3D shapes is a fundamental problem, with applications in computer graphics, computer vision, molecular biology, and a variety of other fields. A challenging aspect of this problem is to find a suitable shape signature that can be constructed and compared quickly, while still discriminating between similar and dissimilar shapes.In this paper, we propose and analyze a method for computing shape signatures for arbitrary (possibly degenerate) 3D polygonal models. The key idea is to represent the signature of an object as a shape distribution sampled from a shape function measuring global geometric properties of an object. The primary motivation for this approach is to reduce the shape matching problem to the comparison of probability distributions, which is simpler than traditional shape matching methods that require pose registration, feature correspondence, or model fitting.We find that the dissimilarities between sampled distributions of simple shape functions (e.g., the distance between two random points on a surface) provide a robust method for discriminating between classes of objects (e.g., cars versus airplanes) in a moderately sized database, despite the presence of arbitrary translations, rotations, scales, mirrors, tessellations, simplifications, and model degeneracies. They can be evaluated quickly, and thus the proposed method could be applied as a pre-classifier in a complete shape-based retrieval or analysis system concerned with finding similar whole objects. The paper describes our early experiences using shape distributions for object classification and for interactive web-based retrieval of 3D models.

REFERENCES

• 1: Aherne, F., Thacker, N., and Rockett, P. 1997. Optimal pairwise geometric histograms. BMVC, 480--490.
• 2: Alt, H. and Guibas, L. J. 1996. Discrete geometric shapes: Matching, interpolation, and approximation: A survey. Tech. Rep. B 96-11, EVL-1996-142, Institute of Computer Science, Freie Universität Berlin.
• 3: Amit, Y., Grenander, U., and Piccioni, M. 1991. Structural image restoration through deformable templates. J. Am. Statistical Assn. 86, 440, 376--387.
• 4: Mihael Ankerst , Gabi Kastenmüller , Hans-Peter Kriegel , Thomas Seidl, Nearest Neighbor Classification in 3D Protein Databases, Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, p.34-43, August 06-10, 1999
• 5: A. P. Ashbrook , N. A. Thacker , P. I. Rockett , C. I. Brown, Robust recognition of scaled shapes using pairwise geometric histograms, Proceedings of the 6th British conference on Machine vision (Vol. 2), p.503-512, July 1995, Birmingham, United Kingdom
• 6: K. Arbter , W. E. Snyder , H. Burhardt , G. Hirzinger, Application of Affine-Invariant Fourier Descriptors to Recognition of 3-D Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.640-647, July 1990 [doi>10.1109/34.56206]
• 7: Esther M. Arkin , L. Paul Chew , Daniel P. Huttenlocher , Klara Kedem , Joseph S. B. Mitchell, An Efficiently Computable Metric for Comparing Polygonal Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.3, p.209-216, March 1991 [doi>10.1109/34.75509]
• 8: Farshid Arman , J. K. Aggarwal, Model-based object recognition in dense-range images—a review, ACM Computing Surveys (CSUR), v.25 n.1, p.5-43, March 1993 [doi>10.1145/151254.151255]
• 9: Ashbrook, A., Rockett, P., and Thacker, N. 1995b. Multiple shape recognition using pairwise geometric histogram based algortihms. IEEE Image Processing.
• 10: Ashbrook, A., Thacker, N., and Rockett, P. 1995c. Pairwise geometric histograms: A scaleable solution for recognition of 2d rigid shapes. 9th SCIA 1, 271--278.
• 11: Bardinet, E., Vidal, S. F., Arroyo, S. D., Malandain, G., and de la Blanca Capilla, N. P. 2000. Structural object matching. Tech. Rep. DECSAI-000303, Dept. of Computer Science and AI, University of Granada, Spain. February.
• 12: Gill Barequet , Subodh Kumar, Repairing CAD models, Proceedings of the 8th conference on Visualization '97, p.363-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 13: Basri, R., Costa, L., Geiger, D., and Jacobs, D. 1998. Determining the similarity of deformable shapes. Vision Research 38, 2365--2385.
• 14: Belongie, S., Malik, J., and Puzicha, J. 2001. Matching shapes. ICCV.
• 15: Paul J. Besl, Triangles as a Primary Representation, Proceedings of the International NSF-ARPA Workshop on Object Representation in Computer Vision, p.191-206, December 05-07, 1994
• 16: Paul J. Besl , Ramesh C. Jain, Three-dimensional object recognition, ACM Computing Surveys (CSUR), v.17 n.1, p.75-145, March 1985 [doi>10.1145/4078.4081]
• 17: Bhattacharyya, A. 1943. On a measure of divergence between two statistical populations defined by their probability distributions. Bulletin of the Calcutta Mathematics Society 35, 99--110.
• 18: Binford, T. 1971. Visual perception by computer. IEEE Conference on Systems Science and Cybernetics.
• 19: Jules Bloomenthal , Chek Lim, Skeletal Methods of Shape Manipulation, Proceedings of the International Conference on Shape Modeling and Applications, p.44, March 01-04, 1999
• 20: Stefan Carlsson, Order Structure, Correspondence, and Shape Based Categories, Shape, Contour and Grouping in Computer Vision, p.58-71, January 1999
• 21: Chang, S. and Smith, J. 1995. Extracting multi-dimensional signal features for content-based visual query. SPIE Symposium on Visual Communications and Signal Processing 2501, 2 (May), 995--1006.
• 22: Chen, J. 2001. The Search for 3D Models. Junior Independent Work, Computer Science Department, Princeton University.
• 23: Jonathan Cohen , Amitabh Varshney , Dinesh Manocha , Greg Turk , Hans Weber , Pankaj Agarwal , Frederick Brooks , William Wright, Simplification envelopes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.119-128, August 1996 [doi>10.1145/237170.237220]
• 24: H. Delingette , M. Hebert , K. Ikeuchi, Shape representation and image segmentation using deformable surfaces, Image and Vision Computing, v.10 n.3, p.132-144, April 1992 [doi>10.1016/0262-8856(92)90065-B]
• 25: Delingette, H., Hebert, M., and Ikeuchi, K. 1993. A spherical representation for the recognition of curved objects. ICCV, 103--112.
• 26: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 27: 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
• 28: Evans, A., Thacker, N., and Mayhew, J. 1992. Pairwise representation of shape. 11th ICPR 1. 133--136.
• 29: Evans, A., Thacker, N., and Mayhew, J. 1993. The use of geometric histograms for model-based object recognition. 4th BMVC, 429--438.
• 30: Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
• 31: James Gain , James Scott, Fast polygon mesh querying by example, ACM SIGGRAPH 99 Conference abstracts and applications, p.241, August 08-13, 1999, Los Angeles, California, United States [doi>10.1145/311625.312134]
• 32: André Guéziec , Gabriel Taubin , Francis Lazarus , William Horn, Converting sets of polygons to manifold surfaces by cutting and stitching, Proceedings of the conference on Visualization '98, p.383-390, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 33: Helgason, S. 1999. The radon transform. Progress in Mathematics, Springer, 2nd ed. 5.
• 34: Holm, L. and Sander, C. 1998. Touring protein fold space with dali/fssp. Nucleic Acids Research 26, 316--319.
• 35: Horn, B. 1984. Extended gaussian images. Proc. of the IEEE 72, 12 (December), 1671--1686.
• 36: Huet, B. and Hancock, E. 1996. Structural indexing of infra-red images using statistical histogram comparison. IWISP, 653--656.
• 37: Igarashi, T., Matsuoka, S., and Tanaka, H. 1999. Teddy: A sketching interface for 3d freeform design. SIGGRAPH, 409--416. ISBN 0-20148-560-5. Held in Los Angeles, California.
• 38: K. Ikeuchi , T. Shakunaga , M. D. Wheeler , T. Yamazaki, Invariant histograms and deformable template matching for SAR target recognition, Proceedings of the 1996 Conference on Computer Vision and Pattern Recognition (CVPR '96), p.100, June 18-20, 1996
• 39: Charles E. Jacobs , Adam Finkelstein , David H. Salesin, Fast multiresolution image querying, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.277-286, September 1995 [doi>10.1145/218380.218454]
• 40: Anil K. Jain , Yu Zhong , Sridhar Lakshmanan, Object Matching Using Deformable Templates, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.3, p.267-278, March 1996 [doi>10.1109/34.485555]
• 41: 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]
• 42: Kullback, S. 1968. Information Theory and Statistics. Dover.
• 43: Stanford University Computer Graphics Laboratory 1996. http://graphics.stanford.edu/data.
• 44: Lamdam, Y. and Wolfson, H. 1988. Geometric hashing: a general and efficient model-based recognition scheme. ICCV.
• 45: Yijia Lin , Jiqing Dou , Hongmei Wang, Contour shape description based on an arch height function, Pattern Recognition, v.25 n.1, p.17-23, Jan. 1992 [doi>10.1016/0031-3203(92)90003-2]
• 46: Loncaric, S. 1998. A survey of shape analysis techniques. Pattern Recognition 31, 8, 983--1001.
• 47: Mori, G., Belongie, S., and Malik, J. 2001. Shape contexts enable efficient retrieval of similar shapes. CVPR.
• 48: T. M. Murali , Thomas A. Funkhouser, Consistent solid and boundary representations from arbitrary polygonal data, Proceedings of the 1997 symposium on Interactive 3D graphics, p.155-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253326]
• 49: Virginia E. Ogle , Michael Stonebraker, Chabot: Retrieval from a Relational Database of Images, Computer, v.28 n.9, p.40-48, September 1995 [doi>10.1109/2.410150]
• 50: Alex Pentland , Stan Sclaroff, Closed-Form Solutions for Physically Based Shape Modeling and Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.7, p.715-729, July 1991 [doi>10.1109/34.85660]
• 51: Arthur R. Pope, Model-Based Object Recognition - A Survey of Recent Research, University of British Columbia, Vancouver, BC, Canada, 1994
• 52: Richard J. Prokop , Anthony P. Reeves, A survey of moment-based techniques for unoccluded object representation and recognition, CVGIP: Graphical Models and Image Processing, v.54 n.5, p.438-460, Sept. 1992 [doi>10.1016/1049-9652(92)90027-U]
• 53: Jan Puzicha , Joachim M. Buhmann , Yossi Rubner , Carlo Tomasi, Empirical Evaluation of Dissimilarity Measures for Color and Texture, Proceedings of the International Conference on Computer Vision-Volume 2, p.1165, September 20-25, 1999
• 54: Rann, A. G. and Katsevich, A. I. 1996. The Radon Transform and Local Tomography. CRC Press.
• 55: Riocreux, P., Thacker, N., and Yates, R. 1994. An analysis of pairwise geometric histograms for view-based object recognition. BMVC.
• 56: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, A Metric for Distributions with Applications to Image Databases, Proceedings of the Sixth International Conference on Computer Vision, p.59, January 04-07, 1998
• 57: Stan Sclaroff , Alex P. Pentland, Modal Matching for Correspondence and Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.6, p.545-561, June 1995 [doi>10.1109/34.387502]
• 58: Shen, H. C. and Wong, A. K. C. 1983. Generalized texture representation and metric. Computer, Vision, Graphics, and Image Processing 23, 187--206.
• 59: Kaleem Siddiqi , Ali Shokoufandeh , Sven J. Dickinson , Steven W. Zucker, Shock Graphs and Shape Matching, Proceedings of the Sixth International Conference on Computer Vision, p.222, January 04-07, 1998
• 60: Steven S. Skiena , Warren D. Smith , Paul Lemke, Reconstructing sets from interpoint distances (extended abstract), Proceedings of the sixth annual symposium on Computational geometry, p.332-339, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98598]
• 61: F. Solina , R. Bajcsy, Recovery of Parametric Models from Range Images: The Case for Superquadrics with Global Deformations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.2, p.131-147, February 1990 [doi>10.1109/34.44401]
• 62: Duane W. Storti , George M. Turkiyyah , Mark A. Ganter , Chek T. Lim , Derek M. Stal, Skeleton-based modeling operations on solids, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.141-154, May 14-16, 1997, Atlanta, Georgia, United States [doi>10.1145/267734.267771]
• 63: Tappert, C. 1982. Cursive script recognition by elastic matching. IBM Res. Develop. 26, 6, 765--771.
• 64: Gabriel Taubin , David B. Cooper, Object recognition based on moment (or algebraic) invariants, Geometric invariance in computer vision, MIT Press, Cambridge, MA, 1992
• 65: Demetri Terzopoulos , Dimitri Metaxas, Dynamic 3D Models with Local and Global Deformations: Deformable Superquadrics, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.7, p.703-714, July 1991 [doi>10.1109/34.85659]
• 66: Thacker, N., Riocreux, P., and Yates, R. 1995. Assessing the completeness properties of pairwise geometric histograms. Image and Vision Computing 13, 5, 423--429.
• 67: Tsai, W. and Yu, S. 1985. Attributive string matching with merging for shape recognition. IEEE Trans. Pattern Anal. Mach. Intell. 7, 453--462.
• 68: Uras, C. and Verri, A. 1994. On the recognition of the alphabet of the sign language through size functions. IAPR, 334--338.
• 69: Claudio Uras , Alessandro Verri, Computing Size Functions from Edge Maps, International Journal of Computer Vision, v.23 n.2, p.169-183, June 1997 [doi>10.1023/A:1007910913691]
• 70: Veltkamp, R. C. and Hagedoorn, M. 1999. State-of-the-art in shape matching. Tech. Rep. UU-CS-1999-27, Utrecht University, the Netherlands.
• 71: Werman, M., Peleg, S., and Rosenfeld, A. 1985. A distance metric for multi-dimensional histograms. Computer, Vision, Graphics, and Image Processing 32, 328--336.
• 72: Wu, K. and Levine, M. 1994. Recovering parametrics geons from multiview range data. CVPR, 159--166.
• 73: Young, I., Walker, J., and Bowie, J. 1974. An analysis technique for biological shape. Computer Graphics and Image Processing 25, 357--370.
• 74: Zhang, D. and Hebert, M. 1999. Harmonic maps and their applications in surface matching. IEEE Conference on Computer Vision and Pattern Recognition (CVPR '99).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Experimentation, Reliability

Keywords:
Shape analysis, shape representation