Diverse M-Best Solutions by Dynamic Programming

Abstract

Many computer vision pipelines involve dynamic programming primitives such as finding a shortest path or the minimum energy solution in a tree-shaped probabilistic graphical model. In such cases, extracting not merely the best, but the set of M-best solutions is useful to generate a rich collection of candidate proposals that can be used in downstream processing. In this work, we show how M-best solutions of tree-shaped graphical models can be obtained by dynamic programming on a special graph with M layers. The proposed multi-layer concept is optimal for searching M-best solutions, and so flexible that it can also approximate M-best diverse solutions. We illustrate the usefulness with applications to object detection, panorama stitching and centerline extraction. Note: We have observed that an assumption in section 4 of our paper is not always fulfilled, see the attached corrigendum for details.

Original document

The different versions of the original document can be found in:

• http://arxiv.org/abs/1803.05748

• http://arxiv.org/pdf/1803.05748

• http://bigwww.epfl.ch/publications/haubold1701.html,

http://bigwww.epfl.ch/publications/haubold1701.pdf,

http://bigwww.epfl.ch/publications/haubold1701.ps,

https://infoscience.epfl.ch/record/234415/files/haubold1701p.pdf,

http://infoscience.epfl.ch/record/234415

• http://link.springer.com/content/pdf/10.1007/978-3-319-66709-6_21,

http://dx.doi.org/10.1007/978-3-319-66709-6_21 under the license http://www.springer.com/tdm

• https://dblp.uni-trier.de/db/journals/corr/corr1803.html#abs-1803-05748,

https://link.springer.com/chapter/10.1007/978-3-319-66709-6_21,

https://arxiv.org/pdf/1803.05748,

https://ui.adsabs.harvard.edu/abs/2018arXiv180305748H/abstract,

https://arxiv.org/abs/1803.05748v1,

http://export.arxiv.org/pdf/1803.05748,

https://doi.org/10.1007/978-3-319-66709-6_21,

http://export.arxiv.org/abs/1803.05748,

https://rd.springer.com/chapter/10.1007/978-3-319-66709-6_21,

https://infoscience.epfl.ch/record/234415,

https://ru.arxiv.org/abs/1803.05748,

https://core.ac.uk/display/148036106,

https://academic.microsoft.com/#/detail/2746198904