Generalised median of a set of correspondences based on the hamming distance.

Moreno-Garc�a, Carlos Francisco; Serratosa, Francesc; Cort�s, Xavier

Abstract

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.

Citation

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

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 2016 Joint International Association of Pattern Recognition (IAPR) structural, syntatic and statistical pattern recognition international workshop (S+SSPR 2016)
• Start Date: Nov 29, 2016
• End Date: Dec 2, 2016
• Acceptance Date: Jun 14, 2016
• Online Publication Date: Nov 5, 2016
• Publication Date: Dec 31, 2016
• Deposit Date: Feb 10, 2020
• Publicly Available Date: Feb 13, 2020
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Pages: 507-518
• Series Title: Lecture notes in computer science
• Series Number: 10029
• Series ISSN: 0302-9743
• Book Title: Lecture Notes in Computer Science
• ISBN: 9783319490540
• DOI: https://doi.org/10.1007/978-3-319-49055-7_45
• Keywords: Correspondence; Mappings; Hamming distance; Generalised median; Linear assignment problem
• Public URL: https://rgu-repository.worktribe.com/output/816413