One of the most straightforward traditional features to find in an image are probably corners (locations where several edges meet). OpenCV provides at least two different algorithms to find corners in an image:

• Harris Dorner Detection: Knowing that edges are areas with high-intensity changes in all directions, Harris and Stephens came up with a fast way of finding such locations. This algorithm is implemented as cv2.cornerHarris in OpenCV.
• Shi-Tomasi Corner Detection: Shi and Tomasi have their own idea of what constitute good features to track, and they usually do better than Harris corner detection by finding the N strongest corners. This algorithm is implemented as cv2.goodFeaturesToTrack in OpenCV.

Harris corner detection works only on grayscale images, so we first want to convert our BGR image to grayscale:

In [6]: img_bgr = cv2.imread('data/rubic-cube.png')
In [7]: img_gray = cv2.cvtColor(img_bgr, cv2.COLOR_BGR2GRAY)

The algorithm then expects an input image, the pixel neighborhood size considered for corner detection (blockSize), an aperture parameter for the edge detection (ksize), and the so-called Harris detector-free parameter (k):

In [8]: corners = cv2.cornerHarris(img_gray, 2, 3, 0.04)

We can plot the resulting corner map using Matplotlib:

In [9]: plt.figure(figsize=(12,6))
...     plt.imshow(corners, cmap='gray')
Out[9]: <matplotlib.image.AxesImage at 0x1f3ea003b70>

This produces a grayscale image that looks like this:

Each pixel in the corner map has a value returned by the Harris Corner Detection technique. Let's only focus on the points that have a value of more than 10% of the maximum value. This can also be done using the cv2.threshold function. Can you figure out the difference between both the implementations? Take a look:

In [10]: corners_to_plot = np.where(corners>0.1*corners.max())

Now, we can plot these corner points using plt.plot, as shown here:

In [11]: plt.figure(figsize=(12,6))
...      plt.imshow(img_bgr);
...      plt.plot(corners_to_plot[1],corners_to_plot[0],'o',c='w',
markersize=4)

The following screenshot shows the image we obtain:

Even though the Harris Corner Detection technique is fast, the results are not highly accurate. This can be resolved by refining the detected corners with sub-pixel accuracy. OpenCV provides the cv2.cornerSubPix function for this.

We start by finding the corners using the Harris Corner Detection technique. We will call these Harris Corners:

1. We will first use the cv2.threshold function to change the pixel values for locations with values more than 10% of the maximum value in the corner map. We will convert the threshold image into an 8-bit unsigned integer. You will see why we are doing this in the next step:

In [12]: ret, corners = cv2.threshold(corners,
0.1*corners.max(),255,0)
In [13]: corners = np.uint8(corners)

2. In the next step, we want to compute the centroids of the corner points using the cv2.connectedComponentsWithStats function. This resolves the case when you have multiple corner points detected very close to each other. This can be because of some noise or inappropriate parameters, or there actually might be multiple corner points close by. In any case, we don't want to waste the computation power in calculating the more accurate corners for each of the closely detected corner points:

In [14]: ret, labels, stats, centroids = cv2.connectedComponentsWithStats(corners)

3. Next, we pass the centroids to the cv2.cornerSubPix function along with a stopping criterion. This stopping criterion defines the conditions about when to stop the iterations. As a simple case, we can stop the iterations when the maximum iteration count or the minimum accuracy required is achieved:

In [15]: criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 100, 0.001)
In [16]: corners = cv2.cornerSubPix(img_gray,np.float32(centroids),(5,5),(-1,-1),criteria)

4. We will then convert these new corners back into integer types:

In [17]: corners = np.int0(corners)
...      centroids = np.int0(centroids)

5. Finally, we can plot these new points and compare the change visually:

In [18]: corners_to_plot = [corners[:,0],corners[:,1]]
...      centroids_to_plot = [centroids[:,0],centroids[:,1]]
In [19]: plt.figure(figsize=(12,6))
...      plt.imshow(img_bgr);
...      plt.plot(corners_to_plot[0],corners_to_plot[1],
'o',c='w',markersize=8)
...      plt.plot(centroids_to_plot[0],centroids_to_plot[1],
'x',c='r',markersize=5)

And we get the following output:

It doesn't look like there is any significant change in the positions, but let's double-check this with the help of some calculations.

We will start by calculating the sum of absolute distance between the centroids and the new centers:

In [20]: np.absolute(centroids-corners).sum(axis=0)
Out[20]: array([41, 31])

This doesn't convey enough information. Let's see what these numbers mean for the image size:

In [21]: height, width, channels = img_bgr.shape
In [22]: np.absolute(centroids-corners).sum(axis=0)/(width,height) * 100
Out[22]: array([4.27974948, 3.23590814])

This means that, on an overall scale, there has been a 4.28% width change in the x direction and a 3.23% height change in the y direction.