Computer Vision: Object Tracking

 Simple frame difference does detect moving objects, but detects non interesting changes and variations. This is an extremely simple algorithm, where label significant difference between current and previous frames as foreground |It - It-1| > T where T is the threshold value. 

A pixel's intensity may change due to object motion and lighting images, and noise and shake, but these are not interesting for the purpose of detecting objects. Maybe we can build a model of the background frame. Maybe we can take the first K frames, compute the average, and treat this as a background frame. A pixel would be foreground if the threshold difference. However, lighting changes could really throw this thing off. This is why the following is messed up. 

Over time, all pixels can accidentally combine, keeping a everything be classified as foreground, so the idea is to change the background model over time. Maybe we can taking a running average, or a median of the first few frames, etc. Changes make many unintended images the foreground. We can make a much, much more robust algorithm which we compute the median of the previous K frames. 

median (It-1, It-2, ... It-k), but this is expensive because computing the median is computationally intensive. Can we get these benefits without an extremely high computation cost? 

There is a method that can maintain a robust background with low computation cost. Consider 1 particular pixel, and the changes in its intensity over time. It may change due to a foreground change (car). We make a histogram of intensities. The X axis is intensity, and Y axis represents the frequency of intensity. 

We are interested in the intensities that happened more often. The intensities that occur more frequently are likely background intensities and the intensities that occur more frequently are likely foreground intensities, which then we can use to categorize a pixel into either foreground or background. The histogram measures the frequency that an pixel intensity is achieved (how many times does the pixel see intensity value x?) As a result, a good next step is to smooth out the histogram intensities. 

We can think of a diagram as a probability distribution. We see if an intensity has a higher or lower likelihood of appearing. The intensities have peaks, which corresponds to a background or foreground process. 

Things can correspond to frames when a car is passing through a particular pixel, making several distinct clusters. We want to represent a probability distribution of clusters. Then we classify each cluster as foreground or background, or classify each picture as a foreground or a background. 

We can use a 1-D Gaussian to smooth such model first. This is 1D Gaussian: 

Assume P(x) is made out of K different Gaussians, a hyperparameter corresponding to everything happening in a scene. The probability distribution is the following such the sum of weights = 1. 

We can express things such as a 3 Dimensional Histogram, and gmDistribution.fit the MATLAB function can actually do this fitting for you. 

The histogram should be normalized. gmdistribution.fit, and she should normalize this histogram. 

The next thing to do is to classify each gaussian as foreground gaussian. Taller but thinner is background and shorter but lighter correspond to foreground using the equation ω/σ.

The following is the Gaussian procedure.

So for each pixel, compute the pixel intensity using the first N frames, and then normalize the histogram as ~H <= H / ||H|| an model the histogram as 3 to 5 Gaussians.

For each subsequent frame, determine the intensity of the pixel at that frame and determine which Gaussian it belongs to. 

If ω/σ is large then background else foreground. Update the histogram using new pixel intensity.

If Hhat and H/||H|| differ a lot (Hhat - H/||H|| is large) H <- H/||H|| and refit the GMM. 

Fortunately there are approximate algorithms, which are quite fast, and it works quite well dspite slight occlusion. 

What if the background is white while the foreground is dark? This method doesn't assume the absolute brightness values about foreground vs background. But a pixel will see foreground intensity fewer times vs background. 

A background pixel sees a particular intensity most of the time. A car that is stationary will be classified as a background pixel because it sees this intensity most of the time. If the background is white the distributions are still Gaussian, the distribution will always work unless everything is completely saturated.  

Once again, the background doesn't necessarily have to be darker than the foreground. That's the beauty of this algorithm. This would just shift background and foreground Gaussians toward a different example, but the everything else will remain the same. Gaussian Mixing Model (GMM) is usually much more robust than the moving median diagram. It works quite well even in these examples.

Now our goal is to find the location of an object of interest inside a frame.

Let's say we want to find the location of Kylian Mbappé, the best match here.

The first is called template based tracking, where we represent an image with pixel intensity. We take the raw image intensities as object template and define a search region in the subsequent frame, and define a search window, and search the neighborhood to find an image match. 

We can either take the sum of absolute differences, sum of squared differences, or a normalized cost-correlation functions.

This approach is very simple, but it is not super robust. The second type is histogram tracking, which is creating a histogram of pixel intensities inside of a window, because now we are going to compare the histogram instead of directly comparing an image itself. 

One ideal is to create a weighted histogram, where we give more importance to pixels at teh center of the window, wherease a pixel near the periphery contributes less to the center. This is called the Epanechnikov kernel, which is 1 - ||x|| ^2 when ||x|| < 1 and 0 otherwise, where x is 

[(x - xc)/W; (y - yc)/H]

The rest of the approach is quite similar once we have created that said histogram. Instead of matching windows, we match the histogram template with the histogram of intensities inside of this window. This approach is more robust to changes in size, scale, and orientation of an object. One popular approach is to compute the cross correlation of the 2 histograms. The larger the correlation value, the better the match. 

We can also can climb the hill using the mean shift, and we search in a local neighborhood and move to the location to the largest value of the small neighborhood. We can do hill climbing using mean shift much faster vs brute force.

Histogram based tracking works well when the object has a unique appearance. This thing is robust. However, bounds can keep switching between objects of similar appearance, and this is failing. It's the same when my facial algorithm recognize me and my little brother as the same person. 

The last approach recognize a collection of interest points as SIFT Features and we use these features to get the features. 

We use a sift detector to find interest points, and any of these points are labelled as object points, and all the other points are labelled as background points. We collect these into object features and background features, respectively. For every subsequent frame, label it either as an object point or a background point by comparing the feature to all the points in both the foreground and the background. Finally, we find an image window with as many bluepoints as possible and avoiding as many red points as possible. We use this new location to update the update the object and background models.

This may not be the best in an application where speed is a critical concern. 

We could use HAAR features, but they might not be robust or accurate, but it is generally better and faster in terms of speed. Doing the matching will be determined by the application-specific requirements.

At frame L:

1. The user selects a bounding box as object/target

2. SIFT is computed

3. Features are classified as object in the box and set them to O1.

4. Classify the remaining features as background and assign them to set B. 

At frame t: 

1. Compute SIFT features.

2. For each feature and corresponding feature descriptor vi:

a. Compute distance do between Vi and the best match in set Ot-1.

b. Compute distance dB between vi and the best match in background set B.

C(vi)  = 1 when do/dB < 0.5 (vi belongs to object) -1 otherwise.

3. For each search window W

a. Compute φ(W) = ΣC(vi) for all features vi inside W.

b. Compute a heuristic (W, Wt-1)

c. Compute match score μ(W) =  φ(W) - τ(W, Wt-1)

4. Select window Wt with the best match as new object location.

5. Update object appearance model Ot = Ot-1 ∪ (vi) ∀ vi inside Wt such that C(vi) = +1.

An good idea is to track players or a ball in sports, and track them off camera all the way around the back of the stadium. 

One approach is a fusion approach, where we use multiple trackers and find the results. SIFT is so effective, it works for object detection as well. Locations of parts may change, but as long as parts appear in a rotated image, we will find them. The algorithm can detect various poses because it updates the foreground and background all the time. We can track the object in all cases other than the time it completely disappears.