Correspondence edit distance to obtain a set of weighted means of graph correspondences.

Abstract

Given a pair of data structures, such as strings, trees, graphs or sets of points, several correspondences (also referred in literature as labellings, matchings or assignments) can be defined between their local parts. The Hamming distance has been largely used to define the dissimilarity of a pair of correspondences between two data structures. Although it has the advantage of being simple in computation, it does not consider the data structures themselves, which the correspondences relate to. In this paper, we extend the definitions of a recently presented distance between correspondences based on the concept of the edit distance, which we called Correspondence edit distance. Moreover, we present an algorithm to compute the set of weighted means between a pair of graph correspondences. Both the Correspondence edit distance and the computation of the set of weighted means are necessary for the calculation of a more representative prototype between a set of correspondences. In the validation section, we show how the use of the Correspondence edit distance increases the quality of the set of weighted means compared to using the Hamming distance.

Citation

MORENO-GARCÍA, C.F., SERRATOSA, F. and XIAOYI, J. 2020. Correspondence edit distance to obtain a set of weighted means of graph correspondences. Pattern recognition letters [online], 134, pages 29-36. Available from: https://doi.org/10.1016/j.patrec.2018.08.027

• Journal Article Type: Article
• Acceptance Date: Aug 10, 2018
• Online Publication Date: Aug 30, 2018
• Publication Date: Jun 30, 2020
• Deposit Date: Sep 27, 2018
• Publicly Available Date: Aug 31, 2019
• Journal: Pattern recognition letters
• Print ISSN: 0167-8655
• Electronic ISSN: 1872-7344
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 134
• Pages: 29-36
• DOI: https://doi.org/10.1016/j.patrec.2018.08.027
• Keywords: Graph correspondence; Hamming distance; Edit distance; Weighted mean; Generalised median
• Public URL: http://hdl.handle.net/10059/3148