Heuristic Search for Structural Constraints in Data Association

arXiv:1711.02823v1 [cs.CV] 8 Nov 2017

Xiao Zhou1 , Peilin Jiang2 and Fei Wang1

Abstract— The research on multi-object tracking (MOT) is
essentially to solve for the data association assignment, the
core of which is to design the association cost as discriminative
as possible. Generally speaking, the match ambiguities caused
by similar appearances of objects and the moving cameras
make the data association perplexing and challenging. In this
paper, we propose a new heuristic method to search for
structural constraints (HSSC) of multiple targets when solving
the problem of online multi-object tracking. We believe that
the internal structure among multiple targets in the adjacent
frames could remain constant and stable even though the video
sequences are captured by a moving camera. As a result,
the structural constraints are able to cut down the match
ambiguities caused by the moving cameras as well as similar
appearances of the tracked objects. The proposed heuristic
method aims to obtain a maximum match set under the
minimum structural cost for each available match pair, which
can be integrated with the raw association costs and make
them more elaborate and discriminative compared with other
approaches. In addition, this paper presents a new method
to recover missing targets by minimizing the cost function
generated from both motion and structure cues. Our online
multi-object tracking (MOT) algorithm based on HSSC has
achieved the multi-object tracking accuracy (MOTA) of 25.0
on the public dataset 2DMOT2015 [1].

I. INTRODUCTION
Currently, researches on MOT algorithms mainly focus
on the problem of data association with given detections,
and tracking-by-detection methods can be generally classified into online and offline MOT methods. For the offline
MOT methods, attentions are often paid to the association
assignment between tracklets, which would inevitably utilize detections from future frames. Therefore, offline MOT
methods are considered as a global optimization scheme,
and it can only be applied to non-real-time occasions such
as offline video analysis. On the other hand, online MOT
methods focus on the data association between detections
in the current frame and historical tracklets, which do not
need detections from future frames as inputs and thus can
be applied to real-time situations such as video surveillance,
robot navigation and so forth.
The design of pairwise association costs between detections and historical tracklets directly affects the performance
of the data association assignment. In MOT methods, appearance features and motion cues of targets are usually extracted
to obtain pairwise association costs. As the appearance
models can help distinguish between different objects very
1 Xiao Zhou and Fei Wang are with the Institute of Artificial Intelligence & Robotics, Xian Jiaotong University, Xi’an, China

zx2962@stu.xjtu.edu.cn,wfx@mail.xjtu.edu.cn
2 Peilin Jiang is with the School of Software Engineering, Xian Jiaotong
University, Xi’an, China pljiang@mail.xjtu.edu.cn

Fig. 1. Structural constraints of multiple targets between adjacent frames.
The pictures are consecutively extracted from the video frames in the dataset
ETH-Sunnyday [1], which is captured by a moving camera. The yellow
solid squares denote the center location of all pedestrian targets, and the
yellow lines with rounded ends represent the internal structures among the
four pedestrian targets. Obviously, the structures in both images basically
remains Invariable, which inspires us to search for structural constraints
among multiple targets in data association assignment.

well in most circumstances, many studies are committed
to finding more discriminative appearance features, such
as [2], [3], [4]. However, the pairwise cost acquired from
appearance information would be easily unreliable when
tracking similar appearance targets. Therefore, the movement
information becomes necessary to discriminate and identify
multiple targets. It is undeniable that, in a fixed scene, we can
use a linear motion model to characterize a simple moving
targets trajectory or establish an autoregressive motion model
[5] for a complex one. However, for a moving camera, the
movement of the individual target becomes the superposition
of both the objects movement itself and the translation of
the frame image due to the moving camera. Under such circumstances, observable motion cues become unstable, unpredictable and unreliable. The conventional motion models can
hardly describe the movement features of these targets, let
alone making accurate prediction in the next frame. Although
the uncertainty of the target motion deteriorates with the
moving camera, the internal structure among multiple targets
in the adjacent frames can approximately remain consistent
and steady, which could be utilized to compensate the short
board on account of ambiguous motion cues, as is shown in
figure 1.
In this paper, we propose a heuristic approach to search
for internal structural constraints between multiple targets to
modify pairwise cost matrix and thus lessen the association
ambiguities in the data association assignment. Furthermore,
we propose a new method based on minimization of the cost
function constructed by both motion and structure cues. This
is applied to predict the next location of a missing target and
thus it can be associated with the reappearing target. This
proposed method based online MOT algorithm primarily
consists of two steps. First, we construct the association

