Feature Detection and Matching
Design and implement a feature detector that allows you to robustly compare images with differences in position, orientation, and illumination.
This project implements Harris corner detection, feature description using simple and MOPS descriptors, and feature matching algorithms to identify corresponding points between images for applications like panorama stitching.
Project Details
| Language: | Python with NumPy, SciPy, OpenCV |
| Key Concepts: | Harris corners, feature descriptors, matching algorithms |
Overview
The goal of feature detection and matching is to identify corresponding points between images that may have differences in position, orientation, and illumination. This forms the foundation for many computer vision applications including panorama stitching, object recognition, and structure from motion.
The project consists of three main components: detecting interest points using Harris corner detection, describing features using both simple and MOPS descriptors, and matching features using different distance metrics.
Implementation
Part 1: Harris Corner Detection
Harris corner detection identifies points in an image where there are significant changes in intensity in multiple directions. These points are robust to small translations and rotations.
Algorithm Steps:
- Compute Image Gradients: Use 3×3 Sobel operators to find x and y derivatives
- Build Harris Matrix: For each pixel, compute the structure tensor in a local window
- Calculate Corner Response: Use the Harris corner strength function
- Find Local Maxima: Select strongest corners that are local maxima in a 7×7 neighborhood
Harris Matrix Mathematics:
Part 2: Feature Description
Once interest points are detected, we need to create descriptors that characterize the local appearance around each point for matching purposes.
Simple Descriptor
A 5×5 patch of pixel intensities around each keypoint. Simple but effective for images related by translation.
MOPS Descriptor
A more sophisticated approach that achieves rotation invariance:
- Extract 40×40 patch around the keypoint
- Rotate patch so keypoint orientation points to the right
- Subsample to 8×8 using affine transformation
- Normalize to zero mean and unit variance
MOPS Transformation Process:
The 40×40 → 8×8 transformation involves a sequence of operations:
- T₁: Translate to center the 40×40 patch at origin
- R: Rotate by negative keypoint orientation (align to horizontal)
- S: Scale down by factor of 5 (40×40 → 8×8)
- T₂: Translate to center the final 8×8 patch
Combined transformation: T = T₂ × S × R × T₁, applied using cv2.warpAffine
Why this works: By rotating the patch so the keypoint orientation points right, features become rotation-invariant. The scaling creates a compact 64-dimensional descriptor (8×8 = 64 values) that can be efficiently compared using distance metrics.
Part 3: Feature Matching
Implemented two distance metrics for finding corresponding features between images:
Sum of Squared Differences (SSD)
Direct Euclidean distance between feature vectors. Simple but can be sensitive to illumination changes.
Ratio Test
Compares the distance to the best match with the distance to the second-best match. More robust to ambiguous matches.
My Results
Implementation Results
Successfully implemented all three components and evaluated performance on the Yosemite benchmark dataset.
Feature Matching Results
Benchmark Results
ROC Curve Analysis on Yosemite Dataset
Evaluated four different combinations of descriptors and distance metrics:
Simple + SSD
AUC Score
Simple + Ratio
AUC Score
MOPS + SSD
AUC Score
MOPS + Ratio
AUC Score ⭐
Best Method: MOPS descriptor with Ratio test distance provides the best performance due to rotation invariance and robust matching criteria.
Key Learnings
Technical Insights
- Harris Corner Detection: Understanding how the structure tensor captures local image variations and corner strength
- Rotation Invariance: MOPS descriptor's use of keypoint orientation to achieve invariance to image rotation
- Robust Matching: Ratio test's effectiveness in handling ambiguous matches and false positives
- Affine Transformations: Practical experience with cv2.warpAffine for geometric image transformations
- Performance Evaluation: ROC analysis and AUC metrics for quantitative comparison of algorithms
Computer Vision Concepts
- Feature Detection: Identifying repeatable, distinctive points robust to image transformations
- Descriptor Design: Balancing discriminative power with computational efficiency
- Invariance Trade-offs: Understanding which image transformations each method can handle
- Evaluation Methodology: Using controlled datasets with ground truth for systematic algorithm comparison
Applications
Real-World Uses
Image Stitching: Feature correspondences enable panorama creation by finding overlapping regions
Object Recognition: Matching features across different views of the same object
Structure from Motion: Reconstructing 3D scene geometry from multiple 2D images
Visual SLAM: Simultaneous localization and mapping for robotics and AR applications