LSAPE - Bipartite Matching
An easy-to-use C++/Matlab toolbox for finding optimal correspondences between the elements of two sets, i.e. solving bipartite matching problems (aka linear sum assignment problems), together with their dual (aka labeling problems). Equivalently, the toolbox allows to design dissimilarity measures between two sets, based on optimal correspondences.
The following problems are solved:
- symmetric MIN-LSAP / minimal-cost perfect bipartite matching
- asymmetric MIN-LSAP / minimal-cost maximum bipartite matching
- MIN-LSAP with Error-correction (LSAPE) / minimal-cost error-correcting bipartite matching
with the Hungarian method (each problem is solved by a specific Hungarian algorithm).
Greedy algorithms are also proposed to find cheap assignments.
Authors
Sébastien Bougleux and Luc Brun (Normandie Univ, CNRS - ENSICAEN - UNICAEN, GREYC)
Contributors
Évariste Daller (Normandie Univ, CNRS - ENSICAEN - UNICAEN, GREYC)
Benoit Gaüzère (Normandie Univ, INSA de Rouen, LITIS)
License CeCILL-C
Don't forget citations
- For error-correcting graph matching, cite this website and
S. Bougleux, B. Gaüzère, L. Brun, A Hungarian Algorithm for Error-Correcting Graph Matching, IAPR TC15 Workshop on Graph-based Represenations, LNCS 10310, p. 118--127, Springer, 2017, or
S. Bougleux and L. Brun, Linear Sum Assignment Problem with Edition, Technical Report, Normandie Univ, 2016 - For birpartite graph matching, cite this website