Feature Points Extraction using Harris Corner Detector

Feature points extraction is a common computer vision task where Harris Corner Detector fits well. Corners are important features of an image, since they provide useful information for objects detection. A robust and accurate interest points detector is that of Harris. This operator performs well in distinguishing between edges and corners. The algorithm performs per pixel basis, so FivekoGFX implements a fast parallel version of Harris corners extractor using WebGL/OpenGL GLSL code.

Checker feature points detection
Тhe recognized key points as a result of Harris corners detection


Some common applications for extracting feature points from images through Harris corner detector are:

  • Image classification
  • Objects recognition
  • Objects tracking in video sequence
  • Image alignment and stitching for panoramic image creation

What is a corner in an image?

Corners are points located between two dominant image edges with different direction. Vertices of image contours are of great importance for defining objects shape. Hence we frequently call them key points or feature points.

How does Harris Corner Detector works?

Feature points extraction by Harris detector is based on image derivatives. Because corners are located around derivatives variations, we look for such significant gradient changes. The principle behind Harris corner detector is the search for significant changes in the gradient intensity for local area (window). For that reason when the window is over a linear gradient segment directional changes will decrease maximum gradient value. Otherwise when window is over a vertex, movements in any direction will increase the intensity change.

Gradient Corners Info
Harris mask scheme over line and corner

Basically the Harris corner detector algorithm will have the following steps:

  • Edge detection – for image derivatives calculation it is appropriate to use Sobel edge detector
  • Image smoothing – frequently this step uses Gaussian or Mean filters
  • Harris measure computation
  • Non-maximum suppression
  • Feature points thresholding

Harris response calculation

A movable image patch at position (x, y) shifts with defined offset (dx,dy):

Harris Corner Detector Matrix

The Harris corner score is used to determine if the current position contains a corner or not:

$\displaystyle{R}= \det{{\left({M}\right)}}-{k}\cdot{\left({t}{r}{a}{c}{e}{\left({M}\right)}\right)}^{2}=\lambda_{{1}}\lambda_{{2}}-{k}{\left(\lambda_{{1}}+\lambda_{{2}}\right)}^{2}$
Harris corner score

Matrix trace calculation

In linear algebra the det(M) stands for a square matrix determinant. To calculate determinant of 2×2 matrix use the following eqution:

Matrix determinant
Calculation of 2×2 matrix determinant

Matrix trace calculation

In linear algebra the trace(M) of a square matrix is the total sum of the main diagonal. To calculate the trace of the Harris matrix use the following equation:

Harris matrix trace
Trace of 2×2 matrix

Harris result image map

Finally, the algorithm creates a gray-scale map image where the bright areas are the corners.

Harris corners result
Harris corners map

Source Code

Below are code snippets of Harris Corner Detection, which are part of FivekoGFX computer vision library. The proposed algorithm uses OpenGL shaders to provide parallel execution and good performance.

Derivatives calculation

First of all we calculate image gradients in horizontal and vertical direction. As a result our algorithm stores the derivatives as in below snippet.

float dx = length((GET_PIXEL(-1, -1)*u_kernel[0] +
			GET_PIXEL(-1,  0)*u_kernel[1] +
			GET_PIXEL(-1, +1)*u_kernel[2]) -
		   (GET_PIXEL(+1, -1)*u_kernel[0] +
			GET_PIXEL(+1,  0)*u_kernel[1] +
			GET_PIXEL(+1, +1)*u_kernel[2]));
float dy = length((GET_PIXEL(-1, -1)*u_kernel[0] +
			GET_PIXEL(0, -1)*u_kernel[1] +
			GET_PIXEL(+1, -1)*u_kernel[2]) -
		   (GET_PIXEL(-1, +1)*u_kernel[0] +
			GET_PIXEL(0, +1)*u_kernel[1] +
			GET_PIXEL(+1, +1)*u_kernel[2]));

gl_FragColor = vec4(dx*dx, dy*dy, dx*dy, 1.0);

Feature points map

Next step is to compute Harris corner score at each image pixel.  Using accelerated GPU computation, FivekoGFX  performs local 3×3 average to get the sums of the derivatives products. The matrix determinant and trace calculates using point parameters from above step.

#define DET(_p)     ((_p).x*(_p).y - (_p).z*(_p).z)
#define TRACE(_p)   ((_p).x + (_p).y)

vec4 p = (GET_PIXEL(0, 0) + GET_PIXEL(-1, -1) + 
		GET_PIXEL(-1,  0) + GET_PIXEL(-1,  1) + 
		GET_PIXEL( 0,  1) + GET_PIXEL( 1,  1) + 
		GET_PIXEL( 1,  0) + GET_PIXEL( 1, -1) +
		GET_PIXEL( 0, -1)) / 9.0;
float k = 0.04;
float R = DET(p) - (k * (TRACE(p)*TRACE(p)));

Non-maximum suppression

Like Canny edge detector, this algorithm also implements a NMS (non-maximum suppression) filter. As a result, places that are less likely to be points of interest are set to zero. Feel free to visit FivekoGFX project on GitHub for the detailed source code.

Fiveko Graphics API

Using FivekoGFX library it is possible to extract Harris corners map with a simple API call. Below is an example code snippet for feature points map extraction.

var fivekogfx = new FivekoGFX();
// Load the initial image from e.g. a canvas source
// Perform Harris Corner Detector
// Extract peaks using non-maximum suppression with specific size
// Draw the result points map

Demo Application



Related Articles