Feature Detection, Part 3: Harris Corner Detection

Feature detection is a website of computer vision that focuses on using tools to detect regions of interest in images. A big aspect of most feature detection algorithms is that they don’t employ machine learning under the hood, making the outcomes more interpretable and even faster in some cases.

Within the previous two articles of this series, we checked out the preferred operators for detecting image edges: Sobel, Scharr, Laplacian, together with the Gaussian used for image smoothing. In some form or one other, these operators used under-the-hood image derivatives and gradients, represented by convolutional kernels.

As with edges, in image evaluation, one other kind of local region is usually explored: corners. Corners appear more rarely than edges and frequently indicate a change of border direction of an object or the tip of 1 object and the start of one other one. Corners are rarer to search out, they usually provide more beneficial information.

Example

Imagine you’re collecting a 2D puzzle. What most individuals do at first is locate a bit with a picture part containing the border (edge) of an object. Why? Because this manner, it is simpler to discover adjoining pieces, because the variety of pieces sharing the same object edge is minimal.

We are able to go even further and deal with picking not edges but corners — a region where an object changes its edge direction. These pieces are even rarer than simply edges and permit for an excellent easier seek for other adjoining fragments due to their unique form.

For instance, within the puzzle below, there are 6 edges (, and ) and only one corner (). By picking the corner from the beginning, it becomes easier to localize its position since it is rarer than edges.

The goal of this text is to know how corners will be detected. To do this, we are going to understand the main points of the Harris corner detection algorithm – certainly one of the only and popular methods developed in 1988.

Idea

Allow us to take three forms of regions: flat, edge, and corner. Now we have already shown the structure of those regions above. Our objective will likely be to know the distribution of gradients across these three cases.

During our evaluation, we may also construct an ellipse that incorporates the vast majority of the plotted points. As we are going to see, its form will provide strong indications of the kind of region we’re coping with.

Flat region

A flat region is the only case. Often, all the image region has nearly the identical intensity values, making the gradient values across the X and Y axes minor and centered around 0.

By taking the gradient points (Gₓ, Gᵧ) from the flat image example above, we will plot their distribution, which looks like below:

We are able to now construct an ellipse across the plotted points having a middle at (0, 0). Then we will discover its two principal axes:

• The major axis along which the ellipse is maximally stretched.
• The minor axis along which the ellipse attains its minimum extent.

Within the case of the flat region, it could be difficult to visually differentiate between the key and minor axes, because the ellipse tends to have a circular shape, as in our situation.

Nevertheless, for every of the 2 principal axes, we will then calculate the ellipse radiuses λ₁ and λ₂. As shown in the image above, they’re almost equal and have small relative values.

Edge region

For the sting region, the intensity changes only in the sting zone. Outside of the sting, the intensity stays nearly the identical. Provided that, a lot of the gradient points are still centered around (0, 0).

Nonetheless, for a small part across the edge zone, gradient values can drastically change in each directions. From the image example above, the sting is diagonal, and we will see changes in each directions. Thus, the gradient distribution is skewed within the diagonal direction as shown below:

For edge regions, the plotted ellipse is often skewed towards one direction and has very different radiuses λ₁ and λ₂.

Corner region

For corners, a lot of the intensity values outside the corners stay the identical; thus, the distribution for the vast majority of the points continues to be situated near the middle (0, 0).

If we have a look at the corner structure, we will roughly consider it as an intersection of two edges having two different directions. For edges, we now have already discussed within the previous section that the distribution goes in the identical direction either in X or Y, or each directions.

By having two edges for the corner, we find yourself with two different point spectrums growing in two different directions from the middle. An example is shown below.

Finally, if we construct an ellipse around that distribution, we are going to notice that it’s larger than within the flat and edge cases. We are able to differentiate this result by measuring λ₁ and λ₂, which on this scenario will take much larger values.

Visualization

Now we have just seen three scenarios wherein λ took different values. To raised visualize results, we will construct a diagram below:

Formula

To find a way to categorise a region into certainly one of three zones, a formula below is usually used to estimate the R coefficient:

R = λ₁ ⋅ λ₂ – k ⋅ (λ₁ + λ₂)² , where 0.04 ≤ k ≤ 0.06

Based on the R value, we will classify the image region:

• R < 0 – edge region
• R ~ 0 – flat region
• R > 0 – corner region

OpenCV

Harris Corner detection will be easily implemented in OpenCV using the cv2.CornerHarris function. Let’s see in the instance below how it will possibly be done.

Here is the input image with which we will likely be working:

First, allow us to import the needed libraries.

import numpy as np
import cv2
import matplotlib.pyplot as plt

We’re going to convert the input image to grayscale format, because the Harris detector works with pixel intensities. Additionally it is needed to convert the image format to float32, as computed values related to pixels can exceed the bounds [0, 255].

path = 'data/input/shapes.png'
image = cv2.imread(path)
grayscale_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
grayscale_image = np.float32(grayscale_image)

Now we will apply the Harris filter. The function takes 4 parameters:

• – input grayscale image within the float32 format.
• – defines the size of the pixel block within the neighborhood of the goal pixel considered for corner detection.
• – the dimension of the Sobel filter used to calculate derivatives.
• – coefficient within the formula used to compute the worth of R.

R = cv2.cornerHarris(grayscale_image, 2, 3, 0.04)
R = cv2.dilate(R, None)

The cv2.cornerHarris function returns a matrix of the precise dimensions as the unique grayscale image. Its values will be well outside the traditional range [0, 255]. For each pixel, that matrix incorporates the R coefficient value we checked out above.

The cv2.dilate is a morphological operator that may optionally be used immediately after to raised visually group the local corners.

A standard technique is to define a threshold below which pixels are considered corners. As an example, we will consider all image pixels as corners whose R value is larger than the maximal global R value divided by 100. In our example, we assign such pixels to red color (0, 0, 255).

To visualise a picture, we’d like to convert it to RGB format.

image[R > 0.01 * R.max()] = [0, 0, 255]
image_rgb = cv2.cvtColor(image, cv2.COLOR_BGR2RGB)

Finally, we use maplotlib to display the output image.

plt.figure(figsize=(10, 8))
plt.imshow(image_rgb)
plt.title('Harris Corner Detection')
plt.axis('off')
plt.tight_layout()
plt.show()

Here is the result:

Conclusion

In this text, we now have examined a strong method for determining whether a picture region is a corner. The presented formula for estimating the R coefficient works well within the overwhelming majority of cases. 

In real life, there may be a standard must run an edge classifier for a whole image. Constructing an ellipse across the gradient points and estimating the R coefficient every time is resource-intensive, so more advanced optimization techniques are used to hurry up the method. Nevertheless, they’re based lots on the intuition we studied here.

Resources