1.4 Corner Detectors

1. CornerHarris Corner Detection

The CornerHarris algorithm is a popular method used in computer vision for detecting corners in an image. Corners are points in the image where the intensity changes significantly in all directions. This algorithm is often used in image processing for feature detection, which is essential in tasks such as object recognition, image matching, and tracking.

The CornerHarris algorithm works by computing the gradients of the image, forming a matrix that captures changes in intensity, and then calculating a response function that identifies corners based on these changes. It is effective in detecting corners that are invariant to rotations and scale changes, making it a robust tool in feature detection for various image processing tasks.

1.1 How It Works:

1. Gradient Computation

• First, the algorithm computes the gradient of the image in the and directions. This can be done using Sobel filters or any other method to find the derivatives and of the image.

2. Structure Tensor (Auto-correlation Matrix)

• The algorithm then computes the structure tensor, also known as the second-moment matrix, at each pixel. This matrix is defined as:

  where:

  • is the squared gradient in the direction.
  • is the squared gradient in the direction.
  • is the product of the gradients in the and directions.

• The elements of this matrix are then smoothed (often with a Gaussian filter) to reduce noise.

3. Corner Response Calculation

• The CornerHarris algorithm then computes the corner response function at each pixel using the structure tensor . The response function is given by:

  where:

  • is the determinant of the matrix .
  • is the trace of the matrix .
  • is a sensitivity parameter (typically a small constant, around 0.04 to 0.06).

• is a scalar value that indicates the likelihood of a pixel being a corner:

  • If is large and positive, it indicates a corner.
  • If is negative, it indicates an edge.
  • If is close to zero, it indicates a flat region.

Purpose of Calculating the Determinant and Trace:

The determinant of captures the “intensity variation” around a pixel in two perpendicular directions. Here’s why it is important:

• Measuring the Response to Corners:

  • The determinant reflects how much the image intensity varies in the local neighborhood of a pixel. A large determinant indicates a strong variation in both directions, which is characteristic of a corner.
  • Specifically:
    • Corners: If is large and positive, it indicates that the pixel has significant intensity variations in all directions, characteristic of a corner.
    • Edges: If the intensity varies significantly in one direction but not in the perpendicular direction, the determinant will be small or close to zero, indicating an edge rather than a corner.
    • Flat Regions: If there is little or no variation in any direction, the determinant will be close to zero, indicating a flat region.

• Corner Response Function :

  • The determinant of is used in the corner response function , which is calculated as:

    where:

    • is the trace of matrix and represents the sum of the eigenvalues of .
    • is a constant (typically around 0.04 to 0.06) that controls the sensitivity of the detector.

  • The purpose of this response function is to combine the determinant (which measures variation) with the trace (which provides a measure of the average intensity change). The combination helps to distinguish corners from edges and flat regions.

4. Thresholding and Non-Maximum Suppression

• The algorithm then applies a threshold to the values to detect strong corners.
• Non-maximum suppression is performed to ensure that only the most prominent corners are retained. This involves comparing each corner’s value to its neighbors and keeping only local maxima.

1.2 Usage:

You can use the CornerHarris algorithm in OpenCV using the cv2.cornerHarris function. Below is a step-by-step guide and example of how to use this function in Python with OpenCV.

1. Load an Image:

Load the image on which you want to detect corners. Grayscale images are preferred for corner detection.

import cv2
import numpy as np

