8  Edges, Corners, and Local Features

Edges, corners, and local features are the first bridge from raw pixel arrays to geometric computer vision. An edge is a local discontinuity or rapid change. A corner is a local two-dimensional change that can be localized in both image directions. A local feature is a stable, repeatable, and describable image structure that can be detected, compared, and matched across images. This chapter develops these objects from calculus, linear algebra, statistics, and optimization, with a view toward both classical feature pipelines and modern learned vision systems.

8.1 Learning Goals

After reading this chapter, students should be able to:

1. define edges using image derivatives and local intensity models;
2. explain why smoothing is necessary before numerical differentiation;
3. compute gradient magnitude and orientation from finite differences or derivative filters;
4. describe the Canny-style edge detection pipeline mathematically;
5. explain the aperture problem and why corners are more localizable than edges;
6. derive the structure tensor and interpret its eigenvalues;
7. compare Harris, Shi–Tomasi, and related corner scores;
8. explain scale-space feature detection and why scale matters;
9. describe a SIFT-style local descriptor as a normalized histogram of local gradient orientations;
10. use descriptor distances, nearest-neighbor matching, and the ratio test;
11. connect handcrafted local features with learned local features and early layers of deep vision models;
12. design Python experiments for edges, corners, descriptors, matching, and robustness.

8.2 7.1 From Local Measurements to Visual Primitives

Chapters 3–6 developed images as sampled functions and local operators. In this chapter we use those tools to construct visual primitives. A visual primitive is a local image-derived object that is more structured than a pixel but less semantic than an object class.

Examples include:

• an edge point;
• an edge orientation;
• a corner point;
• a blob center and scale;
• a local descriptor vector;
• a keypoint match between two images.

The main mathematical idea is that local image structure can be inferred from the behavior of derivatives inside a small neighborhood.

Let

\[ I:\Omega\subset \mathbb{R}^2\to \mathbb{R} \]

be a grayscale image. A local feature detector is a map of the form

\[ D(I)=\{(x_k,s_k,\theta_k,r_k): k=1,\dots,K\}, \]

where \(x_k\in \Omega\) is a location, \(s_k>0\) is a scale, \(\theta_k\) is an orientation, and \(r_k\) is a response score. A descriptor map then assigns a vector

\[ \phi_k = \Phi(I,x_k,s_k,\theta_k)\in \mathbb{R}^d. \]

The detector answers where stable local structures occur. The descriptor answers what local pattern occurs near those structures.

A classical feature pipeline can be summarized as

\[ \text{image} \longrightarrow \text{derivatives} \longrightarrow \text{responses} \longrightarrow \text{keypoints} \longrightarrow \text{descriptors} \longrightarrow \text{matches}. \]

A modern learned feature pipeline replaces some fixed maps with learned maps but often preserves the same conceptual structure.

8.3 7.2 Edges as Rapid Change

An edge is an image location where intensity changes rapidly across one direction. In a continuous image, the gradient is

\[ \nabla I(x,y) = \begin{bmatrix} I_x(x,y)\\ I_y(x,y) \end{bmatrix}. \]

The gradient points in the direction of greatest local increase. The gradient magnitude is

\[ \|\nabla I(x,y)\|_2 = \sqrt{I_x(x,y)^2+I_y(x,y)^2}, \]

and the gradient orientation is

\[ \theta(x,y)=\operatorname{atan2}(I_y(x,y),I_x(x,y)). \]

A simple mathematical edge detector is

\[ E_\tau(I) = \{(x,y): \|\nabla I(x,y)\|_2 > \tau\}, \]

where \(\tau>0\) is a threshold.

This definition captures the idea of large local change, but it is incomplete. In practice, derivative estimates are noisy, edges should be thin, and thresholds should not break long meaningful contours. These issues motivate smoothing, non-maximum suppression, and hysteresis.

8.3.1 Interactive: gradient magnitude and edge strength

This demo constructs a synthetic image, computes approximate derivatives, and displays the gradient magnitude. Strong gradient responses indicate likely edge locations.

8.4 7.3 A Local Taylor Model

Derivative-based edge detection can be understood through Taylor expansion. Near a point \(p=(x_0,y_0)\),

\[ I(p+h) = I(p)+\nabla I(p)^T h + O(\|h\|^2). \]

The first-order term \(\nabla I(p)^T h\) describes local linear change. Among all unit directions \(u\) with \(\|u\|_2=1\), the directional derivative is

\[ D_u I(p)=\nabla I(p)^T u. \]

By Cauchy–Schwarz,

\[ |D_u I(p)|\le \|\nabla I(p)\|_2, \]

with equality when \(u\) is parallel or antiparallel to \(\nabla I(p)\). Thus \(\|\nabla I(p)\|_2\) is the largest first-order change per unit distance.

The direction tangent to a level curve is orthogonal to the gradient. If an edge is locally a level-set transition, then the edge tangent direction is approximately

\[ t(p) = \begin{bmatrix} -I_y(p)\\ I_x(p) \end{bmatrix}. \]

This explains why gradients give both edge strength and edge orientation.

8.5 7.4 Discrete Derivative Filters

A digital image is an array \(I[i,j]\), so derivatives must be approximated. Common finite differences include

\[ D_x^+ I[i,j] = I[i,j+1]-I[i,j], \]

\[ D_x^- I[i,j] = I[i,j]-I[i,j-1], \]

and

\[ D_x^0 I[i,j]=\frac{I[i,j+1]-I[i,j-1]}{2}. \]

The corresponding \(y\)-direction differences are defined similarly.

