Real-World Example: Template Matching

While extracting SIFT keypoints is interesting, their true power lies in Feature Matching. Because SIFT descriptors are highly distinctive and invariant to rotation, scale, and lighting, they are perfect for finding a specific object (a "template") hidden within a larger, cluttered, or rotated scene.

This page walks through the template_matching_demo.py script included in the repository.

The Scenario

Imagine you have an isolated image of a cereal box (box.png). You also have a photograph of a messy kitchen counter taken from a different angle, under different lighting (box_in_scene.png). Our goal is to write a script that draws a polygon around the exact location of the cereal box in the messy kitchen.

The Complete Code

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

# Enable logging to track progress during the long SIFT computation
logging.basicConfig(level=logging.INFO)
logger = logging.getLogger(__name__)

# We need at least 10 mathematically confident matches to assume the object is found
MIN_MATCH_COUNT = 10

# 1. Load the images in grayscale
img1 = cv2.imread('box.png', 0)           # The template (queryImage)
img2 = cv2.imread('box_in_scene.png', 0)  # The scene (trainImage)

# 2. Extract Features using PythonSIFT
print("Extracting features from template...")
kp1, des1 = pysift.computeKeypointsAndDescriptors(img1)

print("Extracting features from scene...")
kp2, des2 = pysift.computeKeypointsAndDescriptors(img2)

# 3. Initialize FLANN Matcher (Fast Library for Approximate Nearest Neighbors)
# FLANN is much faster than brute-force matching for 128-dimensional data.
FLANN_INDEX_KDTREE = 0
index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
search_params = dict(checks = 50)
flann = cv2.FlannBasedMatcher(index_params, search_params)

# Find the 2 best matches in the scene for every feature in the template (k=2)
matches = flann.knnMatch(des1, des2, k=2)

# 4. Filter matches using Lowe's Ratio Test
good = []
for m, n in matches:
    # A match is valid only if the closest neighbor is significantly 
    # closer than the second-closest neighbor.
    if m.distance < 0.7 * n.distance:
        good.append(m)

print(f"Found {len(good)} confident matches out of {len(matches)} total.")

# 5. Estimate Perspective and Draw
if len(good) > MIN_MATCH_COUNT:
    # Extract the (x, y) coordinates of the good matches
    src_pts = np.float32([ kp1[m.queryIdx].pt for m in good]).reshape(-1, 1, 2)
    dst_pts = np.float32([ kp2[m.trainIdx].pt for m in good]).reshape(-1, 1, 2)

    # Calculate the Homography matrix using RANSAC to reject outliers
    M, mask = cv2.findHomography(src_pts, dst_pts, cv2.RANSAC, 5.0)

    # Define the 4 corners of the original template image
    h, w = img1.shape
    pts = np.float32([[0, 0],
                      [0, h - 1],
                      [w - 1, h - 1],
                      [w - 1, 0]]).reshape(-1, 1, 2)

    # Use the Homography matrix to mathematically warp the corners into the scene
    dst = cv2.perspectiveTransform(pts, M)

    # Draw a thick white polygon around the detected object in the scene
    img2 = cv2.polylines(img2, [np.int32(dst)], True, 255, 3, cv2.LINE_AA)

    # --- Visualization Setup (Drawing images side-by-side) ---
    h1, w1 = img1.shape
    h2, w2 = img2.shape
    nWidth = w1 + w2
    nHeight = max(h1, h2)
    hdif = int((h2 - h1) / 2)
    newimg = np.zeros((nHeight, nWidth, 3), np.uint8)

    for i in range(3):
        newimg[hdif:hdif + h1, :w1, i] = img1
        newimg[:h2, w1:w1 + w2, i] = img2

    # Draw blue lines connecting the matched keypoints
    for m in good:
        pt1 = (int(kp1[m.queryIdx].pt[0]), int(kp1[m.queryIdx].pt[1] + hdif))
        pt2 = (int(kp2[m.trainIdx].pt[0] + w1), int(kp2[m.trainIdx].pt[1]))
        cv2.line(newimg, pt1, pt2, (255, 0, 0))

    plt.imshow(newimg)
    plt.title('SIFT Template Matching Result')
    plt.show()
else:
    print(f"Not enough matches are found - {len(good)}/{MIN_MATCH_COUNT}")

Step-by-Step Breakdown

1. FLANN and KD-Trees

Comparing every 128-dimensional descriptor in image 1 against every descriptor in image 2 (Brute Force) is extremely slow. We use OpenCV's FLANN (Fast Library for Approximate Nearest Neighbors). By structuring the descriptors into KD-Trees (trees = 5), we can perform lightning-fast spatial lookups to find the closest matching vectors.

2. Lowe's Ratio Test

This is a critical concept introduced by David Lowe. When matching a feature, we ask FLANN for the two closest matches (k=2).

If the distance to the closest match (m) is very similar to the distance to the second-closest match (n), the feature is likely ambiguous (e.g., repeating patterns like a checkerboard). We apply the formula m.distance < 0.7 * n.distance. This geometrically guarantees that the primary match is highly unique and distinct, effectively eliminating 90% of false positives.

3. Homography and RANSAC

Even with the ratio test, some matches will be wrong. We use cv2.findHomography to find a 3x3 perspective transformation matrix (M) that maps the flat template into the 3D perspective of the scene.

We pass the cv2.RANSAC flag. RANSAC (Random Sample Consensus) randomly picks small subsets of our matches, builds a temporary matrix, and tests how many other matches agree with it. It repeats this until it finds a matrix that ignores the outliers, giving us a perfect bounding box.