1 Introduction2 Problem Statement3 Proposed Method3.1 Global Geodesic Shape Function3.2 Global Geodesic Shape Distribution4 Probabilistic Dissimilarity5 Experimental Results6 Conclusions and Future WorkReferencesGeodesic Object Representation and RecognitionA. Ben Hamza and Hamid KrimDepartment of Electrical and Computer EngineeringNorth Carolina State University, Raleigh NC 27695, USAAbstract. This paper describes a shape signature that captures theintrinsic geometric structure of 3D objects. The primary motivation ofthe proposed approach is to encode a 3D shape into a one-dimensionalgeodesic distribution function. This compact and computationally sim-ple representation is based on a global geodesic distance defined on theobject surface, and takes the form of a kernel density estimate. To gainfurther insight into the geodesic shape distribution and its practicalityin 3D computer imagery, some numerical experiments are provided todemonstrate the potential and the much improved performance of theproposed methodology in 3D object matching. This is carried out usingan information-theoretic measure of dissimilarity between probabilisticshape distributions.Keywords: Geodesic shape distribution, 3D object representation andmatching, Jensen-Shannon divergence.1 IntroductionThree-dimensional objects consist of geometric and topological information, andtheir compact representation is an important step towards a variety of imagingapplications including indexing, retrieval, and matching in a database of 3D mod-els. The latter will be the focus of the present paper. There are two major stepsin object matching. The first step involves finding a reliable and efficient shaperepresentation or descriptor, and the second step is the design of an appropriatedissimilarity measure for object comparison between shape representations.Most three-dimensional shape matching techniques proposed in the literatureof computer graphics, computer vision and computer-aided design are based ongeometric representations which represent the features of an object in such away that the shape dissimilarity problem reduces to the problem of comparingtwo such object representations. Feature-based methods require that features beextracted and described before two objects can be compared. Among feature-based methods, one popular approach is graph matching, where two objectsare represented by their graphs composed of vertices and edges. An efficientrepresentation that captures the topological properties of 3D objects is the Reebgraph descriptor proposed by Shinagawa et al. [1]. The vertices of the Reeb graphare the singular points of a function defined on the underlying object [1,2]. Thesesingularities carry important information for further operations, such as imageregistration, shape analysis, surface evolution and object recognition [3,4,5].I. Nystr¨om et al. (Eds.): DGCI 2003, LNCS 2886, pp. 378–387, 2003.c Springer-Verlag Berlin Heidelberg 2003Geodesic Object Representation and Recognition 379An alternative to feature-based representations is the shape distribution de-veloped by Osada et al [6]. The idea here is to represent an object by a globalhistogram based on the Euclidean distance defined on the surface of the object.The shape matching problem is then performed by computing a dissimilaritymeasure between the shape distributions of two arbitrary objects. This approachis computationally stable and relatively insensitive to noise. Because of unsuit-ability of the Euclidean distance when dealing with nonlinear manifolds, theshape distribution, however, does not capture the nonlinear geometric structureof the data.In this paper, we propose a new approach for object matching based ona global geodesic measure. The key idea behind our technique is to representan object by a probabilistic shape descriptor called geodesic shape distributionthat measures the global geodesic distance between two arbitrary points on thesurface of an object. In contrast to the Euclidean distance which is more suit-able for linear spaces, the geodesic distance has the advantage to be able tocapture the (nonlinear) intrinsic geometric structure of the data. The geodesicshape distribution may be used to facilitate representation, indexing, retrieval,and object matching in a database of 3D models. More importantly, the geodesicshape distribution provides a new way of looking at the object matching problemby exploring the intrinsic geometry of the shape. The matching task thereforebecomes a one-dimensional comparison problem between probability distribu-tions which is much easier than comparing 3D structures. Object matching maybe carried out by dissimilarity measure calculations between the correspondinggeodesic shape distributions, and it is accomplished in a highly efficient way.Information-theoretic measures provide quantitative entropic divergences be-tween two probability distributions. A common entropic dissimilarity measureis Kullback-Leibler divergence [7] which has been successfully used in manyapplications including indexing and image retrieval [8]. Another entropy-basedmeasure is the Jensen-Shannon divergence which may be defined between anynumber of probability distributions [9], and it has been applied to a variety ofsignal/image processing and computer vision applications including DEM imagematching [10], and ISAR image registration [11].The rest of this paper is organized as follows. The next section is devotedto the problem formulation. Section 3 describes the representation step of ourproposed technique. In Section 4, we present the Jensen-Shannon divergenceand show its attractive properties as a dissimilarity measure between probabilitydistributions. In Section 5, we provide numerical simulations to show the powerof the geodesic shape distribution for 3D object matching. And finally, Section 6contains some conclusions and describes a brief outline of possible future work.2 Problem StatementThree-dimensional objects are usually represented as triangular meshes in com-puter graphics and geometric-aided design. A triangle mesh is a pair M =(V, T ),where V =(v1,...,vm) is the set of vertices, and T =(T1,...,Tn) is the set oftriangles.380 A. Ben Hamza and Hamid KrimIn scientific visualization and analysis, a triangle mesh is too large to beexamined without simplification. One way to overcome this limitation is to rep-resent a triangle mesh by surface features which can easily be computed andwhich effectively