CS585 HW4: Multiple Object Tracking

CS 585 HW 4
Ding Jin

Problem Definition

The goal of this assignment is to implement the Hungarian algorithm and Kalman filter for multiple object tracking

Method and Implementation

Object labelling:

The basic idea is simply to find the contours of every segmented object and find the centroids. The justfiction of using the centroids as the inputs of the tracking will be showed below.
Now the procedure for the object labeling will be:
1.Gray Scale conversion + Background subtraction (I did the binray conversion, but it is just not that good)
2.Find contours and for every contours find the centroids (Technically, the 'centroids' of the least circle that round the contours)
3.The idea of extracing only centrodid is that for every Karman filter that applied on the single object(contour here), it will leave the
least invariance when computing the previous covariance matrix and the previous state vector(explicitly); also it reduce the affect of the noise matrix; and last, processing each object to a single vector can reduce a lot of computations
Hungarian Algorithm:

The Hungraian ALgorithm here solves the assignment optimization problem here:
1.Row operations and overcome the unassignmented elements(here will be the centroid that does not resides in the neighbourhood.)
2.Assign as many tasks as possible and mark the respective rows.
3.Reinforce the assignemnts in 2. and repeat
That algorithm also provides the first step correctness here by averaging the squared error here
Kalman filter and correct:

I implemented the Kalman filter here as a class for eaiser scoping; it keeps track of the estimated state of the system and the variance or uncertainty of the estimate.
The update equation will be:
u(k|k-1) = Fu(k|k-1)
P(k|k-1) = FP(k-1) F*T + Q

The correct equation will be:
C = AP(k|k-1) A*T + R
K(k) = P(k|k-1) A*T(C.Inv)
u'(k) = u'(k|k-1) + K(k) -A*u'(k|k-1)
P(k) = P(k|k-1) - K(k)(CK.T)

Tracking result


Bat Tracking
Aqua tracking

Credits and Bibliography

[1]--The correctness and the headstart implementation code are coming from the second cs585 lab
[2]--The Hungarian Algorithm(munkres) package: https://pypi.python.org/pypi/munkres/