|
|
|
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 S-Dimensional Matching is a set M of
hyper-edges or s-tuples such that
no two hyper-edges of M have
common vertices. |
|
|
|
A maximum(minimum) S-D Matching is an S-D
Matching with maximum (minimum) weight |
|
|
|
|
|
NP-Hard 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 NP-Hard, 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 one-to-one 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+s-1 |
|
Compute Cost of correspondence from every vertex
in previous frames (i to i+s-1) 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+s-1 |
|
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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|