CSGY6643 Extra Credits Solved

A) Optical Flow 

 

In this project, you will implement the Lucas-Kanade and Horn-Schunck optical flow methods. Both methods are based on spatial and temporal derivatives, differing mainly in the optimization approach.


Implementation: 
 

1.    Assume two images with the same dimensions, e.g. im1 = sphere0.png and im2 = sphere1.png. 
    

2.    Compute spatial partial derivative images Ix and Iy for im1 using any method of your choice. 


3.    Compute temporal partial derivative It. This can be approximated by image difference im2 - im1. 
 

Implement Lucas-Kanade 


This method solves for optical flow by assuming constant flow within a neighborhood (patch), centered around the current pixel (i,j). Using this assumption, a linear system is constructed and solved to find ui,j and vi,j. This means you must repeat this process for every pixel in the image.

 

Consider using a neighborhood size of 5x5. This results in the linear system shown below, with a matrix consisting of spatial partial derivatives and a vector of temporal partial derivatives at all points in the neighborhood pi. Solve this system of equations via linear least squares to find ui,j and vi,j.  

 

Note, this is not the value of u and v for the entire neighborhood, only for the pixel (i,j). Repeat this process for every pixel in the image. You may ignore the boundary of the image where you cannot sample a full neighborhood.  

 

  

 

Implement Horn-Schunck 

 

This method solves for optical flow by imposing a smoothness penalty on the optical flow field, and uses gradient descent to iteratively estimate optical flow. The cost function to minimize is composed of two parts:  

 

Smoothness on optical flow:

 

  

 

Brightness constancy:

 

  

 

The overall cost function:

 

  

 

Below is a pseudocode algorithm for Horn-Schunck optical flow:

 

  

 

Where the update equations are (for iteration k):

 

  

 

  

You may check for convergence by computing the overall cost and checking that it doesn’t change much between iterations, or you may just run the procedure for a certain number of iterations until you are satisfied with the results. It may take many iterations.

 

 

 

 

 

Experiments: 

 

Synthetic Sphere Images
 

1.    Using sphere0.png and sphere1.png, explore the Lucas-Kanade method using a neighborhood size of 3, 5, 11, and 21. 

•       For each neighborhood size, plot optical flow as a vector field and the magnitude of the optical flow field at every pixel. 

•       Describe the impact of the neighborhood size. Do you conclude that it plays a large role in the estimation of the optical flow field?  

 

2.    Using sphere0.png and sphere1.png, explore the Horn-Schunck method using values of λ = 100, 10, 1, and 0.1. 

•       For each value of λ, plot optical flow as a vector field and the magnitude of the optical flow field at every pixel. 

•       Describe the impact of λ. Do you conclude that it plays a large role in the estimation of the optical flow field?  

 

Real Traffic Images
 

3.    Using traffic0.png and traffic1.png, get the best results you can using the Lucas-Kanade method. 

•       Show the best result you were able to obtain along with any parameter values used. Plot optical flow as a vector field and the magnitude of the optical flow field at every pixel. 

•       Discuss the process of obtaining good results, i.e. was it easy/difficult? 

 

4.    Using traffic0.png and traffic1.png, get the best results you can using the Horn-Schunck method. 

•       Show the best result you were able to obtain along with any parameter values used. Plot optical flow as a vector field and the magnitude of the optical flow field at every pixel. 

•       Discuss the process of obtaining good results, i.e. was it easy/difficult? 

 

Summary
 

5. Give your overall thoughts of the two methods:

•       Do each have certain strengths and weaknesses, or is there one method that you find to be superior?  

•       Compare the methods in terms of difficulty in choosing parameters.  

•       Compare the methods (qualitatively) in terms of run time.

•       Were both methods equally challenging to implement. Did you find one to be easier?  

Helpful hints: 

 

•       Plotting vectors over an image

 

# Subsample the vector field to make it less dense subsample = 6 sub_u = u[0:rows:subsample, 0:cols:subsample] sub_v = v[0:rows:subsample, 0:cols:subsample] 

 xc = np.linspace(0, cols, sub_u.shape[1]) yc = np.linspace(0, rows, sub_u.shape[0]) 

 

# Locations of the vectors xv, yv = np.meshgrid(xc, yc) 

 fig1 = plt.figure(figsize = (14,7)) 

 plt.imshow(im1,cmap = 'gray') plt.title('Optical Flow'), plt.xticks([]), plt.yticks([]) 

 

# Plot the vectors plt.quiver(xv, yv, sub_u, sub_v, color='y') 

 

•       Blurring before computing derivatives  

You may find you get better (or worse) results if you blur before you compute derivatives.

 

•       Downsampling input images 

 

You may find you get better (or worse) results if you downsample the input images.

 

•       Solving Lucas-Kanade via linear least squares instead of exact solution

 

You saw from lecture that you can construct an exact linear system via ATA and ATb. However, this matrix ATA is problematic and will cause solver errors for many pixels in the image. The real solution involves heuristics about the eingenvalues of ATA. Solving via linear least squares avoids having to deal with this issue.