**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.

## 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.

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.

## 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
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);
```