cost matrix between the detections in the current frame and
the historical target tracklets, including the design of the
raw pairwise costs and the amelioration by the structural
constraints. In specific, we exploit motion and appearance
cues to construct the raw pairwise costs and then use the proposed heuristic approach to search for the optimal structural
constraints to ameliorate the association cost matrix. The
second step is the association assignment, in which we utilize
generalized linear assignment [5] to match the available
detections with the historical tracklets, and then recover the
missing targets in a fixed size window by minimizing the
cost function constructed by both motion and structure cues.
II. RELATED WORK
We review related MOT methods that pay much attention
to motion cues and the structure of multiple targets. Andriyenko et al. [6], [7], [8] focus on designing an energy
function and constructing an optimization scheme to find
local minima of the energy function. For this method, all the
detection responses are the input of the energy function, the
solution space of which contains all possible associations.
The velocity models are used in this method to descript
the motion of targets, which can only cover the situation
of simple movements.
Dicle et al. [5] only use motion cues to track multiple
objects with similar appearance, the autoregressive model is
utilized to represent the motion of each target and to construct association cost. This model handles complex target
movements and similar appearances, but cannot work well
when faced with non-stationary cameras. Possegger et al.
[9] exploit the geometric information, including occlusion
information, detector reliability, and motion prediction, to
recover missing objects. Collins et al. [10] develop a higherorder cost function for data association. This method uses
active contour spline energy to measure the quality of a
proposed trajectory. Liu et al. [11] extract game context
features from noisy detections to build context-conditioned
motion models for tracking sports players. Yang and Nevatia
[12] use online conditional random field (CRF) to produce
unary and pairwise energy functions based on linear and
smooth motion to solve the multi-object tracking problems.
Other trackers, like [13], [14], [15] joint both the detection
and the tracking assignments.
Yoon et al. [16] utilize the motion context to construct a
relative motion network to deal with the unexpected camera
motions. However, this method cannot handle abrupt camera
motions and fluctuations. In [17], Yoon et al. exploit the
structural motion constraints and propose an event aggregation approach to solve the MOT problem with moving
cameras. This method shows great performance in public
datasets. However, in this approach, motion cues of the
targets only depend on their relative structure and the update
of structure relies on a linear motion model, which can hardly
handle the objects with sophisticated movement or highspeed motion.
The MOT problem can be regarded as an association
assignment between the object detections and historical

tracklets for online trackers, or tracklets-to-tracklets for offline trackers. There are about two directions to develop a
tracker and make it more sophisticated. On the one hand,
many researches focus on the tool of solving the data association. Therefore, many different approaches are adopted
to solve the association assignment, including minimization
of network flow based cost [18] [19], [20], [21], linear
programming [5], [22], Hungarian matching [17], [3], [23]
and subgraph decomposition [24],[25]. On the other hand,
design of features that are more elaborate [26], [4] and making association cost more discriminative have been broadly
concerned. For example, Rezatofighi et.al. [27] modify the
association costs with joint probabilities, and decompose the
original problem into a series of integer programming, which
is more efficient and time-saving. However, in the method,
each pairwise cost is the aggregation of costs generated by all
possible match event under the fixed pair, and thus the most
likely associated pair would be susceptible to noise caused by
almost impossible associated pair, especially when detections
and targets cannot match each other one-to-one. So does the
tracker in [17].
III. PROPOSED METHOD
A. Overview
The discrimination of pairwise costs is of great significance for solving the association assignments. In the
section of related work, a variety of cost design methods
are discussed, most of which are concerning about objects
appearance and motion cues. For example, [17] proposes an
event aggregation method to integrate structural constraints
in all possible assignment events. In this paper, we propose
a heuristic method to search for the optimal association
event corresponding to the minimum structural cost for each
possible pair.
B. Heuristic search for the optimal structural constraint
The consecutive video sequences guarantee the continuity
of the objects motion, thus making it possible to exploit
structure cues between multiple targets in a frame. We denote
the center location of a detection i at frame t as dti (x, y) and
an object j at frame t − 1 as Tjt−1 (x, y) (In the subsequent
formulas, we will omit (x, y) ). We use ∆dti to denote the
relative displacement between the ith object location and the
spatial distribution center of all detection positions, which is
as shown as follows.

