cvpr cvpr2013 cvpr2013-300 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Asad A. Butt, Robert T. Collins
Abstract: We propose a method for global multi-target tracking that can incorporate higher-order track smoothness constraints such as constant velocity. Our problem formulation readily lends itself to path estimation in a trellis graph, but unlike previous methods, each node in our network represents a candidate pair of matching observations between consecutive frames. Extra constraints on binary flow variables in the graph result in a problem that can no longer be solved by min-cost network flow. We therefore propose an iterative solution method that relaxes these extra constraints using Lagrangian relaxation, resulting in a series of problems that ARE solvable by min-cost flow, and that progressively improve towards a high-quality solution to our original optimization problem. We present experimental results showing that our method outperforms the standard network-flow formulation as well as other recent algorithms that attempt to incorporate higher-order smoothness constraints.
Reference: text
sentIndex sentText sentNum sentScore
1 edu l Abstract We propose a method for global multi-target tracking that can incorporate higher-order track smoothness constraints such as constant velocity. [sent-6, score-0.428]
2 Our problem formulation readily lends itself to path estimation in a trellis graph, but unlike previous methods, each node in our network represents a candidate pair of matching observations between consecutive frames. [sent-7, score-0.757]
3 Extra constraints on binary flow variables in the graph result in a problem that can no longer be solved by min-cost network flow. [sent-8, score-0.861]
4 We work within the paradigm of detect-then-track, where an object detector is run on each frame to hypothesize objects of interest, followed by a data association stage to link detections into multi-frame trajectories. [sent-13, score-0.34]
5 Early approximation methods proposed greedy bipartite data association on a frame-by-frame basis [16] to extend a gradually lengthening set of trajectories over time. [sent-17, score-0.306]
6 The two frame bipartite assignment problem, also known as the (a) Frame 38(b) Frame 50 (c) Frame 68(d) Frame 78 Figure 1: Example result of our algorithm using high order motion model on the TUD sequence [1]. [sent-18, score-0.348]
7 More recent methods have attempted to find globally optimal solutions across the entire sequence by creating net- work flow graphs [2, 13, 20] or by using iterative hierarchical methods to link tracklets [11, 18, 19]. [sent-25, score-0.543]
8 Network flow formulations, in particular, can be solved optimally and efficiently by min-cost flow algorithms. [sent-26, score-0.634]
9 However, a network 111888444644 graph only contains pairwise edges between observations, thus cost information evaluating the quality of a trajectory must be able to be factored into the product/sum of pairwise costs on each frame-to-frame link. [sent-27, score-0.677]
10 In particular, we develop a graph formulation that allows for encoding constant velocity constraints to evaluate path smoothness over three adjacent frames. [sent-33, score-0.564]
11 In the remaining sections we discuss related work (Sec- tion 2), present our graph formulation and Lagrangian relaxation solution method (Sections 3 and 4), and provide experimental results (Section 5). [sent-36, score-0.286]
12 Related Work Recent approaches have formulated multi-frame, multitarget data association as a network flow problem [2, 13, 20]. [sent-39, score-0.67]
13 Candidate object matches in consecutive frames form nodes and edges in a graph G, with edge costs based on pairwise appearance and distance relations. [sent-40, score-0.76]
14 The number and best set of trajectories through the graph can be solved efficiently using min-cost flow to yield the globally optimal solution. [sent-41, score-0.554]
15 [20] create a network where two nodes are assigned to each detection and the link between these nodes is weighted by the probability that the detection is part of the solution. [sent-43, score-0.611]
16 Links between nodes representing detections from consecutive frames are weighted by the cost of both detections being part of the same trajectory. [sent-44, score-0.432]
17 Each link has a maximum capacity of 1, so the flow conservation constraint ensures no two trajectories share an observation. [sent-45, score-0.511]
18 Min-cost flow is solved using a push-relabel method [10]. [sent-46, score-0.342]
19 [2] propose using the more efficient successive shortest path algorithm to solve the min-cost flow problem, resulting in faster run times with the same globally optimal results, and also propose to use dynamic programming to yield approximate solutions very quickly. [sent-49, score-0.345]
20 Hence, these methods can use information such as distance between corresponding observations in adjacent frames, but are unable to leverage higher order smoothness constraints such as constant velocity. [sent-51, score-0.472]
21 Their method is targeted towards motion segmentation of images but can readily be adapted to multi-target tracking as a way to project higher order motion constraints onto pairwise constraints in a regular flow network. [sent-66, score-0.656]
22 Poore and Rijavec [14] use Lagrangian relaxation recursively to reduce a K-frame assignment problem to a K − 1 dimenrsieodnuacle one, -afnrdam so on, gunnmtile a t pwroo-bflreamme to assignment prob111888444755 lem is reached and solved using the Hungarian algorithm. [sent-72, score-0.366]
23 Instead of relaxing one frame of constraints at a time, Poore and Robertson III [15] relax constraints over K − 2 frames simultaneously ItoI get ]to re tlhaex simplified bipartite assignment problem, again solved optimally. [sent-73, score-0.669]
24 Our algorithm also employs Lagrangian relaxation to solve the multi-frame tracking problem, however our graph formulation and use of Lagrangian relaxation is totally different from Poore’s early work. [sent-75, score-0.511]
25 In particular, our relaxation reduces to a global network flow problem, solved optimally by min-cost flow, rather than reducing to a local two-frame assignment problem solved by the Hungarian algorithm. [sent-76, score-0.877]
26 We apply the principle of Lagrangian relaxation to develop an iterative solution method where, at each step, higher-order smoothness constraints are relaxed to form a modified-cost network flow problem that can be solved optimally and efficiently. [sent-81, score-1.038]
27 This sequence of solutions gradually approaches a solution in which the higher-order constraints are satisfied, yielding a high-quality approximate solution to the original hard problem. [sent-82, score-0.287]
28 The top graph in Figure 2 depicts a three frame sequence with three observations (1,2,3) in the first frame, two observations (4,5) in the second, and four observations (6 7 8 9) in the third. [sent-87, score-0.85]
29 Directed edges in the graph connect pairs of observations from adjacent time frames that are candidate matches. [sent-88, score-0.761]
30 We can associate a binary variable xij with each edge, allowing a match to be turned on or off, subject to constraints that the sum of variables on edges coming into a node must be equal to the sum of variables on edges leaving the node. [sent-89, score-0.874]
31 With the addition of source and sink nodes connected to all the observations, unit capacities on all edges, and costs on each edge representing the cost of making a match, this would become a typical min-cost network flow formulation of multi-target, multi-frame matching. [sent-90, score-0.993]
32 Note that costs, being associated with pairwise edges, are functions only of the candidate pair of observations con- nected by that edge, and thus limited to quantities that can be computed from two detections in adjacent frames. [sent-91, score-0.358]
33 Figure 2: (Top) Graph depicting a three frame sequence with three observations in the first frame, two in the second, and four in the third. [sent-92, score-0.397]
34 Here, each square node represents an edge in the original graph, or equivalently, a candidate pair of matching observations, e. [sent-95, score-0.312]
35 node e14 represents a candidate match between observation 1 in the first frame and 4 in the second. [sent-97, score-0.542]
36 Thin black directed edges in this graph connect two nodes that share an observation in the second frame, that is, they connect a pair of candidate match pairs having the middle observation in common. [sent-98, score-0.905]
37 For example, the edge between nodes e14 and e46 represents the path formed by observations 1-4-6. [sent-100, score-0.457]
38 As 111888444866 before, we can now add binary variables on these edges, source and sink nodes, unit capacities, and flow costs. [sent-101, score-0.34]
39 We might be tempted at this point to use min-cost network flow on this new graph to find the optimal three-frame tracking solution. [sent-103, score-0.755]
40 However, that would not be correct, because a feasible solution must satisfy additional constraints due to some nodes sharing observations within the same frame, which introduces a coupling between their edge variables. [sent-104, score-0.569]
41 These extra constraints are shown as thicker, colored hyperedges in the graph, and they constrain either all the in- coming edges or all outgoing edges of the set of nodes they connect to have at most one edge selected. [sent-105, score-0.938]
42 For example, there is a hyperedge connecting nodes e14, e24 and e34 in the graph, signifying that if we turn on one of the outgoing edges of node e14, we can no longer select any outgoing edges from nodes e24 or e34. [sent-106, score-1.177]
43 This is so because all of these edges represent trajectories that pass through observation 4 in the second frame. [sent-107, score-0.341]
44 Likewise, the hyperedge connecting nodes e46 , e47, e48 and e49 means that only one of the incoming edges into that node set can be turned on. [sent-108, score-0.661]
45 Due to the introduction ofthese hyperedges, our problem is no longer equivalent to min-cost network flow. [sent-109, score-0.3]
46 However, we will introduce an approximate solution method based on Lagrangian relaxation that uses min-cost network flow as a core subroutine. [sent-110, score-0.735]
47 Problem Formulation Let lbe the length of a video sequence, Fk be the set of observations in frame k, and rk be the size of that set: Fk = {ob1k, . [sent-113, score-0.316]
48 (1) We form candidate matches between observations in consecutive frames. [sent-120, score-0.365]
49 , mnkk}, (2) where nk is the total number of candidate matches in that frame pair. [sent-126, score-0.323]
50 For the remainder of this paper, we use the words nodes and vertices interchangeably, and links, edges and arcs interchangeably. [sent-134, score-0.342]
51 Vertex set V contains a start node (s), a sink node (t), and two linked nodes 2i 1and 2i for each match ni o=d e1, . [sent-135, score-0.61]
52 (3) For a match mi, all of its incoming edges are connected to node 2i 1 (referred to as an ‘incoming node’), and the outgoing edges are ecodn tnoe actsed a nto ‘ i2nic o(rmefienrgre ndo tdoe as an d‘o tuhtegoing node’). [sent-142, score-0.857]
53 The link between the incoming node and the outgoing node ensures that by splitting each match into two nodes, at most a flow of 1can pass through each match. [sent-143, score-1.053]
54 Another advantage is that any unary and binary constraints can be placed on these edges, thus keeping them separate from the constant velocity constraints. [sent-144, score-0.302]
55 − Figure 3: Network flow graph corresponding to the example in Figure 2. [sent-145, score-0.387]
56 Each match (represented by a rectangle) has an incoming and an outgoing node, and the match number is labeled on the edge between these nodes. [sent-146, score-0.569]
57 Links are created between nodes representing matches from different frame pairs. [sent-148, score-0.391]
58 We can represent our graph as a staged trellis where vertices representing matches from Pk appear in stage tk and edges are directed only for- ward in time. [sent-150, score-0.436]
59 We create an edge (v2i, v2j−1) ∈ E when candidate match pairs mi ∈ Pk and mj ∈ Pk+1 share an observation in frame k + 1. [sent-151, score-0.529]
60 ∈ PThis edge represents the continuity of a trajectory through the three observations involved. [sent-152, score-0.301]
61 To make G a network flow graph, we also add edges from the source node to all the incoming nodes, as well as edges 111888444977 from all outgoing nodes to the target node (s, 2i − 1) ∈ E; (2i, t) ∈ E; i= 1, . [sent-153, score-1.598]
62 Each arc (i,j) has an associated binary flow variable xi,j that takes value 1 when the arc is part of a trajectory in the min-cost flow solution, and 0 otherwise. [sent-161, score-0.628]
63 Conflicts Between Matches Similar to [2, 13, 20], graph G is a network flow graph and each node can be used in at most one track. [sent-166, score-0.889]
64 Matches from the same pair of frames conflict when they have an observation in common, because their shared observation can be used in only one trajectory. [sent-168, score-0.437]
65 We must therefore ensure that only one of those conflicting matches is used in the final flow solution. [sent-169, score-0.471]
66 For each observation a ∈ Fk, consider the set of match pairs r{( eaac, ∗h)} o isne rPvak having a as the incoming node of the pair. [sent-170, score-0.509]
67 F {o(ra e,a∗)ch} o inf t Phese matches, edges entering node a from match pairs in Pk−1 are in conflict: at most one of them can be selected and the rest must be 0. [sent-171, score-0.528]
68 We therefore form an edge conflict constraint set EC to limit the sum of flow variables on edges entering incoming node a to be at most 1. [sent-172, score-1.049]
69 Similarly, for the set of match pairs {(∗, a)} in Pk−1 having a as tlharel outgoing sneotd oef mofa ttcheh pair, we f,oar)m} a nc Ponflict set to limit the sum of flow variables on edges exiting outgoing node a. [sent-173, score-1.135]
70 Let the total number of conflict sets created in this way be q, and the set of all conflict sets be {EC1 , . [sent-174, score-0.402]
71 ,q (8) Similar to previous works, each edge (i, j) is assigned a cost cij based on the cost of linking match pairs, taking into account appearance similarity and path smoothness constraints. [sent-192, score-0.426]
72 Unlike previous network flow approaches, our costs can take into account three-node smoothness measures such as constant velocity, because they are defined between pairs of match pairs, not pairs of observations. [sent-193, score-0.979]
73 The second constraint set (7) contains the standard flow conservation equations, saying that the flow entering a node is equal to the flow exiting it, ensuring continuous paths from s to t. [sent-196, score-1.194]
74 Taken together, equations (5–7) specify a min-cost network flow problem that can be solved using standard algorithms. [sent-197, score-0.594]
75 However, the third set of constraints (8) are needed to ensure that for each edge conflict set, at most one edge is selected, or in other words, that an observation shared by multiple match pairs can be used only once. [sent-198, score-0.716]
76 This set of constraints cannot be directly handled in a network flow framework, and motivates our use of Lagrangian relaxation in the next section. [sent-199, score-0.818]
77 Note that instead of enforcing the hard constraints Cx = d, we now allow those constraints to be violated, but penalize those violations by an amount controlled by λ. [sent-209, score-0.285]
78 Looking back at our binary linear program, it is clear that without the set of conflict constraints (8) this would be a min-cost network flow problem, which we know how to solve efficiently. [sent-215, score-0.869]
79 ed problem in (9) is a standard min-cost network flow problem, and can be solved efficiently by previous methods in the tracking literature [2, 13, 20]. [sent-241, score-0.71]
80 Diving deeper into the details, each edge in such a violating conflict set will have its cost increased by λs, thus encouraging the min-cost flow solution to route flow elsewhere in the graph. [sent-249, score-0.961]
81 The network flow algorithm is now run iteratively, updating λs in each iteration. [sent-250, score-0.544]
82 In cases where some soft constraints remain unsatisfied, we will have conflicting matches in the final trajectories, allowing an observation to be part of two or more different tracks. [sent-263, score-0.369]
83 For all observations in each frame, check if the observation is used in more than one track, and add those tracks to a ‘competing tracks’ list. [sent-267, score-0.314]
84 If the track has observations in the following frames, create a new track with these observations. [sent-273, score-0.293]
85 One sequence has an average of5 observations per frame (known as “sparse” sequence), and the other has an average of 20 observations per frame (known as “dense” sequence). [sent-285, score-0.713]
86 Each sequence is subsampled to form datasets of 1 frame per second, 2 frames per second, and 3 frames per second. [sent-287, score-0.426]
87 The first algorithm (Projection) is based on [12], where the hypergraph with edges connecting observations in three frames (to obtain constant velocity measure) is projected onto a simple graph. [sent-289, score-0.619]
88 The costs on the edges of the simple graph are chosen as the best value of constant velocity between the two connected nodes and a node in the future. [sent-290, score-0.804]
89 Essentially, this is a way to be able to use higher order cost functions in a regular network flow problem. [sent-291, score-0.601]
90 We AlMgODoCurNPitsFhm139T42/U 873D16398E132T17/H1 035M817S4ET2H154M/19S62748(G3T) Table 2: We compare our algorithm with the dynamic programming (DP) algorithm of [13] and the min-cost network flow (MCNF) algorithm of [20] for the TUD and ETHMS (first 350 frames) sequences. [sent-355, score-0.544]
91 also note the total number of (correct) observations used in the final trajectories by the algorithms. [sent-360, score-0.296]
92 For the min-cost network flow algorithm of [20] the total number of observations that are part of the trajectories should be noted. [sent-364, score-0.84]
93 An advantage of our iterative solution approach is that each relaxed network flow subproblem has a special structure that can be leveraged to achieve substantial speed increase over general integer programming solvers, while still yielding high-quality results. [sent-374, score-0.638]
94 Instead of observa- tions, candidate match pairs of observations are used as nodes in the graph, allowing each graph edge to encode a cost based on observations in three frames. [sent-377, score-0.983]
95 However, this higher order information comes with additional constraints, which must be relaxed to yield a min-cost flow network. [sent-378, score-0.345]
96 We use Lagrangian relaxation to form a series of min-cost flow problems that yield solutions that gradually improve to approximate the solution to our original problem. [sent-379, score-0.483]
97 An efficient implementation of a scaling minimum-cost flow algorithm. [sent-445, score-0.292]
98 A lagrangian relaxation algorithm for multidimensional assignment problems arising from multitarget tracking. [sent-468, score-0.497]
99 A new lagrangian re- [16] [17] [18] [19] [20] laxation based algorithm for a class of multidimensional assignment problems. [sent-475, score-0.297]
100 Global data association for multi-object tracking using network flows. [sent-506, score-0.444]
wordName wordTfidf (topN-words)
[('flow', 0.292), ('network', 0.252), ('lagrangian', 0.214), ('conflict', 0.201), ('observations', 0.179), ('poore', 0.163), ('outgoing', 0.162), ('edges', 0.158), ('node', 0.155), ('relaxation', 0.15), ('nodes', 0.147), ('frame', 0.137), ('xij', 0.132), ('constraints', 0.124), ('velocity', 0.123), ('ethms', 0.121), ('incoming', 0.119), ('trajectories', 0.117), ('tracking', 0.116), ('pk', 0.115), ('matches', 0.107), ('match', 0.105), ('tud', 0.105), ('tracklets', 0.105), ('cx', 0.104), ('frames', 0.104), ('ecs', 0.096), ('june', 0.096), ('graph', 0.095), ('assignment', 0.083), ('butt', 0.082), ('sequence', 0.081), ('candidate', 0.079), ('edge', 0.078), ('smoothness', 0.076), ('association', 0.076), ('mismatches', 0.074), ('conflicting', 0.072), ('costs', 0.071), ('conference', 0.07), ('tracks', 0.069), ('fk', 0.068), ('hyperedges', 0.067), ('observation', 0.066), ('greedy', 0.066), ('link', 0.065), ('pairs', 0.064), ('detections', 0.062), ('links', 0.062), ('mismatch', 0.062), ('track', 0.057), ('cost', 0.057), ('id', 0.056), ('constant', 0.055), ('cijxij', 0.054), ('mwis', 0.054), ('swaps', 0.054), ('multipliers', 0.054), ('relaxed', 0.053), ('path', 0.053), ('dp', 0.05), ('solved', 0.05), ('multitarget', 0.05), ('hungarian', 0.049), ('longer', 0.048), ('capacities', 0.048), ('mme', 0.048), ('sink', 0.048), ('targets', 0.047), ('bipartite', 0.047), ('entering', 0.046), ('xjk', 0.045), ('mik', 0.045), ('robertson', 0.045), ('connect', 0.044), ('trajectory', 0.044), ('competing', 0.043), ('handling', 0.043), ('paths', 0.043), ('tracklet', 0.042), ('conflicts', 0.042), ('turned', 0.042), ('solution', 0.041), ('crf', 0.04), ('hyperedge', 0.04), ('pattern', 0.039), ('stopping', 0.039), ('objective', 0.039), ('swap', 0.039), ('ochs', 0.039), ('trellis', 0.039), ('collins', 0.038), ('adjacent', 0.038), ('lagrange', 0.037), ('violations', 0.037), ('switches', 0.037), ('exiting', 0.037), ('arcs', 0.037), ('conservation', 0.037), ('directed', 0.037)]
simIndex simValue paperId paperTitle
same-paper 1 0.9999997 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
Author: Asad A. Butt, Robert T. Collins
Abstract: We propose a method for global multi-target tracking that can incorporate higher-order track smoothness constraints such as constant velocity. Our problem formulation readily lends itself to path estimation in a trellis graph, but unlike previous methods, each node in our network represents a candidate pair of matching observations between consecutive frames. Extra constraints on binary flow variables in the graph result in a problem that can no longer be solved by min-cost network flow. We therefore propose an iterative solution method that relaxes these extra constraints using Lagrangian relaxation, resulting in a series of problems that ARE solvable by min-cost flow, and that progressively improve towards a high-quality solution to our original optimization problem. We present experimental results showing that our method outperforms the standard network-flow formulation as well as other recent algorithms that attempt to incorporate higher-order smoothness constraints.
2 0.23395626 209 cvpr-2013-Hypergraphs for Joint Multi-view Reconstruction and Multi-object Tracking
Author: Martin Hofmann, Daniel Wolf, Gerhard Rigoll
Abstract: We generalize the network flow formulation for multiobject tracking to multi-camera setups. In the past, reconstruction of multi-camera data was done as a separate extension. In this work, we present a combined maximum a posteriori (MAP) formulation, which jointly models multicamera reconstruction as well as global temporal data association. A flow graph is constructed, which tracks objects in 3D world space. The multi-camera reconstruction can be efficiently incorporated as additional constraints on the flow graph without making the graph unnecessarily large. The final graph is efficiently solved using binary linear programming. On the PETS 2009 dataset we achieve results that significantly exceed the current state of the art.
3 0.21902941 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
Author: Anton Milan, Konrad Schindler, Stefan Roth
Abstract: When tracking multiple targets in crowded scenarios, modeling mutual exclusion between distinct targets becomes important at two levels: (1) in data association, each target observation should support at most one trajectory and each trajectory should be assigned at most one observation per frame; (2) in trajectory estimation, two trajectories should remain spatially separated at all times to avoid collisions. Yet, existing trackers often sidestep these important constraints. We address this using a mixed discrete-continuous conditional randomfield (CRF) that explicitly models both types of constraints: Exclusion between conflicting observations with supermodular pairwise terms, and exclusion between trajectories by generalizing global label costs to suppress the co-occurrence of incompatible labels (trajectories). We develop an expansion move-based MAP estimation scheme that handles both non-submodular constraints and pairwise global label costs. Furthermore, we perform a statistical analysis of ground-truth trajectories to derive appropriate CRF potentials for modeling data fidelity, target dynamics, and inter-target occlusion.
4 0.17843144 386 cvpr-2013-Self-Paced Learning for Long-Term Tracking
Author: unkown-author
Abstract: We address the problem of long-term object tracking, where the object may become occluded or leave-the-view. In this setting, we show that an accurate appearance model is considerably more effective than a strong motion model. We develop simple but effective algorithms that alternate between tracking and learning a good appearance model given a track. We show that it is crucial to learn from the “right” frames, and use the formalism of self-paced curriculum learning to automatically select such frames. We leverage techniques from object detection for learning accurate appearance-based templates, demonstrating the importance of using a large negative training set (typically not used for tracking). We describe both an offline algorithm (that processes frames in batch) and a linear-time online (i.e. causal) algorithm that approaches real-time performance. Our models significantly outperform prior art, reducing the average error on benchmark videos by a factor of 4.
5 0.17050643 362 cvpr-2013-Robust Monocular Epipolar Flow Estimation
Author: Koichiro Yamaguchi, David McAllester, Raquel Urtasun
Abstract: We consider the problem of computing optical flow in monocular video taken from a moving vehicle. In this setting, the vast majority of image flow is due to the vehicle ’s ego-motion. We propose to take advantage of this fact and estimate flow along the epipolar lines of the egomotion. Towards this goal, we derive a slanted-plane MRF model which explicitly reasons about the ordering of planes and their physical validity at junctions. Furthermore, we present a bottom-up grouping algorithm which produces over-segmentations that respect flow boundaries. We demonstrate the effectiveness of our approach in the challenging KITTI flow benchmark [11] achieving half the error of the best competing general flow algorithm and one third of the error of the best epipolar flow algorithm.
6 0.16781178 107 cvpr-2013-Deformable Spatial Pyramid Matching for Fast Dense Correspondences
7 0.16253906 441 cvpr-2013-Tracking Sports Players with Context-Conditioned Motion Models
8 0.16166747 334 cvpr-2013-Pose from Flow and Flow from Pose
9 0.15893082 301 cvpr-2013-Multi-target Tracking by Rank-1 Tensor Approximation
10 0.15509516 244 cvpr-2013-Large Displacement Optical Flow from Nearest Neighbor Fields
11 0.15015319 439 cvpr-2013-Tracking Human Pose by Tracking Symmetric Parts
12 0.14790224 10 cvpr-2013-A Fully-Connected Layered Model of Foreground and Background Flow
13 0.14674903 59 cvpr-2013-Better Exploiting Motion for Better Action Recognition
14 0.14588456 158 cvpr-2013-Exploring Weak Stabilization for Motion Feature Extraction
15 0.14395306 345 cvpr-2013-Real-Time Model-Based Rigid Object Pose Estimation and Tracking Combining Dense and Sparse Visual Cues
16 0.1438027 203 cvpr-2013-Hierarchical Video Representation with Trajectory Binary Partition Tree
17 0.14362204 455 cvpr-2013-Video Object Segmentation through Spatially Accurate and Temporally Dense Extraction of Primary Object Regions
18 0.14131179 224 cvpr-2013-Information Consensus for Distributed Multi-target Tracking
19 0.12483762 192 cvpr-2013-Graph Matching with Anchor Nodes: A Learning Approach
topicId topicWeight
[(0, 0.263), (1, 0.077), (2, 0.01), (3, -0.074), (4, 0.022), (5, -0.055), (6, 0.16), (7, -0.15), (8, -0.027), (9, 0.181), (10, 0.114), (11, 0.08), (12, -0.021), (13, 0.025), (14, 0.065), (15, 0.066), (16, -0.032), (17, -0.063), (18, 0.118), (19, -0.043), (20, -0.015), (21, -0.042), (22, -0.084), (23, 0.085), (24, 0.087), (25, 0.033), (26, 0.111), (27, -0.027), (28, -0.062), (29, 0.067), (30, -0.056), (31, -0.021), (32, 0.146), (33, 0.001), (34, 0.03), (35, 0.14), (36, 0.089), (37, 0.0), (38, 0.031), (39, -0.036), (40, -0.038), (41, -0.053), (42, -0.037), (43, -0.054), (44, -0.046), (45, -0.0), (46, -0.025), (47, -0.092), (48, 0.013), (49, -0.058)]
simIndex simValue paperId paperTitle
same-paper 1 0.97652882 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
Author: Asad A. Butt, Robert T. Collins
Abstract: We propose a method for global multi-target tracking that can incorporate higher-order track smoothness constraints such as constant velocity. Our problem formulation readily lends itself to path estimation in a trellis graph, but unlike previous methods, each node in our network represents a candidate pair of matching observations between consecutive frames. Extra constraints on binary flow variables in the graph result in a problem that can no longer be solved by min-cost network flow. We therefore propose an iterative solution method that relaxes these extra constraints using Lagrangian relaxation, resulting in a series of problems that ARE solvable by min-cost flow, and that progressively improve towards a high-quality solution to our original optimization problem. We present experimental results showing that our method outperforms the standard network-flow formulation as well as other recent algorithms that attempt to incorporate higher-order smoothness constraints.
2 0.75961697 209 cvpr-2013-Hypergraphs for Joint Multi-view Reconstruction and Multi-object Tracking
Author: Martin Hofmann, Daniel Wolf, Gerhard Rigoll
Abstract: We generalize the network flow formulation for multiobject tracking to multi-camera setups. In the past, reconstruction of multi-camera data was done as a separate extension. In this work, we present a combined maximum a posteriori (MAP) formulation, which jointly models multicamera reconstruction as well as global temporal data association. A flow graph is constructed, which tracks objects in 3D world space. The multi-camera reconstruction can be efficiently incorporated as additional constraints on the flow graph without making the graph unnecessarily large. The final graph is efficiently solved using binary linear programming. On the PETS 2009 dataset we achieve results that significantly exceed the current state of the art.
3 0.74457765 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
Author: Anton Milan, Konrad Schindler, Stefan Roth
Abstract: When tracking multiple targets in crowded scenarios, modeling mutual exclusion between distinct targets becomes important at two levels: (1) in data association, each target observation should support at most one trajectory and each trajectory should be assigned at most one observation per frame; (2) in trajectory estimation, two trajectories should remain spatially separated at all times to avoid collisions. Yet, existing trackers often sidestep these important constraints. We address this using a mixed discrete-continuous conditional randomfield (CRF) that explicitly models both types of constraints: Exclusion between conflicting observations with supermodular pairwise terms, and exclusion between trajectories by generalizing global label costs to suppress the co-occurrence of incompatible labels (trajectories). We develop an expansion move-based MAP estimation scheme that handles both non-submodular constraints and pairwise global label costs. Furthermore, we perform a statistical analysis of ground-truth trajectories to derive appropriate CRF potentials for modeling data fidelity, target dynamics, and inter-target occlusion.
4 0.73443604 301 cvpr-2013-Multi-target Tracking by Rank-1 Tensor Approximation
Author: Xinchu Shi, Haibin Ling, Junling Xing, Weiming Hu
Abstract: In this paper we formulate multi-target tracking (MTT) as a rank-1 tensor approximation problem and propose an ?1 norm tensor power iteration solution. In particular, a high order tensor is constructed based on trajectories in the time window, with each tensor element as the affinity of the corresponding trajectory candidate. The local assignment variables are the ?1 normalized vectors, which are used to approximate the rank-1 tensor. Our approach provides a flexible and effective formulation where both pairwise and high-order association energies can be used expediently. We also show the close relation between our formulation and the multi-dimensional assignment (MDA) model. To solve the optimization in the rank-1 tensor approximation, we propose an algorithm that iteratively powers the intermediate solution followed by an ?1 normalization. Aside from effectively capturing high-order motion information, the proposed solver runs efficiently with proved convergence. The experimental validations are conducted on two challenging datasets and our method demonstrates promising performances on both.
5 0.69425935 224 cvpr-2013-Information Consensus for Distributed Multi-target Tracking
Author: Ahmed T. Kamal, Jay A. Farrell, Amit K. Roy-Chowdhury
Abstract: Due to their high fault-tolerance, ease of installation and scalability to large networks, distributed algorithms have recently gained immense popularity in the sensor networks community, especially in computer vision. Multitarget tracking in a camera network is one of the fundamental problems in this domain. Distributed estimation algorithms work by exchanging information between sensors that are communication neighbors. Since most cameras are directional sensors, it is often the case that neighboring sensors may not be sensing the same target. Such sensors that do not have information about a target are termed as “naive ” with respect to that target. In this paper, we propose consensus-based distributed multi-target tracking algorithms in a camera network that are designed to address this issue of naivety. The estimation errors in tracking and data association, as well as the effect of naivety, are jointly addressed leading to the development of an informationweighted consensus algorithm, which we term as the Multitarget Information Consensus (MTIC) algorithm. The incorporation of the probabilistic data association mecha- nism makes the MTIC algorithm very robust to false measurements/clutter. Experimental analysis is provided to support the theoretical results.
6 0.66479558 350 cvpr-2013-Reconstructing Loopy Curvilinear Structures Using Integer Programming
7 0.62810141 203 cvpr-2013-Hierarchical Video Representation with Trajectory Binary Partition Tree
8 0.610843 10 cvpr-2013-A Fully-Connected Layered Model of Foreground and Background Flow
9 0.6076231 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median
10 0.59787673 362 cvpr-2013-Robust Monocular Epipolar Flow Estimation
12 0.57888925 441 cvpr-2013-Tracking Sports Players with Context-Conditioned Motion Models
13 0.57685304 192 cvpr-2013-Graph Matching with Anchor Nodes: A Learning Approach
14 0.57500756 190 cvpr-2013-Graph-Based Optimization with Tubularity Markov Tree for 3D Vessel Segmentation
15 0.55535018 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
17 0.54248184 280 cvpr-2013-Maximum Cohesive Grid of Superpixels for Fast Object Localization
18 0.53582603 345 cvpr-2013-Real-Time Model-Based Rigid Object Pose Estimation and Tracking Combining Dense and Sparse Visual Cues
19 0.52733028 244 cvpr-2013-Large Displacement Optical Flow from Nearest Neighbor Fields
20 0.52270389 386 cvpr-2013-Self-Paced Learning for Long-Term Tracking
topicId topicWeight
[(10, 0.127), (16, 0.035), (26, 0.058), (33, 0.352), (34, 0.139), (67, 0.044), (69, 0.047), (87, 0.109)]
simIndex simValue paperId paperTitle
1 0.9599759 439 cvpr-2013-Tracking Human Pose by Tracking Symmetric Parts
Author: Varun Ramakrishna, Takeo Kanade, Yaser Sheikh
Abstract: The human body is structurally symmetric. Tracking by detection approaches for human pose suffer from double counting, where the same image evidence is used to explain two separate but symmetric parts, such as the left and right feet. Double counting, if left unaddressed can critically affect subsequent processes, such as action recognition, affordance estimation, and pose reconstruction. In this work, we present an occlusion aware algorithm for tracking human pose in an image sequence, that addresses the problem of double counting. Our key insight is that tracking human pose can be cast as a multi-target tracking problem where the ”targets ” are related by an underlying articulated structure. The human body is modeled as a combination of singleton parts (such as the head and neck) and symmetric pairs of parts (such as the shoulders, knees, and feet). Symmetric body parts are jointly tracked with mutual exclusion constraints to prevent double counting by reasoning about occlusion. We evaluate our algorithm on an outdoor dataset with natural background clutter, a standard indoor dataset (HumanEva-I), and compare against a state of the art pose estimation algorithm.
2 0.95682114 401 cvpr-2013-Sketch Tokens: A Learned Mid-level Representation for Contour and Object Detection
Author: Joseph J. Lim, C. Lawrence Zitnick, Piotr Dollár
Abstract: We propose a novel approach to both learning and detecting local contour-based representations for mid-level features. Our features, called sketch tokens, are learned using supervised mid-level information in the form of hand drawn contours in images. Patches of human generated contours are clustered to form sketch token classes and a random forest classifier is used for efficient detection in novel images. We demonstrate our approach on both topdown and bottom-up tasks. We show state-of-the-art results on the top-down task of contour detection while being over 200× faster than competing methods. We also achieve large improvements ainn dcoetmecptietoinn agc mceutrhaocdys f.o Wr teh ael sboot atochmi-evuep ltaarsgkse of pedestrian and object detection as measured on INRIA [5] and PASCAL [10], respectively. These gains are due to the complementary information provided by sketch tokens to low-level features such as gradient histograms.
same-paper 3 0.94479167 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
Author: Asad A. Butt, Robert T. Collins
Abstract: We propose a method for global multi-target tracking that can incorporate higher-order track smoothness constraints such as constant velocity. Our problem formulation readily lends itself to path estimation in a trellis graph, but unlike previous methods, each node in our network represents a candidate pair of matching observations between consecutive frames. Extra constraints on binary flow variables in the graph result in a problem that can no longer be solved by min-cost network flow. We therefore propose an iterative solution method that relaxes these extra constraints using Lagrangian relaxation, resulting in a series of problems that ARE solvable by min-cost flow, and that progressively improve towards a high-quality solution to our original optimization problem. We present experimental results showing that our method outperforms the standard network-flow formulation as well as other recent algorithms that attempt to incorporate higher-order smoothness constraints.
4 0.93905318 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
Author: Horst Possegger, Sabine Sternig, Thomas Mauthner, Peter M. Roth, Horst Bischof
Abstract: Combining foreground images from multiple views by projecting them onto a common ground-plane has been recently applied within many multi-object tracking approaches. These planar projections introduce severe artifacts and constrain most approaches to objects moving on a common 2D ground-plane. To overcome these limitations, we introduce the concept of an occupancy volume exploiting the full geometry and the objects ’ center of mass and develop an efficient algorithm for 3D object tracking. Individual objects are tracked using the local mass density scores within a particle filter based approach, constrained by a Voronoi partitioning between nearby trackers. Our method benefits from the geometric knowledge given by the occupancy volume to robustly extract features and train classifiers on-demand, when volumetric information becomes unreliable. We evaluate our approach on several challenging real-world scenarios including the public APIDIS dataset. Experimental evaluations demonstrate significant improvements compared to state-of-theart methods, while achieving real-time performance. – –
5 0.93861407 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
Author: Yan Wang, Rongrong Ji, Shih-Fu Chang
Abstract: Recent years have witnessed a growing interest in understanding the semantics of point clouds in a wide variety of applications. However, point cloud labeling remains an open problem, due to the difficulty in acquiring sufficient 3D point labels towards training effective classifiers. In this paper, we overcome this challenge by utilizing the existing massive 2D semantic labeled datasets from decadelong community efforts, such as ImageNet and LabelMe, and a novel “cross-domain ” label propagation approach. Our proposed method consists of two major novel components, Exemplar SVM based label propagation, which effectively addresses the cross-domain issue, and a graphical model based contextual refinement incorporating 3D constraints. Most importantly, the entire process does not require any training data from the target scenes, also with good scalability towards large scale applications. We evaluate our approach on the well-known Cornell Point Cloud Dataset, achieving much greater efficiency and comparable accuracy even without any 3D training data. Our approach shows further major gains in accuracy when the training data from the target scenes is used, outperforming state-ofthe-art approaches with far better efficiency.
6 0.93754196 147 cvpr-2013-Ensemble Learning for Confidence Measures in Stereo Vision
7 0.93685859 362 cvpr-2013-Robust Monocular Epipolar Flow Estimation
8 0.93604749 188 cvpr-2013-Globally Consistent Multi-label Assignment on the Ray Space of 4D Light Fields
9 0.93582219 227 cvpr-2013-Intrinsic Scene Properties from a Single RGB-D Image
10 0.93580711 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
11 0.93548506 394 cvpr-2013-Shading-Based Shape Refinement of RGB-D Images
12 0.9348309 329 cvpr-2013-Perceptual Organization and Recognition of Indoor Scenes from RGB-D Images
13 0.93453008 443 cvpr-2013-Uncalibrated Photometric Stereo for Unknown Isotropic Reflectances
14 0.93429065 187 cvpr-2013-Geometric Context from Videos
15 0.93417591 111 cvpr-2013-Dense Reconstruction Using 3D Object Shape Priors
16 0.93410969 468 cvpr-2013-Winding Number for Region-Boundary Consistent Salient Contour Extraction
17 0.93391335 143 cvpr-2013-Efficient Large-Scale Structured Learning
18 0.93360847 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
19 0.93357205 155 cvpr-2013-Exploiting the Power of Stereo Confidences
20 0.93357098 373 cvpr-2013-SWIGS: A Swift Guided Sampling Method