The Harris corner detection algorithm also called the Harris & Stephens corner detector is one of the simplest corner detectors available. The idea is to locate interest points where the surrounding neighbourhood shows edges in more than one direction. The basic idea of algorithm is to find the difference in intensity for a displacement of (u,v) in all directions which is expressed as below:
Window function is either a rectangular window or a gaussian window which gives weights to pixels at (x,y). The above equation can be further approximated using Tayler expansion which gives us the final formula as:
Ix and Iy are image derivatives in x and y directions respectively.
Then we finally find the Harris response R given by:
We find the corners using the value of R.
Process of Harris Corner Detection Algorithm
- Color image to Grayscale conversion
- Spatial derivative calculation
- Structure tensor setup
- Harris response calculation
- Find edges and corners using R
You can find the entire source code in this notebook. I am explaining the various parts of the same code here on, so its better you keep that open too for better understanding.
Lets take a small image and find edges and corners. For my sample implementation, I am taking the below image:
Step 1: Covert the image to Grayscale
from skimage.io import imread from skimage.color import rgb2gray img = imread('resources/box.jpg') imggray = rgb2gray(img)
You cannot see much difference but at the array level this is what I have:
Step 2: Spatial derivative calculation
from scipy import signal as sig import numpy as np def gradient_x(imggray): ##Sobel operator kernels. kernel_x = np.array([[-1, 0, 1],[-2, 0, 2],[-1, 0, 1]]) return sig.convolve2d(imggray, kernel_x, mode='same') def gradient_y(imggray): kernel_y = np.array([[1, 2, 1], [0, 0, 0], [-1, -2, -1]]) return sig.convolve2d(imggray, kernel_y, mode='same') I_x = gradient_x(imggray) I_y = gradient_y(imggray)
I am using the Sobel filter to find the derivatives.
Step 3: Structure tensor setup
Ixx = I_x**2 Ixy = I_y*I_x Iyy = I_y**2
Step 4: Harris response calculation
We first calculate the sum of squares of our gradient at each pixel by shifting a window over all the pixels in our image. The window is shifted according to the offset which you decided based on your image.
for y in range(offset, height-offset): for x in range(offset, width-offset): Sxx = np.sum(Ixx[y-offset:y+1+offset, x-offset:x+1+offset]) Syy = np.sum(Iyy[y-offset:y+1+offset, x-offset:x+1+offset]) Sxy = np.sum(Ixy[y-offset:y+1+offset, x-offset:x+1+offset])
Take a look at the below trace to get a rough idea of how the window shifting works. This is done for all Ixx, Iyy and Ixy.
Using the sum of squares of each window we find the harris response R at each pixel.
#Find determinant and trace, use to get corner response det = (Sxx * Syy) - (Sxy**2) trace = Sxx + Syy r = det - k*(trace**2)
k is the sensitivity factor to separate corners from edges, typically a value close to zero, for my analysis I have taken k=0.04. Small values of k result in detection of sharp corners.
Step 5: Find edges and corners using R
- Edge : r < 0
- Corner : r > 0
- Flat: r = 0
for response in harris_response: x, y, r = response if r > 0: img_copy[y,x] = [255,0,0]
If R > 0, I changing the image pixel value to red, the final output is here.
For the above image, I chose a window size of 6. You can try different variants and see how it works.
For production you can use the skimage library for corner detection.
from skimage.feature import corner_harris, corner_peaks # print corner_harris(ximage) coords = corner_peaks(corner_harris(imggray))
- Chris Harris and Mike Stephens (1988). “A Combined Corner and Edge Detector“. Alvey Vision Conference
- Harris Corner Detector, Tom Werner, Center for Machine Perception Czech Technical University Prague
- Interest point detection, Wikipedia
- Interest Point Detection lecture by Dr. Mubarak Shah, UCF Computer Vision Video Lectures 2012