An Edit Distance for Reeb Graphs

Bauer, Ulrich; Fabio, Barbara Di; Landi, Claudia

An Edit Distance for Reeb Graphs

Files

027-034.pdf (164.45 KB)

Date

2016

Authors

Bauer, Ulrich
Fabio, Barbara Di
Landi, Claudia

Publisher

The Eurographics Association

Abstract

We consider the problem of assessing the similarity of 3D shapes using Reeb graphs from the standpoint of robustness under perturbations. For this purpose, 3D objects are viewed as spaces endowed with real-valued functions, while the similarity between the resulting Reeb graphs is addressed through a graph edit distance. The cases of smooth functions on manifolds and piecewise linear functions on polyhedra stand out as the most interesting ones. The main contribution of this paper is the introduction of a general edit distance suitable for comparing Reeb graphs in these settings. This edit distance promises to be useful for applications in 3D object retrieval because of its stability properties in the presence of noise.

        @inproceedings{10.2312:3dor.20161084
,
booktitle = {Eurographics Workshop on 3D Object Retrieval
},
editor = {A. Ferreira and A. Giachetti and D. Giorgi
},
title = {{An Edit Distance for Reeb Graphs
}},
author = {Bauer, Ulrich and 
Fabio, Barbara Di and 
Landi, Claudia
},
year = {2016
},
publisher = {The Eurographics Association
},
ISSN = {1997-0471
},
ISBN = {978-3-03868-004-8
},
DOI = {10.2312/3dor.20161084
}
}