dH #022 Introduction to the Interest Points, Corner Detection – Theory and Applications
Highlights: In this tutorial, we’ll explore the fundamental concepts of computer vision, focusing on interest points and corner detection. You’ll learn how tracking, feature detection, and matching form the backbone of modern computer vision applications – from object recognition to 3D reconstruction. Let’s begin!
Tutorial overview:
- Computer Vision Applications and Use Cases
- Local Features and Interest Point Fundamentals
- Interest Point Detection Methods
1. Introduction to Computer Vision and Interest Points
Computer Vision Applications and Use Cases
Computer Vision Application Domains
Now that we understand the fundamental concepts of computer vision, let’s explore the diverse application domains where these techniques are applied in practice. Computer vision applications rely heavily on tracking capabilities in video sequences, where we analyze multiple frames to follow objects as they move through the scene. The fundamental challenge is establishing correspondences – given a point on an object in one frame, we want to determine where that same point appears in subsequent frames. This allows us to create continuous tracks for multiple objects simultaneously, whether we’re following cars, people, bicycles, or any other moving entities through the video sequence.
Beyond tracking, computer vision encompasses a rich set of applications including stereo matching with dual camera systems, camera calibration, and motion-based segmentation. These capabilities enable us to perform sophisticated tasks like computing disparity maps for depth estimation, calibrating stereo camera pairs, and estimating the fundamental matrix that describes the geometric relationship between stereo image pairs.
The practical applications extend into robotics and information retrieval systems as well. Robot navigation systems depend on computer vision to sense and analyze the environment, helping autonomous systems understand their motion and determine their position in space. For image databases and search applications, we can perform indexing and retrieval tasks – given a query image, the system can find similar images through sophisticated matching algorithms. All of these diverse applications share common building blocks: feature detection, interest point extraction, and robust matching techniques that form the foundation of modern computer vision systems.
Local Features and Interest Point Fundamentals
Local Feature Components and Applications
To understand local features and interest points, let’s start by examining the fundamental process of local feature analysis. This process begins with identifying interest points in images – these are the circles you see scattered across the terrain. The first critical step is detection, where we identify these interest points that represent distinctive locations in the image. Once we have these potential interest points, we move to the description phase, where we extract feature vector descriptors surrounding each interest point. These descriptors are typically high-dimensional feature vectors, often around 128 dimensions, that capture the local characteristics of the region around each point.
The ultimate goal is to use these descriptors to test and match points between different images. This is the main point of image and video analysis – we want to relate one image with another image, and to do that effectively, we need to find something interesting in one image and hopefully find the same thing in another image. Then we can match corresponding points between the two images through the matching phase, where we determine correspondence between descriptors in two different views.
What you see in these images are the potential matches – while humans can easily identify corresponding points between images, the computer has to perform this matching automatically. This three-step process of detection, description, and matching forms the foundation for numerous computer vision applications. Once we can reliably detect, describe, and match local features across images, it opens up possibilities for understanding what makes certain points particularly valuable as interest points.
This example above shows two images taken from different angles. The goal is to detect, describe and match interest points. In this way two images are connected, and can be further processed. For instance, this is basic for panorama image creation.
Interest Point Definition and Concepts
Now that we’ve seen how local features work in practice, let’s dive deeper into what makes certain locations qualify as interest points. When we examine edges in computer vision, we discover that interest points represent particularly valuable features for analysis. A prime example of interest points are corners, which stand out because while there may be numerous edges present in an image, corners occur at specific, unique locations where multiple edges converge. These corner points are fundamentally different from simple edge pixels because they represent locations where the direction of an object’s boundary changes abruptly, creating distinctive geometric features that are both detectable and useful for various computer vision tasks.
The value of corners extends beyond their geometric properties. Consider what happens when you try to match a simple edge point between two images – since edges extend over many pixels, there’s ambiguity about which specific point along the edge corresponds to a particular location in another view. Corners, however, provide precise, unambiguous locations that can be reliably detected and matched across different images. This makes them ideal anchor points for establishing correspondences, which is essential for tasks like stereo vision, object tracking, and image alignment.
Desirable Properties of Interest Points
When designing interest point detectors, we need to consider several critical properties that determine their effectiveness in real-world applications. The first and most fundamental requirement is repeatability – we must be able to detect the same interest points across different images of the same scene, even when viewing conditions change. This means that if we capture multiple photographs of an object from slightly different angles or under varying lighting conditions, our detector should consistently identify the same distinctive points on that object. Without repeatability, we cannot establish reliable correspondences between images, which would render the entire feature matching process useless.
Beyond repeatability, interest point detectors must exhibit saliency – the detected points should be distinctive and easily recognizable in the local neighborhood. A good interest point stands out from its surroundings in a way that makes it identifiable and matchable. Additionally, we require locality – the features should be local, meaning they characterize a relatively small region of the image. This locality property provides robustness against occlusion, where parts of the scene might be blocked or hidden in some views but not others. If our features are too global, a small occlusion could destroy the entire feature, but local features can survive partial occlusions.
The detector must also demonstrate quantity and accuracy. We need a sufficient number of interest points to adequately represent the scene – too few points limit our ability to establish enough correspondences for reliable geometric computations. At the same time, the detected locations must be accurate, precisely localizing the interest points in the image. Finally, efficiency matters greatly for practical applications. The detector should be computationally efficient enough to process images in reasonable time, especially for real-time applications like robot navigation or video tracking where processing speed is critical.
Invariance Requirements for Robust Detection
A particularly important aspect of interest point detection is invariance – the ability to detect the same points despite various transformations applied to the image. Consider what happens when we take multiple photographs of the same object: the camera viewpoint changes, the lighting conditions vary, and the scale of the object in the image differs. For our interest point detector to be useful, it must handle these variations gracefully.
Geometric invariance is perhaps the most critical requirement. The detector should be invariant to translation – detecting the same points regardless of where the object appears in the image frame. It should handle rotation, so that tilting the camera doesn’t cause us to lose track of our interest points. Scale invariance is equally important: whether we’re viewing an object from far away or up close, we want to detect the same distinctive points. Some advanced detectors even aim for affine invariance, handling more complex geometric transformations that occur when viewing planar surfaces from different angles.
Photometric invariance addresses changes in image intensity and appearance. The detector should work despite changes in lighting intensity – the same corner should be detected whether the scene is brightly lit or in shadow. Ideally, we’d like invariance to more complex photometric changes as well, though achieving this while maintaining other desirable properties represents a significant challenge. The most successful interest point detectors, like the Harris corner detector and SIFT (Scale-Invariant Feature Transform), carefully balance these various invariance properties with computational efficiency and detection reliability.
2. Understanding Corners and Gradient Analysis
What Makes a Corner?
Let’s get more specific about what defines a corner in computer vision. When we look at an image, we can categorize different regions based on their gradient characteristics. In flat regions, there’s essentially no gradient in any direction – the image intensity remains constant, making these areas uninformative for matching. Moving to edge regions, we observe a gradient in one specific direction perpendicular to the edge, but no gradient along the edge itself. This creates ambiguity: if you try to match a point on an edge, you can slide along the edge and still get similar-looking patches.
Corners, however, exhibit a unique property: they have significant gradients in multiple directions. This is what makes them so valuable! At a corner, you cannot shift the image patch in any direction without causing a substantial change in appearance. This distinctive characteristic makes corners highly localizable and matchable across different images. When you’re at a corner, moving in any direction produces a noticeable change in the local image structure, providing the distinctiveness we need for reliable feature detection.
The Flat Patch Problem
To understand why corners are superior to other features, consider what happens when we try to match a flat image patch – a region with uniform intensity. The fundamental problem is that flat patches lack distinctive characteristics. If you take a small window from a flat region and try to find it in another image, you’ll discover that it could match almost anywhere else that has similar intensity. There’s no unique “signature” that distinguishes one flat patch from another.
This ambiguity makes flat regions useless for establishing correspondences between images. Without distinctive features, we cannot reliably determine which point in one image corresponds to which point in another image. The matching process becomes arbitrary, and any geometric computations based on these matches would be unreliable. This is precisely why we need to identify and focus on regions with high information content – regions where the local structure is distinctive enough to enable unambiguous matching.
The following figures illustrate the behavior of a flat patch (uniform grayscale intensity) when computing first derivatives (∂f/∂x, ∂f/∂y) and second derivatives (∂²f/∂x², ∂²f/∂y²). We can see that the flat patch generates 4 plots that (near) zeros.
Edge Matching Challenges
Edges present a different but equally problematic challenge. While edges are more distinctive than flat regions, they suffer from the aperture problem – ambiguity in one direction. Imagine you’re looking at an edge through a small window or aperture. You can clearly see that there’s an edge with a specific orientation, and you know the gradient direction perpendicular to the edge. However, along the edge direction, there’s no distinctive information.
For instance, if we have an edge as in the figure below, we will have a derivative over x, and hence, we can allocate this edge. On the other hand, we cannot locate any position along y edge.
This means that if you try to match an edge point between two images, you face uncertainty about where exactly along the edge you are. You might correctly identify that you’re somewhere on a particular edge, but you cannot pinpoint the exact location along that edge. The patch could slide along the edge, and you’d see essentially the same local appearance. This sliding ambiguity makes edges alone insufficient for precise localization and matching, though they can provide useful constraints when combined with other features.
Corner Detection Advantages
Corners solve both the flat patch and edge matching problems simultaneously. At a corner location, we have large gradients in at least two significantly different directions. This means the local image structure changes substantially no matter which direction you move. If you shift your image patch up, down, left, right, or diagonally from a corner, you’ll see a significant change in appearance.
Below, in the following images, we can see why corners are superior! They have non-zero values along both x and y derivatives, as well as second derivatives. The corner is highly localizable!
In the next section, we will learn about the FAMOUS algorithm for corner detection – Harris corner detector.
3. Harris Detector Mathematics and Implementation
Harris Detector Mathematical Framework
Basic Harris Mathematics
Now, this section is a bit math-heavy! But do not worry, we will go slowly so that everything is well understood.
Let’s dive into the mathematical foundation of the Harris detector by examining how we measure intensity changes for displacement \((u,v)\) to detect interest points in images. The approach involves looking at the intensity at position \((x,y)\) and comparing it with the intensity at the shifted position \((x+u, y+v)\). We subtract these intensities and square the difference, creating what is essentially a sum of squared differences (SSD) calculation. This process is similar to autocorrelation, and we perform this computation for every possible displacement \((u,v)\), making our result a function of these displacement parameters.
$$ E(u,v) = \sum_{x,y} w(x,y) [I(x+u, y+v) – I(x,y)]^2 $$
In addition to the basic intensity comparison, we apply weights \(w(x,y)\) to each pixel. These weights can be uniform, giving equal importance to all pixels, or we can apply Gaussian weights to give more importance to pixels that are close to the center position \((x,y)\) compared to pixels that are further away. This weighting scheme helps focus our analysis on the most relevant local neighborhood around each point.
When we examine the correlation surface or SSD for different types of image regions, we see dramatically different behaviors. For a point around a textured area, when we compute the \(E(u,v)\) values for each possible displacement and plot the resulting surface, we get a nice unique minimum – this creates a well-defined peak that clearly identifies an interest point. However, if we take a pixel in a mostly flat region, the \((u,v)\) surface appears very flat and ambiguous, providing little useful information for feature detection.
Similarly, if we examine a point along an edge, such as around a building structure, the resulting profile creates what we call an ‘aperture problem’ because there’s no unique minimum in the surface. The displacement can slide along the edge direction without much change in the error function. Therefore, we prefer regions that produce sharp, well-defined minima in the correlation surface, as these correspond to true interest points or corners that can be reliably detected and tracked. To work with this mathematically, we need a more tractable form of our equation.
The Intuition Behind Harris Corner Detection
What Are We Really Looking For?
The fundamental goal of the Harris corner detector is beautifully simple:
we want to find points in an image where even a tiny shift in any direction makes the local appearance change dramatically.
These are our corners! Let’s understand this through a thought experiment. Imagine you’re looking at an image through a small window centered at some point \((x,y)\). Now, what happens when you nudge this window slightly in different directions?
Three Scenarios: Flat, Edge, and Corner
Scenario 1: Flat Region
If your window is over a flat region (like a uniform wall or sky), shifting it by \((u,v)\) in any direction still shows you basically the same thing – uniform intensity. The function \(E(u,v)\), which measures how much the window content changes, remains small for all possible shifts. This makes flat regions useless for tracking and matching because they look the same everywhere!
Scenario 2: Edge
Now suppose your window contains an edge. If you slide the window along the edge direction, the content looks pretty similar – you’re still seeing the same edge. But if you move perpendicular to the edge, suddenly things look different! This is the aperture problem: \(E(u,v)\) is large in one direction but small in another. Edges give us partial information, but there’s ambiguity about where exactly along the edge we are.
Scenario 3: Corner (The Goal!)
Here’s where it gets interesting! At a corner, moving the window in <em>any</em> direction – left, right, up, down, or diagonally – causes a significant change in appearance. Whether you shift by \((u,v) = (-3, 0)\), \((+3, 0)\), \((0, -3)\), \((+2, +2)\), or any other direction, the value of \(E(u,v)\) is consistently large. This is exactly what we want! A corner is distinctive, localizable, and uniquely identifiable.
The Mathematical Formulation
The error function \(E(u,v)\) captures this intuition mathematically: $$ E(u,v) = \sum_{x,y} w(x,y) [I(x+u, y+v) – I(x,y)]^2 $$ This formula does exactly what we described: – Takes the intensity at the original position: \(I(x,y)\) – Compares it with the intensity at the shifted position: \(I(x+u, y+v)\) – Squares the difference and sums over the window – Applies weights \(w(x,y)\) (usually Gaussian) to emphasize pixels near the window center
Key insight: We’re not looking for where \(E(u,v)\) is minimum! We’re looking for points where \(E(u,v)\) is <em>large for all possible shifts</em> \((u,v)\). This is what makes a point a reliable corner.
This is illustrated in the following images. Imagine that the values are black=0, and white=0. When we move along u, v we will get the following table, and can observe how our function \(E(u,v) is changing\). Note the differences and largest values for the corner case image.
If we do this for every combination of \(u\) and \(v\), we will get the following maps. They will tell us how the heatmaps are behaving.
Now, for the following three cases, we can approximate these heatmpas. Calculating every pixel of these heatmaps is EXPENSIVE and by using eigenvalues, we approximate the calculation, and obtain the following. Have a look at this beautiful approximations!
Why Eigenvalues?
The eigenvalues \(\lambda_1\) and \(\lambda_2\) of the matrix \(M\) encode precisely this information: – Both \(\lambda_1\) and \(\lambda_2\) are small: Flat region – \(E(u,v)\) is small in all directions – One eigenvalue is large, one is small: Edge – \(E(u,v)\) is large in only one direction – Both \(\lambda_1\) and \(\lambda_2\) are large: Corner – \(E(u,v)\) is large in all directions! This is the brilliance of the Harris detector: instead of explicitly computing \(E(u,v)\) for every possible shift direction, we compute the eigenvalues of \(M\) once, and they immediately tell us whether a point behaves like a corner, edge, or flat region.
Taylor Series in Harris Detection
To make our Harris detection equation more mathematically tractable, let me introduce a fundamental concept – the Taylor series. Taylor series is named after the famous mathematician Taylor, and it’s a very simple yet incredibly useful idea for approximating functions. If you have any function \(f(x)\) of one dimension, you can represent that function in terms of the value of the function at a point \(a\) and the derivatives of that function at that point – first derivative, second derivative, and so on. This provides a much better way to approximate a function compared to simpler methods.
$$ f(a) + \frac{f'(a)}{1!}(x – a) + \frac{f”(a)}{2!}(x – a)^2 + \frac{f^{(3)}(a)}{3!}(x – a)^3 + \cdots $$
So here we’re saying \(f(x)\) can be approximated by \(f(a)\), plus the first derivative of \(f\) evaluated at \(a\) times \((x – a)\), plus the second derivative of \(f\) with respect to \(x\) evaluated at \(a\) times \((x – a)^2\), and so on. Now, getting back to Harris corner detection, we have this expression and what we’re going to do is find the Taylor series of the function \(I(x+u, y+v)\) and approximate it around the point \((x,y)\).
$$ E(u,v) = \sum_{x,y} w(x,y) [I(x+u,y+v) – I(x,y)]^2 $$
$$ E(u,v) = \sum_{x,y} w(x,y) [I(x,y) + uI_x + vI_y – I(x,y)]^2 $$
Since this function is two-dimensional, we differentiate with respect to \(x\) first and then with respect to \(y\). The first term is \(I(x,y)\), then we have the first derivative of \(I\) with respect to \(x\), which gives us \(I_x\), and similarly \(I_y\) for the \(y\) direction. We multiply these by \(u\) and \(v\) respectively, where \(u = (x+u) – x\) and \(v = (y+v) – y\). This is a pretty simple approximation using just the first-order terms of Taylor’s series.
Now the interesting thing happens – since \(I(x,y)\) appears in both terms with opposite signs, they cancel out! The weight \(w\) remains the same, and we’re left with \(uI_x + vI_y\) squared. We can break this into two vectors: one is \(\begin{pmatrix} I_x \ I_y \end{pmatrix}\) and another is \(\begin{pmatrix} u \ v \end{pmatrix}\). When we expand the square, we get the vector multiplication \(\begin{pmatrix} u & v \end{pmatrix} \begin{pmatrix} I_x \ I_y \end{pmatrix}\), which gives us a \(1 \times 1\) result since we’re multiplying a \(1 \times 2\) with a \(2 \times 1\) vector.
$$ E(u,v) = \sum_{x,y} w(x,y) [I(x+u,y+v) – I(x,y)]^2 $$
$$ E(u,v) = \sum_{x,y} w(x,y) [I(x,y) + uI_x + vI_y – I(x,y)]^2 $$
$$ E(u,v) = \sum_{x,y} w(x,y) [uI_x + vI_y]^2 $$
$$ E(u,v) = \sum_{x,y} w(x,y) \begin{pmatrix} u & v \end{pmatrix} \begin{pmatrix} I_x \ I_y \end{pmatrix}^2 $$
We can further rearrange this expression by expanding the square term. We’ll have \(\begin{pmatrix} u & v \end{pmatrix}\), then the transpose multiplication gives us \(\begin{pmatrix} I_x & I_y \end{pmatrix} \begin{pmatrix} I_x \ I_y \end{pmatrix}\), and finally \(\begin{pmatrix} u \ v \end{pmatrix}\). Since the weight \(w\) is a scalar, we can move it around, and we’ll group the terms \(w \begin{pmatrix} I_x \ I_y \end{pmatrix} \begin{pmatrix} I_x & I_y \end{pmatrix}\) together and call this the matrix \(M\). This becomes a \(2 \times 2\) matrix where each element is multiplied by \(w\). The final expression becomes \(\begin{pmatrix} u & v \end{pmatrix} M \begin{pmatrix} u \ v \end{pmatrix}\), which leads us naturally to examine the structure of this crucial matrix \(M\).
Derivative Matrix Components
Having derived our matrix form, let’s now examine the structure of this matrix \(M\), which is essentially a \(2 \times 2\) matrix as we discussed. The first term will be \(I_x\) multiplied by \(I_x\), which gives us \(I_x^2\). Then we have \(I_x\) multiplied by \(I_y\) as the second term in that column. Moving to the second column, we get \(I_y\) multiplied by \(I_x\), and finally \(I_y\) multiplied by \(I_y\), which is \(I_y^2\). This gives us our \(M\) matrix, which is shown in the equations below.
$$ E(u,v) = \sum_{x,y} w(x,y) [I(x+u,y+v) – I(x,y)]^2 $$
$$ E(u,v) = \sum_{x,y} w(x,y) [I(x,y) + uI_x + vI_y – I(x,y)]^2 $$
$$ E(u,v) = \sum_{x,y} w(x,y) [uI_x + vI_y]^2 $$
$$ E(u,v) = \sum_{x,y} w(x,y) \left(u \quad v\right) \begin{pmatrix} I_x \ I_y \end{pmatrix}^2 $$
$$ E(u,v) = \sum_{x,y} w(x,y) \left(u \quad v\right) \begin{pmatrix} I_x \ I_y \end{pmatrix} \left(I_x \quad I_y\right) \begin{pmatrix} u \ v \end{pmatrix} $$
$$ E(u,v) = \left(u \quad v\right) \left[\sum_{x,y} w(x,y) \begin{pmatrix} I_x \ I_y \end{pmatrix} \left(I_x \quad I_y\right)\right] \begin{pmatrix} u \ v \end{pmatrix} $$
$$ E(u,v) = \left(u \quad v\right) M \begin{pmatrix} u \ v \end{pmatrix} $$
What’s particularly fascinating here is that we can see how everything ultimately reduces to derivatives of the survey images. We have the derivative in the \(x\) direction, \(I_x\), and the derivative in the \(y\) direction, \(I_y\). All the components of our matrix involve these derivatives: \(I_x^2\), \(I_y^2\), and \(I_x I_y\). This reduction to derivatives is quite remarkable and shows the fundamental role that image gradients play in this analysis.
Eigenvalue Analysis in Harris Detection
Eigenvalue Analysis Introduction
$$ M = \sum_{x,y} w(x,y) \begin{pmatrix} I_x I_x & I_x I_y \\ I_x I_y & I_y I_y \end{pmatrix} $$ $$ E(u,v) = (u \quad v) M \begin{pmatrix} u \\ v \end{pmatrix} $$ Looking at these equations from our Harris corner detection framework, you’ll notice something quite interesting about this second equation – this is actually the equation of an ellipse! The matrix \(M\) here serves as our covariance matrix, which encodes important geometric information about the structure we’re analyzing. What we’re going to do next is take this matrix \(M\) and examine its eigenvalues. This eigenvalue analysis will reveal fundamental properties about the ellipse and help us understand the underlying geometric characteristics of our data structure.
To do this effectively, we first need to understand what eigenvalues and eigenvectors actually represent.
Eigenvalue and Eigenvector Fundamentals
Let’s dive into the fundamental concept of eigenvectors and eigenvalues. An eigenvector \(x\) of a matrix \(A\) is a very special vector with a remarkable property: when you multiply that vector \(x\) by matrix \(A\), you get the original vector back, just scaled by some constant. In mathematical terms, if I take a matrix \(A\) and multiply it with vector \(x\), I get back the vector \(x\) multiplied by some scalar \(\lambda\). Here, \(x\) is called the eigenvector and \(\lambda\) is called the eigenvalue. $$ Ax = \lambda x $$ To find the eigenvalues and eigenvectors of a matrix, we follow a systematic approach. You take your matrix \(A\), subtract \(\lambda\) times the identity matrix \(I\), and find where the determinant of this result equals zero. This determinant equation will give you all the eigenvalues of the matrix. $$ \det(A – \lambda I) = 0 $$ $$ (A – \lambda I)x = 0 $$ You can always verify your results by taking an eigenvector and multiplying it with the corresponding matrix – you should get back the eigenvalue times the original eigenvector. This is the essence of eigenvectors and eigenvalues: it’s a pretty simple idea conceptually, but incredibly useful in many applications. The key insight is that eigenvectors represent directions that remain unchanged under the linear transformation, only getting scaled by their corresponding eigenvalues.
Summary
Is anybody out there? Is someone still following? 🙂
Ok, we do hope that you have liked this analysis. Do not worry if not everything is clear. you can just come back, do some math refresher, and it will sink. The main thing is that you have grasped the intuition about the corners, and how they can elegantly be detected. Without the further ado bye bye until the next post!
We have already wrote about Harris corner detector and you can check this hand-on practical post here as well!