Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

IEORE4004:  Optimization Models and Methods

Homework 7

● You are encouraged to pair up with someone to do this homework.

Moving object detection

Suppose we would like to extract moving objects from a video.  We encode the video as a data matrix 疝 e Rm xn  where each column corresponds to a video frame, and each row corresponds to a pixel.  If all the columns are the same, then there is no movement in the video and the data matrix 疝 has rank one. If one or more objects are moving, then they can be can be viewed as noise ∈ e Rm xn  that is being added to a rank one matrix aUT  (the fixed background) for some a e Rm  and U e Rn . In other words, we have 疝 = aUT + ∈. One can thus try to recover the background (and hence the moving objects) by finding a closest rank one matrix zyT  to the data matrix 疝 , as follows:

1.  Notice that we do not assume that all the elements of the vector U are equal to one another. What is the benefit of allowing them to be different from one another?

2.  Determine the update rule of the stochastic gradient descent method applied to the objective function.

3. Write the update rule in the attached python code (after reading instructions below).  Create a video using your smartphone and apply the algorithm to it. You can film yourself doing something you like  (dancing, soccer, etc) or simply a busy street in NY. Ideally there should be multiple moving objects. Be sure that the smartphone does not move while it is filming. The video should be in mp4 format.  Take a screenshot of your code, input and output videos.  Attach it to your write-up.

4.  Does the algorithm use all the data from your input video to generate the output? Comment.

5. Is the objective function convex?   Show that all local minima are global minima when  ∈ = 0. Comment on the empirical success of the approach.

Instructions for the code

Make sure you have anaconda installed, and open a terminal. Then

1. Write in terminal: conda

2. Write in terminal: source activate

3.  Create a conda environment with name mod: conda create –name mod python=3.8

4.  Activate the environment: conda activate mod

5. Install opencv (for processing videos): conda install -c conda-forge opencv

6. Install tqdm (for showing progress bars): conda install tqdm

7.  Go to the folder where you have the python script: cd /yourcodefolder/

8.  Run the code: python moving object detection.py Before you run the code, you need to

1.  Change video path in python script to the path of your video (path can be found by dragging file into your terminal)

2.  Create a folder where you would like to keep the output videos, and change output folder in the

script to the path to the folder that you just created.