Diverse M-Best Solutions by Dynamic Programming

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.

• Publication year

  2017

• Venue

  German Conference on Pattern Recognition

• Publication date

  2017-09-13

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1007/978-3-319-66709-6_21arXiv 1803.05748
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Graphical model for joint segmentation and tracking of multiple dividing cells

  2015cited by this paper
• Inferring M-Best Diverse Labelings in a Single One

  2015influential reference
• Optimal Joint Segmentation and Tracking of Escherichia Coli in the Mother Machine

  2014cited by this paper
• Mode Estimation for High Dimensional Discrete Tree Graphical Models

  2014cited by this paper
• High-Resolution Stereo Datasets with Subpixel-Accurate Ground Truth

  2014cited by this paper
• Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets

  2014cited by this paper
• Computing the M Most Probable Modes of a Graphical Model

  2013cited by this paper
• Detection- and Trajectory-Level Exclusion in Multiple Object Tracking

  2013cited by this paper
• Learning to Detect Partially Overlapping Instances

  2013cited by this paper
• Discriminative Re-ranking of Diverse Segmentations

  2013cited by this paper
• Diverse M-Best Solutions in Markov Random Fields

  2012influential reference
• An Efficient Message-Passing Algorithm for the M-Best MAP Problem

  2012cited by this paper
• Panorama weaving

  2012cited by this paper
• Maximum Margin Multi-Label Structured Prediction

  2011cited by this paper
• Bucket and Mini-bucket Schemes for M Best Solutions over Graphical Models

  2011cited by this paper
• Inference Schemes for M Best Solutions for Soft CSPs

  2011cited by this paper
• Perturb-and-MAP random fields: Using discrete optimization to learn and sample from energy models

  2011cited by this paper
• CellCognition: time-resolved phenotype annotation in high-throughput live cell imaging

  2010cited by this paper
• An LP View of the M-best MAP problem

  2009cited by this paper
• Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning

  2009cited by this paper
• Stereo correspondence by dynamic programming on a tree

  2005cited by this paper
• Dual Dijkstra Search for paths with different topologies

  2003cited by this paper
• Finding the M Most Probable Configurations using Loopy Belief Propagation

  2003cited by this paper
• Ten Lectures on Statistical and Structural Pattern Recognition

  2002cited by this paper
• An efficient algorithm for finding the M most probable configurationsin probabilistic expert systems

  1998cited by this paper
• An ecient algorithm for nding the M most probable congurations in probabilistic expert systems

  1998cited by this paper
• Finding the k shortest paths

  1994cited by this paper
• An algorithm directly finding the K most probable configurations in Bayesian networks

  1994cited by this paper
• Probabilistic reasoning in intelligent systems: Networks of plausible inference

  1991cited by this paper
• A PROCEDURE FOR COMPUTING THE K BEST SOLUTIONS TO DISCRETE OPTIMIZATION PROBLEMS AND ITS APPLICATION TO THE SHORTEST PATH PROBLEM

  1972cited by this paper
• A note on two problems in connexion with graphs

  1959cited by this paper
• On the Theory of Dynamic Programming.

  1952cited by this paper

• Efficient Algorithms for Global Inference in Internet Marketplaces

  2021cites this paper
• Efficient Vertex-Oriented Polytopic Projection for Web-Scale Applications

  2021cites this paper
• DiversePathsJ: diverse shortest paths for bioimage analysis

  2017cites this paper