A correspondence is a set of mappings that establishes a relation between the elements of two data structures (i.e. sets of points, strings, trees or graphs). If we consider several correspondences between the same two structures, one option to define a representative of them is through the generalised median correspondence. In general, the computation of the generalised median is an NP-complete task. In this paper, we present two methods to calculate the generalised median correspondence of multiple correspondences. The first one obtains the optimal solution in cubic time, but it is restricted to the Hamming distance. The second one obtains a sub-optimal solution through an iterative approach, but does not have any restrictions with respect to the used distance. We compare both proposals in terms of the distance to the true generalised median and runtime.
MORENO-GARCÍA, C.F., SERRATOSA, F. and CORTÉS, X. 2016. Generalised median of a set of correspondences based on the hamming distance. In: Robles-Kelly A., Loog M., Biggio B., Escolano F., Wilson R. (eds.) Structural, syntatic and statistical pattern recognition: proceedings of the 2016 Joint International Association of Pattern Recognition (IAPR) structural, syntatic and statistical pattern recognition international workshop (S+SSPR 2016), 29 November - 2 December 2016, Mérida, Mexico. Lecture Notes in Computer Science, vol 10029. Cham: Springer, pages 507-518. Available from: https://doi.org/10.1007/978-3-319-49055-7_45