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

9. REEB GRAPHS
j associated to model i . Finally, the combination of the different structural/feature-based kernels
is used to enhance the retrieval results. Since each real function f j provides a similarity vector for
the query q , the first r nearest neighbors of q seen with f j can be computed by ranking the simi-
larities in decreasing order. e application of the F real functions thus gives F nearest neighbor
lists for a query q , viewed with each of these functions. An aggregation procedure is adopted
to define a single kernel, function of the basis kernels. In general, weights can encode a priori
knowledge about, e.g., the kernel ability to retrieve some particular classes or expert knowledge.
ey can also be learned from a set of training examples [ 13 , 51 ].
Reeb graphs for partial matching Being a topological structure that explicitly associates the
graph elements (nodes and edges) to shape parts, the Reeb graph has also been successfully
adopted for partial correspondence [ 26 , 197 ].
In [ 197 ] each shape is decomposed into charts with disk or annulus topology only and
the partial similarity between two shapes is evaluated by computing a variant of their maximum
common sub-graph. is shape decomposition enables the computation of concise and efficient
signatures for object parts based on parameterization techniques (see Figure 9.4 ). To limit the
Figure 9.4: Reeb chart (bright colors) and pattern (dark colors) matching between a boy and a centaur.
Unmatched charts are black.
number of possible combinations during the matching process, each signature of the decomposi-
tion (Reeb pattern) is matched only with topologically equivalent patterns. Since the Reeb graph
extraction is based on the geodesic distance from shape extrema, the description is also invariant
against rigid transformations and robust against non-rigid transformations and surface noise.