img = cv2.imread('path_to_your_image.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

2. Convert Image to Float32:

The cornerHarris function requires the input image to be in the float32 format.

gray = np.float32(gray)

3. Apply the CornerHarris Function:

Use cv2.cornerHarris to detect corners. You can adjust the parameters to fit your needs.

dst = cv2.cornerHarris(gray, blockSize=2, ksize=3, k=0.04)

• gray: The input image in float32 format.

• blockSize: The size of the neighborhood considered for corner detection. A larger blockSize makes the algorithm consider more surrounding pixels, which can help detect larger features but may miss smaller details.

• ksize: Aperture parameter for the Sobel operator (used for gradient computation). This affects the computation of image gradients. A larger ksize will make the gradients more smooth.

• k: Harris detector free parameter, typically between 0.04 and 0.06. A sensitivity parameter that adjusts the detection threshold. Lower values tend to be more sensitive to edges, while higher values make the detection stricter.

4. Dilate the Result (Optional):

Dilate the corner image to enhance the corners (this is often done for better visualization).

dst = cv2.dilate(dst, None)

7. Threshold and Mark the Corners:

Threshold the image to highlight the corners. For visualization, you can mark these corners on the original image.

img[dst > 0.01 * dst.max()] = [0, 0, 255]

Here, the corners are marked in red on the original image.

8. Display the Image with Detected Corners:

Finally, show the image with detected corners using OpenCV’s imshow function.

cv2.imshow('Corners Detected', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

9. Full Example Code:

import cv2
import numpy as np

# Load the image and convert it to grayscale
img = cv2.imread('path_to_your_image.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# Convert to float32 format
gray = np.float32(gray)

# Detect corners using the Harris Corner Detection method
dst = cv2.cornerHarris(gray, blockSize=2, ksize=3, k=0.04)

# Dilate the detected corners for better visibility
dst = cv2.dilate(dst, None)

# Threshold to mark the corners on the original image
img[dst > 0.01 * dst.max()] = [0, 0, 255]

# Display the image with corners
cv2.imshow('Corners Detected', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

10. Additional Tips:

• Experiment with the blockSize, ksize, and k parameters to fine-tune the corner detection for your specific image.
• Consider using cv2.cornerSubPix to refine the corner locations for sub-pixel accuracy if needed.

2. Shi-Tomasi Corner Detection

The Shi-Tomasi corner detection algorithm is an improvement over the Harris Corner Detection method. It is also known as the “Good Features to Track” algorithm. Shi-Tomasi refines the Harris method by providing a more reliable way to detect corners, especially in scenarios involving image tracking and matching.

2.1 How It Works:

1. Structure Tensor (Matrix ):

• Similar to the Harris algorithm, the Shi-Tomasi method begins by computing the structure tensor (also called the second-moment matrix) at each pixel: where and are the image gradients in the and directions, respectively.

2. Eigenvalue Calculation:

• The key difference between Harris and Shi-Tomasi lies in how corners are detected from the matrix .
• For each pixel, the algorithm computes the eigenvalues and of the matrix . These eigenvalues represent the intensity changes in two perpendicular directions.

Understanding Eigenvalues in Image Gradients:

Eigenvalues and :

• The eigenvalues and of the matrix represent the amount of variation (or change in intensity) in the image along two orthogonal directions.

• These directions are determined by the eigenvectors corresponding to the eigenvalues.

Largest Eigenvalue:

• The largest eigenvalue (assuming ) represents the direction in which the image intensity changes the most. This direction is not necessarily aligned with the or axes; it could be any orientation depending on the local image structure.

• A large indicates significant variation in intensity along this principal direction, which could be a combination of changes in both and .

Smallest Eigenvalue:

• The smallest eigenvalue represents the intensity variation in the direction orthogonal to the direction of .

• If is also large, it indicates significant variation in the perpendicular direction as well, which is characteristic of a corner.

{:.block-tip}

IMPORTANT

In corner detection:

• A corner is identified when both and are large, meaning there is significant variation in all directions around that pixel.
• An edge is characterized by a large and a small , meaning the intensity varies strongly in one direction but not much in the perpendicular direction.
• A flat region has both and small, indicating little to no variation in any direction.

3. Corner Response Criterion:

• Instead of using a response function like Harris, the Shi-Tomasi algorithm directly uses the smallest eigenvalue as the corner response:
• A large indicates that both eigenvalues are large, suggesting significant intensity changes in both directions, which is characteristic of a corner.
• If is small or close to zero, it indicates an edge or a flat region.

4. Corner Selection:

• Corners are selected as the pixels with the highest values, subject to a threshold. The threshold is typically chosen to select the strongest corners.
• Non-maximum suppression is applied to ensure that only the most prominent corners are retained.

2.2 Advantages of Shi-Tomasi Over Harris

• Shi-Tomasi is more stable in detecting corners because it avoids the need to combine eigenvalues into a single response function.
• It directly considers the smallest eigenvalue, which better represents the quality of a corner, especially when one direction has a much larger intensity change than the other.

2.3 Usage

Here’s how you can use the Shi-Tomasi algorithm in Python with OpenCV:

import cv2
import numpy as np

# Load the image in grayscale
img = cv2.imread('path_to_your_image.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# Shi-Tomasi corner detection
corners = cv2.goodFeaturesToTrack(gray, maxCorners=100, qualityLevel=0.01, minDistance=10)

# Convert the corners to integer values
corners = np.int0(corners)

# Draw circles around the detected corners
for i in corners:
    x, y = i.ravel()
    cv2.circle(img, (x, y), 3, (0, 255, 0), -1)

# Display the image with detected corners
cv2.imshow('Shi-Tomasi Corners', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

• gray: The grayscale input image.
• maxCorners: The maximum number of corners to detect. If more corners are found, the algorithm retains only the strongest ones.
• qualityLevel: A value between 0 and 1, which determines the minimum acceptable quality of corners. A lower value means more corners might be detected.
• minDistance: The minimum Euclidean distance between detected corners to avoid detecting too many closely located corners.

2.4 Keypoints

• Shi-Tomasi Corner Detection: An algorithm that improves upon the Harris method by directly using the smallest eigenvalue of the structure tensor as the corner response.
• More Robust: It tends to be more reliable in detecting corners, especially in real-world applications like feature tracking.
• Implementation: OpenCV provides a built-in function cv2.goodFeaturesToTrack to perform Shi-Tomasi corner detection easily.
• The Shi-Tomasi algorithm is particularly useful in applications like object tracking, where reliable corner detection is crucial.