Feature Matching

• Harris Corner Detector

• Scale-Invariant Feature Transform (SIFT)

• Speeded Up Robust Features (SURF)

• FAST (Features from Accelerated Segment Test)

• ORB (Oriented FAST and Rotated BRIEF)

• Histogram of Oriented Gradients (HOG)

• Edge Detectors (e.g., Canny Edge Detector)

Harris Corner Detector

• Haris corner detection is a method in which we can detect the corners of the image
by sliding a slider box all over the image by finding the corners and it will apply a
threshold and the corners will be marked in the image.

• This algorithm is mainly used to detect the corners of the image.

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

# Load the image

image = cv2.imread('tank.bmp',0)

org_img = image.copy()
# Harris corner detection parameters

block_size = 2 # Neighborhood size for corner detection

ksize = 3 # Aperture parameter for the Sobel operator
k = 0.04 # Harris detector free parameter (typically 0.04 - 0.06)

# Detect corners using Harris corner detection

corners = cv2.cornerHarris(image, block_size, ksize, k)

# Threshold for an optimal value, it may vary depending on the image

and the Harris detector parameter k

threshold = 0.01 * corners.max()

# Mark detected corners in the image

image[corners > threshold] = [0]

# Display the resul

plt.subplot(1,2,1)
plt.title('Original Image')
plt.imshow(org_img, cmap='gray')
plt.axis(False)

plt.subplot(1,2,2)
plt.title('Harris Corner Detection')
plt.imshow(image, cmap='gray')
plt.axis(False)

plt.tight_layout()
plt.show()

SIFT (Scale-Invariant Feature Transform)

• While Haris is the algorithms to detect the corners of the image.

• SIFT is one of the important algorithms that detect objects irrelevant to the scale
and rotation of the image and the reference.
 • This helps a lot while we are comparing the real-world objects to an image though it
is independent of the angle and scale of the image.

• This method will return the key points of the images which we need to mark in the
image.

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

# Load the image

image = cv2.imread('tank.bmp')

gray_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

# Initialize the SIFT detector

sift = cv2.SIFT_create()

# Detect keypoints and compute descriptors

keypoints, descriptors = sift.detectAndCompute(gray_image, None)

# Draw keypoints on the image

image_with_keypoints = cv2.drawKeypoints(image, keypoints, None,
flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)

plt.subplot(1,2,1)
plt.title('Original Image')
plt.imshow(image)
plt.axis(False)

plt.subplot(1,2,2)
plt.title('SIFT Keypoints')
plt.imshow(image_with_keypoints)
plt.axis(False)

plt.tight_layout()
plt.show()
speeded up robust features (SURF)
• In computer vision, speeded up robust features (SURF) is a patented local feature
detector and descriptor. It can be used for tasks such as object recognition, image
registration, classification, or 3D reconstruction.

• It is partly inspired by the scale-invariant feature transform (SIFT) descriptor.

• The standard version of SURF is several times faster than SIFT and claimed by its
authors to be more robust against different image transformations than SIFT.

import cv2
import matplotlib.pyplot as plt

# Load an image
image = cv2.imread('tank.bmp', cv2.IMREAD_COLOR)

# Create a SURF object

surf = cv2.xfeatures2d.SURF_create()

# Detect and compute SURF keypoints and descriptors

keypoints, descriptors = surf.detectAndCompute(image, None)

# Draw the keypoints on the image

image_with_keypoints = cv2.drawKeypoints(image, keypoints, None, (0,
255, 0), 4)

# Display the original image with keypoints

plt.subplot(1,2,1)
plt.title('Original Image')
plt.imshow(image)
plt.axis(False)

plt.subplot(1,2,2)
plt.title('SURF Keypoints')
plt.imshow(image_with_keypoints)
plt.axis(False)

plt.tight_layout()
plt.show()

----------------------------------------------------------------------
-----
error Traceback (most recent call
last)
<ipython-input-25-af8db48d390c> in <cell line: 0>()
6
7 # Create a SURF object
----> 8 surf = cv2.xfeatures2d.SURF_create()
9
10 # Detect and compute SURF keypoints and descriptors

error: OpenCV(4.11.0)
/io/opencv_contrib/modules/xfeatures2d/src/surf.cpp:1026: error: (-
213:The function/feature is not implemented) This algorithm is
patented and is excluded in this configuration; Set
OPENCV_ENABLE_NONFREE CMake option and rebuild the library in function
'create'

Hessian operator
• The Hessian operator is a mathematical tool used in image processing and computer
vision for analyzing the second-order spatial derivatives of an image.

