Joint Graph Decomposition and Node Labeling: Problem, Algorithms, Applications
arXiv:1611.04399
Abstract
We state a combinatorial optimization problem whose feasible solutions define both a decomposition and a node labeling of a given graph. This problem offers a common mathematical abstraction of seemingly unrelated computer vision tasks, including instance-separating semantic segmentation, articulated human body pose estimation and multiple object tracking. Conceptually, the problem we state generalizes the unconstrained integer quadratic program and the minimum cost lifted multicut problem, both of which are NP-hard. In order to find feasible solutions efficiently, we define two local search algorithms that converge monotonously to a local optimum, offering a feasible solution at any time. To demonstrate their effectiveness in tackling computer vision tasks, we apply these algorithms to instances of the problem that we construct from published data, using published algorithms. We report state-of-the-art application-specific accuracy for the three above-mentioned applications.
References in corpus (6)
- MOT16: A Benchmark for Multi-Object Tracking
- The Cityscapes Dataset for Semantic Urban Scene Understanding
- DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs
- Proposal-free Network for Instance-level Object Segmentation
- Monocular Object Instance Segmentation and Depth Ordering with CNNs
- The Minimum Cost Connected Subgraph Problem in Medical Image Analysis
Cited by in corpus (6)
- InstanceCut: from Edges to Instances with MultiCut
- Trajectory Factory: Tracklet Cleaving and Re-connection by Deep Siamese Bi-GRU for Multiple Object Tracking
- Multi-Person Pose Estimation via Column Generation
- Pixelwise Instance Segmentation with a Dynamically Instantiated Network
- Bi-directional Graph Structure Information Model for Multi-Person Pose Estimation
- Efficient Algorithms for Moral Lineage Tracing