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.
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.
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):
The Harris corner score is used to determine if the current position contains a corner or not:
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 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 result image map
Finally, the algorithm creates a gray-scale map image where the bright areas are the corners.
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 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);