Video-Processing-Homework 3 Solved

Part A:

Please answer the following questions. Keep your answers short as possible and show the general direction of your solution. There is more than one correct answer.

1.      We saw that       . Explain the formula and how it

relates to the Kalman/Particle filter. Start from explaining what is the posterior, prior𝑝𝑜𝑠𝑡𝑒𝑟𝑖𝑜𝑟 ∝ 𝑝𝑟𝑖𝑜𝑟 × 𝑙𝑖𝑘𝑒𝑙𝑖ℎ𝑜𝑜𝑑

and likelihood.

2.      For the measurement step in the particle filter, we used the histogram of the two patches (the patch around the new particle and the original patch of the object).

a.      Why do we use the histogram to score the patches? what are the pros and cons of using this method?

b.      We took the patches and computed the histogram and their distances. Why didn’t we use the SSD (sum square difference) between the patches (in the image space)?

c.       Can you think of another method to compare the patches? What are the pros and cons of the new method?

You can describe an example if it helps you.

3.      Will particle filter work when the tracked object changes its scale (like a person walking towards and away from the camera)? What about the viewpoint of the object (like a person dancing)?

4.      Can you think about a way to know when to update the template? Think of a scenario where we track a person. We keep a patch of the object’s appearance in the first frame, and then compare each new patch to it. One of the problems is that, as time passes, the original patch no longer represents the object (light, viewpoint, …). Can you think of a way to determine when to update the patch of the object? And how to determine the new patch (based on the previous frame/ based on the last two frames/…)?

Part B:

Basic theory (just a reminder):

In the Kalman filter, the density propagation changes from one Gaussian to another Gaussian distribution. What changes is the mean and variance.

This is very good if our system is linear and the noise is Gaussian. But if it isn’t (i.e. cluttered data etc.) – Kalman fails.

This is where the particle filter enters - in every stage we create a new probability density function which can take any shape (not limited to being a Gaussian).

This shape is formed by sampling particles, each with a given weight and cumulative density function. This will be further elaborated in the continuation of this worksheet.

In short – we’re still computing likelihood and prior probabilities and derive the posterior from them (similar to Kalman), but we’re using more dynamic (non-Gaussian) probability functions to model the system.

Definitions:

For a given time stage, the system is described using the state vectors, their weights and their CDF’s.

For N particles this is comprised of {𝑠(𝑡𝑛) , 𝑤(𝑡𝑛) , 𝑐(𝑡𝑛)}𝑁𝑛=1 

And in short writing we’ll say that:

                     𝑆                                                                                                                                                

𝑐

𝑖∑=1 𝑤(𝑡𝑖) = 1

For example -and all this is true for time𝑠(𝑡15) , 𝑤(𝑡15) , 𝑐(𝑡15) denotes that state vector 𝑠𝑡(15) has a weight of 𝑤𝑡(15) and a CDF of

𝑐(𝑡15)                  Algorithm stages you’ll implement in the assignment:𝑡 = 𝑡1

For brevity, we won’t always write the time step indices. But keep in mind we’re starting with the particle filter for time t-1 (‘before the first image’) and each new image is the next time step (t, t+1, t+2 etc. but because the images are discrete this doesn’t mean much.)

Step A:

Here we will create an initial particle filter (composed of 100 particles) for the previous time stage (t-1).

For this assignment each state vector has the following form:

 𝑠(𝑡𝑛) = ⎡⎢⎣𝑋(𝑐𝑛), 𝑌(𝑐𝑛), 𝑊𝑖𝑑𝑡ℎ2 (𝑛), 𝐻𝑒𝑖𝑔ℎ𝑡2 (𝑛), 𝑋𝑣𝑒𝑙𝑜𝑐𝑖𝑡𝑦(𝑛)                                         , 𝑌(𝑣𝑒𝑙𝑜𝑐𝑖𝑡𝑦𝑛)           ⎤⎥⎦ @ 𝑡𝑖𝑚𝑒 𝑡 and 𝑛∈[1, 2, …, 100]