• It is primarily employed for detecting and characterizing local structures and

features within an image, such as edges, corners, and blobs.

• In the context of feature detection, the Hessian matrix is used to compute the
Hessian determinant, which is a measure of local structure and can be used for
features like blobs or regions of interest.

import cv2
import numpy as np
import matplotlib.pyplot as plt
# Load the image
image = cv2.imread('tank.bmp', 0)

# Define the Hessian operator masks

mask_x = np.array([[1, 0, -1], [2, 0, -2], [1, 0, -1]])
mask_y = np.array([[1, 2, 1], [0, 0, 0], [-1, -2, -1]])

# Compute the second-order partial derivatives

Ix = cv2.filter2D(image, cv2.CV_64F, mask_x)
Iy = cv2.filter2D(image, cv2.CV_64F, mask_y)

# Compute elements of the Hessian matrix

Ixx = cv2.filter2D(Ix, cv2.CV_64F, mask_x)
Iyy = cv2.filter2D(Iy, cv2.CV_64F, mask_y)
Ixy = cv2.filter2D(Ix, cv2.CV_64F, mask_y)

# Calculate the determinant of the Hessian matrix

hessian_det = (Ixx * Iyy) - (Ixy**2)

# Display the images or do further processing based on

hessian_det

# For visualization (optional)

import matplotlib.pyplot as plt

# Create subplots for each image

plt.figure(figsize=(15, 10))

# Image
plt.subplot(2, 4, 1)
plt.imshow(image.astype(np.uint8), cmap='gray')
plt.title('Image')
plt.axis('off')

# Ix
plt.subplot(2, 4, 2)
plt.imshow(Ix, cmap='gray')
plt.title('Ix')
plt.axis('off')

# Iy
plt.subplot(2, 4, 3)
plt.imshow(Iy, cmap='gray')
plt.title('Iy')
plt.axis('off')

# Ixx
plt.subplot(2, 4, 4)
plt.imshow(Ixx, cmap='gray')
plt.title('Ixx')
plt.axis('off')

# Iyy
plt.subplot(2, 4, 5)
plt.imshow(Iyy, cmap='gray')
plt.title('Iyy')
plt.axis('off')

# Ixy
plt.subplot(2, 4, 6)
plt.imshow(Ixy, cmap='gray')
plt.title('Ixy')
plt.axis('off')

# Hessian Determinant
plt.subplot(2, 4, 7)
plt.imshow(hessian_det.astype(np.uint8), cmap='gray')
plt.title('Hessian Determinant')
plt.axis('off')

plt.tight_layout()
plt.show()
FAST(Features from Accelerated Segment Test)
• SURF is fast when compared to SIFT but not as fast to use with real-time devices like
mobile phones and surveillance cameras.

• So FAST algorithm was introduced with a very fast computing time.

• However FAST gives us only the key points and we may need to compute
descriptors with other algorithms like SIFT and SURF.

• With a Fast algorithm, we can detect corners and also blobs.

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

# Load image in grayscale

img = cv.imread('tank.bmp', 0)

# Initialize FAST detector

fast = cv.FastFeatureDetector_create()

# Detect keypoints with nonmaxSuppression = True

kp1 = fast.detect(img, None)
img_with_kp1 = cv.drawKeypoints(img, kp1, None, color=(255, 0, 0))

# Print parameters
print("Threshold: {}".format(fast.getThreshold()))
print("nonmaxSuppression: {}".format(fast.getNonmaxSuppression()))
print("neighborhood: {}".format(fast.getType()))
print("Total Keypoints with nonmaxSuppression: {}".format(len(kp1)))

# Detect keypoints with nonmaxSuppression = False

fast.setNonmaxSuppression(0)
kp2 = fast.detect(img, None)
img_with_kp2 = cv.drawKeypoints(img, kp2, None, color=(255, 0, 0))

