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

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. (C) 2018 Elsevier B.V. All rights reserved.