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.

Journal Article Type Article
Publication Date Jun 30, 2020
Journal Pattern recognition letters
Print ISSN 0167-8655
Electronic ISSN 1872-7344
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 134
Pages 29-36
Institution 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:
Keywords Graph correspondence; Hamming distance; Edit distance; Weighted mean; Generalised median


You might also like

Downloadable Citations