


Khurram Hassan Shafique and Mubarak Shah 

Computer Vision Laboratory 

University of Central Florida 







Handling Missed Detections and Occlusions 

Dummy targets are added if the number of
detected targets in is less
than number of detected targets in
. 

Handling Noise and Ambiguities 

Different Heuristics are used as a high level
process that is not part of optimization process. 




Sequence of n frames corresponding to n time
instances 







Find a set of tracks such that 



Each track
is the sequence of points that are the 2D projections of exactly one
point X in the world 

No other track contains any 2D projection of X. 








Ambiguities 

Detection Errors 

Noise 

Occlusion 

Entry & Exit 







Graceful Degradation 

Least Commitment 






Combinatorial Nature of Problem 

Computational Complexity 

Real Time Requirements 

Formulating Noise, Detection Errors, and
Occlusion as a part of optimization problem. 





An SDimensional Matching is a set M of
hyperedges or stuples such that
no two hyperedges of M have
common vertices. 



A maximum(minimum) SD Matching is an SD
Matching with maximum (minimum) weight 





NPHard even when S=3 

Assumes that the object is visible continuously
in S frames. 

Does not deal directly with occlusion and
missing information 










Given a directed graph G 



Find a set of vertex disjoint paths that has
maximum/minimum weight among all such paths. 








This problem is also NPHard, even in the case
of unweighted graphs 



However, when the directed graph is acyclic, a
polynomial solution exists. 



In our problem, the directed graph is acyclic 








The split of a digraph D is a bipartite graph G
whose partite sets are
copies of . 

For each
vertex , there is one
vertex and one
vertex . 

For each edge from u to v in D, there is an edge
with endpoints in G 








Theorem: 

The sets of vertex disjoint paths of acyclic
digraph D are in onetoone correspondence with the matchings of its split
graph G. 





The same algorithm for 2 frames can now be used
on split graph to find a set of vertex disjoint paths. 

The complexity of algorithm is 

n is the maximum number of targets in a single
frame 

S is the number of frames 





The algorithm requires that the cost function is
independent of previous correspondence 

This is not usually true 

If the cost function is based on velocity, the
above algorithm can not be used. 








Given the correspondences from frame i to i+s1 

Compute Cost of correspondence from every vertex
in previous frames (i to i+s1) to every vertex in current frame (i+s). 

Prune the graph if the cost is above certain
threshold 

Find the split of the graph and compute minimum
matching 

For j= i to i+s1 

Delete erroneous correspondences 

Find the correspondence among the uncorresponded
vertices in frames j and j+1. 







Gain Function must satisfy the following
inequality 





Where
are 2D projections of some point X 





Occlusions & Missed observations can be
handled only for limited frames 

For large Occlusions & Missed observations,
high level processes are required. 

Occlusion & Scene Entry/Exit are conflicting
problems, which can only be solved by high level processes 




Track Errors 









Errors are calculated by averaging the errors of
100 runs of algorithm on sequences generated using the same parameters 




Uniform distributions for initial point
positions 

Normal distributions for magnitude of initial
velocity 

Uniform distribution for angle of initial
velocity 

Normal distribution for velocity update 

Probability of occlusion & Missed Detection 

Probability of Entry & Exit 
















