By the same authors

From the same journal

From the same journal

Discovering shape classes using tree edit-distance and pairwise clustering

Research output: Contribution to journalArticle

Published copy (DOI)

Author(s)

Department / unit(s)

Publication details

JournalInternational Journal of Computer Vision
Journal publication date1 May 2007
Issue number3
Volume72
Number of pages27
Pages (from-to)259-285
Original languageEnglish

Abstract

This paper describes work aimed at the unsupervised learning of shape-classes from shock trees. We commence by considering how to compute the edit distance between weighted trees. We show how to transform the tree edit distance problem into a series of maximum weight clique problems, and show how to use relaxation labeling to find an approximate solution. This allows us to compute a set of pairwise distances between graph-structures. We show how the edit distances can be used to compute a matrix of pairwise affinities using x(2) statistics. We present a maximum likelihood method for clustering the graphs by iteratively updating the elements of the affinity matrix. This involves interleaved steps for updating the affinity matrix using an eigendecomposition method and updating the cluster membership indicators. We illustrate the new tree clustering framework on shock-graphs extracted from the silhouettes of 2D shapes.

Discover related content

Find related publications, people, projects and more using interactive charts.

View graph of relations