Joint probabilistic matching using m-Best solutions

Seyed Hamid Rezatofighi, Anton Milani, Zhen Zhang, Qinfeng Shi, Anthony Dick, Ian Reid

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

23 Citations (Scopus)


Matching between two sets of objects is typically approached by finding the object pairs that collectively maximize the joint matching score. In this paper, we argue that this single solution does not necessarily lead to the optimal matching accuracy and that general one-to-one assignment problems can be improved by considering multiple hypotheses before computing the final similarity measure. To that end, we propose to utilize the marginal distributions for each entity. Previously, this idea has been neglected mainly because exact marginalization is intractable due to a combinatorial number of all possible matching permutations. Here, we propose a generic approach to efficiently approximate the marginal distributions by exploiting the m-best solutions of the original problem. This approach not only improves the matching solution, but also provides more accurate ranking of the results, because of the extra information included in the marginal distribution. We validate our claim on two distinct objectives: (i) person re-identification and temporal matching modeled as an integer linear program, and (ii) feature point matching using a quadratic cost function. Our experiments confirm that marginalization indeed leads to superior performance compared to the single (nearly) optimal solution, yielding state-of-the-art results in both applications on standard benchmarks.

Original languageEnglish
Title of host publicationProceedings - 29th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016
EditorsLourdes Agapito, Tamara Berg, Jana Kosecka, Lihi Zelnik-Manor
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages10
ISBN (Electronic)9781467388504
ISBN (Print)9781467388528
Publication statusPublished - 2016
Externally publishedYes
EventIEEE Conference on Computer Vision and Pattern Recognition 2016 - Las Vegas, United States of America
Duration: 27 Jun 201630 Jun 2016 (Proceedings)


ConferenceIEEE Conference on Computer Vision and Pattern Recognition 2016
Abbreviated titleCVPR 2016
Country/TerritoryUnited States of America
CityLas Vegas
Internet address

Cite this