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

Chapter 7

3D Shape Matching for Retrieval and Recognition

Benjamin Bustos and Ivan Sipiran

Abstract Nowadays, multimedia information, such as images and videos, are present in many aspects of our lives. Three-dimensional information is also becoming important in different applications, for instance entertainment, medicine, security, art, just to name a few. Therefore, it is necessary to study how to process 3D information in order to take advantage of the properties that it provides. This chapter gives an overview of 3D shape matching and its applications to 3D shape retrieval and 3D shape recognition. In order to present the subject, we describe in detail four approaches with a good balance of maturity and novelty across the different methods. The selected approaches are: the depth buffer descriptor, spin images, salient spectral geometric features and heat kernel signatures.

7.1 Introduction

The ability to store and manipulate large amounts of information has enabled the emergence of a number of applications. Generally, the information is given as text because it is easy to produce and understand by a computer. However, there are situations where information cannot be suitably represented by text, such as a tourist’s photo album.

Thus, the use and availability of multimedia information has increased considerably, on the one hand to support new applications and on the other hand due to the proliferation and accessibility of inexpensive capture devices such as digital cameras. A number of applications have benefited from this availability of images, videos and three-dimensional models, such as security, entertainment, and engineering processes. Unlike text, multimedia information is difficult to be compared directly and therefore we require techniques to manipulate it effectively.

This work has been supported by Fondecyt (Chile) Project 1110111.

B. Bustos ( ) · I. Sipiran

Department of Computer Science, University of Chile, Santiago, Chile e-mail: bebustos@dcc.uchile.cl

I. Sipiran

e-mail: isipiran@dcc.uchile.cl

Our goal in this chapter is to address the problem of comparing two 3D objects based on their shapes. Shape matching refers to the process of finding a correspondence between two shapes based on some similarity criterion. The criterion which has received most attention by the research community is the visual similarity, that is to say, two shapes should be matched if they share visually common features. In this chapter, we are interested in two processes involving 3D shapes matching, namely retrieval and recognition.

Although these processes are related, they are slightly different. On the one hand, shape recognition consists of identifying a given 3D object within a set of possible alternatives. The outcome of this process is generally the class to which the object belongs or the recognized object as stored by the recognition system. The latter is useful when the queried object represents a partial or occluded portion such as a range scan. On the other hand, shape retrieval consists of defining a measure in order to quantify the similarity between shapes. A typical outcome of this process is an ordered list of objects according to their associated measure.

In recent years, we have witnessed increasing interest in the computer graphics and computer vision communities for 3D shape retrieval and recognition. As a result, a number of techniques and approaches have been proposed for shape representation, object and feature description, feature selection, and matching algorithms. It is also important to note the large number of applications that have emerged, such as:

•Geometric 3D comparison for the shoe industry [79].

•3D hippocampi retrieval [61].

•Classification of pollen in 3D volume datasets [92].

•3D retrieval for museums [49].

•Human ear recognition in 3D [31].

•3D object classification for craniofacial research [9].

•3D protein retrieval and classification [87, 88, 112].

•CAD/CAM [113].

•Archeology [54].

•3D video sequences [53].

To improve performance in each of these applications, it is important to evaluate and compare new approaches, as they appear, with existing ones. Due to the large amount of research carried out and the large dissemination of 3D information obtained through increasingly better capture devices, several benchmarks have been presented, such as the Princeton Shape Benchmark [96], the Konstanz 3D database [26], the TOSCA dataset [18], and the Shape Retrieval Contest (SHREC) datasets (see Fig. 7.1 with objects from different datasets). Such is the interest in 3D shape retrieval that, for several years now, there have been annual competitions with more tracks and more competitors year after year.

Fig. 7.1 Datasets provide shapes with several characteristics such as size, level of detail and shape classes. This figure shows some examples from

(a) TOSCA dataset, (b) Konstanz database, (c) SHREC dataset, and (d) Princeton shape benchmark

