Accelerating Dynamic Programs via Nested Benders Decomposition with Application to Multi-Person Pose Estimation
We present a novel approach to solve dynamic programs (DP), which are frequent in computer vision, on tree-structured graphs with exponential node state space. Typical DP approaches have to enumerate the joint state space of two adjacent nodes on every edge of the tree to compute the optimal messages. Here we propose an algorithm based on Nested Benders Decomposition (NBD) which iteratively lower-bounds the message on every edge and promises to be far more efficient. We apply our NBD algorithm along with a novel Minimum Weight Set Packing (MWSP) formulation to a multi-person pose estimation problem. While our algorithm is provably optimal at termination it operates in linear time for practical DP problems, gaining up to 500x speed up over traditional DP algorithm which have polynomial complexity.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Person Pose EstimationPose EstimationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Accelerating Signal-Temporal-Logic-Based Task and Motion Planning of Bipedal Navigation using Benders Decomposition
Task and motion planning under Signal Temporal Logic constraints is known to be NP-hard. A common class of approaches formulates these hybrid problems, which involve discrete task scheduling and continuous motion plannin…
Motion PlanningAccelerating L-shaped Two-stage Stochastic SCUC with Learning Integrated Benders Decomposition
Benders decomposition is widely used to solve large mixed-integer problems. This paper takes advantage of machine learning and proposes enhanced variants of Benders decomposition for solving two-stage stochastic security…
regressionAccelerating Message Passing for MAP with Benders Decomposition
We introduce a novel mechanism to tighten the local polytope relaxation for MAP inference in Markov random fields with low state space variables. We consider a surjection of the variables to a set of hyper-variables and …
Exploiting skeletal structure in computer vision annotation with Benders decomposition
Many annotation problems in computer vision can be phrased as integer linear programs (ILPs). The use of standard industrial solvers does not to exploit the underlying structure of such problems eg, the skeleton in pose …
Pose EstimationMassively Parallel Benders Decomposition for Correlation Clustering
We tackle the problem of graph partitioning for image segmentation using correlation clustering (CC), which we treat as an integer linear program (ILP). We reformulate optimization in the ILP so as to admit efficient opt…
Clusteringgraph partitioningImage SegmentationSemantic Segmentation