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 and recognition. A classical interest points detector is the one developed by Harris as this operator is robust and accurate 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


Applications

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 InfoHarris 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
  • Harris measure computation
  • Non-maximum suppression
  • Feature points thresholding

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

$\displaystyle{M}=\sum_{{{x},{y}}}{W}{\left({x},{y}\right)}{\left[\begin{matrix}{I}{x}^{2}&{I}{x}{I}{y}\\{I}{x}{I}{y}&{I}{y}^{2}\end{matrix}\right]}$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

Where:

Matrix determinant calculation

In linear algebra the det(M) stands for a square matrix determinant. Calculation of the determinant of the 2×2 matrix is performed as follows:

Matrix determinant Matrix determinant

Matrix trace calculation

In linear algebra the trace(M) of a square matrix is the total sum of the main diagonal. For Harris matrix, the trace calculates as follows:

Harris matrix trace Harris matrix trace

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

Harris corners resultHarris corners resulting image


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 non-maximum suppression 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
fivekogfx.load(canvas);
// Perform Harris Corner Detector
fivekogfx.harrisCorners();
// Extract peaks using non-maximum suppression with specific size
fivekogfx.nms(size);
// Draw the result points map
fivekogfx.draw(canvas);

 


Demo Application

Elapsed:

Visit FivekoGFX on GitHub for more image processing examples and detailed source code!


References




Related Articles