∆dti = dti −

n
X
k=1

dtk , ∆Tjt−1 = Tjt−1 −

m
X

Tkt−1

(1)

k=1

If the detection i in the frame t is associated with the object j, the assignment is denoted by {Xij =1} or {dti , Tjt−1 }.
Otherwise, it is denoted by {Xij =0}. Assuming there are m
detections in the current frame and m historical objects in the
past, and they could also match each other one-to-one, then
the optimal assignment solution based on minimum structural
cost of each possible pair {Xpq =1} can be constructed as:

Fig. 2. Heuristic search for structural constraints. The circles represent the targets in the last frame, the opaque crosses denote detections in the current
frame, and the translucent crosses represent the optimal prediction of the targets under the current structural constraint by using Eq. (4). There are two
states of detections or targets, including the in-match-set with green marker, and the out-of-match-set with blue marker. The orange dash lines express the
alternative structural constraints between the match set and other available pairs. The orange solid lines indicate the optimal structural constraints under
the current condition. In the first graph, the match set is initialized as the given associated pair marked in green. Using the Eq. (4), we can obtain the
optimal prediction of each target in the current frame, which is denoted by translucent crosses. Then it would be easy to find a detection coupled with the
nearest target that minimize the structural cost between detections and targets in both the match set and the available pair. The second graph shows the
cost is less than the threshold, and thus the available pair is merged into the match set. In the third graph, we can see the algorithm tries to find the forth
element of the match set, but the structural cost is far beyond the cost threshold. Therefore, the heuristic search is terminated and the output is the match
set with three pairs.

d
X
ij = arg min

m
X

1
dbti = Tjt−1 +
n

m
X

Xij

∆dti

−

i=1,i6=p j=1,j6=q
t−1 2
∆Tj
Xij + ∆dtp

(2)
−

2
∆Tqt−1

Obviously, the above formula can be easily solved by
the Hungarian algorithm. However, the actual number of
detections in the current frame are usually different from
the number of objects in the past due to false positives, false
negatives and other noises. In other words, it can neither
find global structural constraints between all detections and
objects nor promise one-to-one match. Thus, Eq. (2) cannot
be used to fit the practical assignments. As such, we present
a heuristic method to search for the optimum match set
by minimizing structural cost in each search loop, which
is described as below.

With a certain association pair dtm , Tnt−1 and
 the corresponding match set Θmn , which is initialized as dtm , Tnt−1 ,
we are
 able to search alternative match pairs for the optimal
pair dti , Tjt−1 by minimizing the structural cost function
generated among elements in the match set and the alternative pair heuristically and continually. The structural cost
function is described by:
n
o
t−1
dbti , Td
= arg
j
∆dti − ∆Tjt−1

min
/ mn
{dti ,Tjt−1 }∈Θ
X
2
+
∆dtp − ∆Tqt−1

2

(3)

{p,q}∈Θmn

If the structural cost computed from the above formula
is
than a certain threshold ϕs , we add the pair
 tsmaller
di , Tjt−1 into the matching set Θmn and repeat the entire
procedure to find the next optimal pair on the circumstance
of the updated match set. Otherwise, we end the search.
The maximum match set Θmn has been found under such
structural constraints.
When solving Eq.(3), we fix the target and assume that the
solution space of detections dbti is consecutive. The extreme
point under such condition appears as the following formula:

X

(dtp − Tqt−1 )

(4)

{p,q}∈Θmn