Derivative filters can be written as convolution or cross-correlation kernels. For example, the central difference in the horizontal direction corresponds to

\[ K_x = \frac{1}{2} \begin{bmatrix} -1 & 0 & 1 \end{bmatrix}. \]

The vertical central difference is

\[ K_y = \frac{1}{2} \begin{bmatrix} -1\\ 0\\ 1 \end{bmatrix}. \]

Sobel filters combine differentiation with smoothing:

\[ S_x= \begin{bmatrix} -1&0&1\\ -2&0&2\\ -1&0&1 \end{bmatrix}, \qquad S_y= \begin{bmatrix} -1&-2&-1\\ 0&0&0\\ 1&2&1 \end{bmatrix}. \]

The Sobel \(x\)-filter is separable:

\[ S_x = \begin{bmatrix}1\\2\\1\end{bmatrix} \begin{bmatrix}-1&0&1\end{bmatrix}. \]

Thus it smooths vertically and differentiates horizontally.

8.6 7.5 Noise and Differentiation

Differentiation amplifies high-frequency noise. Suppose an observed one-dimensional signal is

\[ Y_i=f_i+\varepsilon_i, \qquad \varepsilon_i\stackrel{\text{iid}}{\sim}(0,\sigma^2). \]

The forward difference estimator is

