Reeb Graphs - Mathematical Tools for Shape Analysis and Description - page 72

9. REEB GRAPHS
where b M denotes the number of boundary components of the 2 -manifold M having genus g .
eoretical results are available for non-orientable 2 -manifolds. In this case, the number of loops
of the Reeb graph verifies the following relations: 0 1 .K/ g 2 when M is closed, and 0
1 .K/gCb M 1 for manifolds with boundary. As for 3 -manifolds, it is not true that the
number of the loops of an orientable, closed 3 -manifold is independent of the function f . In
addition, it has been proven that for every 3 -manifold M there exists at least one Morse function
f such that the Reeb graph of M with respect to f is a tree [ 48 ].
For 3 -manifolds with boundary, the 3 -manifold structure is studied either by introducing a
virtual closure of the manifold [ 68 ], or by associating a Reeb graph to each 2 -manifold boundary
component of the 3 -manifold and keeping track of the changes between interior and void with
a supplementary graph [ 180 , 181 ]. Several techniques have been reported in the literature for
the computation of Reeb graphs on 2D and 3D models [ 25 ], but also for higher dimensions
[ 63 , 98 , 157 , 159 , 196 ].

9.3 CONCEPTS IN ACTION

Feature selection and Reeb graphs for 3D classification Classifying 3D shapes is an important
issue for many applications. In [ 28 ] the authors propose a scheme for supervised 3D classification
in a multi-class problem, having two main ingredients: the first is the description of 3D objects via
spectral features obtained from Reeb graphs; the second is a feature selection technique based on
information theory. More precisely, three types of Reeb graphs are extracted from each 3D object,
corresponding to three real functions (Fig. 9.2 , left). For each graph, nine different measures are
calculated and transformed into histograms (Fig. 9.2 , middle). Only structural graph information
is taken into account, that is, only the graph connectivity, without any geometric attribute. en,
the feature selection process decides which measure and which graph to discard (Fig. 9.2 , right);
this is done by exploiting information theory to filter those features which do not contribute to
the separability of the objects into classes.
e results in [ 28 ] demonstrate the feasibility of multi-class 3D classification based on
unattributed graphs and purely structural spectral features. Moreover, the authors investigate the
importance of each of the spectral features used, and to what extent that importance depends on
the real function used to extract Reeb graphs.

Combining topological graphs and geometric attributes for efficient shape retrieval Among the
different methods for retrieval using Reeb graphs, we describe here the method in [ 12 ] that as-
sociates geometric attributes to the Extended Reeb graph [ 6 ] and performs 3D shape retrieval
through a graph matching technique based on the combination of several kernels. In such an
approach the model parts are coupled to nodes and edges: each node n of a graph G represents
one region r2R.S/ and each edge eD.v 1 ;v 2 / is associated with the surface portion bounded
by the regions r 1 and r 2 associated with v 1 and v 2 , respectively. e geometric descriptor selected
to code the model parts is the spherical harmonic descriptor [ 84 ]. Even if any feature vector de-