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.
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.
A movable image patch at position (x, y) shifts with defined offset (dx,dy):
The Harris corner score is used to determine if the current position contains a corner or not:
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 + GET_PIXEL(-1, 0)*u_kernel + GET_PIXEL(-1, +1)*u_kernel) - (GET_PIXEL(+1, -1)*u_kernel + GET_PIXEL(+1, 0)*u_kernel + GET_PIXEL(+1, +1)*u_kernel)); float dy = length((GET_PIXEL(-1, -1)*u_kernel + GET_PIXEL(0, -1)*u_kernel + GET_PIXEL(+1, -1)*u_kernel) - (GET_PIXEL(-1, +1)*u_kernel + GET_PIXEL(0, +1)*u_kernel + GET_PIXEL(+1, +1)*u_kernel)); 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)));
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);