Feature Detection Fundamentals

A feature in classical computer vision is a compact, localized piece of image structure — typically a point (keypoint), sometimes a small region or an edge segment — selected because it can be reliably located again in another image of the same scene, and because its local appearance is distinctive enough to be matched against candidates elsewhere. This is different from "feature" in the general machine-learning sense (any input variable); here a feature is itself an output of an algorithm run over the image, chosen from millions of candidate pixel locations. Three formal properties define a good feature, and nearly every detector in the literature can be understood as an attempt to optimize them:

Repeatability. If the same 3D scene point is imaged twice — under a different viewpoint, scale, rotation, illumination, or with sensor noise — the detector should fire at the corresponding image location in both images. Formally, if $x$ is a detected feature in image $I_1$ and $T$ is the (possibly unknown) geometric/photometric transformation mapping $I_1$ to $I_2$, we want the detector applied to $I_2$ to also fire near $T(x)$. Repeatability is measured empirically as the fraction of features in one image that have a corresponding detection within some pixel tolerance in the transformed image.

Distinctiveness (saliency). The local neighborhood around the feature must contain enough information to distinguish it from other locations, both nearby and across the whole image. A feature with a highly distinctive local signature can be matched confidently by comparing descriptors; a feature that looks like a thousand other pixels (e.g., anywhere inside a flat gray wall) cannot be matched — matching becomes ambiguous or impossible. Distinctiveness is what makes the later description stage (assigning a vector to the patch) actually useful.

