Joint Graph Decomposition & Node Labeling: Problem, Algorithms, Applications

By Evgeny Levinkov, Jonas Uhrig, Siyu Tang, Mohamed Omran, Eldar Insafutdinov, Alexander Kirillov, Carsten Rother, Thomas Brox, Bernt Schiele, Bjoern Andres. 2016

109 citations recorded by the source corpus.

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, it 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 the effectiveness of these algorithms in tackling computer vision tasks, we apply them to instances of the problem that we construct from published data, using published algorithms. We report state-of-the-art application-specific accuracy in the three above-mentioned applications.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computer Vision and Pattern Recognition

In Graph Learning

Citations in the corpus

InstanceCut: From Edges to Instances with MultiCut (2016, methodology): “Although the problem (5)-(8) is NP-hard and it contains a lot of hard constraints, there exists an efficient approximate solver for it [32], which we used in our experiments.”
MaskLab: Instance Segmentation by Refining Object Detection with Semantic and Direction Features (2017, neutral): “[42] propose efficient local search algorithms for instance segmentation.”
SSAP: Single-Shot Instance Segmentation With Affinity Pyramid (2019, methodology): “Graph based algorithm [26] is also utilized for post-processing [31, 28], which segments an image into instances with global reasoning.”
Spatial-Temporal Relation Networks for Multi-Object Tracking (2019, unknown): “ot;MT(%)"ML(%)# FP# FN# IDS#Frag#AR# Ofﬂine NOMT [11] 46.4 76.6 53.3 73.2 41.9 18.3 41.4 9,753 87,565 359504 18.6 MCjoint [23] 47.1 76.3 52.3 73.9 40.4 20.4 46.9 6,703 89,368 370 598 19.8 NLLMPa [30] 47.6 78.5 47.3 67.2 36.5 17.0 40.4 5,844 89,093 629 768 18.8 FWT [18] 47.8 75.5 44.3 60.3 35 19”
Recovering Accurate 3D Human Pose in the Wild Using IMUs and a Moving Camera (2018, background): “Although the presented graph labeling problem in (5) is NP-Hard, it can be solved efficiently in practice [7, 12].”
Online Multi-Object Tracking with Dual Matching Attention Networks (2018, unknown): “6 NLLMPa [29] 47.”
PersonLab: Person Pose Estimation and Instance Segmentation with a Bottom-Up, Part-Based, Geometric Embedding Model (2018, methodology): “[58] formulate the instance segmentation problem as a combinatorial optimization problem that consists of graph decomposition and node labeling and propose efficient local search algorithms to iteratively refine an initial solution.”
MOTChallenge: A Benchmark for Single-Camera Multiple Target Tracking (2020, methodology): “Interestingly, the ﬁrst methods outperforming NOMT on MOT16 were published only in 2017 (AMIR (Sadeghian et al. 2017) and NLLMP (Levinkov et al. 2017)).”
Box2Pix: Single-Shot Instance Segmentation by Assigning Pixels to Object Boxes (2018, methodology): “5 Graph Decomposition [29] 43.”
OpenPose: Realtime Multi-Person 2D Pose Estimation Using Part Affinity Fields (2018, unknown): “[71] 89.”
Associative Embedding: End-to-End Learning for Joint Detection and Grouping (2016, unknown): “.5 35.0 42.2 36.7 31.1 43.1 Insafutdinov et al., ECCV16 [28] 78.4 72.5 60.2 51.0 57.2 52.0 45.4 59.5 Insafutdinov et al., arXiv16a [45] 89.4 84.5 70.4 59.3 68.9 62.7 54.6 70.0 Levinkov et al., CVPR17 [33] 89.8 85.2 71.8 59.6 71.1 63.0 53.5 70.6 Insafutdinov et al., CVPR17 [27] 88.8 87.0 75.9 64.9 74”