Research

Many-to-Many Matching

A matching algorithm that establishes many-to-many correspondences between nodes of noisy, vertex-labeled weighted graphs. The algorithm is based on recent developments in efficient low-distortion metric embedding of graphs into normed vector spaces. By embedding weighted graphs into normed vector spaces, the problem of many-to-many graph matching is reduced to that of computing a distribution-based distance measure between graph embeddings. We use a specific measure, the Earth Mover's Distance, to compute distances between sets of weighted vectors.

Reference
M. F. Demirci, A. Shokoufandeh, Y. Keselman, L. Bretzner, and S. Dickinson. Object Recognition as Many-to-Many Feature Matching. International Journal of Computer Vision, 2006, Volume 69, Number 2, pp. 203-222.

Skeletal Shape Abstraction

A new technique for learning an abstract shape prototype from a set of exemplars whose features are in many-to-many correspondence. Focusing on the domain of silhouettes, a silhouette is represented as a medial axis graph, whose nodes correspond to "parts" defined by medial branches and whose edges connect adjacent parts. Given a pair of medial axis graphs, a many-to-many correspondence between their nodes is established to find correspondences among articulating parts. Based on these correspondences, we recover the abstracted medial axis graph along with the positional and radial attributes associated with its nodes.

Reference
M. Fatih Demirci, A. Shokoufandeh, and S. Dickinson. Skeletal Shape Abstraction from Examples. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2009, Volume 31, Number 5, pp 944-952, 2009.

Shape Indexing

A technique for indexing multimedia databases in which entries can be represented as graph structures. In our method, the topological structure of a graph as well as that of its subgraphs are represented as vectors whose components
correspond to the sorted laplacian eigenvalues of the graph or subgraphs. Given
the laplacian spectrum of graph G, we draw from recently-developed techniques in the field of spectral integral variation to generate the laplacian spectrum of graph
G + e without computing its eigendecomposition, where G+e is a graph obtained by adding edge e to graph G. By doing a nearest neighbor search around the query spectra, similar but not necessarily isomorphic graphs are retrieved.

Reference
M. Fatih Demirci, R. van Leuken, R. Veltkamp. Indexing through Laplacian Spectra. Computer Vision and Image Understanding (CVIU), Volume 110/3, 2008, pp 312--325.