𝑋𝑐, 𝑌𝑐 = 𝑐𝑜𝑜𝑟𝑑𝑖𝑛𝑎𝑡𝑒𝑠 𝑡𝑜 𝑡ℎ𝑒 𝑐𝑒𝑛𝑡𝑒𝑟 𝑜𝑓 𝑜𝑏𝑗𝑒𝑐𝑡 (𝑡ℎ𝑒 𝑝𝑒𝑟𝑠𝑜𝑛 𝑤𝑒'𝑟𝑒 𝑔𝑜𝑖𝑛𝑔 𝑡𝑜 𝑡𝑟𝑎𝑐𝑘)

 𝑊𝑖𝑑𝑡ℎ2   , 𝐻𝑒𝑖𝑔ℎ𝑡2     = ℎ𝑎𝑙𝑓 𝑜𝑓 𝑡ℎ𝑒 𝑤𝑖𝑑𝑡ℎ 𝑎𝑛𝑑 ℎ𝑒𝑖𝑔ℎ𝑡 𝑜𝑓 𝑜𝑢𝑟 𝑡𝑟𝑎𝑐𝑘𝑒𝑑 𝑝𝑒𝑟𝑠𝑜𝑛

𝑋𝑣𝑒𝑙𝑜𝑐𝑖𝑡𝑦, 𝑌𝑣𝑒𝑙𝑜𝑐𝑖𝑡𝑦 = 𝑡ℎ𝑒 𝑠𝑝𝑒𝑒𝑑 𝑜𝑓 𝑜𝑢𝑟 𝑝𝑒𝑟𝑠𝑜𝑛 𝑖𝑛 𝑒𝑎𝑐ℎ 𝑐𝑜𝑜𝑟𝑑𝑖𝑛𝑎𝑡𝑒

Hint – you don’t have to change the width and height between time steps.

Now for the actual steps:

      1.2. Create a matrix of vector states sized 6x100 by adding random additive noise toSet 𝑠𝑖𝑛𝑖𝑡𝑖𝑎𝑙 = [297, 139, 16, 43, 0, 0]

𝑠one state vector, each row describes one of the state vector components for 100𝑖𝑛𝑖𝑡𝑖𝑎𝑙. Repeating this will create 100 particle state vectors (each column describes

different particles). We’ll call thisYou can use step C (prediction) using the initial state vector for this part.𝑆 (with a capital S).

3.       Load the first image and compute the normalized histogram for this image using

𝑠This step can be confusing, so please read this carefully:𝑖𝑛𝑖𝑡𝑖𝑎𝑙. We’ll call this normalized histogram ‘q’.

Your current frame ‘I’ is described in 3 dimension (width x height x 3 channels, RGB).

𝑠The histogram is computed for the pixels in the rectangle sized width x height with𝑖𝑛𝑖𝑡𝑖𝑎𝑙 is 2 dimensional sized 6x1.

the centers xc and yc. You receive this information fromLooking at this sub-portion of I, you’ll notice the pixel intensities vary between 0 and𝑠𝑖𝑛𝑖𝑡𝑖𝑎𝑙.

255 (8-bit). We want to quantize this to 4 bits (0 to 15).

Next we look at each new combination of I_subportion(R,G,B) and we have a total of

16each element in the vector describes the number of times this RGB combination3 = 4096 combinations of RGB values. We’ll build a histogram vector such that

appears. Do this for 16x16x16 values and reshape it into a 4096x1 vector.

Normalize this vector such that the sum of all elements is equal to 1.

4.       Repeat step 3, but this time use the first image and use the first column ofWe’ll call this normalized histogram ‘p’. p is computed exactly like q was computed in𝑆

the long explanation in step 3.

Now we compute the weights of each particle using the Bhattacharyya distance between p and q. This similarity index will be our way to determine the weights.

Repeat this step for all 100 columns ofwhere each element is𝑆 and you’llthe single Bhattacharyya distanceend up with value. The equation is:𝑊 = {𝑤1, 𝑤2, …, 𝑤100}   

5.       Normalize vector W such that𝑤 = 𝑑𝑖𝑠𝑡100(𝑝, 𝑞) = 𝑒𝑥𝑝       𝑞𝑖

𝑖∑=1 𝑤(𝑖) = 1

6.       Compute vector 𝐶 = {𝑐1, …, 𝑐𝑗, …, 𝑐100} = ⎱⎰𝑤1, …, 𝑖∑=𝑗1 𝑤(𝑖), …, 100𝑖∑=1 𝑤(𝑖) = 1⎰⎱

We now have a complete set for our initial particle filter, normalized, weighted and with the CDFs.

Next we have to:

●     sample the previous particle filter (step B)

●     predict the next particle filter and update the weights + CDF (step C)

●     display the results (step D)

Step B (sampling, deterministic ‘drift’):

       ●1. Repeat the following steps 1-3 for each value ofGenerate a random value from a uniform distribution.𝑛∈[1, 𝑁]

2.3.                                                                       Find the smallest value ‘j’ such thatSet          where index ‘j’ corresponds𝑟∈[0, 1] (𝑡−𝑗)1≥𝑟 𝑐

                      𝑠'𝑡(𝑛) = 𝑠(𝑡−𝑗)1                                                                                   with the ‘j’ we found in step 2.

We now have N sampled particles 𝑆'𝑡 = {𝑠'𝑡(𝑛)}𝑁𝑛=1

Step C (prediction, random ‘diffusion’):

Project the sampled particles from the previous step to their new location using a dynamic model and adding noise.  This is done by setting:

The noise is white additive noise (you decide what noise!).𝑆𝑡 = 𝐴𝑆'𝑡 + 𝑛𝑜𝑖𝑠𝑒

A is a dynamic model (like in Kalman) – you may simply add the previous velocity components such that

Step D (show results):𝑆𝑡 = ⎡⎢⎣𝑋(𝑐𝑛) + 𝑋(𝑣𝑒𝑙𝑜𝑐𝑖𝑡𝑦𝑛) , 𝑌(𝑐𝑛) + 𝑌(𝑣𝑒𝑙𝑜𝑐𝑖𝑡𝑦𝑛)              , 𝑊𝑖𝑑𝑡ℎ2        (𝑛), 𝐻𝑒𝑖𝑔ℎ𝑡2                        (𝑛), 𝑋(𝑣𝑒𝑙𝑜𝑐𝑖𝑡𝑦𝑛)       , 𝑌(𝑣𝑒𝑙𝑜𝑐𝑖𝑡𝑦𝑛)                                                 ⎤⎥⎦𝑡 + 𝑛𝑜𝑖𝑠𝑒

You are required to plot the average particle filter rectangle in green and to plot the maximal particle filter (with the largest weight) in red.

There are numerous ways to achieve this type of plot.

The title of the image plot must be HW3_ID1_ID2- Frame number = xxx.

When you display a figure to the screen, make sure the open figure window won’t block the progress of the code (use the block=False flag, in plt.show).