A Beginners Guide to Computer Vision (Part 3)- Harris Interest Point Detection
Complete Harris Interest Point Detection Algorithm and implementation without using OpenCV.
Have a look at the example above, It shows the image of a building in two different views. How can we make the computer to realize that these two images shows the same building? Here comes the concept of Interest Points. Look at cross marks in those two images , the position of these points(cross marks) haven’t changed even the position of camera changed. Take a small window around each of these points in both the images. Consider you have a mechanism to map the window in one image to another window in the second image according to their features(feature extraction), then we completed our task of recognizing the objects. Don’t worry about feature extraction now, it will be covered in upcoming articles. Let’s concentrate on interest points in this article.
If you look closely onto the example above, you can realize that these interest points are merely the corner points, which can be seen at the intersections and sudden curvature changes. So we need an algorithm that can detect these corner points.
Harris algorithm is entirely depended upon one of his observation on corners. Look at the image above. If we take a small window around a point and move that window by giving it a small shift in all directions, what harris observed is there is a significant change in intensity if the window is it the corner point. Even you can observe this right!!
Mathematics of Harris Corner Detector
Sum of Squared Difference(SSD) is used to get the intensity change. Let I be the gray scale image, you obtain the change in intensity for the shift (u,v) from the equation below. here (x,y)∈W where, W is the window.
we also use a window function which make the above equation act like a weighted average. We can uniform window function for giving equal importance to every pixel or Gaussian function to give more importance to center pixel. Then the above function changes to the one below.
The next step is to rewrite the “shifted intensity” term with Taylor series. Lets me give a small introduction to Taylor series.
Taylor series
A function can be approximated by using a finite number of terms of its Taylor series. If you know the output of a function a at point, you can approximate the function use Taylor series in terms of it’s derivatives. Formula of Taylor series for a function f(x) is given below.
for example Taylor series for f(x) = 1/x at a = 1 is
Back to our topic
Now get back to our intensity change equation E(x,y), we can rewrite the term I(x+u,y+v) using Taylor series and the equation turns out like
There is nothing impossible happened here, don’t panic. We just expanded the term I(x+u,y+v) at the point (x,y) as show below
We approximate the function by considering only the first order partial derivatives.
Now equation can rewritten as
By substituting the term ‘M’ in E(x,y), the equation can be written as
This is the equation of ellipse with M as covariance matrix. After a lot of research, Harris came to a conclusion that using the terms of the matrix M, we can determine whether the window is at a corner point or at an edge or somewhere else in an image. He came up with parameter Response(R)
So if R>0 in a window, then that point is a corner
if R<0 in a window, then that point is a part of a edge
if |R| is small in a window, then that point is a part of a flat region.
Many researcher also suggested other relation of R some of those are in terms of the eigen values of M. Even the relation given by Harris can also be written in terms of eigen values as
value of k should be in between 0.04 to 0.06
Algorithm of Harris Corner Detector
- Compute X and Y derivatives of the image (Take in gray scale). If you learn about differentiation of images go through my previous article. link given below
- Compute Ix2, Ixy, Iy2 three images, code snippet is below
ix2 = ix**2
ixy = ix*iy
iy2 = iy**2- Apply Gaussian filter to these three images (sigma =1)
If you don’t know the concept of Gaussian filtering, here is a link to my article on it
#gkern gives you the gaussian kernal
ix2 = ndimage.convolve(ix2, gkern(3,1))
iy2 = ndimage.convolve(iy2, gkern(3,1))
ixy = ndimage.convolve(ixy, gkern(3,1))- Compute the sum of products of derivatives at every pixel and make matrix M out of it. calculate the response and store it accordingly. look at the code snippet below.
these are the results
- Now compute the local maxima points in the image of corners, use this code snippet below
from skimage.feature import peak_local_max
coordinates = peak_local_max(corners, min_distance=10)After the coordinates over the image, Result will look like this
I placed those those red dots at local maxima using pyplot.
You can go through the total code here
Yeah that’s the end. Stay tuned for more on computer vision.
