Материал: [2.1] 3D Imaging, Analysis and Applications-Springer-Verlag London (2012)

proposed to represent a 3D object as a set of salient geometric features, which determine the complete object. Their scheme entirely relies on curvature information over the shape’s surface and the matching is done by indexing the salient features using geometric hashing [108] with a vote scheme to determine similar objects.

An interesting approach was given by Hu and Hua [52] to address the non-rigid and partial matching problem. Their method consists in using the Laplace-Beltrami operator to detect and describe interest points in 3D objects. This operator captures the information of a mesh in different scales, and it is also an isometric invariant, which is an important property to support geometric invariance. The authors proposed an energy function based on the Laplace-Beltrami spectrum to detect interest points with its associated scale. Using these points, along with their respective scales, it is possible to extract descriptors for each interest point from the local Laplace-Beltrami spectrum. The matching is performed by solving an integer quadratic programming problem where two sets of features belonging to shapes to be matched are involved.

One of the most widely used approaches for managing local descriptors is the bag-of-features approach. This begins by clustering all the local descriptors from an entire collection and calculating the centroids for each cluster. Then, each shape is represented as a histogram with a number of bins equal to the number of clusters. Each descriptor adds one into the bin corresponding to the closest centroid. Toldo et al. [103] proposed to segment a given mesh and build a descriptor for each segment. Subsequently, a bag-of-features approach combines all the descriptors in the mesh. Similarly, Ovsjanikov et al. [83] proposed a soft version of the Bag-of-Features approach applied to dense descriptors based on the heat kernel signature, originally introduced by Sun et al. [97], which is related to the Laplace-Beltrami operator. The authors also presented a spatially sensitive bag-of-features technique which gave good results in shape retrieval.

Obviously, the use of local features highlights a new problem: the amount of information used in the matching. With these approaches, a shape is represented with a set of descriptors and the problem of matching becomes non-trivial. In addition, the matching step is more expensive than computing a distance between points, as used in global matching. In this respect, future research directions could be motivated by this kind of matching.

With respect to 3D shape recognition, Table 7.2 shows a selection of techniques proposed to date.

As noted, most presented techniques make extensive use of local features because these can mitigate the effect of occlusion in cluttered scenes. Nevertheless, imagebased proposals have also been considered. Lee and Drew [69] extracted contours from 2D projections around a 3D object, and subsequently scale-space curvature image was obtained for each projection. These images were used to identify the class of an object and determine the object in the selected class. In addition, Cyr and Kimia [35] extracted 2D views which were grouped in view sets called aspects. These aspects were represented by a prototype view for accelerating the recognition process given views from new objects.

Although it is possible to apply any approach from shape retrieval proposals to object recognition, the general technique that has received most attention is matching by local features. In their seminal work, Chua and Jarvis [33] presented the point signature, a 1D descriptor for points on a surface. To construct the descriptor around some 3D surface point, a 3D space curve is generated as the intersection of a sphere around that point. A plane is fitted to this curve which is translated along its normal until it contains the sphere center (i.e. the surface point). The distance profile of the space curve to this plane, then forms the point’s local surface descriptor. In matching, correspondences were found and a voting scheme allowed the determination of objects in a scene.

Following the idea of representing the surrounding geometry of a point, Johnson and Hebert [57] proposed their well-known and well-studied spin images. Given an object, the authors constructed 2D descriptors for points over the surface. As the name suggests, a spin image was obtained by spinning a half plane around the analyzed point’s normal and accumulating the points lying in bins of that half plane. The matching was performed by finding correspondences using the spin images between an object and a scene and subsequently a geometric verification with a modified version of the iterative closest point (ICP) algorithm [14] was performed. A variation of this technique was spherical spin images, presented by Ruiz-Correa et al. [94].

Simple information has also been employed. For instance, Hetzel et al. [50] used pixels depth, normals and curvature information in order to combine them in multi-dimensional histograms. Thus, the matching step was performed using χ 2- divergence and a posteriori Bayesian classifier. Sun et al. [98] proposed their point fingerprint, which consisted of geodesic contours projected onto a point’s tangent plane. Frome et al. [41] introduced 3D shape contexts and harmonic shape contexts. The idea behind the shape context approach is accumulating the surrounding points using concentric spheres around the analyzed point. The authors proposed to use

