Unfolding Motion Detection [Part 1]: Feature Detections

If you belong from a computer vision or deep learning domain or you like that machine learning domain, you know that tracking motion using computer vision techniques is a bit on the complex side from a practical standpoint of view.

Motion detection is a continuous tracking salient features that are tracking spatial(with space) and temporal(with time) changes of features across multiple sequence frames. And many traditional techniques that have developed in computer vision are designed by keeping some constraints such as Changing Illumination, Rapid movement, etc

In this blog, I will try to describe my own intuitions of some of the commonly used traditional & modern methods that I have learned from different sources in past to do motion tracking and other required computer vision & machine learning tasks and try my best to condense into single blog posts (maybe series) from both theory & practical point of view importance as brief as possible. 

Creating Algorithm from ground-up:

We cannot track each and every pixel in the image, that would be really computationally impossible to achieve, so we have to find good features of the image subject. What are good features of the image? , Points that can be found in other variations of that image precisely and reliably. So most naive approach to find good features is to find Edges & Corners in images, let's explore intuition behind detecting edges and corner 

We cannot track each and every pixel in the image, that would be really computationally impossible to achieve, so we have to find good features of the image subject. What are good features of the image? , Points that can be found in other variations of that image precisely and reliably.

So most naive approach to find good features is to find Edges & Corners in images, let's explore intuition behind detecting edges and corner 

Finding Edges 

To find edges we first have to find Gradients in X & Y (Change of Intensity)direction then we can take the magnitude of that to find the edges in a given images

Gradients

Therefore gradient is [df/dx , df/dy]

Let's see what this function looks like in Python using Numpy & OpenCV

Gradient along X

img2 = img.astype(np.float)
    dimg = np.zeros(img.shape).astype(np.float)
    for i in range(img2.shape[0]):
        y = img2[i,:]
        x = np.arange(img2.shape[1]).astype(np.float)
        dy = np.zeros(y.shape,np.float).astype(np.float)
        #For Direction
        dy[0:-1] = np.diff(y)/np.diff(x)
        #Remember Slope formula from high school ?
        dy[-1] = (y[-1] - y[-2])/(x[-1] - x[-2])

        dimg[i] = dy

Similarly for Y

Running this on this below original image will give some result like

Gradient along with X result

Gradient along with Y result

Using pre-built filters

We can also find edges by filtering with pre-built filters from any library ski-image, OpenCV, etc

Actually starting building Motion Detection Algorithm :)

I think you maybe saw this coming that edges are good features for other image processing tasks but tracking edges in motion is not a good idea, because you see this what edge looks like along with its gradient at X(derivative graph)

Derivative along X

x = np.ones((50,50))*255
x[:,10:20] = 0
ax = plt.subplot(131)
ax.imshow(x)
ax = plt.subplot(132)
ax.plot(x[10,:])

# Finding Derivative 
x10 = np.arange(50)
y = x[:,10]
dy = np.zeros(y.shape,np.float)
dy[0:-1] = np.diff(y)/np.diff(x10)
dy[-1] = (y[-1]?-?y[-2])/(x10[-1]?-?x10[-2])
ax = plt.subplot(133)

ax.plot(dy)

And suppose this edge move along x by some distance and the gradient graph along X will be 

But for the same change along the Y gradient will be constant

As you can see it's not possible to track changes when edges move along its own axis

Here comes corner

Continuing the same intuitions suppose we create a corner and calculate derivative along X & Y and its motion 

Initial Derivative graph

Suppose it's displaced along XY Then, Derivative graph will be

and you can see the spike change, So what we actually looking here is the corner.

Harris Corner Detection

Harris corner model is based on the approximation model and error model of intensity which means, We have to find the behavior of this function on corner vs non-corner regions.

To predict the functions for small shifts they used Taylor expansion

Starting with your 1Dimensional textbook Taylor approximation

This is what second-order Taylor expansion for 2Dimesnion of E(u,v) about (0,0) (a local quadratic approximation for small (u,v) look like (I did not derive this taken from paper:)

Consider a constant “slice” of E(u,v):

∑I2xu2+2∑IxIyuv+∑I2yv2=k∑Ix2u2+2∑IxIyuv+∑Iy2v2=k

[uv]M[uv]=const

First, consider the axis-aligned case where gradients are either horizontal or vertical

If either λ is close to 0, then this is not a corner, so look for locations where both are large

The axis lengths of the ellipse are determined by the eigenvalues and the orientation is determined by R

Now we can Classify of image points using eigenvalues of M:

Creating a Response function from λ1& λ2 

λ1& λ2 range examples

Harris detector algorithm

1. Compute Gaussian derivatives at each pixel
2. Compute second-moment matrix M in a Gaussian window around each pixel
3. Compute corner response function R
4. Threshold R
5. Find local maxima of response function (non-maximum suppression)

In python :

#Find x and y derivatives
dx = cv.Sobel(gimg,cv.CV_64F,1,0,ksize=5)
dy = cv.Sobel(gimg,cv.CV_64F,0,1,ksize=5)
Ixx = dx**2
Ixy = dy*dx
Iyy = dy**2
height = int(img.shape[0])
width = int(img.shape[1])


cornerList = []
color_img = img.copy()
offset = int(window_size/2)


#Looping through image and find our corners

    for y in range(offset, height-offset):
        for x in range(offset, width-offset):
            #Calculate sum of squares
            windowIxx = Ixx[y-offset:y+offset+1, x-offset:x+offset+1]
            windowIxy = Ixy[y-offset:y+offset+1, x-offset:x+offset+1]
            windowIyy = Iyy[y-offset:y+offset+1, x-offset:x+offset+1]
            sxx = windowIxx.sum()
            sxy = windowIxy.sum()
            syy = windowIyy.sum()


            #Finding determinant and trace, use to get corner response

            det = (sxx * syy) - (sxy**2)
            trace = sxx + syy

            
            r = det - k*(trace**2)

Output 

Orignal Input

Processed after harris corner

Now there are also other ways to find corners using methods like SIFT, Shi-Tomasi, etc, But remember this blog is about exploring Motion, not an evaluation of different corner detection algorithm.so we’re gonna focus on tracking features. 

In the next part, we’ll start with the Optical flow using Lucas and Kanade method and other modern Deep learning methods.