7.1.1 Retrieval and Recognition Evaluation

A very important consideration is the methodology of evaluation for shape retrieval and recognition techniques. In this sense, the evaluation relies on the solid background of mature fields, such as pattern recognition and information retrieval. In the case of shape retrieval, the common evaluation methods are Precision-Recall curves, cumulated gain-based measurements, nearest neighbor, first-tier and secondtier [10]. For shape recognition, Receiver Operating Characteristic (ROC) curves and error rates have commonly been used [38]. In order to keep this chapter relatively self-contained, we briefly describe the evaluation measures commonly used in the literature.

In retrieval, the evaluation measures mostly consider the ranked lists retrieved when query objects are presented to the system. The main measures are as follows:

Precision: the extent to which the retrieved objects are relevant to a query. Formally, it is the ratio of correctly retrieved objects with respect to the total number of retrieved objects.

Recall: the extent to which the relevant objects are correctly retrieved. Formally, it is the ratio of correctly retrieved objects with respect to the total number of relevant objects for the query.

R-Precision: precision when the number of retrieved objects equals the number of relevant objects.

Cumulated gain-based measurements: the idea is to use the ranked position of relevant objects. First, we need to convert the retrieved list into a binary list G with 1’s in position where relevant objects appear. Second, the discounted cumulated

7.2 Literature Review

To support similarity search between two multimedia objects, we must define a model that allows us to compare them. It cannot be done directly because we are interested in retrieving similar objects stored in a database, rather than extracting identical copies. A lot of work has been done to assess the visual similarity between 3D objects when the required model is global. By global, we mean that given a 3D object, an algorithm retrieves those objects in database that look visually similar and the whole shape structure is used for the comparison. The most widely used model consists of obtaining an abstract representation of an object such as feature vectors or graphs, and the similarity is calculated based upon these representations. For example, distance metrics are commonly used to calculate similarity among feature vectors. Another similarity model which has gained much interest involves local features, especially in non-rigid and partial shape retrieval and recognition. The problem of defining a similarity model is very challenging. For example, a visual model allows us to represent a shape by its aspect. However, this model cannot be used to discriminate two shapes semantically similar, but with different aspect.

Bustos et al. [26] described a methodology that consists of representing 3D objects as real vectors of a certain dimension obtained through a transformation function. Then, these vectors can be organized in a multidimensional index, where the similarity corresponds to the proximity in the space where vectors are defined. The Minkowski distance family is usually used to measure the proximity of feature vectors. The authors presented experimental results comparing several transformation functions where the depth-buffer descriptor proposed by Vranic [106] showed the best results. Iyer et al. [55] and Tangelder et al. [100] also discussed techniques for 3D object retrieval, identifying future trends and important issues to be addressed. Also, the Princeton Shape Benchmark [96] provides a reference collection and experimental tests for several descriptors. Other surveys and reports were written by Funkhouser et al. [42], Del Bimbo et al. [15] and Bustos et al. [25, 27]. In 3D shape recognition, Campbell and Flynn [28] presented a comprehensive study of representation and recognition of free-form shapes.

Since then, many other techniques have been proposed to improve effectiveness and efficiency. A brief summary of representative approaches for shape retrieval is given in Table 7.1. Due to space limitations, this table does not show all techniques presented so far. We recommend reading Sect. 7.6 for further references.

Table 7.1 shows a simple taxonomy depending of the extracted shape information which is used in matching. Histogram-based methods summarize certain shape properties such as distribution between points on the surface [82], angle information [86], distribution of face normals [59], and so forth. These properties are used to build histograms which represent shapes and matching is done with common histogram measures. In contrast, transform-based methods apply some transform to the shapes to convert them to a numerical representation of the underlying object. Some examples of such transforms are: Fourier Transform [39], Radon Transform [36], and Wavelet Transform [67]. Image-based methods represent a 3D object as a set of projected images, so the matching becomes an image matching problem. For