How to implement Harris Corner Detector with Python

This tutorial pretends to let you know what the Harris Corner Detector is and how you can implement it using python. Two implementations are presented to you, one following each step of the harris corner detector and another using OpenCV.

What is it and how does it work?

Finding reliable and meaningful features in images is very important for data interpretation. Edges and Corners present in images are features that have a lot of information and if correctly found they can be very helpful in a lot of computer vision tasks.

Moravec [2] stated that if a window made small sifts over an image in various directions the average changes of the image intensity would be:

• small in all directions if the patch is of constant intensity (flat region);
• large in all directions if the patch contains a corner;
• small and large if the patch move, respectively, along with or perpendicular to an edge.

With this in mind, Harris, and Stephens developed the Harris Corner Detector [1], a mathematical approach to detect corners and edges in images. They picked the statements of Moravec and gave it a mathematical signification, Equation 1.

After apply Taylor expansion it is possible to obatin the following aproximation of Equation2.

where:

The Ix and Iy present in Equation 2 are the x and y image derivatives. To conclude, the response of the corner detector is obtained with Equation 3. Depending on the value obtained by this response, is possible to determine if a region contains a flat region, an edge, or a corner.

Harris and Stephens present the chart of Figure 1 in order to classify the values obtained with the response function. Negative R values indicate edge detection. Large and positive R values indicate corner detection. Finally, small values (closer to zero) indicate the detection of a flat region.

How to implement it?

In order to implement your own Harris corner detector, you can follow the following 6 steps:

1. Calculate image x and y derivatives. For this you can apply the Sobel() function of Open-CV;
2. Derivate again the previous values to obtain the second derivative;
3. For each pixel, sum the last step obtained derivatives. Here we are making a 1 pixel sift of the windows over the image;
4. For each pixel and using the sums of the previous step, define H matrix;
5. Calculate the response of the detector;
6. Use a threshold value in order to exclude some of the detections.

Code

Bellow has presented two Harris Corner Detectors implemented in python. The first code section is a manual implementation. The second is the detector implemented with recourse of OpenCV [3]. In the manual implementation, the response results were normalized and only vary between 0 and 1, this way the threshold value should also be a value between 0 and 1.

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


def my_harris(img_dir,window_size,k,threshold):

    img = cv2.imread(img_dir)
    gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

    img_gaussian = cv2.GaussianBlur(gray,(3,3),0)

    # Check if the image is exists
    if img is None:
        print('Invalid image:' + img_dir)
        return None
    else:
        print('Image successfully read...')
        
    height = img.shape[0]   #.shape[0] outputs height 
    width = img.shape[1]    #.shape[1] outputs width .shape[2] outputs color channels of image
    matrix_R = np.zeros((height,width))
    
    #   Step 1 - Calculate the x e y image derivatives (dx e dy)
    dx = cv2.Sobel(img_gaussian, cv2.CV_64F, 1, 0, ksize=3)
    dy = cv2.Sobel(img_gaussian, cv2.CV_64F, 0, 1, ksize=3)
    # dy, dx = np.gradient(gray)

    #   Step 2 - Calculate product and second derivatives (dx2, dy2 e dxy)
    dx2=np.square(dx)
    dy2=np.square(dy)
    dxy=dx*dy

    offset = int( window_size / 2 )
    #   Step 3 - Calcular a soma dos produtos das derivadas para cada pixel (Sx2, Sy2 e Sxy)
    print ("Finding Corners...")
    for y in range(offset, height-offset):
        for x in range(offset, width-offset):
            Sx2 = np.sum(dx2[y-offset:y+1+offset, x-offset:x+1+offset])
            Sy2 = np.sum(dy2[y-offset:y+1+offset, x-offset:x+1+offset])
            Sxy = np.sum(dxy[y-offset:y+1+offset, x-offset:x+1+offset])

            #   Step 4 - Define the matrix H(x,y)=[[Sx2,Sxy],[Sxy,Sy2]]
            H = np.array([[Sx2,Sxy],[Sxy,Sy2]])

            #   Step 5 - Calculate the response function ( R=det(H)-k(Trace(H))^2 )
            det=np.linalg.det(H)
            tr=np.matrix.trace(H)
            R=det-k*(tr**2)
            matrix_R[y-offset, x-offset]=R
    
    #   Step 6 - Apply a threshold
    cv2.normalize(matrix_R, matrix_R, 0, 1, cv2.NORM_MINMAX)
    for y in range(offset, height-offset):
        for x in range(offset, width-offset):
            value=matrix_R[y, x]
            if value>threshold:
                # cornerList.append([x, y, value])
                cv2.circle(img,(x,y),3,(0,255,0))
                
    # cv2.imwrite("%s_threshold_%s.png"%(img_dir[5:-4],threshold), img)
    plt.figure("Manually implemented Harris detector")
    plt.imshow(cv2.cvtColor(img, cv2.COLOR_BGR2RGB)), plt.title("Manually implemented Harris detector")
    plt.xticks([]), plt.yticks([])
    plt.savefig('My_harris_detector-thresh_%s.png'%(threshold), bbox_inches='tight')
    plt.show()

my_harris("D:/geekering/harris.jpg", 5, 0.04, 0.30) # Change this path to one that will lead to your image

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

def harris(img_dir):
    img = cv2.imread(img_dir)
    gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)  # Turn image to gray

    harris = cv2.cornerHarris(gray,2,3,0.04)  # Applies harris corner detector to gray image

    # Result is dilated for marking the corners, not important
    harris = cv2.dilate(harris,None)

    # Threshold for an optimal value, it may vary depending on the image.
    img[harris>0.01*harris.max()]=[0,0,255]

    plt.figure("Harris detector")
    plt.imshow(cv2.cvtColor(img, cv2.COLOR_BGR2RGB)), plt.title("Harris")
    plt.xticks([]), plt.yticks([])
    plt.savefig('Harris_detector', bbox_inches='tight')
    plt.show()

harris("D:/geekering/harris.jpg")  # Change this path to one that will lead to your image

Results

Here are presented two result comparisons between the OpenCV and a manually implemented Harris Corner detector. The first comparison between artificial images, the logo of geekering (Figure 2 and 3) can archive the detection of the majority of the corners, which can be adjusted by changing the threshold value. The second comparison demonstrates that this implementation also can obtain good performance in natural images (Figure 4 and 5).

As you can see a similar result between manual and OpenCV implementations was obtained, only differing due to different used parameters like threshold and initial used Gaussian kernel size.

References

[1] C. Harris and M. Stephens, “A combined corner and edge detector,” in Proceedings of the Alvey Vision Conference 1988, 1988.

[2] Moravec, H, Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover, Tech Report CMU-RI-TR-3, Carnegie-Mellon University, Robotics Institute, September 1980.

[3] “Harris Corner Detection,” OpenCV. [Online]. Available: https://docs.opencv.org/master/dc/d0d/tutorial_py_features_harris.html. [Accessed: 23-Jun-2021].