Evidently, there exists a unique location prediction in the
current frame for each historical object under the condition
of the known match set. Due to the discretization of the
detections, we have to find the closest detection with the solution dbti of each target and extract the one that generates the
minimum structural cost of the map between detections and
targets in the current match set. If the minimum structural
cost corresponding to the optimal pair is less than the certain
threshold, we expand the match set. Otherwise jump out of
the loop and end the search. The match set Θmn is what we
need. The specific procedure is shown in Algorithm 1 and
Fig. 2.
C. Pairwise cost
In this section, we will introduce the construction and the
improvement of the raw pairwise costs. This paper exploits
the movements and appearances of the targets to construct
their raw association costs with the detections in the current
frame. Specifically, we establish a velocity autoregressive
model [5] for the individual target and then predict the
location for each object in the current frame. The Euclidean
distance between each predicted position and every detection
is taken as the raw motion cost for each possible pair. At the
same time, we utilize the color histogram features of each
target to design its raw appearance cost. Furthermore, the
raw association cost for each pair is generated by coupling
the raw motion cost with the raw appearance cost. In the
section B, we have obtained the maximum match set for each
possible pair, which can help us modify the raw association
cost matrix as the Eq.(5).
The appearance model would undoubtedly become ambiguous and incapable when the targets have almost the
same manners. Similarly, the motion model would become
unstable and powerless when the video frames are captured
by a moving camera. Correspondingly, the different raw
pairwise costs made of appearance and motion costs would
be almost the same level. Such resemblance would inevitably

Algorithm 1 Heuristic search for structural constraints
n
o
Input: dtm , Tnt−1
. a certain fixed association pair
Input: dti
. the detection i in frame t
Input: Tjt−1
. the target j in frame t − 1
Output: Θ
. the optimal match set for each fixed pair
nmn
o
function( dtm , Tnt−1 ,dti ,Tjt−1 )
o
n
min
= 0;
Θmn = dtm , Tnt−1 ;Cstructure
While count < nt (the number of targets)
Candidate pair set P = ∅
count = count + 1
for j = 1 : nt
Find the closest detection dti with the location dbti
computed n
by Eq. (4) o
P = P ∪ dti , Tjt−1
end
Compute minimization of structural cost from the alternative
min
pairs by Cstructure
= n min o ,
dti ,Tjt−1 ∈P

∆dti −

∆Tjt−1

2

∆dtp − ∆Tqt−1

P

+

2

{p,q}∈Θmn

min
if Cstructure
< ϕns
o
Θmn = Θmn ∪ dti , Tjt−1

min
Cstructure

else
break;
end

;

end
end

make the data association assignment more ambiguous and
challenging. However, with the operation of each raw pairwise cost using Eq. (5), we can find that the more the number
of match pairs in each match set, the lower the modified cost
and vice versa. This is because the size of match set for each
available pair is positively related to the structural similarity
between the detections in the current frame and the historical
tracklets under the condition of a fixed pair association.
Obviously, the lager the size of the match set, the more likely
the detection and the target in the fixed pair to be associated
with each other, thus the lower their association cost and vice
versa. Therefore, this modification using structural penalty
makes the raw association cost, which might be generated
from ambiguous appearance features and unreliable motion
cues, more elaborate and discriminative.
Cst (dti , Tjt−1 ) =

nmax
n2Θij

X

Cinit (dtp , Tqt−1 ) (5)

{dtp ,Tqt−1 }∈Θij

nmax = max nΘij

between detections and objects. In this paper, we apply the
generalized linear assignment algorithm [5] to solve the data
association assignment.
E. Prediction of missing targets
Generally, the false positive and false negative detections,
and the situation that the targets enter into or walk out
from the field of view would possibly lead to no detection
in the current frame associated with the certain target in
the final optimal assignment event, which is called the
occurrence of missing targets. Here, we propose a target
prediction method based on structural constraints as well
as the motion inertia. Most of the conventional prediction
methods can only promise one-frame prediction accuracy as
the measurement information is not updated continuously.
However, we exploit both the target motion information,
which is along the time axis, and the structural information
between the multi-targets, which is perpendicular to the time
axis, to predict the location of missing targets. Owing to
the fact that the structural information between the multiple
objects is continually updated, the predicted location of a
certain target would not be extended stiffly along the motion
inertia, which could also alleviate the effect on motion cues
caused by unpredictable moving cameras.
We denoteΦas the match set in the frame t and Φ as
ft (j ∈ Φ)
the set of missing targets. Tit (i ∈ Φ) and T
j
are defined by the location of the object i in the match
set and the predicted location of the object j, obtained by
motion cues only, in the set of missing targets respectively.
ct (j ∈ Φ) represents the predicted location of the object j
T
j
under the constraints of both structure and motion cues. The
minimization is formulated by
ct j ∈ Φ̄ = arg min
T
j
Tjt (j∈Φ̄)
X
X
2
ct − T
ft
∆Tit − ∆Tit−1 +
T
j
j
i∈Φ