locality-sensitive hashing for matching. Likewise, Li and Guskov [72] used spin images and normal based signatures to describe selected points over range scans. A combination of pyramid matching and support vector machines (SVMs) were applied for object recognition giving good results on CAD models and faces.

More recently, Chen and Bhanu [32] proposed an approach to recognize highly similar 3D objects in range images. As the authors claimed, several techniques have been proposed to recognize objects in dissimilar classes, however the task of recognizing objects with high similarity is challenging. Given an object, the authors extracted local surface patches on interest points found using curvature information. Due to the high dimensionality of the descriptors, these were embedded in a low dimensional space using FastMap [40]. Then, the low dimensional descriptors were organized in a kd-tree where efficient nearest neighbor algorithms can be applied. Using the kd-tree, it is possible to find correspondences between two objects. A SVM classifier ranks the correspondences according to geometric constraints returning the most promising correspondences which were verified with the iterative closest point algorithm. The object with the least mean square error is selected.

7.3 3D Shape Retrieval Techniques

The aim of this section is to present both mature and promising recent material concerning 3D shape retrieval and recognition. We provide detailed descriptions of four techniques: the depth-buffer descriptor, spin images, salient spectral features for shape matching, and heat kernel signatures.

The aforementioned methods address different aspects of shape matching. Firstly, the depth-buffer descriptor is a technique suitable for global matching. Secondly, the spin image is a pioneering representation and approach in 3D object recognition. Finally, salient spectral features and heat kernel signatures methods are recent proposals to tackle the problems of non-rigid and partial 3D shape matching.

An important issue to be considered before describing the approaches is shape representation. Although there are many ways to represent a 3D object, boundary representations have mostly been used where objects are represented by a limit surface that distinguishes the inside from the outside of the object. Moreover, the surface can be approximated in a piece-wise manner, reducing the amount of information needed to represent it at the expense of losing detail. The most common way is depicting the surface by a set of points (vertices) and polygons (faces) and, in fact, it is preferable to take triangular faces for efficiency and effectiveness in computation. Surprisingly, this representation allows one to conceive almost any object with the desired level of detail.

All the techniques presented in this section use triangular meshes for representing shapes.

7.3.1 Depth-Buffer Descriptor

The depth-buffer descriptor [106] is an image-based descriptor. It computes 2D projections of the 3D model, and then computes its feature vector from the obtained projections. This descriptor considers not only the silhouette of each projection of the 3D model, but also considers the depth information (distance from the clipping plane, where the projection starts, to the 3D model).

The process to obtain the feature vector associated to the depth-buffer descriptor is summarized as follows.

1.Pose normalization: The depth-buffer descriptor starts with the 3D model oriented and scaled according to a predefined normalized pose.

2.Depth buffer construction: The feature extraction method renders six greyscale images using parallel projection (two projections for each principal axis). Each pixel in the 2D projection encodes, to an 8-bit grey value, the orthogonal distance from the viewing plane (i.e. sides of the bounding cube) to the object. These images correspond to the concept of z- or depth-buffers in computer graphics.

3.Fourier transformation: After rendering, the method transforms the six images using the standard 2D discrete Fourier transform.

4.Selection of coefficients: The magnitudes of certain k low-frequency coefficients of each image contribute to the depth-buffer feature vector of dimensionality 6k.

7.3.1.1 Computing the 2D Projections

The first step of the depth-buffer descriptor computes 2D projections of the 3D model. To accomplish this, the model must be first normalized in pose (by means of PCA analysis, for example), as this descriptor is not inherently invariant to rotations or scaling. Then, the model must be enclosed in a bounding cube. Each face of this cube is divided into n × n cells (with initial value 0), which will be used to compute the depth-buffers for each 2D projection. Finally, the 3D model is orthogonally projected to the face of the bounding cube. The value associated to each cell is the normalized orthogonal distance (a value in [0, 1]) between the face of the bounding cube and the closest point (orthogonally) in the 3D model.

Formally, let w be the width of the bounding cube. If a point p belongs to the surface of the 3D model, its closest orthogonal cell in the face of the bounding cube is c, and p is the closest point in the mesh to c, the associated value of c is

value(c) = w − δ(c, p) , w

where δ(c, p) is the distance from c to p.

This method works well if the 3D model does not contain a significant number of outliers. Otherwise, the faces of the bounding cube may be too far to the actual