Harris corner detection

In the realm of image processing and computer vision, corner detection plays a crucial role. It helps identify important points in images that have significant intensity changes in multiple directions. One popular and efficient method for corner detection is the Harris corner detection algorithm, developed by Chris Harris and Mike Stephens in 1988. This algorithm is widely recognized for its effectiveness and reliability.

In this Answer, we will explore the inner workings of the Harris Corner Detection algorithm and explain its mathematical foundations and implement it using the OpenCV library.

Fundamental concepts: Intensity and gradient

Understanding the Harris Corner Detection algorithm requires familiarity with the fundamental concepts of intensity and gradient in an image:

1. Intensity: Intensity represents the brightness or color information at a specific point in the image. It is mathematically denoted as $I(x, y)$.

2. Gradient: The gradient represents the direction of maximum intensity change at a given point. It is a two-dimensional vector whose components are partial derivatives of the intensity along the $x$ and $y$ directions, denoted as:

Formulation

At its core, the Harris algorithm determines the variation in intensity for a displacement $(u,v)$ across all directions. This is encapsulated by the function $E(u,v)$ as follows:

Here, $w(x, y)$ is the window function that applies weights to the underlying pixels. It could be a rectangular window or, more typically, a Gaussian window, which offers smoother weighting.

In the Harris algorithm, corners are detected by maximizing the function $E(u,v)$. This is achieved by applying Taylor expansion to the equation and performing several mathematical transformations. The resulting equation is:

Where the matrix $M$ is defined as:

The derivatives $I_x$ and $I_y$ represent the changes in intensity along the $x$ and $y$ directions. These are calculated using methods such as Sobel operator.

Corner scoring

The Harris algorithm introduces a corner score, or a specific mathematical criterion, to decide whether a region contains a corner. This corner score $R$ is given by:

The determinant of the matrix $M$, $det(M)$, is the product of its eigenvalues, i.e., $det(M) = \lambda_1\lambda_2$, while the trace of $M$, trace$(M)$, is the sum of its eigenvalues, i.e., $trace(M) = \lambda_1 + \lambda_2$.

The relative magnitudes of the eigenvalues $\lambda_1$ and $\lambda_2$ guide the classification of each region as a corner, edge, or flat region:

1. Flat region: If $|R|$ is small, which occurs when both $\lambda_1$ and $\lambda_2$ are small, the region is considered flat.

2. Edge: If $R < 0$, implying that one eigenvalue is significantly larger than the other, the region is identified as an edge.

3. Corner: If $R$ is large, indicating that both $\lambda_1$ and $\lambda_2$ are large and approximately equal, the region is classified as a corner.

This is illustrated below:

cv2.cornerHarris()

The cv2.cornerHarris() function is the Harris Corner Detector provided by the OpenCV library.

It has the following parameters:

• src: The source image. The image must be grayscale and its type should be float32.

• blockSize: The size of the neighborhood considered for corner detection.

• ksize: The aperture parameter of the Sobel derivative used. This is the size of the Sobel kernel used to get derivates of the image.

• k: The Harris detector free parameter in the equation $R = det(M) - k(trace(M))^2$. The empirical value of k is usually in the range of 0.04 - 0.06.

The function returns the corner map (an image with corner intensities). Corners in the returned image are marked with large positive values.

Algorithm

Here is a step-by-step algorithm for the Harris Corner Detection to implement it using the OpenCV library.

1. Load the input image.

2. Convert the image to grayscale as corner detection relies on intensity values.

3. Normalize pixel values to a range of 0 to 255.

4. Apply the cv2.cornerHarris() function to detect corners.

5. Dilate corner markers for better visualization.

6. Superimpose detected corners on the original image.

Implementation

Here's how we can implement the Harris Corner Detection algorithm in Python using OpenCV:

Code explanation

Here’s a line-by-line explanation of the given Python script:

• Lines 1–2: Import the necessary libraries. cv2 is the OpenCV library used for image processing, and numpy is used for numerical operations.

• Line 6: Read the image using the cv2.imread() function. Replace ‘input.jpg’ with the path to the image you want to process.

• Line 9: Convert the color image to grayscale using the cv2.cvtColor() function. The Harris corner detection method works with grayscale images.

• Line 12: Convert the grayscale image to a float32 data type. This is a requirement for the cv2.cornerHarris() function used later.

• Line 15: Apply the cv2.cornerHarris() function to the grayscale image to detect corners. The arguments include the image, the size of the neighborhood considered for corner detection (2 in this case), the Sobel aperture parameter (3 here), and the Harris detector free parameter (0.04 here).

• Line 18: Apply the cv2.dilate() function to the corners detected by the Harris detector. This step is used to enhance the corner points.

• Line 21: Define a threshold for the corners. Only corners with a Harris response greater than the threshold are considered. The threshold is defined as 1% of the maximum response.

• Lines 24–28: Iterate through all the pixels in the harris_corners matrix. If the response at a pixel location is greater than the threshold, draw a circle at that location in the original image. The cv2.circle() function takes the image, the center of the circle, the radius of the circle, the color of the circle (red in this case), and the thickness (which is -1 to fill the circle) as arguments.

• Lines 31–33: Display the image with the detected corners using cv2.imshow(). Wait for a key press using cv2.waitKey(0). Then, close all windows with cv2.destroyAllWindows().

Conclusion

The Harris corner detection algorithm is an invaluable tool in computer vision, allowing efficient detection and marking of corners within images. Through a combination of Python and OpenCV, we can implement this powerful algorithm to perform tasks ranging from image recognition to 3D reconstruction, opening doors to a broad spectrum of applications.

Test your knowledge