COMPUTER VISION

Week 5 — Study Guide

Feature Detection, Scale Invariance & Harris Corner Detection
Topics: Image Features | Feature Types & Detectors | Panorama Stitching | Scale Invariance |
SIFT | Harris Corner Detector

1. Summary of Main Topics

1.1 What Are Image Features?
Image features are distinctive, locatable elements or structures in an image that can be reliably
detected and described. They serve as the building blocks for nearly every higher-level computer vision
task — from matching two photos of the same scene to reconstructing 3D geometry.

Core properties of a good feature:

• Variability: Features must be sufficiently different from one another so they can be
told apart.
• Repeatability: The same feature should be detectable across different images
(varying scale, rotation, illumination).
• Distinctiveness: The descriptor of a feature should uniquely identify it among many
candidates.
• Locality: Features describe a small region; large changes elsewhere in the image
do not affect them.

1.2 Types of Features

Four main categories of features are commonly used in computer vision pipelines:
Feature Type Detection Method Use Cases

Edges Gradient-based (e.g., Canny) Boundary detection, shape

analysis

Corners Harris, Shi-Tomasi, FAST Matching, tracking, stitching

Blobs Difference of Gaussians (DoG), Object recognition, wide-baseline

SIFT, SURF matching

Descriptors SIFT, ORB, BRIEF, AKAZE Matching features across images

1.3 Application: Panorama Stitching

Panorama stitching is a classic application that ties together feature detection, matching, and geometric
estimation. The goal is to align multiple overlapping photos into a single seamless wide-angle image.

4-Step Panorama Pipeline:

1. Detect features — Find distinctive keypoints (corners, blobs) in each image using
 algorithms such as SIFT or ORB.
2. Match features — Use descriptor distance (e.g., Euclidean) + Lowe's ratio test to
find reliable correspondences between images.
3. Estimate homography — Use RANSAC with the matched point pairs to compute
the 3×3 homography matrix H that maps one image plane to another.
4. Warp and blend — Apply [Link]() to align images, then blend the
seam for a seamless result.

Note: Overlapping photos need a 20–30 % overlap region to ensure enough common features are found between
adjacent images.

1.4 Scale Invariance & Multi-Scale Representation

A scale-invariant algorithm detects the same features regardless of the size at which an object appears
in the image. This is critical because the same object can appear at vastly different sizes depending on
camera distance.

The problem with fixed-scale detectors:

• Standard detectors (e.g., Harris) operate at a fixed window size.
• A corner at small scale may look like a flat region when the object is magnified, so
the detector misses it.
• Solution: represent the image across all scales — the Scale Space.

The Gaussian Pyramid implements a discrete scale space by sequentially blurring and downsampling
the image:
• Level 0: Original full-resolution image.
• Level 1: Gaussian-blurred and halved in resolution.
• Level 2+: Repeated blurring and subsampling, suppressing finer structures at each level.

1.5 SIFT — Scale-Invariant Feature Transform

Developed by David Lowe (1999, published 2004), SIFT is the gold standard for local feature detection
and description. It is explicitly designed to be invariant to scale, rotation, and illumination changes.

SIFT Invariance Properties:

• Scale invariance: Keypoints are detected in DoG scale-space; the characteristic
scale is selected automatically.
• Rotation invariance: The descriptor is aligned to the dominant gradient orientation
so it is the same regardless of image rotation.
• Illumination invariance: Descriptor vectors are L2-normalised, making them robust
to linear brightness changes.
• Viewpoint robustness: Local histogram structure handles moderate 3-D viewpoint
changes and affine distortions.

Constructing the SIFT Descriptor:

 5. Sample a 16×16 pixel neighbourhood around the keypoint.
6. Compute gradient magnitude and orientation for every pixel.
7. Build an orientation histogram to find the dominant orientation (rotation invariance).
8. Divide the neighbourhood into a 4×4 grid of sub-regions.
9. Compute an 8-bin orientation histogram for each sub-region.
10. Concatenate all 16 histograms: 4 × 4 × 8 = 128-dimensional descriptor vector.

1.6 Feature Matching & Outlier Rejection

Once descriptors are computed, matching finds corresponding keypoints across images. Two key
challenges are computational cost (brute-force is O(N²)) and false matches from background clutter.

Lowe's Ratio Test (Outlier Rejection):

• For each query descriptor, find the two closest matches: d1 (best) and d2 (second-
best).
• Keep the match only if d1 < threshold × d2 (typically 0.75).
• Rationale: true matches have d1 << d2; false matches have similar distances (d1 ≈
d2).

