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)



Publication details

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


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.

    Research areas

  • shock trees, shape recognition, pairwise clustering, edit-distance, MAXIMUM CLIQUE PROBLEM, SHOCK GRAPHS, RECOGNITION, SIMILARITY, ALGORITHM, DYNAMICS

Discover related content

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

View graph of relations