\[ \widehat f'_i=Y_{i+1}-Y_i. \]

The noise part is \(\varepsilon_{i+1}-\varepsilon_i\), whose variance is

\[ \operatorname{Var}(\varepsilon_{i+1}-\varepsilon_i) = \operatorname{Var}(\varepsilon_{i+1})+\operatorname{Var}(\varepsilon_i) =2\sigma^2. \]

Thus differencing increases noise variance. The central difference

\[ \frac{Y_{i+1}-Y_{i-1}}{2} \]

has noise variance \(\sigma^2/2\), but still responds strongly to high-frequency noise. A standard solution is to smooth first and differentiate second.

Let \(G_\sigma\) be a Gaussian kernel. Then the smoothed image is

\[ I_\sigma = G_\sigma * I. \]

Derivative estimates are computed as

\[ I_{\sigma,x}=\partial_x(G_\sigma*I) =(\partial_xG_\sigma)*I, \]

and similarly for \(I_{\sigma,y}\). The equality follows from the derivative-convolution identity under suitable smoothness and boundary assumptions. This is the mathematical basis of Gaussian derivative filters.

8.7 7.6 Scale-Space Derivatives

The Gaussian-smoothed image \(I_\sigma=G_\sigma*I\) depends on scale \(\sigma\). Small \(\sigma\) reveals fine details and noise. Large \(\sigma\) reveals coarse structures.

A scale-space edge strength is

\[ M_\sigma(x,y)=\sqrt{I_{\sigma,x}(x,y)^2+I_{\sigma,y}(x,y)^2}. \]

Scale matters because an edge is not only a location. It is also a phenomenon observed at a certain resolution. A crack in a road, the boundary of a lane marking, and the boundary of the road itself may all appear as edges at different scales.

For scale-normalized derivatives, one often uses

\[ \sigma^m \partial^m I_\sigma, \]

where \(m\) is the derivative order. Scale normalization helps compare responses across different values of \(\sigma\).

8.8 7.7 Non-Maximum Suppression

Thresholding the gradient magnitude gives thick edges. To obtain thin edge curves, we keep only local maxima of edge strength in the gradient direction.

Let

\[ g(p)=\nabla I_\sigma(p), \qquad n(p)=\frac{g(p)}{\|g(p)\|_2}. \]

The point \(p\) is a candidate edge point if

\[ M_\sigma(p)\ge M_\sigma(p+t n(p)) \quad \text{and}\quad M_\sigma(p)\ge M_\sigma(p-t n(p)) \]

for small \(t>0\). In a discrete image, the direction \(n(p)\) is quantized or interpolated.

This step is geometric: it selects ridge points of the gradient magnitude surface in the direction perpendicular to the edge.

8.9 7.8 Hysteresis Thresholding

A single threshold is unstable. If \(\tau\) is too high, meaningful weak edges disappear. If \(\tau\) is too low, noise appears as edges. Hysteresis uses two thresholds:

\[ \tau_{\text{high}}>\tau_{\text{low}}>0. \]

Strong edge points satisfy

\[ M_\sigma(p)>\tau_{\text{high}}. \]

Weak candidate edge points satisfy

\[ \tau_{\text{low}}<M_\sigma(p)\le \tau_{\text{high}}. \]

A weak point is kept if it is connected to a strong point through a chain of weak candidate points. This introduces a global connectivity condition into an otherwise local edge detector.

8.10 7.9 The Canny-Style Pipeline

A Canny-style edge detector contains four mathematical operations:

1. smooth the image: \(I_\sigma=G_\sigma*I\);
2. compute derivatives: \(I_{\sigma,x}\) and \(I_{\sigma,y}\);
3. compute magnitude and orientation:

\[ M_\sigma=\sqrt{I_{\sigma,x}^2+I_{\sigma,y}^2}, \qquad \theta=\operatorname{atan2}(I_{\sigma,y},I_{\sigma,x}); \]

4. apply non-maximum suppression and hysteresis thresholding.

8.10.1 Interactive: smoothing scale and edge detection

This demo compares gradient magnitude after different Gaussian smoothing scales. Larger scales suppress noise but also move or blur fine edge structures.

The important applied-mathematics lesson is that edge detection is not just differentiation. It is a full pipeline with regularization, local geometry, discrete approximation, and decision rules.

8.11 7.10 Edges and the Aperture Problem

A local edge gives strong information in one direction but weak information in the tangent direction. Consider a small patch containing a straight edge. Moving the patch along the edge tangent may produce almost no change, while moving across the edge produces a large change.

This is the aperture problem: through a small window, motion or localization along an edge is ambiguous.

Mathematically, suppose local image variation is approximately

\[ I(p+h)-I(p)\approx \nabla I(p)^T h. \]

The scalar observation \(\nabla I(p)^T h\) strongly constrains only the component of \(h\) parallel to \(\nabla I(p)\). The component orthogonal to \(\nabla I(p)\) is poorly constrained.

Corners are more stable because they vary in two independent directions.

8.12 7.11 Corners as Two-Directional Change

A corner is a local structure where small shifts in any direction change the patch significantly. Let \(W\) be a local window and consider the shifted-window difference

\[ E(u,v) = \sum_{(x,y)\in W} w(x,y) \left[I(x+u,y+v)-I(x,y)\right]^2, \]

where \(w\) is a nonnegative window function, often Gaussian.

Using Taylor expansion,

\[ I(x+u,y+v)-I(x,y) \approx I_x(x,y)u+I_y(x,y)v. \]

Therefore

\[ E(u,v) \approx \sum_{(x,y)\in W} w(x,y) \left(I_xu+I_yv\right)^2. \]

Writing \(h=(u,v)^T\), this becomes

\[ E(h) \approx h^T M h, \]

where

\[ M = \sum_{(x,y)\in W} w(x,y) \begin{bmatrix} I_x^2 & I_xI_y\\ I_xI_y & I_y^2 \end{bmatrix}. \]

The matrix \(M\) is called the structure tensor, second-moment matrix, or local autocorrelation matrix.

8.13 7.12 The Structure Tensor

At each location, define

\[ M_\sigma(p) = G_\rho * \begin{bmatrix} I_{\sigma,x}^2 & I_{\sigma,x}I_{\sigma,y}\\ I_{\sigma,x}I_{\sigma,y} & I_{\sigma,y}^2 \end{bmatrix}(p). \]

Here \(\sigma\) is the derivative scale and \(\rho\) is the integration scale. The derivative scale controls how derivatives are estimated. The integration scale controls the neighborhood over which derivative evidence is pooled.

Since \(M_\sigma(p)\) is symmetric positive semidefinite, it has eigenvalues

\[ \lambda_1(p)\ge \lambda_2(p)\ge 0. \]

The local interpretation is:

• flat region: \(\lambda_1\approx 0\), \(\lambda_2\approx 0\);
• edge: \(\lambda_1\) large, \(\lambda_2\approx 0\);
• corner: \(\lambda_1\) large and \(\lambda_2\) large.

This classification follows from the quadratic form

\[ E(h)\approx h^T M h. \]

If both eigenvalues are large, every nonzero small shift produces large change. That is exactly the localizability condition for a corner.

8.13.1 Interactive: structure tensor eigenvalues

This demo shows synthetic patches and the corresponding structure-tensor eigenvalue interpretation: flat, edge, and corner.

8.14 7.13 Harris Corner Score

The Harris corner detector uses the determinant and trace of \(M\):

\[ \det(M)=\lambda_1\lambda_2, \qquad \operatorname{tr}(M)=\lambda_1+\lambda_2. \]

The Harris response is

\[ R = \det(M)-k\operatorname{tr}(M)^2, \]

where \(k\) is usually a small positive constant, often around \(0.04\) to \(0.06\) in applications.

In eigenvalue coordinates,

\[ R = \lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2. \]

The score is positive when both eigenvalues are sufficiently large and comparable. It is negative when one eigenvalue dominates, as in an edge.

NoteWhy determinant and trace?

The determinant measures two-dimensional change. It is large only when both eigenvalues are large. The trace measures total change. The penalty \(k\operatorname{tr}(M)^2\) suppresses edge-like regions where one eigenvalue is large but the other is small.

8.15 7.14 Shi–Tomasi Corner Score

The Shi–Tomasi score uses the smaller eigenvalue:

\[ R_{\text{ST}}=\min(\lambda_1,\lambda_2)=\lambda_2. \]

A point is accepted as a corner if

\[ \lambda_2>\tau. \]

This directly encodes the condition that the patch changes significantly in every direction. Since

\[ \min_{\|h\|_2=1} h^T M h = \lambda_2, \]

\(\lambda_2\) is the worst-case local change over all unit shifts.

The Harris score and Shi–Tomasi score often select similar points, but the Shi–Tomasi score has a particularly clean variational interpretation.

8.16 7.15 Non-Maximum Suppression for Corners

A corner response produces a scalar image \(R[i,j]\). To obtain a set of keypoints, we keep locations that are local maxima:

\[ R[i,j] \ge R[i+a,j+b] \quad \text{for all } (a,b)\in \{-r,\dots,r\}^2. \]

Then we threshold by response strength. This converts a dense response map into a sparse set of keypoints.

The procedure is simple but important. Without non-maximum suppression, a single physical corner can generate many nearby candidate points.

8.17 7.16 Harris Score in the Eigenvalue Plane

The eigenvalues of the structure tensor provide a two-dimensional diagnostic. The Harris score is

\[ R(\lambda_1,\lambda_2) =\lambda_1\lambda_2-k(\lambda_1+\lambda_2)^2. \]

When \(\lambda_2\ll \lambda_1\), the determinant is small relative to the trace penalty. When both eigenvalues are large, the determinant can dominate.

8.17.1 Interactive: Harris and Shi–Tomasi scores

This demo plots corner scores as functions of the structure-tensor eigenvalues. Flat regions, edges, and corners occupy different parts of the eigenvalue plane.

8.18 7.17 Subpixel Localization

Detected keypoints are initially located on the pixel grid. Many applications benefit from subpixel localization. Suppose \(R(x,y)\) is a smooth approximation of the response near a discrete maximum. A second-order Taylor expansion around \(p_0\) gives

\[ R(p_0+h) \approx R(p_0)+g^T h+\frac{1}{2}h^T Hh, \]

where

\[ g=\nabla R(p_0), \qquad H=\nabla^2 R(p_0). \]

If \(H\) is negative definite, the local maximizer satisfies

\[ g+Hh=0, \]

so

\[ h^*=-H^{-1}g. \]

The refined keypoint is \(p_0+h^*\). This is the same quadratic approximation principle used throughout numerical optimization.

8.19 7.18 Repeatability and Stability

A local feature detector should be repeatable: the same physical point should be detected across different images of the same scene. A descriptor should be discriminative: different physical points should usually have different descriptors.

Important transformations include:

• translation;
• rotation;
• change of scale;
• illumination change;
• viewpoint change;
• blur;
• noise;
• partial occlusion.

A detector \(D\) is approximately equivariant to a transformation \(T\) if

\[ D(TI)\approx T D(I). \]

A descriptor \(\Phi\) is approximately invariant to a transformation \(T\) if corresponding local patches have similar descriptors:

\[ \Phi(TI, T x)\approx \Phi(I,x). \]

This distinction is important:

• locations should transform with the image;
• descriptor values should remain comparable after accounting for location, scale, and orientation.

8.20 7.19 Scale-Space Keypoints

A feature that is stable at one scale may disappear at another. Scale-space keypoint detectors search over both position and scale:

\[ (x^*,y^*,\sigma^*) = \operatorname*{arg\,extremum}_{x,y,\sigma} R(x,y,\sigma). \]

For blob-like structures, a common response is the scale-normalized Laplacian:

\[ L(x,y,\sigma) = \sigma^2 \left(I_{\sigma,xx}(x,y)+I_{\sigma,yy}(x,y)\right). \]

The factor \(\sigma^2\) normalizes the second derivative across scales.

The Difference of Gaussians approximates the scale-normalized Laplacian:

\[ D(x,y,\sigma) = (G_{k\sigma}-G_\sigma)*I(x,y). \]

For nearby scales, this is proportional to \(\sigma^2\Delta(G_\sigma*I)\) up to a scale-dependent constant. This approximation is one reason Difference-of-Gaussians detectors are computationally attractive.

8.21 7.20 Orientation Assignment

To make descriptors rotation invariant, each keypoint can be assigned a dominant orientation. Around a keypoint \((x_k,y_k)\) at scale \(\sigma_k\), compute local gradients

\[ m(x,y)=\sqrt{I_x(x,y)^2+I_y(x,y)^2}, \qquad \theta(x,y)=\operatorname{atan2}(I_y(x,y),I_x(x,y)). \]

A weighted orientation histogram is then formed:

\[ H_b = \sum_{(x,y)\in W_k} w_k(x,y)m(x,y)\,\mathbf{1}\{\theta(x,y)\in B_b\}, \]

where \(B_b\) is the \(b\)th orientation bin and \(w_k\) is a spatial window. The dominant orientation is

\[ \theta_k=\operatorname*{arg\,max}_{b} H_b. \]

The local coordinate frame is then rotated by \(-\theta_k\) before computing the descriptor. This is how a descriptor can become approximately invariant to in-plane rotation.

8.22 7.21 Local Descriptors

A local descriptor converts a patch into a vector:

\[ \phi=\Phi(I,x,s,\theta)\in \mathbb{R}^d. \]

Good descriptors should be:

• stable under small image changes;
• discriminative across different local structures;
• robust to illumination changes;
• efficient to compute and compare.

A very simple descriptor is the vectorized normalized patch:

\[ \phi = \frac{p-\bar p\mathbf{1}}{\|p-\bar p\mathbf{1}\|_2+\epsilon}, \]

where \(p\in\mathbb{R}^{m^2}\) is a patch vector. This descriptor is invariant to additive brightness shifts and approximately invariant to contrast scaling.

However, raw patches are sensitive to small translations, rotations, and viewpoint changes. Gradient-orientation histograms are more stable.

8.23 7.22 SIFT-Style Gradient Histogram Descriptors

A SIFT-style descriptor divides a local patch into spatial cells. In each cell, it accumulates a histogram of gradient orientations. A common SIFT descriptor uses a \(4\times 4\) grid of cells and 8 orientation bins, giving

\[ d=4\cdot 4\cdot 8=128 \]

dimensions.

Abstractly, for cell \(c\) and orientation bin \(b\),

\[ \phi_{c,b} = \sum_{(x,y)\in \text{cell } c} w(x,y)m(x,y)\,\eta_b(\theta(x,y)), \]

where \(\eta_b\) is a soft binning function. The full vector is normalized:

\[ \phi \leftarrow \frac{\phi}{\|\phi\|_2+\epsilon}. \]

Often the vector is clipped and renormalized to reduce the influence of very large gradients.

8.23.1 Interactive: local orientation histogram descriptor

This demo shows how local gradients are accumulated into orientation bins. The histogram is a compact descriptor of local shape.

8.24 7.23 Matching Descriptors

Suppose image \(A\) has descriptors

\[ \phi_1^A,\dots,\phi_m^A \]

and image \(B\) has descriptors

\[ \phi_1^B,\dots,\phi_n^B. \]

The simplest matching rule uses nearest neighbors:

\[ j^*(i) = \operatorname*{arg\,min}_{1\le j\le n} \|\phi_i^A-\phi_j^B\|_2. \]

A match is accepted if the distance is small enough. But some descriptors are ambiguous. The ratio test compares the nearest and second-nearest distances:

\[ \frac{d_1}{d_2}<\alpha, \qquad 0<\alpha<1. \]

Here \(d_1\) is the nearest-neighbor distance and \(d_2\) is the second-nearest-neighbor distance. A small ratio means the best match is much better than the next alternative.

This is a statistical idea: a match is more credible when there is a strong margin between the best explanation and the second-best explanation.

8.25 7.24 Matching, Geometry, and Outliers

Descriptor matching produces candidate correspondences

\[ (x_i^A,x_{j(i)}^B). \]

Some matches are correct, and some are outliers. Later chapters on camera geometry will show how to estimate geometric transformations from these correspondences.

For example, if two images are related by a planar projective transformation, then corresponding homogeneous points satisfy

\[ x_i^B \sim H x_i^A, \]

where \(H\in\mathbb{R}^{3\times 3}\) is a homography. If the images come from two views of a 3D scene, correspondences satisfy the epipolar constraint

\[ (x_i^B)^T F x_i^A=0. \]

Feature detection and description are therefore not isolated topics. They provide the measurements used by higher-level geometric estimation.

8.26 7.25 Statistical Viewpoint: Detection as Hypothesis Testing

A simple edge detector can be viewed as a hypothesis test. At a pixel \(p\), define

\[ T(p)=\|\nabla I_\sigma(p)\|_2. \]

We may compare

\[ H_0: \text{no edge at }p \qquad \text{versus}\qquad H_1: \text{edge at }p. \]

Thresholding \(T(p)\) controls a tradeoff between false positives and false negatives. If the noise distribution and local model are known, one can derive thresholds from error probabilities. In practice, natural images violate simple noise assumptions, so thresholds are often tuned, learned, or adapted.

Similarly, corner detection can be viewed as testing whether the smaller structure-tensor eigenvalue is above noise:

\[ H_0:\lambda_2\le \tau_0, \qquad H_1:\lambda_2>\tau_0. \]

The statistical viewpoint clarifies why smoothing, normalization, and response calibration matter.

8.27 7.26 Statistical Viewpoint: Descriptors as Random Vectors

A descriptor is a random vector because the image is random:

\[ \Phi=\Phi(I,X,S,\Theta)\in\mathbb{R}^d. \]

For a correct match, two descriptors should be close:

\[ \|\Phi_A-\Phi_B\|_2 \text{ small}. \]

For an incorrect match, they should usually be farther apart. This suggests modeling descriptor distances using two distributions:

\[ D_{\text{same}}=\|\Phi_A-\Phi_B\|_2\mid \text{same physical point}, \]

\[ D_{\text{diff}}=\|\Phi_A-\Phi_B\|_2\mid \text{different physical point}. \]

Good descriptors make these distributions well separated.

The ratio test can also be interpreted as a margin criterion. It does not only ask whether the nearest descriptor is close. It asks whether it is clearly closer than the next best candidate.

8.28 7.27 Optimization Viewpoint

Many local feature computations can be written as optimization problems.

8.28.1 Edge localization

Non-maximum suppression searches for local maxima of \(M_\sigma\) along gradient directions:

\[ p^* = \operatorname*{arg\,max}_{t\in[-\epsilon,\epsilon]} M_\sigma(p+t n(p)). \]

8.28.2 Corner localization

Subpixel refinement solves a local quadratic maximization:

\[ h^*=-H^{-1}g. \]

8.28.3 Descriptor matching

Nearest-neighbor matching solves

\[ \min_j \|\phi_i^A-\phi_j^B\|_2^2. \]

8.28.4 Learned local features

Modern systems may learn detector and descriptor maps by minimizing contrastive or matching losses. A simple contrastive loss for pair labels \(y\in\{0,1\}\) is

\[ \ell(\phi_a,\phi_b,y) = y\|\phi_a-\phi_b\|_2^2 + (1-y)\max\{0,m-\|\phi_a-\phi_b\|_2\}^2. \]

Here \(y=1\) means the pair matches and \(y=0\) means it does not match.

8.29 7.28 Learned Local Features

Classical descriptors are manually designed. Learned local features replace parts of the pipeline with neural networks.

A learned detector may output a score map

\[ R_\theta(I)\in\mathbb{R}^{H\times W}. \]

A learned descriptor network may output a dense descriptor field

\[ F_\theta(I)\in\mathbb{R}^{H\times W\times d}. \]

At location \((i,j)\), the descriptor is

\[ \phi_{i,j}=F_\theta(I)[i,j,:]. \]

A typical objective encourages matching descriptors to be close and nonmatching descriptors to be separated. Learned features can be more robust than handcrafted features when trained on diverse data, but they require data, supervision or self-supervision, and careful evaluation.

The mathematical continuity is important: even modern local features still rely on locality, invariance, equivariance, stability, and discriminative embeddings.

8.30 7.29 Relation to CNNs

The early layers of a CNN often learn filters that resemble edge and texture detectors. A first convolutional layer computes

\[ A_k[i,j] = \sigma\left(b_k+\sum_{c=1}^C\sum_{a,b}W_{k,c,a,b}I_c[i+a,j+b]\right). \]

This is a learned multi-channel local operator. The first-layer filters often behave like oriented derivatives, color-opponent filters, or blob filters. Deeper layers compose these into higher-level patterns.

Thus classical feature detection and CNNs are not unrelated. Classical vision explicitly designs local measurements. CNNs learn local measurements from data.

8.31 7.30 Relation to Vision Transformers

Vision transformers begin by partitioning an image into patches. Each patch is embedded into a vector:

\[ z_i=E\operatorname{vec}(P_i)+p_i. \]

This is a learned patch descriptor. Self-attention then compares and mixes patch descriptors:

\[ \operatorname{Attention}(Q,K,V) = \operatorname{softmax}\left(\frac{QK^T}{\sqrt{d}}\right)V. \]

Classical local descriptors compare patches using fixed distances. Transformers compare learned token embeddings using learned attention scores. The mathematical theme is again representation, similarity, and invariance.

8.32 7.31 AI Component: Using AI to Audit Local Feature Explanations

AI tools can be useful for learning this chapter, but they often blur important distinctions. When using AI assistance, ask it to be precise about the following:

1. Is the operation continuous or discrete?
2. Is the method using convolution or cross-correlation?
3. Is the gradient computed before or after smoothing?
4. What is the derivative scale and what is the integration scale?
5. Is a score equivariant or invariant?
6. Is the descriptor normalized?
7. What failure modes occur under blur, noise, rotation, or viewpoint change?

A good AI-assisted workflow is:

\[ \text{ask for explanation} \longrightarrow \text{translate into equations} \longrightarrow \text{check assumptions} \longrightarrow \text{test with code}. \]

8.33 7.32 Python Example: Edges from Finite Differences

import numpy as np
import matplotlib.pyplot as plt

n = 128
y, x = np.mgrid[-1:1:complex(n), -1:1:complex(n)]
img = 0.2 * x + 0.8 * ((x**2 + y**2) < 0.35**2)
img += 0.6 * ((np.abs(x + 0.35) < 0.18) & (np.abs(y - 0.30) < 0.18))
img += 0.05 * np.random.default_rng(7).normal(size=img.shape)

Ix = np.zeros_like(img)
Iy = np.zeros_like(img)
Ix[:, 1:-1] = (img[:, 2:] - img[:, :-2]) / 2
Iy[1:-1, :] = (img[2:, :] - img[:-2, :]) / 2
mag = np.sqrt(Ix**2 + Iy**2)

fig, axes = plt.subplots(1, 3, figsize=(12, 4))
axes[0].imshow(img, cmap="gray")
axes[0].set_title("image")
axes[1].imshow(Ix, cmap="gray")
axes[1].set_title("horizontal derivative")
axes[2].imshow(mag, cmap="magma")
axes[2].set_title("gradient magnitude")
for ax in axes:
    ax.axis("off")
plt.show()

8.34 7.33 Python Example: Gaussian Smoothing Before Differentiation

import numpy as np
import matplotlib.pyplot as plt
from scipy.ndimage import gaussian_filter

rng = np.random.default_rng(12)
n = 160
y, x = np.mgrid[-1:1:complex(n), -1:1:complex(n)]
clean = ((x > -0.25) & (x < 0.45) & (y > -0.35) & (y < 0.35)).astype(float)
noisy = clean + 0.25 * rng.normal(size=clean.shape)

fig, axes = plt.subplots(2, 4, figsize=(13, 6))
for col, sigma in enumerate([0, 1, 2, 4]):
    if sigma == 0:
        smoothed = noisy
        title = "no smoothing"
    else:
        smoothed = gaussian_filter(noisy, sigma=sigma)
        title = f"sigma={sigma}"
    Iy, Ix = np.gradient(smoothed)
    mag = np.sqrt(Ix**2 + Iy**2)
    axes[0, col].imshow(smoothed, cmap="gray")
    axes[0, col].set_title(title)
    axes[1, col].imshow(mag, cmap="magma")
    axes[1, col].set_title("gradient magnitude")

for ax in axes.ravel():
    ax.axis("off")
plt.tight_layout()
plt.show()

8.35 7.34 Python Example: Structure Tensor and Harris Response

import numpy as np
import matplotlib.pyplot as plt
from scipy.ndimage import gaussian_filter, maximum_filter

n = 160
img = np.zeros((n, n), dtype=float)
img[35:115, 40:120] = 1.0
img[70:135, 75:140] += 0.7
img = gaussian_filter(img, sigma=1.0)

Iy, Ix = np.gradient(img)

# Integration scale for the second-moment matrix
rho = 2.0
A = gaussian_filter(Ix * Ix, sigma=rho)
B = gaussian_filter(Ix * Iy, sigma=rho)
C = gaussian_filter(Iy * Iy, sigma=rho)

k = 0.05
det = A * C - B**2
trace = A + C
R = det - k * trace**2

local_max = R == maximum_filter(R, size=9)
threshold = np.percentile(R, 99.5)
corners = local_max & (R > threshold)
ys, xs = np.nonzero(corners)

fig, axes = plt.subplots(1, 3, figsize=(12, 4))
axes[0].imshow(img, cmap="gray")
axes[0].scatter(xs, ys, s=30, facecolors="none", edgecolors="red")
axes[0].set_title("detected corners")
axes[1].imshow(det, cmap="magma")
axes[1].set_title("determinant")
axes[2].imshow(R, cmap="magma")
axes[2].set_title("Harris response")
for ax in axes:
    ax.axis("off")
plt.show()

8.36 7.35 Python Example: A Simple Orientation Histogram Descriptor

import numpy as np
import matplotlib.pyplot as plt

rng = np.random.default_rng(4)
n = 32
y, x = np.mgrid[-1:1:complex(n), -1:1:complex(n)]
patch = np.exp(-30 * (y - 0.2 * x)**2) + 0.1 * rng.normal(size=(n, n))

Iy, Ix = np.gradient(patch)
mag = np.sqrt(Ix**2 + Iy**2)
angle = np.mod(np.arctan2(Iy, Ix), 2 * np.pi)

num_bins = 8
bins = np.linspace(0, 2 * np.pi, num_bins + 1)
hist, _ = np.histogram(angle.ravel(), bins=bins, weights=mag.ravel())
hist = hist / (np.linalg.norm(hist) + 1e-12)

fig, axes = plt.subplots(1, 2, figsize=(9, 4))
axes[0].imshow(patch, cmap="gray")
axes[0].set_title("local patch")
axes[0].axis("off")
centers = 0.5 * (bins[:-1] + bins[1:])
axes[1].bar(np.arange(num_bins), hist)
axes[1].set_xlabel("orientation bin")
axes[1].set_ylabel("normalized weight")
axes[1].set_title("orientation histogram")
plt.show()

8.37 7.36 Python Example: Descriptor Matching and Ratio Test

import numpy as np

rng = np.random.default_rng(10)
num_true = 40
d = 64

# Synthetic descriptors for image A
A = rng.normal(size=(num_true, d))
A = A / np.linalg.norm(A, axis=1, keepdims=True)

# Matching descriptors in image B plus distractors
B_true = A + 0.12 * rng.normal(size=A.shape)
B_true = B_true / np.linalg.norm(B_true, axis=1, keepdims=True)
B_false = rng.normal(size=(120, d))
B_false = B_false / np.linalg.norm(B_false, axis=1, keepdims=True)
B = np.vstack([B_true, B_false])

# Pairwise distances
D = np.linalg.norm(A[:, None, :] - B[None, :, :], axis=2)
order = np.argsort(D, axis=1)
nearest = order[:, 0]
second = order[:, 1]
d1 = D[np.arange(num_true), nearest]
d2 = D[np.arange(num_true), second]
ratio = d1 / d2

accepted = ratio < 0.8
num_accepted = accepted.sum()
num_correct = np.sum(nearest[accepted] == np.arange(num_true)[accepted])

print("accepted matches:", num_accepted)
print("correct accepted matches:", num_correct)
print("precision among accepted:", num_correct / max(num_accepted, 1))

8.38 7.37 TensorFlow Example: A Learned Local Descriptor Field

import tensorflow as tf

# A small network that maps an image to a dense descriptor field.
# This is not a full feature matcher; it is a minimal architectural sketch.
inputs = tf.keras.Input(shape=(None, None, 1))
x = tf.keras.layers.Conv2D(32, 3, padding="same", activation="relu")(inputs)
x = tf.keras.layers.Conv2D(64, 3, padding="same", activation="relu")(x)
x = tf.keras.layers.Conv2D(64, 3, padding="same", activation="relu")(x)
desc = tf.keras.layers.Conv2D(32, 1, padding="same", activation=None)(x)

# Normalize descriptor vectors at every pixel.
desc = tf.math.l2_normalize(desc, axis=-1)
model = tf.keras.Model(inputs, desc)

print(model.summary())

This model computes a dense map

\[ F_\theta(I)\in \mathbb{R}^{H\times W\times 32}, \]

where each pixel has a 32-dimensional descriptor. A full training pipeline would use matching or contrastive losses on corresponding and noncorresponding locations.

8.39 7.38 AI-Assisted Study Prompts

Use these prompts as structured study activities.

8.39.1 Prompt 1: Derivative scale versus integration scale

Ask an AI tool:

Explain the difference between derivative scale and integration scale in the structure tensor. Give an example where choosing them poorly causes failure.

Then verify that the answer distinguishes \(\sigma\) in \(I_\sigma\) from \(\rho\) in the averaging of products of derivatives.

8.39.2 Prompt 2: Harris score derivation

Ask:

Derive the Harris response from the quadratic approximation of patch shift error.

Check that the derivation includes the Taylor approximation, the structure tensor, eigenvalues, determinant, and trace.

8.39.3 Prompt 3: Descriptor invariance

Ask:

Compare raw-patch descriptors and gradient-histogram descriptors in terms of invariance and stability.

Then write a mathematical summary using normalization, orientation assignment, and histogram binning.

8.39.4 Prompt 4: Debugging a feature-matching pipeline

Ask:

My feature matching code gives many wrong matches. What mathematical checks should I perform?

A good answer should mention descriptor normalization, ratio test, symmetric matching, geometric verification, repeated textures, scale mismatch, and viewpoint change.

8.40 7.39 Common Misconceptions

8.40.1 Misconception 1: Edges are just large pixel differences

Large pixel differences are a crude signal, but edge detection also requires smoothing, derivative estimation, localization, thresholding, and often connectivity.

8.40.2 Misconception 2: Corners are high-gradient points

A high-gradient point may be an edge. A corner requires strong variation in two independent directions, which is why the smaller eigenvalue of the structure tensor matters.

8.40.3 Misconception 3: A descriptor should memorize a patch

A descriptor should keep task-relevant information while discarding nuisance variation. Good descriptors are not raw memory; they are structured summaries.

8.40.4 Misconception 4: Classical features are obsolete

Modern learned features are powerful, but the mathematical ideas of locality, stability, invariance, and matching still organize the problem. Classical features remain useful for understanding, debugging, and some geometry pipelines.

8.41 7.40 Exercises

8.41.1 Conceptual Exercises

1. Explain why smoothing before differentiating is usually necessary.
2. Describe the difference between gradient direction and edge tangent direction.
3. Explain why a straight edge is hard to localize along its tangent direction.
4. Explain why corners are better keypoints than generic edge points.
5. Compare translation equivariance of keypoint locations with invariance of descriptors.
6. Explain why local descriptors are useful for image matching.
7. Give an example of a visual pattern that produces ambiguous feature matches.
8. Explain the statistical meaning of the ratio test.

8.41.2 Mathematical Exercises

1. Use Taylor expansion to derive the approximation \[ E(h)\approx h^T M h. \]
2. Prove that the structure tensor is positive semidefinite.
3. Show that \[ \min_{\|h\|_2=1}h^TMh=\lambda_2 \] for a \(2\times2\) symmetric positive semidefinite matrix with eigenvalues \(\lambda_1\ge\lambda_2\).
4. Express the Harris response in terms of eigenvalues.
5. Determine for which ratios \(r=\lambda_2/\lambda_1\) the Harris score is positive when \(\lambda_1>0\).
6. Derive the noise variance of a forward-difference derivative estimator under iid additive noise.
7. Show that the Sobel operator is separable.
8. Derive the subpixel refinement formula \(h^*=-H^{-1}g\) from a quadratic Taylor approximation.
9. Show that normalizing a patch by subtracting its mean makes it invariant to additive brightness shifts.
10. Explain why the Euclidean distance between unit-normalized descriptors is related to cosine similarity.

8.41.3 Python Exercises

1. Implement gradient magnitude using finite differences.
2. Implement Sobel edge detection from scratch.
3. Compare edge maps for different Gaussian smoothing scales.
4. Implement non-maximum suppression for gradient magnitude.
5. Implement the structure tensor and visualize \(\lambda_1\) and \(\lambda_2\).
6. Implement Harris corner detection and local non-maximum suppression.
7. Implement the Shi–Tomasi score and compare selected points with Harris points.
8. Build a simple orientation-histogram descriptor.
9. Simulate descriptor matching and study the ratio test as the noise level changes.
10. Use a small CNN to produce dense descriptors and visualize descriptor similarity across an image.

8.41.4 AI-Assisted Exercises

1. Ask an AI tool to explain Canny edge detection. Rewrite the answer as a sequence of mathematical maps.
2. Ask an AI tool to compare Harris and Shi–Tomasi. Check whether it correctly uses eigenvalues of the structure tensor.
3. Ask an AI tool to generate code for Harris corner detection. Identify whether it includes smoothing, derivative estimation, integration scale, thresholding, and non-maximum suppression.
4. Ask an AI tool to explain SIFT. Extract from the answer the detector, orientation assignment, descriptor construction, and matching rule.
5. Ask an AI tool to compare handcrafted local features and learned local features. Rewrite the answer using the language of equivariance, invariance, and representation learning.

8.42 7.41 Summary

This chapter developed edges, corners, and local features as mathematical tools for local visual representation. The main ideas are:

• edges are locations of strong local change;
• gradients provide edge strength and orientation;
• differentiation is noise-sensitive, so smoothing is essential;
• Canny-style edge detection combines smoothing, derivatives, non-maximum suppression, and hysteresis;
• corners are points with strong variation in two independent directions;
• the structure tensor summarizes local gradient geometry;
• Harris and Shi–Tomasi scores are functions of the structure-tensor eigenvalues;
• scale-space methods detect structures across resolution levels;
• local descriptors summarize patches using normalized features such as gradient histograms;
• descriptor matching is a nearest-neighbor problem with ambiguity control;
• learned local features generalize handcrafted features through trainable detector and descriptor maps.

The next chapter moves from local features to segmentation. Instead of detecting sparse points or curves, segmentation assigns structure to regions or pixels across the image.

8.43 Notes and References

Classical discussions of edges, gradients, corners, and local features appear in standard computer vision and image processing references such as Szeliski (2022) and Gonzalez and Woods (2018). The Canny edge detector is a foundational method for edge detection (Canny 1986). The Harris detector introduced a widely used structure-tensor corner response (Harris and Stephens 1988). The Shi–Tomasi score gives a clean eigenvalue-based criterion for good features to track (Shi and Tomasi 1994). SIFT is a landmark local feature system based on scale-space extrema and gradient-histogram descriptors (Lowe 2004).

Canny, John. 1986. “A Computational Approach to Edge Detection.” IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-8 (6): 679–98.

Gonzalez, Rafael C., and Richard E. Woods. 2018. Digital Image Processing. 4th ed. Pearson.

Harris, Chris, and Mike Stephens. 1988. “A Combined Corner and Edge Detector.” Proceedings of the Alvey Vision Conference, 147–51.

Lowe, David G. 2004. “Distinctive Image Features from Scale-Invariant Keypoints.” International Journal of Computer Vision 60 (2): 91–110.

Shi, Jianbo, and Carlo Tomasi. 1994. “Good Features to Track.” IEEE Conference on Computer Vision and Pattern Recognition, 593–600.

Szeliski, Richard. 2022. Computer Vision: Algorithms and Applications. 2nd ed. Springer. https://szeliski.org/Book/.