Skip to main content

Research Repository

Advanced Search

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

Moreno-Garc�a, Carlos Francisco; Serratosa, Francesc; Xiaoyi, Jiang


Francesc Serratosa

Jiang Xiaoyi


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.


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:

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
Keywords Graph correspondence; Hamming distance; Edit distance; Weighted mean; Generalised median
Public URL


You might also like

Downloadable Citations