For large databases, Best-Bin-First (BBF) search with k-d trees accelerates nearest-neighbour lookup
by limiting the number of nodes visited, trading a small accuracy loss for a major speed gain.

1.7 Harris Corner Detector

Proposed by Chris Harris & Mike Stephens (1988), the Harris detector finds corners by looking for
image locations where intensity changes strongly in every direction when a small window is shifted.

Intuition — Three Region Types:

• Flat region: Little change in any direction. Both eigenvalues λ₁ and λ₂ are small. |R|
≈ 0.
• Edge: Large change in one direction only. One eigenvalue large, one small. R < 0.
• Corner: Large change in all directions. Both λ₁ and λ₂ large. R > 0 (strong corner).

The detector evaluates the auto-correlation matrix M (structure tensor) formed from image gradients
over a local window, then computes the Harris Response R to classify each pixel.
2. Key Concepts & Definitions
Term Definition
Feature A distinctive element or structure in an image (edge, corner, blob)
that can be reliably detected and matched across different views.
Keypoint The spatial location and scale of a detected feature point. Paired
with a descriptor to enable matching.
Descriptor A compact numerical representation (e.g., 128-D vector for SIFT)
that encodes the appearance around a keypoint.
Scale Space A continuous multi-resolution representation of an image built by
progressively blurring with Gaussians, allowing detection at all
scales.
Gaussian Pyramid Discrete implementation of scale space: repeatedly apply
Gaussian blur then downsample by a factor of 2. Each level
halves the resolution.
DoG (Difference of Approximation of the Laplacian of Gaussian (LoG); computed by
Gaussians) subtracting adjacent Gaussian-blurred levels. Used by SIFT to
detect blobs as scale-space extrema.
SIFT Scale-Invariant Feature Transform (Lowe, 1999). Detects
keypoints via DoG extrema and describes them with a 128-D
gradient orientation histogram.
ORB Oriented FAST and Rotated BRIEF. A fast binary descriptor
alternative to SIFT; good for real-time applications.
AKAZE Accelerated-KAZE. Nonlinear scale-space detector. Accuracy
between ORB and SIFT; computationally efficient.
Homography A 3×3 projective transformation matrix H that maps points from
one image plane to another. Estimated from ≥ 4 matched point
pairs.
RANSAC Random Sample Consensus. Iteratively fits a model using
random subsets of matches, discarding outliers. Used to robustly
estimate homography.
Ratio Test (Lowe's) Filter for feature matches: keep a match only if d1 < ratio × d2.
Typically ratio = 0.75. Rejects ambiguous background matches.
BBF Search Best-Bin-First. Approximate nearest-neighbour search using k-d
trees, limiting visited nodes for speed with minimal accuracy loss.
Harris Detector Corner detector (Harris & Stephens, 1988). Computes the
structure tensor M from image gradients, then classifies pixels via
the response R = det(M) − k·trace²(M).
Structure Tensor M 2×2 matrix M = Σ [[Ix², IxIy],[IxIy, Iy²]] over a local window.
Eigenvalues λ₁, λ₂ describe the dominant gradient directions.
Harris Response R R = det(M) − k·trace²(M). R > 0 → corner; R < 0 → edge; |R| ≈ 0
→ flat. Empirical constant k ≈ 0.04–0.06.
Warp Perspective Applying a homography to geometrically transform an image onto
 another plane ([Link]). Used in panorama
blending.

3. Formulas & Equations

3.1 Auto-Correlation Function (Harris)
Measures how much intensity changes when a window is shifted by (u, v):

E(u,v) = Σ w(x,y) · [I(x+u, y+v) − I(x,y)]²

• E(u,v): Change in intensity for shift (u,v).

• w(x,y): Window function — Gaussian or rectangular.
• I(x,y): Original image intensity at (x,y).

3.2 Taylor Expansion (Linearised Intensity Shift)

First-order Taylor approximation of the shifted intensity, valid for small (u, v):

I(x+u, y+v) ≈ I(x,y) + Ix·u + Iy·v

• Ix = ∂I/∂x: Horizontal image gradient.

• Iy = ∂I/∂y: Vertical image gradient.

3.3 Structure Tensor M

The auto-correlation E(u,v) can be written in matrix form. M is the structure tensor (second moment
matrix):

M = Σ(x,y) [ Ix² IxIy ]

[ IxIy Iy² ]

3.4 Harris Corner Response R

Computed from the eigenvalues λ₁, λ₂ of M without explicit eigenvalue decomposition:

R = det(M) − k · trace²(M)
= λ₁λ₂ − k(λ₁ + λ₂)²
(k ≈ 0.04 – 0.06 empirically)

• R > 0: Corner — both eigenvalues large.

• R < 0: Edge — one eigenvalue large, one small.
• |R| ≈ 0: Flat region — both eigenvalues small.
3.5 SIFT Descriptor Dimensionality
4 × 4 grid × 8 orientation bins = 128 dimensions
4. Code Examples
4.1 SIFT Feature Detection (OpenCV / Python)
Detect keypoints and compute 128-D descriptors using OpenCV's SIFT implementation:
import cv2
import numpy as np

# 1. Load image and convert to grayscale

img = [Link]('campus_image.jpg')
gray = [Link](img, cv2.COLOR_BGR2GRAY)

# 2. Create SIFT detector

sift = cv2.SIFT_create()

# 3. Detect keypoints and compute descriptors

# kp → list of KeyPoint objects
# des → numpy array of shape (N, 128)
kp, des = [Link](gray, None)

# 4. Visualise keypoints with scale and orientation

img_kp = [Link](
img, kp, None,
flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS
)

[Link]('SIFT Keypoints', img_kp)

[Link](0)
[Link]()

4.2 Feature Matching with Lowe's Ratio Test

Brute-Force matching (BFMatcher) with k-NN (k=2) and Lowe's ratio test to filter false matches:
# Assume kp1, des1 from image1 and kp2, des2 from image2

# 1. Create Brute-Force Matcher

bf = [Link]()

# 2. Find 2 nearest neighbours for each descriptor

matches = [Link](des1, des2, k=2)

# 3. Apply Lowe's ratio test

def filter_matches(matches, ratio_thresh=0.75):
good = []
for m, n in matches:
if [Link] < ratio_thresh * [Link]:
[Link]([m])
return good

good_matches = filter_matches(matches)

# 4. Draw matches
img_matches = [Link](
img1, kp1, img2, kp2, good_matches, None,
flags=cv2.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS
)
[Link]('Matches', img_matches)
[Link](0)
4.3 Homography Estimation & Image Warping
Estimate the homography using RANSAC, then warp and blend images for panorama stitching:
import cv2
import numpy as np

# Assume src_pts and dst_pts are Nx2 float32 arrays of

# corresponding keypoint coordinates.

# 1. Estimate homography with RANSAC

H, mask = [Link](
srcPoints=src_pts,
dstPoints=dst_pts,
method=[Link],
ransacReprojThreshold=5.0
)

# 2. Warp img2 into img1's coordinate frame

h, w = [Link][:2]
warped = [Link](
img2, H, (w + [Link][1], h)
)

# 3. Simple overlay blend

warped[0:h, 0:w] = img1

[Link]('Panorama', warped)
[Link](0)

4.4 Harris Corner Detection

Detect corners using OpenCV's cornerHarris() and mark them on the image:
import cv2
import numpy as np

# 1. Load image and convert to grayscale float32

img = [Link]('[Link]')
gray = [Link](img, cv2.COLOR_BGR2GRAY)
gray = np.float32(gray) # required by cornerHarris

# 2. Detect Harris corners

# Parameters: image, blockSize, ksize (Sobel aperture), k
dst = [Link](gray, blockSize=2, ksize=3, k=0.04)

# 3. Dilate to make corners visible

dst = [Link](dst, None)

# 4. Threshold and mark in red

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

[Link]('Harris Corners', img)

[Link](0)
[Link]()
5. Practice Questions
Section A — Features & Detectors

Q1. What is the PRIMARY reason image features are important in computer vision?
A. They reduce image file size
B. They enable tasks like matching, recognition, and reconstruction
C. They improve image colour saturation
D. They sort images alphabetically

Answer: B. They enable tasks like matching, recognition, and reconstruction

Features capture essential structural information that allows algorithms to match objects, recognise
patterns, and reconstruct 3-D scenes — regardless of size, rotation, or lighting.

Q2. Which of the following is NOT a commonly detected feature type in images?
A. Edges
B. Corners
C. Blobs
D. Colors

Answer: D. Colors
Color is a global pixel property, not a 'feature type' in the localised detection sense. Edges, corners,
and blobs are the three canonical feature categories.

Q3. Which algorithm is most commonly used to detect edge features?

A. SIFT
B. Harris
C. Canny
D. ORB

Answer: C. Canny
Canny (1986) is the standard multi-stage edge detector. SIFT detects blobs; Harris detects corners;
ORB is a binary descriptor.

Q4. Why do feature detectors struggle with low-texture regions?

A. These regions are too bright
B. There is little intensity change, so no strong features exist
C. Image resolution is too low
D. Only corners are detected in low-texture areas

Answer: B. There is little intensity change, so no strong features exist

Low-texture regions have near-zero gradients in all directions, providing no distinctive signal for any
gradient-based feature detector.
Section B — Scale Invariance & SIFT

Q5. What does 'scale invariance' mean in the context of feature detection?
A. The algorithm works on one fixed image size only
B. Detection does not depend on the object's size within the image
C. All pixels have the same intensity value
D. Features are always blurred

Answer: B. Detection does not depend on the object's size within the image
Scale invariance means the same feature can be detected regardless of how large or small the object
appears — achieved by searching across a scale-space pyramid.

Q6. A Gaussian pyramid is used to:

A. Stretch the image in one direction
B. Build multi-resolution versions of the image
C. Convert colour images to grayscale
D. Remove image noise only

Answer: B. Build multi-resolution versions of the image

The Gaussian pyramid successively blurs then downsamples the image, creating a hierarchy of
resolutions that supports multi-scale feature detection.

Q7. SIFT detects keypoints using which key concept?

A. Edge detection via Canny
B. Difference of Gaussians (DoG) extrema in scale space
C. Thresholding raw pixel values
D. Colour histograms

Answer: B. Difference of Gaussians (DoG) extrema in scale space

SIFT computes DoG by subtracting adjacent Gaussian-blurred levels. Local extrema in this DoG
scale-space are selected as scale-invariant keypoints.

Q8. How many dimensions does a SIFT feature descriptor have?

A. 8
B. 32
C. 64
D. 128

Answer: D. 128
A SIFT descriptor is a 4×4 grid of 8-bin orientation histograms: 4 × 4 × 8 = 128 dimensions.

Q9. The SIFT descriptor is explicitly designed to be invariant to:

 A. Color and brightness only
B. Scale and rotation
C. Edges and blobs
D. Translation only

Answer: B. Scale and rotation

SIFT achieves scale invariance via DoG pyramids and rotation invariance by aligning the descriptor
to the dominant gradient orientation.

Q10. In OpenCV, calling kp, des = [Link](gray, None) — what is des?

A. A list of KeyPoint objects
B. A NumPy array of 128-D SIFT descriptors
C. A grayscale image
D. A homography matrix

Answer: B. A NumPy array of 128-D SIFT descriptors

des is a (N × 128) float32 NumPy array where each row is the 128-D descriptor for one detected
keypoint — its unique local 'fingerprint'.

Section C — Feature Matching & Homography

Q11. Feature matching commonly uses which approach to filter ambiguous matches?
A. Matching by colour histogram
B. Lowe's ratio test
C. Maximum pixel value comparison
D. Minimum gradient magnitude

Answer: B. Lowe's ratio test

Lowe's ratio test keeps a match only if d1 < threshold × d2 (typically 0.75). True matches have d1 <<
d2; false matches have similar d1 and d2.

Q12. What is the role of homography in panorama stitching?

A. Adds colour to the panorama
B. Finds the projective transformation that aligns overlapping images
C. Blurs image edges for seamless blending
D. Removes feature keypoints

Answer: B. Finds the projective transformation that aligns overlapping images

A homography H is a 3×3 projective matrix that maps points from one image plane to another,
warping one image into alignment with its neighbour.

Q13. Which of the following limits the effectiveness of feature-based panorama stitching?
A. Too many features detected
B. Strong illumination changes or repetitive textures
 C. All features are perfectly unique
D. Only edge features are used

Answer: B. Strong illumination changes or repetitive textures

Strong lighting variation can cause descriptors to change between images; repetitive textures lead to
many false ambiguous matches, both causing stitching artifacts.

Section D — Harris Corner Detector

Q14. What is the key mathematical idea behind Harris corner detection?
A. Compute image colour histograms
B. Analyse intensity changes in all directions using the auto-correlation function
C. Use deep learning to classify pixels
D. Detect only horizontal edges

Answer: B. Analyse intensity changes in all directions using the auto-correlation function
Harris looks for pixels where shifting a local window in any direction causes a large change in
intensity — the signature of a corner (significant change in all directions).

Q15. In the Harris Response formula R = det(M) − k·trace²(M), when do you get R > 0 (a corner)?
A. Both eigenvalues of M are small
B. One eigenvalue is large, the other is near zero
C. Both eigenvalues are large
D. Trace(M) = 0

Answer: C. Both eigenvalues are large

Corners have strong intensity gradients in ALL directions, so both λ₁ and λ₂ of the structure tensor M
are large, making det(M) large and R > 0.

Q16. In OpenCV, which function detects Harris corners?

A. [Link]()
B. [Link]()
C. [Link]()
D. cv2.SIFT_create()

Answer: B. [Link]()
[Link](gray, blockSize, ksize, k) takes a float32 grayscale image and returns the Harris
response map. Pixels with high response are corners.

Section E — Short Answer

Q17. Explain why SIFT builds a Gaussian pyramid before computing the Difference of
Gaussians. What problem does this solve?
Hint: Think about what happens to the same corner feature when the object moves closer or farther
from the camera. A fixed-scale detector would miss features that are prominent at one scale but not
another.

Q18. Why does detecting circles with the Hough Transform require significantly more
computation than detecting lines?
Hint: Compare the dimensionality of the accumulator arrays. For lines: 2D (ρ, θ). For circles: 3D (a, b,
r). Consider how memory and vote-counting scale with dimensionality.

Q19. You run SIFT on two photos of the same building taken at different times of day.
Many matches fail the ratio test. Give two possible reasons and how you might
address each.
Hint: Consider what illumination and lighting changes do to gradient magnitudes, and whether the
ratio test threshold might need adjustment for this scenario.

Q20. Harris corner detection is described as rotation-invariant but not scale-invariant.

Explain why.
Hint: Think about what the structure tensor M captures (gradient directions) versus what it does not
capture (the scale at which the window is applied). Compare with how SIFT achieves both
invariances.
6. Quick Reference Cheat Sheet
Feature Detector Comparison
Accuracy: SIFT >> AKAZE > ORB (for complex matching tasks)
Speed: ORB >> AKAZE > SURF > SIFT (ORB is suitable for real-time)
Scale invariant: SIFT ✓ SURF ✓ ORB ≈ Harris ✗
Rotation invariant: SIFT ✓ ORB ✓ Harris ✓ (all modern detectors)

Harris Response — Region Classification

R > 0 (large): Corner — both λ₁, λ₂ are large.
R < 0: Edge — one eigenvalue dominates.
|R| ≈ 0: Flat region — gradients near zero in all directions.

SIFT at a Glance
• Developer: David Lowe (1999/2004). Published in IJCV.
• Keypoint detection: Local extrema in Difference-of-Gaussians (DoG) scale space.
• Descriptor: 128-D vector from 4×4 grid × 8-bin orientation histograms.
• Invariances: Scale, rotation, illumination (L2-normalised vector).
• Matching: Euclidean distance + Lowe's ratio test (threshold ≈ 0.75).
• OpenCV API: cv2.SIFT_create() → [Link](gray, None)

Panorama Pipeline at a Glance

• Step 1 — Detect: SIFT / ORB keypoints in each image.
• Step 2 — Match: [Link]() + Lowe's ratio test.
• Step 3 — Estimate H: [Link](src_pts, dst_pts, [Link]).
• Step 4 — Warp & Blend: [Link](img, H, output_size).
• Overlap needed: 20–30 % between adjacent photos for reliable feature matches.
• Limitations: Strong illumination changes and repetitive textures cause false
matches and stitching artifacts.

Common Midterm Pitfalls — Week 5

• Harris IS rotation-invariant but NOT scale-invariant — window size is fixed.
• SIFT's 128-D vector = 4 × 4 × 8 (sub-regions × orientation bins). Don't confuse with
16 sub-regions × 8 bins = 128.
• Lowe's ratio test: threshold on distance RATIO d1/d2, not on absolute distance d1.
• The structure tensor M's eigenvalues relate to gradient strength — NOT to position
or scale.
• DoG ≈ Laplacian of Gaussian (LoG) — SIFT uses DoG for computational efficiency.
• [Link]() requires a float32 grayscale input, NOT uint8.
 • Homography requires ≥ 4 point correspondences; RANSAC is used to handle outlier
matches robustly.
• des from [Link]() is a (N × 128) float32 NumPy array — NOT a list
of keypoints.

References: Lowe, D.G. (2004). Distinctive Image Features from Scale-Invariant Keypoints. IJCV. | Harris, C. &
Stephens, M. (1988). A Combined Corner and Edge Detector. Alvey Vision Conference. | OpenCV
Documentation: Feature Detection & Description.