Graph embedding using tree edit-union

doi:10.1016/j.patcog.2006.09.006

Return

Graph embedding using tree edit-union

2007-05-01

PRE

Andrea Torsello *

Edwin R. Hancock

DOI：10.1016/j.patcog.2006.09.006

Original

Original request for help

Save

Abstract

En 中文

In this paper we address the problem of how to learn a structural prototype that can be used to represent the variations present in a set of trees. The prototype serves as a pattern space representation for the set of trees. To do this we construct a super-tree to span the union of the set of trees. This is a chicken and egg problem, since before the structure can be estimated correspondences between the nodes of the super-tree and the nodes of the sample tree must be to hand. We demonstrate how to simultaneously estimate the structure of the super-tree and recover the required correspondences by minimizing the sum of the tree edit-distances over pairs of trees, subject to edge consistency constraints. Each node of the super-tree corresponds to a dimension of the pattern space, and for each tree we construct a pattern vector in which the elements of the weights corresponding to each of the dimensions of the super-tree. We perform pattern analysis on the set of trees by performing principal components analysis on the vectors. The method is illustrated on a shape analysis problem involving shock-trees extracted from the skeletons of 2D objects. (c) 2006 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.

Keywords:

2D shape

skeleton

tree-union

embedding

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.