iccv iccv2013 iccv2013-200 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Chetan Arora, Amir Globerson
Abstract: This paper addresses the data assignment problem in multi frame multi object tracking in video sequences. Traditional methods employing maximum weight bipartite matching offer limited temporal modeling. It has recently been shown [6, 8, 24] that incorporating higher order temporal constraints improves the assignment solution. Finding maximum weight matching with higher order constraints is however NP-hard and the solutions proposed until now have either been greedy [8] or rely on greedy rounding of the solution obtained from spectral techniques [15]. We propose a novel algorithm to find the approximate solution to data assignment problem with higher order temporal constraints using the method of dual decomposition and the MPLP message passing algorithm [21]. We compare the proposed algorithm with an implementation of [8] and [15] and show that proposed technique provides better solution with a bound on approximation factor for each inferred solution.
Reference: text
sentIndex sentText sentNum sentScore
1 l Abstract This paper addresses the data assignment problem in multi frame multi object tracking in video sequences. [sent-5, score-0.377]
2 Traditional methods employing maximum weight bipartite matching offer limited temporal modeling. [sent-6, score-0.232]
3 It has recently been shown [6, 8, 24] that incorporating higher order temporal constraints improves the assignment solution. [sent-7, score-0.323]
4 Finding maximum weight matching with higher order constraints is however NP-hard and the solutions proposed until now have either been greedy [8] or rely on greedy rounding of the solution obtained from spectral techniques [15]. [sent-8, score-0.404]
5 We propose a novel algorithm to find the approximate solution to data assignment problem with higher order temporal constraints using the method of dual decomposition and the MPLP message passing algorithm [21]. [sent-9, score-0.845]
6 We compare the proposed algorithm with an implementation of [8] and [15] and show that proposed technique provides better solution with a bound on approximation factor for each inferred solution. [sent-10, score-0.231]
7 Introduction Popularity of tracking by detection approaches [2] has led to a renewed interest in the data assignment problem in computer vision. [sent-12, score-0.273]
8 This is typically done by associating a score with each such assignment, and finding the assignment with a maximum score. [sent-15, score-0.256]
9 For example, low scores may be given to matching pairs which are visually dissimilar or are detected far from each other. [sent-17, score-0.229]
10 In a crowded scenario such scores fail to disambiguate the correct assignment from other possible assignments. [sent-18, score-0.348]
11 For example, scores which consider the velocity vectors implied by a matching, and constrain those to be physically valid are recommended for such cases. [sent-20, score-0.193]
12 If the scores factor as a sum over individual assignments, then the problem can be solved via network flow algorithms [4, 25] or as a sum of bipartite matchings [23] defined over set of every two consecutive frames. [sent-23, score-0.594]
13 , a score which depends on three frames simultaneously), and the maximization problem becomes NP hard. [sent-27, score-0.224]
14 We refer to such assignment problems with con- straints involving more than 2 frames as higher order assignment/matching problems. [sent-28, score-0.448]
15 Several approximate maximization algorithms have recently been proposed to address NP hardness of higher order assignment problems [6–8, 15]. [sent-29, score-0.38]
16 Leordeanu and Hebert [15] relax the integrality and matching constraints (a detection in one frame must be assigned to exactly one detection each in previous and next frame). [sent-30, score-0.352]
17 Since the solution obtained may not be 177 feasible, they employ a greedy rounding scheme which iteratively removes the conflicting variables to generate a feasible assignment solution. [sent-32, score-0.418]
18 Collins [8] proposed a block ICM based technique for assignment problems with constraints involving two or more frames. [sent-33, score-0.432]
19 It is similar to the iterated conditional modes (ICM) algorithm, but is applied at each step to a block of variables representing possible associations between two consecutive frames. [sent-35, score-0.257]
20 The block-optimal conditional mode at each step is calculated as the solution to a bipartite matching problem. [sent-36, score-0.267]
21 Butt and Collins [6] have proposed to solve a series of independent higher order matching problems over frame triplets which are then merged into longer trajectories. [sent-37, score-0.304]
22 Additionally there is no bound on approximation factor of the solution available with any of the discussed approaches [6, 8, 15]. [sent-40, score-0.231]
23 The problem of matching in a arbitrarily long sequence with constraints involving 3 frames can also be formulated as 3-matching problem defined over a T-partite graph (T is the overall number of frames). [sent-41, score-0.283]
24 [10] have suggested a method called COMPOSE for optimizing matching problems with additional scores on pairs of edges. [sent-45, score-0.274]
25 Given the above, our goal was to develop better approximation algorithms for the higher order assignment problem. [sent-50, score-0.301]
26 It turns out that the dual decomposition (DD) framework (see below) is a perfect fit for this problem, and provides several desirable properties. [sent-51, score-0.383]
27 Third, it can be naturally extended to other higher order scores involving three or more frames. [sent-54, score-0.267]
28 4 for a general overview and [14, 21] for applications to inference) is conceptually simple: it takes a complex score function and breaks it down into a sum of scores that can be efficiently optimized. [sent-58, score-0.298]
29 These problems are then modified using messages such that the sum of the separate maximizations yields an upper bound on the true max. [sent-59, score-0.41]
30 Finally, the messages are optimized such that the bound is as tight as possible. [sent-60, score-0.218]
31 [9] have suggested a Lagrangian relaxation scheme that is related to dual decomposition [20]. [sent-64, score-0.416]
32 However, their objective is more involved and the message passing scheme we suggest is considerably simpler than their algorithm. [sent-65, score-0.221]
33 However, the resulting algorithm is different from ours, since it needs to solve a complete flow problem in each iteration, and uses subgradient updates which typically converge more slowly than coordinate descent [e. [sent-67, score-0.205]
34 The paper is structured as follows: we first present the higher order assignment problem in Section 2 followed by a brief review of the DD approach in Section 3. [sent-70, score-0.269]
35 Specifically, we show that the proposed algorithm outperforms state of the art approaches [8, 15], yielding higher scoring assignments on various publicly available datasets [1, 2, 11], while also providing upper and lower bounds on the optimal score. [sent-73, score-0.302]
36 The goal is to find a set of paths from detections in the first frame to those in the last frame. [sent-85, score-0.195]
37 Since the X variables correspond to a set of disjoint paths, they must satisfy the constraint that each detection in frame t is assigned to a single detection in frame t + 1, and vice versa. [sent-102, score-0.323]
38 teNdex bty, we wish to construct a score function that maps each X to a number indicating how likely the proposed assignment is. [sent-124, score-0.256]
39 For example, since we know that objects tend to move in straight lines, it makes sense to give higher scores to X assignments that correspond to such trajectories, as suggested in [8]. [sent-129, score-0.285]
40 i,j,k (1) This can be simplified, by absorbing the local scores into the pairwise ones. [sent-137, score-0.176]
41 a probabilistic model here, but it is possible to and only local costs are considered, then the problem becomes easy since it can be separated into T separate bipartite matching constraints. [sent-151, score-0.232]
42 However, introducing the higher order scores makes the problem considerably more complicated, requiring approximate solution approaches. [sent-152, score-0.254]
43 In what follows we describe a simple and effective scheme for pairwise scores, which can be generalized to other higher order score functions as well. [sent-153, score-0.28]
44 Specifically, we define a set of dual variables δfi (Xi) for each factor f, each variable i ∈ Sf and each value )X fio (e. [sent-177, score-0.453]
45 These dual variables may be thought of as a message from factor f to variable i, indicating a prior on the value Xi. [sent-180, score-0.562]
46 f Next, define the following dual function L(δ) : L(δ) =? [sent-186, score-0.257]
47 One that is particularly simple and effective is to use block coordinate descent on the δ variables. [sent-196, score-0.188]
48 Here we use the MPLP algorithm [21] which fixes all messages except those from a particular f to all variables i. [sent-198, score-0.25]
49 ∈fδi−f(Xi)⎦⎤, ⎦(9) where |f| denotes the number of variables in the factor θf, and we used (Xi) to denote the sum of messages into i that are not from f. [sent-201, score-0.382]
50 3 Eventually, we are interested in an assignment for X. [sent-211, score-0.184]
51 Any such decoded assignment X provides a natural lower bound on θ∗, namely θ(X). [sent-213, score-0.306]
52 Thus, if the upper bound L(δ) and the lower bound coincide, we know we have found the θ∗ value and maximizing assignment. [sent-214, score-0.253]
53 Our functions will combine the matching constraints with the score elements from S(X). [sent-218, score-0.268]
54 For convenience, we define a function st,i (X) that contains the pairwise scores 4 corresponding to the ith detection in the tth frame: st,i(X) = ? [sent-219, score-0.237]
55 4Pairwise score in the formulation refers to the score corresponding to matching a triplet in three adjacent frames. [sent-226, score-0.286]
56 Next, define a function θt,i (X) that has a value of −∞ if the ith detection in the tth (frXa)me th avito hlaatse sa tvhaleu matching constraint. [sent-227, score-0.156]
57 (14), we introduce dual variables for messages between each factor (t, i) and the variables that participate in this factor. [sent-245, score-0.703]
58 Recall that the factor (t, i) depends on the variables Xt,i,j (i. [sent-246, score-0.196]
59 e, matchings between frame t and t + 1) and Xt−1,j,i (i. [sent-247, score-0.178]
60 e Teno fraedctuocre ( nt,o ti)a iaonnda Xt,i,j by δt,i↑j (Xt,i,j) and the message between factor (t, i) and Xt−1,j,i by δt,i↓j (Xt−1,j,i) (see figure 2). [sent-251, score-0.202]
61 The max operation in these updates involves all variables in θt,i, namely 2D variables (assuming D matching pairs in each two consecutive frames). [sent-265, score-0.455]
62 However, we note that θt,i is non-infinite only for O(D2) assignments satisfying the matching constraints, making the MPLP updatestractable. [sent-267, score-0.19]
63 ,i,k(21) The above MPLP updates monotonically decrease L(δ), providing an upper bound on the MAP. [sent-293, score-0.209]
64 To obtain an assignment from δ we consider the singleton scores θtδ,i,j (Xt,i,j) and return a matching that maximizes these. [sent-294, score-0.508]
65 ,i,jθtδ,i,j(Xt,i,j) (22) This can be solved efficiently by solving a maximum weight bipartite matching independently for each consecutive frames t and t + 1. [sent-296, score-0.371]
66 6This corresponds to a matching between k and iin frames t 1, t respecTtihvisel cyo, arnreds p boentwdese tno ia a mnda j hiinn tghe b efrtwameeens t,ta n+d 1i rines pfraemctivesel ty. [sent-298, score-0.181]
67 As mentioned earlier, in this case, the maximization of S(X) simply turns into T separate bipartite matching problems and can therefore be solved efficiently. [sent-307, score-0.388]
68 The maximization maxX θtδ,i (X) here is particularly simple since it breaks down into two separate maximizations (for the previous and next frames). [sent-313, score-0.197]
69 jδt,i↑j(0) Given this simplified form, we can now take the dual of the minimization in Eq. [sent-320, score-0.257]
70 Introduce dual variables μt,i↓j , μt,i↑j , μt,i,j for the three sets of constraints above. [sent-332, score-0.414]
71 8 In deriving the dual we actually obtain that μt,i↑j = μt+1,j↓i = μt,i,j, namely only the μt,i,j variables are needed. [sent-333, score-0.411]
72 The dual then simplifies to (up to factor 2): sm. [sent-334, score-0.35]
73 181 Algorithm 1 HO Matching Algorithm Algorithm 1HO Matching Algorithm Input: Weights Wt,i,j,kspecifying the score for matching detections i,j,k in frames t − 1,t,t + 1. [sent-342, score-0.32]
74 1: 2: 3: 4: 5: 6: 7: while Change in dual is not small enough do for All factors t,iin a random order do Calculate Wt? [sent-345, score-0.286]
75 Second, the LP for each t is in fact precisely the LP formulation of bipartite matchings, which is known to have an integral solution, and return the maximum bipartite matching (e. [sent-354, score-0.404]
76 Finally, we emphasize that our procedure will in practice return the exact matchings in many other cases, where higher order factors are not zero. [sent-363, score-0.219]
77 Since Spectral requires eigenvalue decomposition and scales quadratically with T as opposed to our method and block ICM, we evaluate it only on the short toy problem sequences. [sent-367, score-0.237]
78 The pairwise scores are set as the distance between the detection in the middle frame and the centroid of detections in the first and third frames of the frame triplet (constant velocity assumption). [sent-377, score-0.624]
79 This is one instance of higher order scores, and other scores utilizing appearance based cues could have been used. [sent-378, score-0.219]
80 However, the purpose of experiments is to study the inference capabilities of the various algorithms with higher order matching constraints when the appearance based cues are ambiguous. [sent-379, score-0.234]
81 Indicatory scores consonant with the objective have been used accordingly without compromising the generality of the algorithmic approach. [sent-380, score-0.172]
82 Furthermore, in 5/9 cases, MPLP finds a provably optimal solution (since the upper and lower bounds coincide). [sent-384, score-0.186]
83 Due to our experience in the toy problem and the scalability issues with Spectral approach we compare only to the block ICM approach. [sent-387, score-0.156]
84 The local and pairwise scores have been set similarly as in toy problem case. [sent-388, score-0.231]
85 One possible explanation for the results could be that the technique in [8] iterates through hard assignments as opposed to the message passing style of our method. [sent-390, score-0.244]
86 The assignment differences between MPLP and block ICM have been marked with white rectangles. [sent-395, score-0.285]
87 MPLP performs better than block ICM in the presence of strong matching ambiguities arising due to multiple close detections. [sent-396, score-0.238]
88 Figure 4: Change in primal and dual during MPLP iterations on PSU Seq 3 Figure 4 shows an instance of the upper and lower bounds reported by MPLP. [sent-397, score-0.477]
89 We show primal and dual val- ues after different outer iterations (an outer iteration processes each factor exactly once) of MPLP on a test dataset (PSU Seq 3). [sent-398, score-0.453]
90 As the iterations proceed, the quality/score of primal solutions keep increasing while the upper bound on the optimal primal given by the value of dual keeps tight183 ening. [sent-399, score-0.524]
91 In this problem instance, the bounds do not meet and we cannot conclude that the solution is optimal. [sent-401, score-0.158]
92 Conclusion We presented an approach for optimizing higher order assignment problems that arise in the context of tracking by detection. [sent-406, score-0.372]
93 Our approach relies on the dual decomposition framework which breaks the difficult assignment problem into simpler tractable tasks. [sent-407, score-0.575]
94 We showed the inference capability of the algorithm in the presence of pairwise matching scores arising from detections in 3 consecutive frames. [sent-408, score-0.433]
95 Such scores can successfully capture the constant velocity assumption which is a useful assignment cue in crowded scene when local scores are ambiguous. [sent-409, score-0.541]
96 9 The DD message passing framework is very general, and thus we expect it will be effective for other higher order factors that are introduced into the tracking problem. [sent-413, score-0.292]
97 As new frames arrive, we can perform a small number of message passes for the most recent frames, to obtain upper and lower bounds for the overall sequence. [sent-417, score-0.346]
98 A generalized s-d assignment algorithm for multisensormultitarget state estimation. [sent-477, score-0.184]
99 Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking. [sent-542, score-0.341]
100 A tutorial on dual decomposition and Lagrangian relaxation for inference in natural language processing. [sent-552, score-0.382]
wordName wordTfidf (topN-words)
[('mplp', 0.553), ('icm', 0.277), ('dual', 0.257), ('dd', 0.186), ('assignment', 0.184), ('psu', 0.174), ('messages', 0.147), ('bipartite', 0.137), ('scores', 0.134), ('butt', 0.112), ('message', 0.109), ('variables', 0.103), ('block', 0.101), ('matchings', 0.099), ('assignments', 0.095), ('matching', 0.095), ('factor', 0.093), ('bounds', 0.093), ('frames', 0.086), ('seq', 0.084), ('decomposition', 0.081), ('frame', 0.079), ('score', 0.072), ('bound', 0.071), ('primal', 0.069), ('subgradient', 0.068), ('detections', 0.067), ('maximization', 0.066), ('singleton', 0.06), ('velocity', 0.059), ('tracking', 0.058), ('upper', 0.058), ('deb', 0.056), ('mjax', 0.056), ('xjwt', 0.056), ('higher', 0.056), ('xt', 0.055), ('toy', 0.055), ('constraints', 0.054), ('descent', 0.053), ('consecutive', 0.053), ('maximizing', 0.053), ('breaks', 0.053), ('lagrangian', 0.052), ('namely', 0.051), ('maximizations', 0.05), ('exactness', 0.05), ('updates', 0.05), ('np', 0.049), ('paths', 0.049), ('involving', 0.048), ('wt', 0.048), ('coincide', 0.048), ('triplet', 0.047), ('functions', 0.047), ('maxx', 0.046), ('problems', 0.045), ('ho', 0.045), ('turns', 0.045), ('collins', 0.044), ('relaxation', 0.044), ('xi', 0.044), ('spectral', 0.044), ('globerson', 0.043), ('arising', 0.042), ('pairwise', 0.042), ('accelerated', 0.042), ('passing', 0.04), ('dummy', 0.04), ('duchi', 0.04), ('sum', 0.039), ('multitarget', 0.038), ('objective', 0.038), ('meant', 0.037), ('combinatorial', 0.037), ('sf', 0.037), ('lp', 0.036), ('smoothing', 0.035), ('return', 0.035), ('solution', 0.035), ('coordinate', 0.034), ('exactly', 0.034), ('scheme', 0.034), ('notational', 0.033), ('decoding', 0.033), ('rounding', 0.033), ('approximation', 0.032), ('association', 0.032), ('detection', 0.031), ('jt', 0.031), ('leordeanu', 0.031), ('tth', 0.03), ('monotonically', 0.03), ('conclude', 0.03), ('crowded', 0.03), ('order', 0.029), ('greedy', 0.029), ('multi', 0.028), ('fi', 0.028), ('next', 0.028)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999994 200 iccv-2013-Higher Order Matching for Consistent Multiple Target Tracking
Author: Chetan Arora, Amir Globerson
Abstract: This paper addresses the data assignment problem in multi frame multi object tracking in video sequences. Traditional methods employing maximum weight bipartite matching offer limited temporal modeling. It has recently been shown [6, 8, 24] that incorporating higher order temporal constraints improves the assignment solution. Finding maximum weight matching with higher order constraints is however NP-hard and the solutions proposed until now have either been greedy [8] or rely on greedy rounding of the solution obtained from spectral techniques [15]. We propose a novel algorithm to find the approximate solution to data assignment problem with higher order temporal constraints using the method of dual decomposition and the MPLP message passing algorithm [21]. We compare the proposed algorithm with an implementation of [8] and [15] and show that proposed technique provides better solution with a bound on approximation factor for each inferred solution.
2 0.12620306 309 iccv-2013-Partial Enumeration and Curvature Regularization
Author: Carl Olsson, Johannes Ulén, Yuri Boykov, Vladimir Kolmogorov
Abstract: Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. This partial enumeration technique reduces complex highorder energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. Our main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach. 1
3 0.12614433 230 iccv-2013-Latent Data Association: Bayesian Model Selection for Multi-target Tracking
Author: Aleksandr V. Segal, Ian Reid
Abstract: We propose a novel parametrization of the data association problem for multi-target tracking. In our formulation, the number of targets is implicitly inferred together with the data association, effectively solving data association and model selection as a single inference problem. The novel formulation allows us to interpret data association and tracking as a single Switching Linear Dynamical System (SLDS). We compute an approximate posterior solution to this problem using a dynamic programming/message passing technique. This inference-based approach allows us to incorporate richer probabilistic models into the tracking system. In particular, we incorporate inference over inliers/outliers and track termination times into the system. We evaluate our approach on publicly available datasets and demonstrate results competitive with, and in some cases exceeding the state of the art.
4 0.094470739 264 iccv-2013-Minimal Basis Facility Location for Subspace Segmentation
Author: Choon-Meng Lee, Loong-Fah Cheong
Abstract: In contrast to the current motion segmentation paradigm that assumes independence between the motion subspaces, we approach the motion segmentation problem by seeking the parsimonious basis set that can represent the data. Our formulation explicitly looks for the overlap between subspaces in order to achieve a minimal basis representation. This parsimonious basis set is important for the performance of our model selection scheme because the sharing of basis results in savings of model complexity cost. We propose the use of affinity propagation based method to determine the number of motion. The key lies in the incorporation of a global cost model into the factor graph, serving the role of model complexity. The introduction of this global cost model requires additional message update in the factor graph. We derive an efficient update for the new messages associated with this global cost model. An important step in the use of affinity propagation is the subspace hypotheses generation. We use the row-sparse convex proxy solution as an initialization strategy. We further encourage the selection of subspace hypotheses with shared basis by integrat- ing a discount scheme that lowers the factor graph facility cost based on shared basis. We verified the model selection and classification performance of our proposed method on both the original Hopkins 155 dataset and the more balanced Hopkins 380 dataset.
5 0.092036478 238 iccv-2013-Learning Graphs to Match
Author: Minsu Cho, Karteek Alahari, Jean Ponce
Abstract: Many tasks in computer vision are formulated as graph matching problems. Despite the NP-hard nature of the problem, fast and accurate approximations have led to significant progress in a wide range of applications. Learning graph models from observed data, however, still remains a challenging issue. This paper presents an effective scheme to parameterize a graph model, and learn its structural attributes for visual object matching. For this, we propose a graph representation with histogram-based attributes, and optimize them to increase the matching accuracy. Experimental evaluations on synthetic and real image datasets demonstrate the effectiveness of our approach, and show significant improvement in matching accuracy over graphs with pre-defined structures.
6 0.087797381 390 iccv-2013-Shufflets: Shared Mid-level Parts for Fast Object Detection
7 0.087255515 237 iccv-2013-Learning Graph Matching: Oriented to Category Modeling from Cluttered Scenes
8 0.083129667 58 iccv-2013-Bayesian 3D Tracking from Monocular Video
9 0.081550546 140 iccv-2013-Elastic Net Constraints for Shape Matching
10 0.080869831 120 iccv-2013-Discriminative Label Propagation for Multi-object Tracking with Sporadic Appearance Features
11 0.079941466 65 iccv-2013-Breaking the Chain: Liberation from the Temporal Markov Assumption for Tracking Human Poses
12 0.078974463 165 iccv-2013-Find the Best Path: An Efficient and Accurate Classifier for Image Hierarchies
13 0.078621462 104 iccv-2013-Decomposing Bag of Words Histograms
14 0.077027246 87 iccv-2013-Conservation Tracking
15 0.072783493 61 iccv-2013-Beyond Hard Negative Mining: Efficient Detector Learning via Block-Circulant Decomposition
16 0.07258635 115 iccv-2013-Direct Optimization of Frame-to-Frame Rotation
17 0.067685619 186 iccv-2013-GrabCut in One Cut
18 0.067371644 441 iccv-2013-Video Motion for Every Visible Point
19 0.066523209 64 iccv-2013-Box in the Box: Joint 3D Layout and Object Reasoning from Single Images
20 0.066161081 214 iccv-2013-Improving Graph Matching via Density Maximization
topicId topicWeight
[(0, 0.179), (1, -0.03), (2, -0.008), (3, 0.01), (4, 0.01), (5, 0.046), (6, -0.045), (7, 0.067), (8, 0.02), (9, -0.017), (10, -0.054), (11, -0.021), (12, 0.018), (13, 0.054), (14, 0.064), (15, 0.067), (16, 0.01), (17, 0.027), (18, -0.008), (19, 0.014), (20, -0.024), (21, -0.022), (22, -0.004), (23, -0.062), (24, 0.05), (25, -0.024), (26, 0.02), (27, -0.091), (28, 0.0), (29, 0.026), (30, -0.003), (31, -0.0), (32, -0.004), (33, -0.008), (34, 0.072), (35, -0.035), (36, 0.01), (37, -0.034), (38, 0.01), (39, 0.008), (40, 0.061), (41, 0.043), (42, 0.087), (43, 0.058), (44, -0.073), (45, -0.013), (46, 0.067), (47, -0.018), (48, -0.025), (49, 0.008)]
simIndex simValue paperId paperTitle
same-paper 1 0.94118816 200 iccv-2013-Higher Order Matching for Consistent Multiple Target Tracking
Author: Chetan Arora, Amir Globerson
Abstract: This paper addresses the data assignment problem in multi frame multi object tracking in video sequences. Traditional methods employing maximum weight bipartite matching offer limited temporal modeling. It has recently been shown [6, 8, 24] that incorporating higher order temporal constraints improves the assignment solution. Finding maximum weight matching with higher order constraints is however NP-hard and the solutions proposed until now have either been greedy [8] or rely on greedy rounding of the solution obtained from spectral techniques [15]. We propose a novel algorithm to find the approximate solution to data assignment problem with higher order temporal constraints using the method of dual decomposition and the MPLP message passing algorithm [21]. We compare the proposed algorithm with an implementation of [8] and [15] and show that proposed technique provides better solution with a bound on approximation factor for each inferred solution.
2 0.68569356 87 iccv-2013-Conservation Tracking
Author: Martin Schiegg, Philipp Hanslovsky, Bernhard X. Kausler, Lars Hufnagel, Fred A. Hamprecht
Abstract: The quality of any tracking-by-assignment hinges on the accuracy of the foregoing target detection / segmentation step. In many kinds of images, errors in this first stage are unavoidable. These errors then propagate to, and corrupt, the tracking result. Our main contribution is the first probabilistic graphical model that can explicitly account for over- and undersegmentation errors even when the number of tracking targets is unknown and when they may divide, as in cell cultures. The tracking model we present implements global consistency constraints for the number of targets comprised by each detection and is solved to global optimality on reasonably large 2D+t and 3D+t datasets. In addition, we empirically demonstrate the effectiveness of a postprocessing that allows to establish target identity even across occlusion / undersegmentation. The usefulness and efficiency of this new tracking method is demonstrated on three different and challenging 2D+t and 3D+t datasets from developmental biology.
3 0.67372876 230 iccv-2013-Latent Data Association: Bayesian Model Selection for Multi-target Tracking
Author: Aleksandr V. Segal, Ian Reid
Abstract: We propose a novel parametrization of the data association problem for multi-target tracking. In our formulation, the number of targets is implicitly inferred together with the data association, effectively solving data association and model selection as a single inference problem. The novel formulation allows us to interpret data association and tracking as a single Switching Linear Dynamical System (SLDS). We compute an approximate posterior solution to this problem using a dynamic programming/message passing technique. This inference-based approach allows us to incorporate richer probabilistic models into the tracking system. In particular, we incorporate inference over inliers/outliers and track termination times into the system. We evaluate our approach on publicly available datasets and demonstrate results competitive with, and in some cases exceeding the state of the art.
4 0.6709407 120 iccv-2013-Discriminative Label Propagation for Multi-object Tracking with Sporadic Appearance Features
Author: K.C. Amit Kumar, Christophe De_Vleeschouwer
Abstract: Given a set of plausible detections, detected at each time instant independently, we investigate how to associate them across time. This is done by propagating labels on a set of graphs that capture how the spatio-temporal and the appearance cues promote the assignment of identical or distinct labels to a pair of nodes. The graph construction is driven by the locally linear embedding (LLE) of either the spatio-temporal or the appearance features associated to the detections. Interestingly, the neighborhood of a node in each appearance graph is defined to include all nodes for which the appearance feature is available (except the ones that coexist at the same time). This allows to connect the nodes that share the same appearance even if they are temporally distant, which gives our framework the uncommon ability to exploit the appearance features that are available only sporadically along the sequence of detections. Once the graphs have been defined, the multi-object tracking is formulated as the problem of finding a label assignment that is consistent with the constraints captured by each of the graphs. This results into a difference of convex program that can be efficiently solved. Experiments are performed on a basketball and several well-known pedestrian datasets in order to validate the effectiveness of the proposed solution.
5 0.64846718 65 iccv-2013-Breaking the Chain: Liberation from the Temporal Markov Assumption for Tracking Human Poses
Author: Ryan Tokola, Wongun Choi, Silvio Savarese
Abstract: We present an approach to multi-target tracking that has expressive potential beyond the capabilities of chainshaped hidden Markov models, yet has significantly reduced complexity. Our framework, which we call tracking-byselection, is similar to tracking-by-detection in that it separates the tasks of detection and tracking, but it shifts tempo-labs . com Stanford, CA ssi lvio @ st an ford . edu ral reasoning from the tracking stage to the detection stage. The core feature of tracking-by-selection is that it reasons about path hypotheses that traverse the entire video instead of a chain of single-frame object hypotheses. A traditional chain-shaped tracking-by-detection model is only able to promote consistency between one frame and the next. In tracking-by-selection, path hypotheses exist across time, and encouraging long-term temporal consistency is as simple as rewarding path hypotheses with consistent image features. One additional advantage of tracking-by-selection is that it results in a dramatically simplified model that can be solved exactly. We adapt an existing tracking-by-detection model to the tracking-by-selectionframework, and show improvedperformance on a challenging dataset (introduced in [18]).
6 0.63049418 418 iccv-2013-The Way They Move: Tracking Multiple Targets with Similar Appearance
7 0.6200887 324 iccv-2013-Potts Model, Parametric Maxflow and K-Submodular Functions
8 0.61118805 167 iccv-2013-Finding Causal Interactions in Video Sequences
9 0.59996343 140 iccv-2013-Elastic Net Constraints for Shape Matching
10 0.58968657 433 iccv-2013-Understanding High-Level Semantics by Modeling Traffic Patterns
11 0.5889051 58 iccv-2013-Bayesian 3D Tracking from Monocular Video
12 0.58465803 395 iccv-2013-Slice Sampling Particle Belief Propagation
13 0.58420771 171 iccv-2013-Fix Structured Learning of 2013 ICCV paper k2opt.pdf
14 0.57062942 131 iccv-2013-EVSAC: Accelerating Hypotheses Generation by Modeling Matching Scores with Extreme Value Theory
15 0.56344318 429 iccv-2013-Tree Shape Priors with Connectivity Constraints Using Convex Relaxation on General Graphs
16 0.54841316 141 iccv-2013-Enhanced Continuous Tabu Search for Parameter Estimation in Multiview Geometry
17 0.54700077 393 iccv-2013-Simultaneous Clustering and Tracklet Linking for Multi-face Tracking in Videos
18 0.52666354 422 iccv-2013-Toward Guaranteed Illumination Models for Non-convex Objects
19 0.52141196 441 iccv-2013-Video Motion for Every Visible Point
20 0.51773471 292 iccv-2013-Non-convex P-Norm Projection for Robust Sparsity
topicId topicWeight
[(2, 0.084), (7, 0.014), (12, 0.013), (26, 0.086), (31, 0.052), (34, 0.018), (40, 0.016), (42, 0.105), (48, 0.017), (64, 0.085), (73, 0.04), (75, 0.156), (89, 0.204), (95, 0.016)]
simIndex simValue paperId paperTitle
1 0.9460063 247 iccv-2013-Learning to Predict Gaze in Egocentric Video
Author: Yin Li, Alireza Fathi, James M. Rehg
Abstract: We present a model for gaze prediction in egocentric video by leveraging the implicit cues that exist in camera wearer’s behaviors. Specifically, we compute the camera wearer’s head motion and hand location from the video and combine them to estimate where the eyes look. We further model the dynamic behavior of the gaze, in particular fixations, as latent variables to improve the gaze prediction. Our gaze prediction results outperform the state-of-the-art algorithms by a large margin on publicly available egocentric vision datasets. In addition, we demonstrate that we get a significant performance boost in recognizing daily actions and segmenting foreground objects by plugging in our gaze predictions into state-of-the-art methods.
same-paper 2 0.89527774 200 iccv-2013-Higher Order Matching for Consistent Multiple Target Tracking
Author: Chetan Arora, Amir Globerson
Abstract: This paper addresses the data assignment problem in multi frame multi object tracking in video sequences. Traditional methods employing maximum weight bipartite matching offer limited temporal modeling. It has recently been shown [6, 8, 24] that incorporating higher order temporal constraints improves the assignment solution. Finding maximum weight matching with higher order constraints is however NP-hard and the solutions proposed until now have either been greedy [8] or rely on greedy rounding of the solution obtained from spectral techniques [15]. We propose a novel algorithm to find the approximate solution to data assignment problem with higher order temporal constraints using the method of dual decomposition and the MPLP message passing algorithm [21]. We compare the proposed algorithm with an implementation of [8] and [15] and show that proposed technique provides better solution with a bound on approximation factor for each inferred solution.
3 0.89430356 277 iccv-2013-Multi-channel Correlation Filters
Author: Hamed Kiani Galoogahi, Terence Sim, Simon Lucey
Abstract: Modern descriptors like HOG and SIFT are now commonly used in vision for pattern detection within image and video. From a signal processing perspective, this detection process can be efficiently posed as a correlation/convolution between a multi-channel image and a multi-channel detector/filter which results in a singlechannel response map indicating where the pattern (e.g. object) has occurred. In this paper, we propose a novel framework for learning a multi-channel detector/filter efficiently in the frequency domain, both in terms of training time and memory footprint, which we refer to as a multichannel correlation filter. To demonstrate the effectiveness of our strategy, we evaluate it across a number of visual detection/localization tasks where we: (i) exhibit superiorperformance to current state of the art correlation filters, and (ii) superior computational and memory efficiencies compared to state of the art spatial detectors.
4 0.88848436 136 iccv-2013-Efficient Pedestrian Detection by Directly Optimizing the Partial Area under the ROC Curve
Author: Sakrapee Paisitkriangkrai, Chunhua Shen, Anton Van Den Hengel
Abstract: Many typical applications of object detection operate within a prescribed false-positive range. In this situation the performance of a detector should be assessed on the basis of the area under the ROC curve over that range, rather than over the full curve, as the performance outside the range is irrelevant. This measure is labelled as the partial area under the ROC curve (pAUC). Effective cascade-based classification, for example, depends on training node classifiers that achieve the maximal detection rate at a moderate false positive rate, e.g., around 40% to 50%. We propose a novel ensemble learning method which achieves a maximal detection rate at a user-defined range of false positive rates by directly optimizing the partial AUC using structured learning. By optimizing for different ranges of false positive rates, the proposed method can be used to train either a single strong classifier or a node classifier forming part of a cascade classifier. Experimental results on both synthetic and real-world data sets demonstrate the effectiveness of our approach, and we show that it is possible to train state-of-the-art pedestrian detectors using the pro- posed structured ensemble learning method.
5 0.85681754 338 iccv-2013-Randomized Ensemble Tracking
Author: Qinxun Bai, Zheng Wu, Stan Sclaroff, Margrit Betke, Camille Monnier
Abstract: We propose a randomized ensemble algorithm to model the time-varying appearance of an object for visual tracking. In contrast with previous online methods for updating classifier ensembles in tracking-by-detection, the weight vector that combines weak classifiers is treated as a random variable and the posterior distribution for the weight vector is estimated in a Bayesian manner. In essence, the weight vector is treated as a distribution that reflects the confidence among the weak classifiers used to construct and adapt the classifier ensemble. The resulting formulation models the time-varying discriminative ability among weak classifiers so that the ensembled strong classifier can adapt to the varying appearance, backgrounds, and occlusions. The formulation is tested in a tracking-by-detection implementation. Experiments on 28 challenging benchmark videos demonstrate that the proposed method can achieve results comparable to and often better than those of stateof-the-art approaches.
6 0.85602003 95 iccv-2013-Cosegmentation and Cosketch by Unsupervised Learning
7 0.85540259 445 iccv-2013-Visual Reranking through Weakly Supervised Multi-graph Learning
8 0.85408843 379 iccv-2013-Semantic Segmentation without Annotating Segments
9 0.85375667 359 iccv-2013-Robust Object Tracking with Online Multi-lifespan Dictionary Learning
10 0.85331148 188 iccv-2013-Group Sparsity and Geometry Constrained Dictionary Learning for Action Recognition from Depth Maps
11 0.85287935 340 iccv-2013-Real-Time Articulated Hand Pose Estimation Using Semi-supervised Transductive Regression Forests
12 0.85278445 65 iccv-2013-Breaking the Chain: Liberation from the Temporal Markov Assumption for Tracking Human Poses
13 0.85270464 204 iccv-2013-Human Attribute Recognition by Rich Appearance Dictionary
14 0.85213232 420 iccv-2013-Topology-Constrained Layered Tracking with Latent Flow
15 0.85129619 127 iccv-2013-Dynamic Pooling for Complex Event Recognition
16 0.85068464 425 iccv-2013-Tracking via Robust Multi-task Multi-view Joint Sparse Representation
17 0.85031474 253 iccv-2013-Linear Sequence Discriminant Analysis: A Model-Based Dimensionality Reduction Method for Vector Sequences
18 0.84966981 240 iccv-2013-Learning Maximum Margin Temporal Warping for Action Recognition
19 0.84946752 349 iccv-2013-Regionlets for Generic Object Detection
20 0.84929848 86 iccv-2013-Concurrent Action Detection with Structural Prediction