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

4.Stop criterion: If centroids remain unchanged after update step, stop and return M. Otherwise, go to step 2.

Using the set of centroids, M, and the heat kernel signatures previously calculated for a shape, P, we need to compute a single descriptor for P, so it is necessary to combine the local descriptors in a shape descriptor. To tackle this problem, we calculate the feature distribution at a vertex x P as θ (x) = (θ1(x), . . . , θk (x))T where

where c(x) is a constant selected such that θ (x) 2 = 1, p(x) is the heat kernel signature of x, mi is the centroid of cluster Ci , and σ is constant. Each bin in θ (x) can be considered as the probability that x belongs to the cluster corresponding to such a bin. This is a soft version of quantization because the classic bag of features approach considers placing a one in the bin corresponding to the closest cluster and zeros in the rest. Although the classic way can be performed here, the soft version has proved to be effective in experiments.

To obtain a shape descriptor, the feature distributions are simply added to obtain

x S

and the matching between two shapes S and T is performed by using the L1 distance

Nevertheless, during the quantization process, the spatial information is lost. Obviously, this information could be useful in the matching process. To address this problem, Ovsjanikov et al. [83] proposed a feature distribution among pairs of descriptors using a weighting factor related to spatial information. Again, we can use the heat kernel Kt (x, y) as a spatial factor which will have high values for close points x and y. Therefore, the following definition for descriptors should be used:

x S y S

This descriptor results in a k × k matrix and the distance between two shapes can be done with the L1 distance, as usual.

Table 7.6 Performance using bag of features with vocabulary size 48. Table reproduced from Ovsjanikov et al. [83]

7.3.4.1 Evaluation

The main goal of this technique is to be robust in large scale databases, so the authors composed a database with models from the TOSCA dataset, the Princeton shape benchmark and the Sumner dataset. The performance was measured using ROC curves. It is important to note that the shapes in the TOSCA dataset were used as positive examples. These shapes contain transformed versions of the original shapes (null shapes), so the experiments were performed to assess the ability of the algorithm to retrieve shapes under the transformations (isometry, topology, triangulation, partiality).

The parameters used in computing the final descriptor were t0 = 1024 and α = 1.32, the size of vocabulary was 48, σ for soft quantization was set to twice the median size of the clusters in the geometric vocabulary. In addition, only 200 eigenvalues were used to compute the heat kernel signatures in Eq. (7.44).

The authors used three criteria to evaluate their method:

•Equal error rate (EER), the value of false positive rate (FPR) at which it equals the false negative rate (FNR).

•FPR at 1 % FNR.

•FPR at 0.1 % FNR.

In terms of EER, when null shapes were used as queries, the method obtained 0.97 %. With respect to the transformations, ‘topology’ gave the best performance with 1.12 %, followed by ‘isometry’ with 1.34 %. These results show that this method is robust in the presence of transformations such as topology changes and isometry. We can conjecture that the formulation of the heat kernel signatures, over which the algorithm is based, largely supports these issues. This fact is also noted in the performance of the partiality transformation (3.81 % in terms of EER). As the heat kernel signature is based on the Laplace-Beltrami operator, the partiality transformation reduces the chance of correctly retrieving similar shapes because with partial shapes the intrinsic geometry changes considerably. Tables 7.6 and 7.7 show the complete results.

a number of areas which require further work and progress. This section is devoted to presenting the trends in future research and the challenges which concern the community.

Query specification. The research is commonly focused on testing the effectiveness and efficiency of the presented proposals, however an important factor is left out, users. As a result, little work has been done in query specification. It is generally assumed that we have a query object in the representation required by the application. Nevertheless, often we are interested in retrieving objects similar to the query, so a natural question arises: If we have an object (the query) visually similar to our needs, why do we proceed to search? A more interesting approach is to provide the query as images, video, sketches, or text. However, this proposal will often require human interaction to periodically feed back advisory information to the search. For example, in content-based image retrieval, much research has turned to using sketches as a more natural way of querying an image. This trend has raised new challenges and research interests which are also expected to emerge in the shape retrieval and recognition community.

