Generalised Median of a Set of Correspondences Based on the Hamming Distance
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 r
- PDF / 1,779,589 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 50 Downloads / 197 Views
ract. 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. Keywords: Correspondence Mappings median Linear assignment problem
Hamming distance
Generalised
1 Introduction In several pattern recognition applications, there is a need to define an element-to-element relation between two objects. This process, commonly referred as “matching”, has been applied on data structures such as sets of points [1], strings [2], trees [3] and most notably, graphs [4–8]. While this previous work demonstrates that there has been a long standing effort to increase the quality of the methods that perform structural matching, it may also derive in scenarios where we encounter two or more parties which, having applied different matching algorithms, have produced several matching solutions. These solutions, onwards referred as “correspondences”, may be the result of the several existing methodologies or different parameterisations of these
This research is supported by projects DPI2013-42458-P, TIN2013-47245-C2-2-R, and by Consejo Nacional de Ciencia y Tecnología (CONACyT México). © Springer International Publishing AG 2016 A. Robles-Kelly et al. (Eds.): S+SSPR 2016, LNCS 10029, pp. 507–518, 2016. DOI: 10.1007/978-3-319-49055-7_45
508
C.F. Moreno-García et al.
methodologies, which generate each time a different set of mappings between the elements of an output data structure and the elements of an input data structure. Given a set of objects, their median is defined as the object that has the smallest sum of distances (SOD) [9, 10] to all objects in the set [11]. From this definition, we are able to identify the generalised median (GM) and the set median, which difference lies in the space where each median is searched for. In the first case there are no restrictions for the search, while on the second case the exploration space is restricted to the elements in the set. Due to its robustness, the concept of GM has been implemented to deduce the representative prototype of a set of data structures [12] and for clustering ensemble purposes [13] on data structures such as strings [14], graphs [15] and data clusters [16]. For these data structures (and for correspondences as well), the GM computation turns out to be an NP-complete
Data Loading...