Deakin University
Browse

File(s) under permanent embargo

Geometric graph comparison from an alignment viewpoint

journal contribution
posted on 2012-10-01, 00:00 authored by Surya Prakash, Antonio Robles-KellyAntonio Robles-Kelly
In this paper we propose a new approach for the comparison and retrieval of geometric graphs formulated from an alignment perspective. The algorithm presented here is quite general in nature and applies to geometric graphs of any dimension. The method involves two major steps. Firstly graph alignment is effected making use of an optimisation approach whose target function arises from a diffusion process over the graphs under study. This provides, from the theoretical viewpoint, a link between stochastic processes on graphs and the heat kernel. The second step involves using a probabilistic approach to recover the transformation parameters that map the graph-vertices to one another so as to permit the computation of a similarity measure based on the goodness of fit between the two graphs under study. Here, we view the transformation parameters as random variables and aim at minimising the Kullback–Liebler divergence between the two graphical structures under study. We provide a sensitivity analysis on synthetic data and illustrate the utility of the method for purposes of comparison and retrieval of CAD objects and binary shape categorisation. We also compare our results to those yielded by alternatives elsewhere in the literature.

History

Journal

Pattern recognition

Volume

45

Pagination

3780-3794

Location

Amsterdam, The Netherlands

ISSN

0031-3203

Language

eng

Publication classification

C1.1 Refereed article in a scholarly journal

Copyright notice

2012, Elsevier Ltd.

Issue

10

Publisher

Elsevier