Barbara di Fabio (University of Bologna)

The shape similarity problem has been studied since long by the computer vision community for dealing with shape classi?cation and retrieval tasks. Shape properties, such as curvature, are encoded in compact representations of shapes, namely, shape descriptors. In this framework, shape similarity can be measured by de?ning an appropriate distance on the set of the chosen shape descriptors. A question that deserves attention is the choice of the distance used to compare shape descriptors. Indeed, it is clear that any data acquisition is subject to perturbations, noise and approximation errors and, without stability, distinct computational investigations of the same object could produce completely different results. So a major problem in shape comparison concerns the stability against data perturbations.
In this seminar we focus on the Reeb graph shape descriptor. Reeb graphs provide a method to combinatorially describe the shape of a manifold endowed with a Morse function.
We define a combinatorial metric for Reeb graphs of orientable surfaces in terms of the cost necessary to transform one graph into another by edit operations. The main contributions we present are the stability property and the optimality of this edit distance. More precisely, the stability result states that changes in the functions, measured by the maximum norm, imply not greater changes in the corresponding Reeb graphs, measured by the edit distance. The optimality result states that our edit distance discriminates Reeb graphs better than any other metric for Reeb graphs of surfaces satisfying the stability property.

Predavanje bo potekalo v predavalnici 104 na PMF Univerze v Zagrebu.