print("Total Keypoints without nonmaxSuppression:

{}".format(len(kp2)))

# Convert BGR to RGB for displaying correctly in Matplotlib

img_with_kp1 = cv.cvtColor(img_with_kp1, cv.COLOR_BGR2RGB)
img_with_kp2 = cv.cvtColor(img_with_kp2, cv.COLOR_BGR2RGB)

# Show both results side by side

plt.figure(figsize=(12, 6))

plt.subplot(1, 3, 1)
plt.imshow(img, cmap='gray')
plt.title('Orignal')
plt.axis('off')

plt.subplot(1, 3, 2)
plt.imshow(img_with_kp1, cmap='gray')
plt.title('With nonmaxSuppression')
plt.axis('off')

plt.subplot(1,3,3)
plt.imshow(img_with_kp2, cmap='gray')
plt.title('Without nonmaxSuppression')
plt.axis('off')

plt.tight_layout()
plt.show()

Threshold: 10
nonmaxSuppression: True
neighborhood: 2
Total Keypoints with nonmaxSuppression: 7966
Total Keypoints without nonmaxSuppression: 20360

BRIEF(Binary Robust Independent Elementary

Features)
• we use binary strings as an efficient feature point descriptor, which is called BRIEF.

• BRIEF is very fast both to build and to match.

• BRIEF easily outperforms other fast descriptors such as SURF and SIFT in terms of
speed and terms of recognition rate in many cases.

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

# Load image in grayscale

image = cv2.imread('tank.bmp', cv2.IMREAD_GRAYSCALE)

# Check if image loaded correctly

if image is None:
print("Error: Image not found!")
else:
# Initialize FAST detector
fast = cv2.FastFeatureDetector_create()

# Detect keypoints using FAST

keypoints = fast.detect(image, None)

# Initialize BRIEF descriptor extractor

brief = cv2.xfeatures2d.BriefDescriptorExtractor_create()

# Compute descriptors using BRIEF

keypoints, descriptors = brief.compute(image, keypoints)

# Draw keypoints on the image

image_with_keypoints = cv2.drawKeypoints(image, keypoints, None,
color=(255, 0, 0))

# Convert to RGB for matplotlib

image_with_keypoints = cv2.cvtColor(image_with_keypoints,
cv2.COLOR_BGR2RGB)

# Show the image using matplotlib

plt.figure(figsize=(8, 6))

plt.subplot(1,2,1)
plt.title('Original Image')
plt.imshow(image, cmap='gray')
plt.axis('off')

plt.subplot(1,2,2)
plt.imshow(image_with_keypoints)
plt.title('FAST + BRIEF Keypoints')
plt.axis('off')
plt.show()
ORB (Oriented FAST and Rotated Brief)
• builds upon the FAST keypoint detector and the BRIEF descriptor, adding
enhancements to make it more robust to rotation and scale changes.

• It combines two key methods:

– FAST (Features from Accelerated Segment Test): A corner detection method

that quickly identifies key points in an image.

– BRIEF (Binary Robust Independent Elementary Features): A feature

descriptor that uses binary strings to describe the key points identified by
FAST.

import cv2
import matplotlib.pyplot as plt

# Reading the image and converting it to grayscale

image = cv2.imread('tank.bmp')
gray_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

# Applying the ORB detector

orb = cv2.ORB_create(nfeatures=2000)
kp, des = orb.detectAndCompute(gray_image, None)

# Drawing the keypoints

kp_image = cv2.drawKeypoints(image, kp, None, color=(0, 255, 0),
flags=0)
# Convert the image from BGR to RGB format for matplotlib
kp_image_rgb = cv2.cvtColor(kp_image, cv2.COLOR_BGR2RGB)

# Display the image using matplotlib

plt.subplot(1,2,1)
plt.title('Original Image')
plt.imshow(image)
plt.axis('off')

plt.subplot(1,2,2)
plt.imshow(kp_image_rgb)
plt.axis('off')
plt.title('ORB Keypoints')
plt.show()

histogram of oriented gradients (HOG)

• The Histogram of Oriented Gradients (HOG) is a popular feature descriptor
technique in computer vision and image processing.

• It analyzes the distribution of edge orientations within an object to describe its

shape and appearance.

• The HOG method involves computing the gradient magnitude and orientation for
each pixel in an image and then dividing the image into small cells.

• It is better than any edge descriptor as it uses magnitude as well as angle of the
gradient to compute the features.

import cv2
import numpy as np
import matplotlib.pyplot as plt
from skimage.feature import hog
from skimage import exposure

# Load image in grayscale

image = cv2.imread('tank.bmp', cv2.IMREAD_GRAYSCALE)

# Check if image loaded correctly

if image is None:
print("Image not found. Please check the path.")
else:
# Compute HOG features and visualization
hog_features, hog_image = hog(
image,
orientations=9,
pixels_per_cell=(8, 8),
cells_per_block=(2, 2),
visualize=True,
block_norm='L2-Hys'
)

# Improve the contrast of the HOG image

hog_image_rescaled = exposure.rescale_intensity(hog_image,
in_range=(0, 10))

# Plot original and HOG image

#plt.figure(figsize=(12, 6))

plt.subplot(1, 2, 1)
plt.imshow(image, cmap='gray')
plt.title('Original Image')
plt.axis('off')

plt.subplot(1, 2, 2)
plt.imshow(hog_image_rescaled, cmap='gray')
plt.title('HOG Visualization')
plt.axis('off')

plt.tight_layout()
plt.show()
Feature Matching

Brute Force Matcher

• The Brute-Force Matcher in OpenCV is a simple and straightforward method for
matching features between two sets of descriptors extracted from images.

• It computes the distances between descriptors and finds the best matches based on
a chosen criterion (e.g., Euclidean distance).

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

# Load the images

img1 = cv2.imread('left.png', cv2.IMREAD_GRAYSCALE)
img2 = cv2.imread('right.png', cv2.IMREAD_GRAYSCALE)

# Initialize the ORB detector

orb = cv2.ORB_create()

# Find the keypoints and descriptors with ORB

keypoints1, descriptors1 = orb.detectAndCompute(img1, None)
keypoints2, descriptors2 = orb.detectAndCompute(img2, None)

# Create a BFMatcher object

bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
# Match descriptors
matches = bf.match(descriptors1, descriptors2)

# Sort them in ascending order of distance

matches = sorted(matches, key=lambda x: x.distance)

# Draw the first 10 matches

matched_img = cv2.drawMatches(img1, keypoints1, img2, keypoints2,
matches[:10], None, flags=cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)

# Display the matches

plt.imshow(matched_img)
plt.axis('off')
plt.show()

BFMatcher with KNN

• Performing K-nearest neighbor (KNN) matching using the Brute-Force Matcher
(BFMatcher) in OpenCV involves finding the K-best matches for each descriptor
from one set to another.

• This is often used for more robust feature matching.

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

# Load the images

img1 = cv2.imread('left.png', cv2.IMREAD_GRAYSCALE)

img2 = cv2.imread('right.png', cv2.IMREAD_GRAYSCALE)

# Initialize the SIFT detector

sift = cv2.SIFT_create()
# Find the keypoints and descriptors with SIFT
keypoints1, descriptors1 = sift.detectAndCompute(img1, None)
keypoints2, descriptors2 = sift.detectAndCompute(img2, None)

# BFMatcher with default params

bf = cv2.BFMatcher()

# KNN matching
matches = bf.knnMatch(descriptors1, descriptors2, k=2)

# Apply ratio test

good_matches = []
for m, n in matches:
if m.distance < 0.75 * n.distance:
good_matches.append(m)

# Draw the matches

matched_img = cv2.drawMatches(img1, keypoints1, img2, keypoints2,

good_matches, None,
flags=cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)

plt.imshow(matched_img)
plt.axis('off')
plt.show()

Earth Mover’s Distance (EMD)

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

# Load grayscale images

image1 = cv2.imread('left.png', 0)
image2 = cv2.imread('right.png', 0)
# Compute histograms
hist1 = cv2.calcHist([image1], [0], None, [256], [0, 256])
hist2 = cv2.calcHist([image2], [0], None, [256], [0, 256])

# Normalize histograms
hist1 = hist1 / hist1.sum()
hist2 = hist2 / hist2.sum()

# Create signatures: each row = [weight (hist value), feature (bin

index)]
sig1 = np.array([[hist1[i][0], float(i)] for i in range(256)],
dtype=np.float32)
sig2 = np.array([[hist2[i][0], float(i)] for i in range(256)],
dtype=np.float32)

# Calculate EMD using L2 distance

emd_result, _, _ = cv2.EMD(sig1, sig2, cv2.DIST_L2)

# Print result
print("Earth Mover's Distance (EMD):", emd_result)

Earth Mover's Distance (EMD): 14.674192428588867

Nearest Neighbor Search (Query Point: (3,5))

import cv2
import numpy as np

# Sample data (points)

data = np.array([[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]],
dtype=np.float32)

# Create FLANN index

index_params = dict(algorithm=1, trees=5) # KDTree
flann = cv2.flann_Index(data, index_params)

# Query point
query_point = np.array([[3, 5]], dtype=np.float32)

# Perform knn search (k = 1)

idxs, dists = flann.knnSearch(query_point, 1, params={})

# Find nearest neighbor

nearest_neighbor = data[idxs.ravel()]

print("Query Point:", query_point)

print("Nearest Neighbor:", nearest_neighbor)
Query Point: [[3. 5.]]
Nearest Neighbor: [[4. 7.]]