OpenCV & Python – Harris Corner Detection – a method to detect corners in an image

Introduction

As promised, here is another article in a series of articles about the world of OpenCV and Python development. In a previous article you have already seen the concept of edge detection, this article will show you a particular algorithm called Harris Corner Detection.

If you see more, this is the previous post:

Other edge detection algorithms:

The Harris Corner Detection algorithm

This particular algorithm was developed to identify the inside corner of an image. The corners are regions within an image in which there are large variations in intensity of the gradient in all directions.

One such attempt was made in 1988 by Chris Harris & Mike Stephens, who developed an algorithm able to perform both edge detection that corner detection. So the name of this algorithm is derived from the author’s name and the corner detection

The two authors calculated the difference of intensity through a mathematical formula, E (u, v).

E(u,v) = \sum _{x,y} w(x,y)[ I(x+u,y+v) - I(x,y)]^{2}

The window function w (x, y) may be a Gaussian function or a rectangular function. This function E (u, v), however, must be maximized for the corner detection. then applying the Taylor expansion of the equation and after some approximations you get to the expression:

E(u,v) \approx \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix}

where

M = \displaystyle \sum_{x,y} w(x,y) \begin{bmatrix} I_x^{2} & I_{x}I_{y} \\ I_xI_{y} & I_{y}^{2} \end{bmatrix}

Ix and Iy are the derivatives of the image in the x and y. They can be easily calculated by using the OpenCV cv2.Sobel() function.

Now comes the main part of the algorithm. In fact the algorithm calculates a score based on an equation that determines whether a window can contain a corner or not.

R = det(M) - k(trace(M))^{2}

where

  • det(M)=λ1λ2
  • trace(M)=λ1+λ2
  • λ1 and λ2 are the eigenvalues of M

The values assumed by the eigenvalues determine whether a region is a corner, an edge or flat (with nothing).

  • Flat:  when|R| is small, that is when λ1 and λ2 are small.
  • Edge: when R<0, that is when λ1>>λ2 or λ2>>λ1.
  • Corner: when R is large, that is when λ1 and λ2 are large and with similar values λ1∼λ2.

The concept described above can be represented in the eigenvalues plan.

At the end of the algorithm the result is an image in grayscale, in which the shades of gray are equivalent precisely to the score.

Before you start programming

First to run the code in this article, certain requirements must be met.

Activate the virtual environment in which you have compiled and installed the OpenCV library.

source ~/.profile
workon cv
(cv) $

If you have not yet installed OpenCV, follow the installation procedure described in this article.

In addition, to improve the display of multiple images at once, you will use the matplotlib library. If you have not yet installed on your virtual environment, you can do this by typing

pip --no-cache-dir install matplotlib

Then install the Tkinter package required for the proper functioning of matplotlib.

sudo apt-get install python-tk

At first you’ll run some tests on a simple image with which to test the effectiveness of the algorithm. For example, the following image:

Download it and save it as blackandwhite.jpg.

Programming a Harris Corner Detection with Python

In OpenCV, this kind of edge detection has already been implemented and is activated by calling the  cv2.cornerHarris() function.

cv2.cornerHarris(image, blockSize, ksize, k)

This function takes four arguments.

  • img – image to be analyzed, must be in grayscale and with float32 values.
  • blockSize – size of the windows considered for the corner detection
  • ksize – parameter for the derivative of Sobel
  • k – free parameter for the Harris equation.

Write the following code and try it on the image of the test with the two white arrows on a black background. The values passed as arguments are optimum values for good performance in most cases.

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

img = cv2.imread('blackandwhite.jpg',0)
img = np.float32(img)
corners = cv2.cornerHarris(img,2,3,0.04)

corners = cv2.cornerHarris(img,2,3,0.04)

plt.subplot(2,1,1), plt.imshow(corners ,cmap = 'jet')
plt.title('Harris Corner Detection'), plt.xticks([]), plt.yticks([])

img2 = cv2.imread('blackandwhite.jpg')
corners2 = cv2.dilate(corners, None, iterations=3)
img2[corners2>0.01*corners2.max()] = [255,0,0]

plt.subplot(2,1,2),plt.imshow(img2,cmap = 'gray')
plt.title('Canny Edge Detection'), plt.xticks([]), plt.yticks([])

plt.show()

If you run the code you’ll get the following results.

As you can see the Harris Corner Detection algorithm is able to show up for well both the edges of the two arrows (edge detection) both their vertices (corner detection).

Other tests on images

Now you can begin to carry out the analysis on a rich picture of details and contours. In this regard, I chose a leaf.

And here are the results. Not bad…

Conclusions

In this article you saw in the field of edge detection, the Harris Corner Detection algorithm that is able to detect the corner within a picture. Thanks to the OpenCV library, all this analysis can be invoked through the use of a single cv2.cornerHarris() function, making the work much easier to carry out analysis of images at a higher level with Python.

[:]

Leave a Reply