Robert Osada
Skip Abstract Section
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.
- Aherne, F., Thacker, N., and Rockett, P. 1997. Optimal pairwise geometric histograms. BMVC, 480--490.]]Google Scholar
- 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.]]Google Scholar
- Amit, Y., Grenander, U., and Piccioni, M. 1991. Structural image restoration through deformable templates. J. Am. Statistical Assn. 86, 440, 376--387.]]Google Scholar
- Ankerst, M., Kastenmüller, G., Kriegel, H.-P., and Seidl, T. 1999. Nearest neighbor classification in 3d protein databases. ISMB.]] Google Scholar
- Ashbrook, A., Thacker, N. A., Rockett, P. I., and Brown, C. I. 1995a. Robust recognition of scaled shapes using pairwise geometric histograms. BMVC, 503--512.]] Google Scholar
- Arbter, K., Snyder, W. E., Burkhardt, H., and Hirzinger, G. 1990. Application of affine-invariant Fourier descriptors to recognition of 3-D objects. IEEE Trans. Pattern Anal. Mach. Intell. 12, 7 (July), 640--647.]] Google Scholar
- Arkin, E. M., Chew, L. P., Huttenlocher, D. P., Kedem, K., and Mitchell, J. S. 1991. An efficiently computable metric for comparing polygonal shapes. IEEE Trans. Pattern Anal. Mach. Intell. 13, 3 (March), 209--216.]] Google Scholar
- Arman, F. and Aggarwal, J. 1993. Model-based object recognition in dense-range images---a review. ACM Comput. Surv. 25, 1, 5--43.]] Google Scholar
- Ashbrook, A., Rockett, P., and Thacker, N. 1995b. Multiple shape recognition using pairwise geometric histogram based algortihms. IEEE Image Processing.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- Barequet, G. and Kumar, S. 1997. Repairing CAD models. IEEE Visualization '97, 363--370.]] Google Scholar
- Basri, R., Costa, L., Geiger, D., and Jacobs, D. 1998. Determining the similarity of deformable shapes. Vision Research 38, 2365--2385.]]Google Scholar
- Belongie, S., Malik, J., and Puzicha, J. 2001. Matching shapes. ICCV.]]Google Scholar
- Besl, P. 1995. Triangles as a primary representation. Object Recognition in Computer Vision LNCS 994, 191--206.]] Google Scholar
- Besl, P. J. and Jain, R. C. 1985. Three-dimensional object recognition. Comput. Surv. 17, 1 (March), 75--145.]] Google Scholar
- 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.]]Google Scholar
- Binford, T. 1971. Visual perception by computer. IEEE Conference on Systems Science and Cybernetics.]]Google Scholar
- Bloomenthal, J. and Lim, C. 1999. Skeletal methods of shape manipulation. Shape Modeling and Applications, 44--47.]] Google Scholar
- Carlsson, S. 1999. Order structure, correspondence, and shape based categories. Shape, Contour and Grouping in Computer Vision, 58--71.]] Google Scholar
- 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.]]Google Scholar
- Chen, J. 2001. The Search for 3D Models. Junior Independent Work, Computer Science Department, Princeton University.]]Google Scholar
- Cohen, J., Varshney, A., Manocha, D., Turk, G., Weber, H., Agarwal, P., Frederick P. Brooks, Jr., and Wright, W. 1996. Simplification envelopes. SIGGRAPH, 119--128.]] Google Scholar
- Delingette, H., Hebert, M., and Ikeuchi, K. 1992. Shape representation and image segmentation using deformable surfaces. Image and Vision Computing 10, 3 (April), 132--144.]] Google Scholar
- Delingette, H., Hebert, M., and Ikeuchi, K. 1993. A spherical representation for the recognition of curved objects. ICCV, 103--112.]]Google Scholar
- Duda, R., Hart, P., and Stork, D. 2001. Pattern Classification, Second Edition. John Wiley & Sons, New York.]] Google Scholar
- Elad, M., Tal, A., and Ar, S. 2001. Content based retrieval of VRML objects---an iterative and interactive approach. The 6th Eurographics Workshop in Multimedia, Manchester, U.K.]] Google Scholar
- Evans, A., Thacker, N., and Mayhew, J. 1992. Pairwise representation of shape. 11th ICPR 1. 133--136.]]Google Scholar
- Evans, A., Thacker, N., and Mayhew, J. 1993. The use of geometric histograms for model-based object recognition. 4th BMVC, 429--438.]]Google Scholar
- Flickner, M., Sawhney, H., Niblack, W., Ashley, J., and Huang, Q. 1995. Query by image and video content: the qbic system. IEEE Comput. 28, 9, 23--32.]] Google Scholar
- Gain, J. and Scott, J. 1999. Fast polygon mesh querying by example. SIGGRAPH Technical Sketches.]] Google Scholar
- Gueziec, A., Taubin, G., Lazarus, F., and Horn, W. 1998. Converting sets of polygons to manifold surfaces by cutting and stitching. IEEE Visualization '98, 383--390.]] Google Scholar
- Helgason, S. 1999. The radon transform. Progress in Mathematics, Springer, 2nd ed. 5.]]Google Scholar
- Holm, L. and Sander, C. 1998. Touring protein fold space with dali/fssp. Nucleic Acids Research 26, 316--319.]]Google Scholar
- Horn, B. 1984. Extended gaussian images. Proc. of the IEEE 72, 12 (December), 1671--1686.]]Google Scholar
- Huet, B. and Hancock, E. 1996. Structural indexing of infra-red images using statistical histogram comparison. IWISP, 653--656.]]Google Scholar
- 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.]]Google Scholar
- Ikeuchi, K., Shakunaga, T., Wheeler, M., and Yamazaki, T. 1996. Invariant histograms and deformable template matching for sar target recognition. Computer Vision and Pattern Recognition.]] Google Scholar
- Jacobs, C., Finkelstein, A., and Salesin, D. 1995. Fast multiresolution image querying. SIGGRAPH, 277--286.]] Google Scholar
- Jain, A., Zhong, Y., and Lakshmanan, S. 1996. Object matching using deformable templates. IEEE Trans. Pattern Anal. Mach. Intell. 18, 3, 267--278.]] Google Scholar
- Johnson, A. E. and Hebert, M. 1999. Using spin-images for efficient multiple model recognition in cluttered 3-d scenes. IEEE PAMI 21, 5, 433--449.]] Google Scholar
- Kullback, S. 1968. Information Theory and Statistics. Dover.]]Google Scholar
- Stanford University Computer Graphics Laboratory 1996. http://graphics.stanford.edu/data.]]Google Scholar
- Lamdam, Y. and Wolfson, H. 1988. Geometric hashing: a general and efficient model-based recognition scheme. ICCV.]]Google Scholar
- Lin, Y., Dou, J., and Wang, H. 1992. Contour shape description based on an arch height function. Pattern Recognition 25, 17--23.]] Google Scholar
- Loncaric, S. 1998. A survey of shape analysis techniques. Pattern Recognition 31, 8, 983--1001.]]Google Scholar
- Mori, G., Belongie, S., and Malik, J. 2001. Shape contexts enable efficient retrieval of similar shapes. CVPR.]]Google Scholar
- Murali, T. and Funkhouser, T. 1997. Consistent solid and boundary representations from arbitrary polygonal data. Computer Graphics (1997 SIGGRAPH Symposium on Interactive 3D Graphics), 155--162.]] Google Scholar
- Ogle, V. and Stonebraker, M. 1995. Chabot: Retrieval from a relational database of images. IEEE Computer 28, 9, 40--48.]] Google Scholar
- Pentland, A. and Sclaroff, S. 1991. Closed-form solutions for physically based shape modeling and recognition. IEEE Trans. Pattern Anal. Mach. Intell. 13, 7, 715--729.]] Google Scholar
- Pope, A. R. 1994. Model-based object recognition: A survey of recent research. Tech. Rep. TR-94-04, University of British Columbia. January.]] Google Scholar
- Prokop, R. J. and Reeves, A. P. 1992. A survey of moment-based techniques for unoccluded object representation and recognition. CVGIP: Graphics Models and Image Processsing 54, 5, 438--460.]] Google Scholar
- Puzicha, J., Rubner, Y., Tomasi, C., and Buhmann, J. M. 1999. Empirical evaluation of dissimilarity measures for color and texture. IEEE International Conference on Computer Vision, 1165--1173.]] Google Scholar
- Rann, A. G. and Katsevich, A. I. 1996. The Radon Transform and Local Tomography. CRC Press.]]Google Scholar
- Riocreux, P., Thacker, N., and Yates, R. 1994. An analysis of pairwise geometric histograms for view-based object recognition. BMVC.]]Google Scholar
- Rubner, Y., Tomasi, C., and Guibas, L. 1998. A metric for distributions with applications to image databases. 6th ICCV, 59--66.]] Google Scholar
- Sclaroff, S. and Pentland, A. 1995. Modal matching for correspondence and recognition. IEEE Trans. Pattern Anal. Mach. Intell. 17, 6 (June), 545--561.]] Google Scholar
- Shen, H. C. and Wong, A. K. C. 1983. Generalized texture representation and metric. Computer, Vision, Graphics, and Image Processing 23, 187--206.]]Google Scholar
- Siddiqi, K., Shokoufandeh, A., Dickinson, S. J., and Zucker, S. W. 1998. Shock graphs and shape matching. Computer Vision, 222--229.]] Google Scholar
- Skiena, S., Smith, W., and Lemke, P. 1990. Reconstructing sets from interpoint distances. Proceedings of the Sixth Annual Symposium on Computational Geometry, 332--339.]] Google Scholar
- Solina, F. and Bajcsy, R. 1990. Recovery of parametric models from range images: The case for superquadrics with global deformations. Pattern Anal. Mach. Intell. 12, 2 (February), 131-- 147.]] Google Scholar
- Storti, D., Turkiyyah, G., Ganter, M., Lim, C., and Stal, D. 1997. Skeleton-based modeling operations on solids. Solid Modeling, 141--154.]] Google Scholar
- Tappert, C. 1982. Cursive script recognition by elastic matching. IBM Res. Develop. 26, 6, 765--771.]]Google Scholar
- Taubin, G. and Cooper, D. 1992. Geometric Invariance in Computer Vision. MIT Press, Chapter Object recognition based on moment (of algebraic) invariants.]] Google Scholar
- Terzopoulos, D. and Metaxas, D. 1991. Dynamic 3d models with local and global deformations: Deformable superquadrics. IEEE Trans. Pattern Anal. and Mach. Intell. 13, 7, 703--714.]] Google Scholar
- Thacker, N., Riocreux, P., and Yates, R. 1995. Assessing the completeness properties of pairwise geometric histograms. Image and Vision Computing 13, 5, 423--429.]]Google Scholar
- Tsai, W. and Yu, S. 1985. Attributive string matching with merging for shape recognition. IEEE Trans. Pattern Anal. Mach. Intell. 7, 453--462.]]Google Scholar
- Uras, C. and Verri, A. 1994. On the recognition of the alphabet of the sign language through size functions. IAPR, 334--338.]]Google Scholar
- Uras, C. and Verri, A. 1997. Computing size functions from edge maps. Int. J. Comput. Vis. 23, 2, 169--183.]] Google Scholar
- Veltkamp, R. C. and Hagedoorn, M. 1999. State-of-the-art in shape matching. Tech. Rep. UU-CS-1999-27, Utrecht University, the Netherlands.]]Google Scholar
- Werman, M., Peleg, S., and Rosenfeld, A. 1985. A distance metric for multi-dimensional histograms. Computer, Vision, Graphics, and Image Processing 32, 328--336.]]Google Scholar
- Wu, K. and Levine, M. 1994. Recovering parametrics geons from multiview range data. CVPR, 159--166.]]Google Scholar
- Young, I., Walker, J., and Bowie, J. 1974. An analysis technique for biological shape. Computer Graphics and Image Processing 25, 357--370.]]Google Scholar
- Zhang, D. and Hebert, M. 1999. Harmonic maps and their applications in surface matching. IEEE Conference on Computer Vision and Pattern Recognition (CVPR '99).]]Google Scholar
Index Terms
- Shape distributions
Recommendations
Ricci Flow for 3D Shape Analysis
Ricci flow is a powerful curvature flow method, which is invariant to rigid motion, scaling, isometric, and conformal deformations. We present the first application of surface Ricci flow in computer vision. Previous methods based on conformal geometry, ...
2D-Shape Analysis Using Conformal Mapping
The study of 2D shapes and their similarities is a central problem in the field of vision. It arises in particular from the task of classifying and recognizing objects from their observed silhouette. Defining natural distances between 2D shapes creates ...
Pairwise Harmonics for Shape Analysis
This paper introduces a simple yet effective shape analysis mechanism for geometry processing. Unlike traditional shape analysis techniques which compute descriptors per surface point up to certain neighborhoods, we introduce a shape analysis framework ...
Comments