Locality. The feature should be defined by a small spatial neighborhood. This buys robustness to occlusion (only part of the scene needs to be visible), to clutter (background changes don't affect the feature), and to non-rigid or non-planar scene structure (local regions are closer to planar/rigid than the whole scene). Locality trades off against distinctiveness: a huge neighborhood carries more information (more distinctive) but is less local (less robust and less repeatable under perspective/occlusion change). A fourth, more practical property is efficiency: since a detector must scan every pixel (and often every scale) of every image, detection must be computable in time roughly linear in image size, using cheap local operations — this is why almost every classical detector is built from convolutions and simple pointwise arithmetic on image gradients, rather than expensive global search. The central diagnostic question a detector must answer at every pixel is: does the local neighborhood have enough two-dimensional structure to pin down its own location? This question has a clean geometric answer once we look at how image intensity changes when a small patch is shifted.

Why flat regions and edges fail

Consider a small window $W$ centered at pixel $(x, y)$, and ask how much the intensity pattern inside $W$ changes when the window is shifted by a small displacement $(u, v)$. Define the sum of squared differences (SSD) — the local autocorrelation:

where $w$ is a weighting window (uniform or Gaussian) emphasizing pixels near the center. This single function $E(u,v)$ is the conceptual seed of essentially all corner/blob detectors, and the analysis of its shape gives us the classification a good detector must perform:

• Flat region: $I$ is nearly constant in $W$. Then $E(u,v) \approx 0$ for all $(u,v)$ — the window can slide in any direction with almost no change. There is no way to localize this pixel; it is indistinguishable from its neighbors. Reject.
• Edge: $I$ varies strongly across the edge but is nearly constant along the edge direction. Then $E(u,v)$ is large for shifts across the edge but near zero for shifts along it. This is the classical aperture problem: looking through a small local window at an edge, you cannot tell how far the edge has moved along its own direction. Position along the edge is unconstrained. Reject as a point feature (edges remain useful as edge features, but not as localizable keypoints).
• Corner / blob / high-texture region: $I$ varies significantly in every direction. Then $E(u,v)$ grows quickly for shifts in all directions — the window's appearance changes no matter which way you nudge it. This is exactly the property that makes a location repeatable and precisely localizable. Accept.

This qualitative story is made quantitative by locally approximating $E(u,v)$ using a first-order (gradient) Taylor expansion of $I$, which yields a $2\times 2$ matrix — the structure tensor (also called the second-moment matrix):

built entirely from the local image gradients $I_x, I_y$ — precisely the prerequisite concept this article assumes. Then, to second order,

The eigenvalues $\lambda_1 \ge \lambda_2 \ge 0$ of $M$ tell the whole story:

This eigen-analysis is exactly the mechanism that Harris Corner Detection turns into a practical, efficient score (avoiding an explicit, costly eigendecomposition at every pixel), and it is the same structural idea that scale-space detectors extend across scale in SIFT: Scale-Invariant Features.

The generic detection pipeline

Regardless of which exact scoring function is used, every classical feature detector follows the same generic algorithmic shape: ``` ALGORITHM GenericFeatureDetector(image I, window radius r, threshold τ) ------------------------------------------------------------------ 1. Compute image gradients Ix, Iy (e.g. via Sobel convolution) 2. For every pixel p in I: Form the local structure tensor M(p) using gradients in a window of radius r around p (Gaussian-weighted) Compute a scalar "cornerness" score S(p) from M(p) (e.g. from eigenvalues, or a fast proxy — see Harris) 3. Threshold: mark p as a CANDIDATE if S(p) > τ 4. Non-maximum suppression: For each candidate p, keep it only if S(p) is the maximum among candidates in its local neighborhood (removes duplicate detections clustered on one corner) 5. Return the surviving set of keypoints {p : locally maximal, S(p) > τ} ------------------------------------------------------------------ ``` Two implementation details matter for correctness, and both are common sources of bugs:

• Gaussian weighting, not a hard box window. A uniform box window makes $M(p)$ discontinuous as pixels enter/exit the window under sub-pixel shifts, hurting repeatability. A Gaussian weight $w$ gives a smooth, rotation-invariant estimate of local structure.
• Non-maximum suppression (NMS) is not optional. Without it, a single strong corner produces a whole cluster of neighboring pixels above threshold, all describing "the same" feature — wasting computation and destroying the locality/distinctiveness of downstream matching. NMS enforces that detected features are spatially well-separated local maxima of the score.

Time complexity. Let the image have $N = HW$ pixels and let the local window used to build $M(p)$ have $O(w^2)$ pixels (a small constant, e.g. $7\times7$ or $9\times9$). Gradient computation is a fixed-size convolution: $O(N)$. Building $M(p)$ at every pixel via Gaussian-weighted sums can be implemented as a small set of separable convolutions ($I_x^2$, $I_y^2$, $I_xI_y$ each smoothed by a separable Gaussian), so this step is also $O(N \cdot w)$ using separable filtering, effectively $O(N)$ for fixed window size. Scoring is $O(1)$ per pixel, thresholding is $O(N)$, and non-maximum suppression over a fixed neighborhood is $O(N)$. Total: $O(N)$, i.e., linear in image size — essential, since a detector must run on every pixel of every frame in real-time systems like visual SLAM.

Space complexity. We must store the gradient image and the three second-moment channels, each $O(N)$, so overall space is $O(N)$, independent of the number of features actually detected.

Why $O(N)$ is the right target, and the honest tradeoff. A naive "compare every pixel's neighborhood to every other pixel's neighborhood" approach to finding distinctive regions is $O(N^2)$ or worse and is never used for detection (it belongs, in a bounded form, to the later matching stage). Locality is precisely what saves us: because the structure tensor only requires information from a small, fixed-radius window, the cost per pixel is $O(1)$ (constant window size), giving global linear-time detection. This is a direct algorithmic payoff of the locality property demanded earlier — a feature definition that required global context (e.g., "is this patch unique in the whole image?") would force at least $O(N)$ work per pixel, yielding $O(N^2)$ overall, which does not scale to megapixel images or video.

Correctness argument (informal, but precise). The claim to justify is: the eigenvalue test on $M(p)$ correctly identifies pixels where the local window's position is uniquely determined by its appearance. The Taylor expansion $E(u,v) \approx [u\ v] M [u\ v]^T$ is a quadratic form; its eigenvectors are the directions of principal curvature of the "cost of moving the window" surface, and its eigenvalues are the curvatures along those directions. A direction $d$ with eigenvalue $\lambda \approx 0$ means $E$ is flat along $d$ — shifting the window along $d$ produces (to second order) no change in appearance, so the window's position along $d$ is unrecoverable from local appearance alone; this is a formal restatement of the aperture problem. Only when both eigenvalues are large is $E(u,v)$ bowl-shaped in every direction, meaning the window's appearance changes under any small shift — which is exactly the condition for the local position to be uniquely (locally) determined by intensity. This directly justifies the flat/edge/corner classification as more than a heuristic: it is the correct second-order condition for local invertibility of "shift versus appearance change."

Honest limitations. This is a local, second-order, small-baseline argument: it says a corner is locally distinguishable under small shifts, not that it will survive large viewpoint change, scale change, or illumination change — those robustness properties require additional machinery (scale-space search, orientation normalization, illumination-invariant descriptors) that later detectors add on top of this same structure-tensor foundation. The theory also assumes locally smooth, differentiable intensity, so it degrades under heavy sensor noise unless the gradients are computed from a suitably smoothed image first.

Take a small synthetic $9\times9$ patch representing a dark square occupying the bottom-right of a bright background (a right-angle corner), and compare it against two neighboring $9\times9$ windows sampled from a pure vertical edge and from a flat sky region of the same image. Suppose (values illustrative but structurally faithful to a real Sobel-gradient computation, gradients scaled to a comparable range) the Gaussian-weighted sums over each window give:

Walking through the eigenvalues (using $\lambda = \tfrac{a+d}{2} \pm \sqrt{(\tfrac{a-d}{2})^2 + b^2}$ for $M = \begin{bmatrix}a&b\\b&d\end{bmatrix}$):

• Flat sky: $a=0.4, d=0.3, b=0.05 \Rightarrow \lambda_{1,2} \approx 0.42, 0.28$. Both eigenvalues are close to zero (relative to the corner case's ~30–40 scale) — confirms no direction of appearance change, matching intuition: sky pixels look alike wherever you nudge the window. Rejected by any reasonable threshold $\tau$.
• Vertical edge: $a=48.0, d=0.6, b=0.2 \Rightarrow \lambda_1 \approx 48.0$ (across the edge), $\lambda_2 \approx 0.59$ (along the edge). The huge ratio $\lambda_1/\lambda_2 \approx 81$ is the numerical signature of the aperture problem — sliding the window vertically along the edge produces almost no change in $E$. Rejected as a point feature even though $\lambda_1$ alone is large — this is precisely why detectors must look at the smaller eigenvalue, not just the total gradient energy.
• Right-angle corner: $\lambda_1 \approx 38.7,\ \lambda_2 \approx 19.8$. Both eigenvalues are large and of comparable magnitude ($\lambda_2/\lambda_1 \approx 0.51$), meaning $E(u,v)$ rises sharply in every direction. This window survives both a magnitude threshold ($\lambda_2 > \tau$) and passes non-maximum suppression if it scores higher than its immediate neighbors (which, being interior to the flat or edge regions, score much lower). This is the point selected as a keypoint.

This trace shows exactly why the minimum eigenvalue (or a proxy for it) is the correct scalar summary of "cornerness" — a criterion the later Harris Corner Detection algorithm turns into an efficient closed-form score avoiding explicit eigendecomposition.

Feature detection is the entry point of nearly every classical geometric vision pipeline. Panorama stitching software (as in phone cameras and tools like Photoshop's photomerge) detects features in overlapping photos, matches them, and estimates the homography that aligns the images — none of it works without repeatable, distinctive keypoints. Structure-from-motion and 3D reconstruction systems (e.g., COLMAP, and the pipelines behind photogrammetry and cultural-heritage digitization) detect features across dozens or thousands of photos to recover camera poses and sparse 3D point clouds. Visual SLAM and odometry in robotics and augmented reality (ARKit, ARCore, autonomous drones) track features frame-to-frame in real time, which is precisely why detection must be linear-time and cheaply re-runnable per frame. Image retrieval and object recognition systems, before the deep-learning era, represented images as "bags" of local feature descriptors built on top of detected keypoints. Even in the deep learning era, learned keypoint detectors (SuperPoint, D2-Net) are still evaluated against exactly the same repeatability/distinctiveness/locality criteria introduced here, and are still typically followed by a description-and-matching stage — the conceptual pipeline outlives the specific algorithm. Understanding this foundational vocabulary is the prerequisite for the concrete algorithms that operationalize it: Harris Corner Detection turns the eigenvalue test into an efficient score, and SIFT: Scale-Invariant Features extends the same reasoning across scale and orientation to survive zoom and rotation.

Ask the tutor: How does the Harris detector turn the eigenvalue test into a score without computing eigenvalues explicitly, and why is that faster?