In the previous blog, we discussed the Harris Corner Detector and saw how this uses a score function to evaluate whether a point is a corner or not. But this algorithm doesn’t always yield satisfactory results. So, in 1994, J. Shi and C. Tomasi in their paper Good Features to Track made a small modification to it which shows better results compared to Harris Corner Detector. So, let’s understand how they improved the algorithm.
As you might remember, the scoring function used by Harris Corner Detector is
Instead of this, Shi-Tomasi proposed a new scoring function
So, for a pixel, if this score R is greater than a certain threshold then that pixel is considered as a corner. Similar to Harris Corner Detector if we plot this in λ1−λ2 space, then we will get the below plot
So, as we can see that
- only when λ1 and λ2 are above a minimum value, λmin, it is considered as a corner(green region)
- when either λ1 or λ2 are below a minimum value, λmin, it is considered as a edge(orange region)
- when both λ1 and λ2 are below a minimum value, λmin, it is considered as a flat region(grey region)
So, this is the improvement that Shi-Tomasi did to the Harris Corner Detector. Other than this, the entire algorithm is the same. Now, let’s see how to implement this using OpenCV-Python.
OpenCV
OpenCV provides a built-in function cv2.goodFeaturesToTrack() that finds N strongest corners in the image by either Shi-Tomasi or Harris Corner Detector. Below is the algorithm that this function uses
- First, this function calculates the corner quality score at every pixel using either Shi-Tomasi or Harris Corner
- Then this function performs a non-maximum suppression (the local maximums in 3 x 3 neighborhood are retained).
- After this, all the corners with the quality score less than qualityLevel*maxx,yqualityScore(x,y) are rejected. This maxx,yqualityScore(x,y) is the best corner score. For instance, if the best corner has the quality score = 1500, and the qualityLevel=0.01 , then all the corners with the quality score less than 15 are rejected.
- Now, all the remaining corners are sorted by the quality score in the descending order.
- Function throws away each corner for which there is a stronger corner at a distance less than maxDistance.
Here is the syntax of this function
1 2 3 4 5 6 7 8 9 10 11 |
cv2.goodFeaturesToTrack(image, maxCorners, qualityLevel, minDistance, [,mask[,blockSize[,useHarrisDetector[,k]]]]) # image - Input 8-bit or floating-point 32-bit, single-channel image # maxCorners - Maximum number of corners to return. If there are more corners than are found, the strongest of them is returned. if <= 0 implies that no limit on the maximum is set and all detected corners are returned # qualityLevel - Parameter characterizing the minimal accepted quality of image corners. See the above paragraph for explanation # minDistance - Minimum possible Euclidean distance between the returned corners # mask - Optional region of interest. If the image is not empty it specifies the region in which the corners are detected # blockSize - Size of an average block for computing a derivative covariation matrix over each pixel neighborhood # useHarrisDetector - whether to use Shi-Tomasi or Harris Corner # k - Free parameter of the Harris detector |
Now, let’s take the image we used in the previous blog and detect the top 20 corners. Below is the code for this
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
import numpy as np import cv2 # Read the image and convert to greyscale img = cv2.imread('D:/downloads/contracing.png') gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY) # Find the top 20 corners using the cv2.goodFeaturesToTrack() corners = cv2.goodFeaturesToTrack(gray,20,0.01,10) corners = np.int0(corners) # Iterate over the corners and draw a circle at that location for i in corners: x,y = i.ravel() cv2.circle(img,(x,y),5,(0,0,255),-1) # Display the image cv2.imshow('a', img) cv2.waitKey(0) |
Below is the result of this
You can also use the Harris Corner Detector method by specifying the flag useHarrisDetector and the k parameter in the above function as shown
1 |
corners = cv2.goodFeaturesToTrack(gray,20,0.01,10, useHarrisDetector=True, k=0.04) |
So, that’s all about Shi-Tomasi Detector.
Limitations
Both Shi-Tomasi and Harris Corner work well for most of the cases but when the scale of the image changes both of these algorithms doesn’t give satisfactory results. So, in the next blog, we will discuss one of the famous algorithms for finding scale-invariant features known as SIFT (Scale-Invariant Feature Transform). This algorithm was a breakthrough in this field. See you in the next blog. Hope you enjoy reading.
If you have any doubts/suggestions please feel free to ask and I will do my best to help or improve myself. Goodbye until next time.