Logo image
Back
Multilayer matching of metric structures using hierarchically well-separated trees
Journal article   Open access   Peer reviewed

Multilayer matching of metric structures using hierarchically well-separated trees

Yusuf Osmanlioglu and Ali Shokoufandeh
Pattern recognition letters, v 87, pp 63-70
01 Feb 2017
DOI: https://doi.org/10.1016/j.patrec.2016.05.030
url
https://doi.org/10.1016/j.patrec.2016.05.030View
Accepted (AM)Open Access (Publisher-Specific),  Open

Abstract

Computer Science Computer Science, Artificial Intelligence Science & Technology Technology
We consider the matching problem between two metric distributions where establishing a one-to-one matching of features may not always be possible. Although many-to-many graph matching techniques achieve the desired multi map between features, they ignore the spatial structure of the nodes. We propose a novel technique, multilayer matching, for solving the matching problem which utilizes both the individual node features and the clustering information of nodes. Our method uses the hierarchically well-separated trees (HSTs) to represent the metric distribution such that non-leaf nodes in the tree representation corresponds to a constellation of features in the original structure. By using HSTs in a linear programming setup, we obtain a matching between features through finding a mapping between non-leaf nodes among the two HSTs. We further provide a primal-dual approximation algorithm for the multilayer matching which runs several order of magnitudes faster while achieving comparable success rates. Application of the method to the image matching problem is also presented in the paper. Empirical evaluation of the method and its primal-dual extension on a set of recognition tests show the robustness and efficiency of the overall approach. (C) 2016 Elsevier B.V. All rights reserved.

Metrics

5 Record Views
2 citations in Web of Science
2 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Web of Science research areas
Computer Science, Artificial Intelligence
Logo image