Efficiency and large scale retrieval. Although a relative level of effectiveness has recently been achieved both in shape retrieval and recognition, important issues related to the efficiency require attention, even if approaches such as local features and the Laplace-Beltrami operator have begun to be extensively used. In addition, most techniques present results over publicly available datasets of no more than 2000 objects and results about efficiency are not even provided. Moreover, Laplace-Beltrami based approaches rely on extensive computations of eigenvalues and eigenvectors of huge matrices, so it is often necessary to simplify the meshes before processing at the expense of losing the level of detail. In this sense, efficient variants and alternatives are expected to be studied.

Object representation. As can be noted from previous sections of this chapter, many approaches rely on a boundary representation for 3D shapes. Perhaps this follows from the fact that this representation is preferred to others because its simplicity and suitability for rendering tasks. In addition, triangle meshes are widely available for processing and the vast majority of 3D objects on the Internet are found in this way. Nevertheless, some potential applications use different representations such as parametric surfaces in CAD and volumetric information in medicine. Each representation has intrinsic advantages which should be considered in order to exploit the information as it is.

Partial matching. A lot of work has been done for 3D objects when the required matching model is global, visual similarity. By global, we mean that given a 3D object, and algorithm retrieves those objects in the database that look visually similar and the whole shape structure is used for comparison. However, many presented methods do not allow partial matching due to the restricted global model that they assume. So given a part of a shape as a query, an interesting problem is to try to retrieve those objects in the database that contain visually similar parts to that query. Difficulties can arise due to the need to represent a model in a compact way, for instance, with local information whose extent is unknown a-priori. In addition, the

matching becomes an expensive task because of the exponential amount of possible memberships of the query. Moreover, an even harder problem is to quantify the similarity and partiality, since the similarity strongly depends of the level of partiality allowed while searching.

Domain applications. With the increasing interest of the computer vision community in 3D shape retrieval and recognition, a current trend is to research the support that these can give to high level vision tasks. What is more, computer vision aims at recognizing and understanding the real composition of a viewed scene through a camera, where a scene is part of a three-dimensional world. In the future, we could consider the combination of shape retrieval and recognition with 3D reconstructions of scenes from images as an attempt to break the semantic gap between a three-dimensional scene and the image which represents it. In the same way, the field of medicine could take advantage in building 3D image analysis automated systems such as magnetic resonance images (MRI) and computed tomographies. It is easy to obtain three-dimensional representations from this kind of information and further processing can be beneficial. Another interesting application is modeling support, such as is required in videogames, 3D films and special effects; all of these require a large amount of work in modeling. These applications could benefit from shape retrieval and recognition tasks to reduce the time spent modeling.

Automatic 3D objects annotation. In order to increase effectiveness, we may require more semantic information to complement the geometric information extracted from the shape. Information about composition is a good choice, so it is necessary to maintain textual information which represent rich semantic information to be used in retrieval tasks. Nevertheless, attaching tags to shapes by humans is an expensive task, taking into account the amount of objects in a database. Thus, by using shape retrieval and recognition we can assign textual tags based on visual similarity or functionality. In addition, this approach can be used to add semantic information, which can be used to improve the visual search effectiveness.

7.5 Concluding Remarks

This chapter introduces the 3D shape matching process from the point of view of representative approaches in the field, potential applications and the main challenges which need to be addressed. The wide variety of available 3D data allows us to choose between different characteristics such as level of detail, shapes classes, and so forth. In addition to the standard datasets, many shape recognition applications use custom-acquired data in order to test their proposals with respect to domainoriented information. However it is important to use datasets widely employed and accepted by the community to have consistent research results and valuable performance comparisons.

Just as the amount of available 3D data has considerably grown in recent times, there is also an increasing interest of researchers for proposing new approaches for shape matching and studying the potential applications in several fields. We have