S

Φ̄

2

(7)

j∈Φ̄

The extreme point of the cost function in Eq. (7) is the
optimal predicted location of missing targets. We set a certain
time window, in which we continuously predict the location
of a missing target until the target appears again. If a target
does not show up in the whole time window, it would be
considered as an end of a trajectory.
IV. EXPERIMENT

(6)

Here, Cinit (dtp , 
Tqt−1 ) denotes the raw association cost of
t
the possible pair dtp , Tqt−1 . C
Tjt−1 ) is the associstt(di ,t−1
ation cost of the possible pair di , Tj
under structural
constraints; and nΘij denotes the number of elements in the
maximum match set of the possible pair dti , Tjt−1 .
D. Association assignment
Data association aims to find the optimal assignment
event, which corresponds to the minimum cost function,

In this section, we will show the performance of the proposed method on the public data set 2DMOT2015 [1], as well
as the performance of other multi-object tracking approaches.
It is worth mentioning that the proposed heuristic search for
structure constraint could largely diminish the association
noise caused by moving cameras and similar appearances,
and thus to make the association cost more elaborate and
discriminative. It is a universal framework, in which the
initial cost can be arbitrarily designed. In this paper, we
establish a velocity autoregressive model for each target to
obtain its motion cost, and extract the color histogram feature

of the individual target to construct its appearance cost. In
addition, we use the generalized linear assignment algorithm
to solve the data association. For the termination of the
historical targets and the initialization of the new targets, we
performed the measurements by using a fixed frame number
gap (this article uses 10). We will simply terminate a target
if it is not associated with any detections for 10 consecutive
frames. If a detection in the current frame does not match
any one of the historical trajectories, we will initialize this
detection as a new target.
Data set 2DMOT2015 provides both training and test data
sets, each of which contain 11 video sequences of different
scenes and pedestrian detections obtained by Aggregate
Channel Features (ACF) pedestrian detector [28]. To evaluate
of the performance of trackers, we adopt the widely used
MOT evaluation metrics [29], in which Multiple Object
Tracking Accuracy (MOTA) is regarded as a comprehensive evaluation considering false detection, missed test and
IDs. Multiple Object Tracking Precision (MOTP) measures
the misalignment between the annotated and the predicted
bounding boxes. For both MOTA and MOTP, a higher value
represents a better performance. In addition, we also used
other evaluation metrics like Mostly Tracked Targets (MT),
Mostly Lost Targets (ML), FAF (The average number of
false alarms per frame), False Positives (FP), False Negatives
(FN), ID Sw. and so forth.
In the test datasets, the cameras keep moving in five
scenes, including ADL-Rundle-1, ETH-Crossing, ETHJelmoli, ETH-Linthescher, and KITTI-19. The performance
of the proposed method on these datasets is shown in table
I. We also compared our method with other online trackers,
including RMOT [16], TC ODAL [4], RNN LSTM [30]. The
RMOT constructs a relative motion network to deal with
the unexpected camera motion. The TC ODAL pay much
attention to learning discriminative appearance features of
targets. The RNN LSTM propose an end-to-end learning
approach for online multi-object tracking. It can be seen
that the proposed method in this paper achieves best or
second best performance in MOTA as well as FP in the video
frames captured by moving cameras. This is because the
moving cameras would inevitably make the objects motion
cues unstable and unpredictable. As a result, the association
cost computed from motion model would become much more
ambiguous and less discriminative. However the internal
structure among objects in adjacent frames would basically
remain constant and stable, which could be perfectly used
to compensate the undermining of motion cues. The RMOT
also uses the structural constraints among objects. However,
the performance of RMOT is worse than our method except
for the dataset ETH-Jelmoli.
Table II shows the overall performance of our method and
other online trackers, including RMOT [16], TC ODAL [4]
and RNN LSTM [30] as well as offline trackers, including ALExTRAC [3], SegTrack [13] and DCO X [8]. The
ALExTRAC utilizes appearance cues to learn an affinity
model to estimate the data association cost. The SegTrack
proposes a unified CRF model for joint tracking and seg-

TABLE I
C OMPARISON TO OTHER ONLINE TRACKERS ON THE MOT C HALLENGE
DATASET WITH MOVING CAMERAS ( PEDESTRIAN SEQUENCES )

Dataset

Method
RMOT
TC ODAL
RNN LSTM
Ours

MOTA MOTP
-1.3
69.7
-0.2
69.9
-2.2
69.9
11.5
71.8

MT
21.9
15.6
18.8
15.6

ML
21.9
18,8
25.0
28.1

FP
4790
4476
4213
2812

FN
4541
4782
5058
5303

ID
96
70
241
124

ETHCrossing

RMOT
TC ODAL
RNN LSTM
Ours

16.8
16.3
21.1
23.8

73.6
73.6
75.5
74.5

3.8
0.0
0.0
0.0

76.9
73.1
57.7
53.8

11
69
27
26

813
770
757
718

10
1
7
20

ETHJelmoli

RMOT
TC ODAL
RNN LSTM
Ours

40.4
31.2
34.8
35.2

71.3
72.0
73.3
73.3

17.8
13.3
17.8
15.6

33.3
33.3
28.9
33.3

263
495
314
289

1219
1227
1280
1281

29
23
59
73

ETHLinthescher

RMOT
TC ODAL
RNN LSTM
Ours

13.1
14.1
12.4
19.4

71.9
73.3
74.7
74.5

1.5
1.0
1.5
2

81.2
78.7
79.7
72.1

142
292
164
157

7589
7352
7609
6908

26
26
49
131

KITTI-19

RMOT
TC ODAL
RNN LSTM
Ours

17.8
12.9
17.7
18.9

65.5
66.5
68.3
66.1

4.8
4.8
6.5
4.8

32.3
27.4
25.8
24.2

1198
1351
1388
1152

3117
3237
2818
3016

79
66
191
166

ADLRundle-1

mentation of multiple targets. The DCO X models the data
association problem as minimization of unified discretecontinuous energy function. From table II, we can conclude
that our method achieves better performance on MOTA,
FAF, ML and FP. The DCO X get the best performance
on IDS. As an offline tracker, the DCO X deals with the
data association assignment of detections-to-tracklets and
tracklets-to-tracklets as well, so the length of each tracklet
tends to get longer and the number of tracklets is smaller,
which, to some extent, can lessen the number of IDs, but
aggravate false positive detections. So does other trackers.
The performance of recovery of the missing targets directly affect the overall performance of a tracker. If the recovery method work well, it can cut down the false negatives
and the IDs as well. Otherwise, it could barely decrease the
false negatives and it could even increase the false positives.
Therefore, when setting the parameters of our tracker, we
adopt relatively prudential strategies as much as possible,
which explains the low FPs, high IDs of our tracking results
in table II. Nevertheless, the encouraging thing is that the
FNs of our tracker are not as high as we thought and the ML
of our tracker is better than other trackers, which indicate that
our recovery method of the missing targets perform pretty
well compared with other approaches.
TABLE II
C OMPARISON TO OTHER ONLINE TRACKERS ON THE MOT C HALLENGE
DATASET WITH MOVING CAMERAS ( PEDESTRIAN SEQUENCES )

Method
RMOT
TC ODAL
RNN LSTM
ALExTRAC
SegTrack
DCO X
Ours

MOTA
18.2
15.1
19.0
17.0
22.5
19.6
25.0

MOTP
69.6
70.5
71.0
71.2
71.7
71.4
71.2

FAF
2.2
2.2
2.0
1.6
1.4
1.8
1.3

MT
5.3
3.2
5.5
3.9
5.8
5.1
5.0

ML
53.3
55.8
45.6
52.4
63.9
54.9
43.8

FP
12473
12970
11578
9233
7890
10652
7645

FN
36835
38538
36706
39933
39020
38232
36936

ID
684
637
1490
1859
697
521
1504

Fig. 3. Recovery of the missing targets. The first column shows the pedestrian detections of a frame on the TUD-Crossing and ETH-Linthescher datasets.
The bounding boxes with solid line denotes the pedestrian detections detected by ACF pedestrian detector[28], and the blue dash line boxes indicate
the missing targets, which appeared in the past several frames. The following columns shows the tracking results of the RNN LSTM, the RMOT, the
TC ODAL, and our tracker respectively. It can be seen that in the first row, the RNN LSTM and our tracker manage to recover the missing target. Similarly,
the TC ODAL and our tracker manage to recover the missing object in the second row.

Figure 3 shows the examples of recovery of the missing
targets from several online MOT trackers, which is obtained
from the MOT Benchmark [1]. The first column shows
the pedestrian detections on the TUD-Crossing and ETHLinthescher dataset. The following columns shows the tracking result of the RNN LSTM, the RMOT, the TC ODAL,
and our tracker respectively. The bounding boxes with solid
lines in the first column represents the detections generated
by ACF pedestrian detector [28], and the blue dash line
boxes indicate the targets missing abruptly, which appeared
in the past several frames. The tracking results illustrate
that our tracker manage to recover the missing targets in
both of the two frames. The RNN LSTM method and the
TC ODAL tracker manage to recover the missing target once
respectively and the RMOT fails to recover the missing
targets.
V. CONCLUSION
When the video sequences are captured by a moving
camera, the motion of the targets will become unsteady,
unpredictable and ambiguous. In this paper, we propose a
new heuristic approach to search for the optimal internal
structure constraints between multiple targets, which could
be utilized to alleviate the ambiguities of the objects motion
costs and thereby make each pairwise association cost much
more elaborate and discriminative. Furthermore, we models
the assignment of recovery missing targets as minimization
of a cost function constructed from both motion and structure
cues. Experimental results show that the proposed method
achieves encouraging performance on the MOT Challenge
dataset. In future work, we intend to establish a dynamic
model for the structural constraint and thus make it more
stable and predictable.
ACKNOWLEDGMENT
This work was supported by the National Natural Science Foundation of China under Grant Nos: 61273366 and
61231018 and the program of introducing talents of discipline to university under grant no: B13043.

R EFERENCES
[1] L. Leal-Taixé, A. Milan, I. Reid, S. Roth, and K. Schindler, “Motchallenge 2015: Towards a benchmark for multi-target tracking,” arXiv
preprint arXiv:1504.01942, 2015.
[2] F. Solera, S. Calderara, and R. Cucchiara, “Learning to divide and
conquer for online multi-target tracking,” in Proceedings of the IEEE
International Conference on Computer Vision, 2015, pp. 4373–4381.
[3] A. Bewley, L. Ott, F. Ramos, and B. Upcroft, “Alextrac: Affinity learning by exploring temporal reinforcement within association chains,” in
Robotics and Automation (ICRA), 2016 IEEE International Conference
on. IEEE, 2016, pp. 2212–2218.
[4] S.-H. Bae and K.-J. Yoon, “Robust online multi-object tracking based
on tracklet confidence and online discriminative appearance learning,”
in Proceedings of the IEEE conference on computer vision and pattern
recognition, 2014, pp. 1218–1225.
[5] C. Dicle, O. I. Camps, and M. Sznaier, “The way they move: Tracking
multiple targets with similar appearance,” in Proceedings of the IEEE
International Conference on Computer Vision, 2013, pp. 2304–2311.
[6] A. Andriyenko and K. Schindler, “Multi-target tracking by continuous
energy minimization,” in Computer Vision and Pattern Recognition
(CVPR), 2011 IEEE Conference on. IEEE, 2011, pp. 1265–1272.
[7] A. Milan, S. Roth, and K. Schindler, “Continuous energy minimization
for multitarget tracking,” IEEE transactions on pattern analysis and
machine intelligence, vol. 36, no. 1, pp. 58–72, 2014.
[8] A. Milan, K. Schindler, and S. Roth, “Multi-target tracking by discretecontinuous energy minimization,” IEEE transactions on pattern analysis and machine intelligence, vol. 38, no. 10, pp. 2054–2068, 2016.
[9] H. Possegger, T. Mauthner, P. M. Roth, and H. Bischof, “Occlusion
geodesics for online multi-object tracking,” in Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition, 2014, pp.
1306–1313.
[10] R. T. Collins, “Multitarget data association with higher-order motion
models,” in Computer Vision and Pattern Recognition (CVPR), 2012
IEEE Conference on. IEEE, 2012, pp. 1744–1751.
[11] J. Liu, P. Carr, R. T. Collins, and Y. Liu, “Tracking sports players
with context-conditioned motion models,” in Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition, 2013, pp.
1830–1837.
[12] B. Yang and R. Nevatia, “An online learned crf model for multi-target
tracking,” in Computer Vision and Pattern Recognition (CVPR), 2012
IEEE Conference on. IEEE, 2012, pp. 2034–2041.
[13] A. Milan, L. Leal-Taixé, K. Schindler, and I. Reid, “Joint tracking
and segmentation of multiple targets,” in Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition, 2015, pp.
5397–5406.
[14] H.-U. Kim and C.-S. Kim, “Cdt: Cooperative detection and tracking
for tracing multiple objects in video sequences,” in European Conference on Computer Vision. Springer, 2016, pp. 851–867.

[15] S. Tang, M. Andriluka, and B. Schiele, “Detection and tracking of
occluded people,” International Journal of Computer Vision, vol. 110,
no. 1, pp. 58–69, 2014.
[16] J. H. Yoon, M.-H. Yang, J. Lim, and K.-J. Yoon, “Bayesian multiobject tracking using motion context from multiple objects,” in Applications of Computer Vision (WACV), 2015 IEEE Winter Conference
on. IEEE, 2015, pp. 33–40.
[17] J. Hong Yoon, C.-R. Lee, M.-H. Yang, and K.-J. Yoon, “Online
multi-object tracking via structural constraint event aggregation,” in
Proceedings of the IEEE Conference on Computer Vision and Pattern
Recognition, 2016, pp. 1392–1400.
[18] A. Dehghan, Y. Tian, P. H. Torr, and M. Shah, “Target identity-aware
network flow for online multiple target tracking,” in Proceedings of
the IEEE Conference on Computer Vision and Pattern Recognition,
2015, pp. 1146–1154.
[19] V. Chari, S. Lacoste-Julien, I. Laptev, and J. Sivic, “On pairwise costs
for network flow multi-object tracking,” in Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition, 2015, pp.
5537–5545.
[20] A. A. Butt and R. T. Collins, “Multi-target tracking by lagrangian
relaxation to min-cost network flow,” in Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition, 2013, pp.
1846–1853.
[21] C. Haubold, J. Aleš, S. Wolf, and F. A. Hamprecht, “A generalized
successive shortest paths solver for tracking dividing targets,” in
European Conference on Computer Vision. Springer, 2016, pp. 566–
582.
[22] H. Jiang, S. Fels, and J. J. Little, “A linear programming approach for
multiple object tracking,” in Computer Vision and Pattern Recognition,
2007. CVPR’07. IEEE Conference on. IEEE, 2007, pp. 1–8.
[23] C. Huang, B. Wu, and R. Nevatia, “Robust object tracking by hierarchical association of detection responses,” in European Conference
on Computer Vision. Springer, 2008, pp. 788–801.
[24] S. Tang, B. Andres, M. Andriluka, and B. Schiele, “Subgraph decomposition for multi-target tracking,” in Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition, 2015, pp.
5033–5041.
[25] A. Dehghan, S. Modiri Assari, and M. Shah, “Gmmcp tracker: Globally optimal generalized maximum multi clique problem for multiple
object tracking,” in Proceedings of the IEEE Conference on Computer
Vision and Pattern Recognition, 2015, pp. 4091–4099.
[26] S. Zhang, Y. Gong, J.-B. Huang, J. Lim, J. Wang, N. Ahuja, and
M.-H. Yang, “Tracking persons-of-interest via adaptive discriminative
features,” in European Conference on Computer Vision. Springer,
2016, pp. 415–433.
[27] S. Hamid Rezatofighi, A. Milan, Z. Zhang, Q. Shi, A. Dick, and
I. Reid, “Joint probabilistic data association revisited,” in Proceedings
of the IEEE International Conference on Computer Vision, 2015, pp.
3047–3055.
[28] P. Dollár, R. Appel, S. Belongie, and P. Perona, “Fast feature pyramids
for object detection,” IEEE Transactions on Pattern Analysis and
Machine Intelligence, vol. 36, no. 8, pp. 1532–1545, 2014.
[29] K. Bernardin and R. Stiefelhagen, “Evaluating multiple object tracking
performance: the clear mot metrics,” EURASIP Journal on Image and
Video Processing, vol. 2008, no. 1, p. 246309, 2008.
[30] A. Milan, S. H. Rezatofighi, A. R. Dick, I. D. Reid, and K. Schindler,
“Online multi-target tracking using recurrent neural networks.” in
AAAI, 2017, pp. 4225–4232.

