06 Image Gradient, Smoothing and Laplacian of Gaussian Approach, Hough Transform, Local Image Features

In our previous lectures, we have built a solid foundation. We journeyed from the physics of image formation to the mathematics of filtering, learning how to manipulate and enhance pixel values. We saw how linear shift-invariant filters, particularly convolution, can be used for tasks like noise reduction (smoothing) and structure extraction (computing image gradients to find edges).

Today, we take a significant leap forward. We will move from processing images to understanding them. The goal is no longer just to modify pixels, but to distill the vast, unstructured grid of pixel data into a compact, meaningful, and robust set of image features. These features will serve as the fundamental building blocks for nearly all high-level computer vision tasks, from object recognition and image stitching to 3D reconstruction.

Recap: The Power and Purpose of Image Filtering

Let’s briefly revisit the key concepts from our discussion on filtering, as they are the tools we will use to build our features.

• Linear Shift-Invariant Filtering: This is the core operation, where we compute a new value for each pixel as a weighted sum of its neighbors. This is defined by a kernel.
• Convolution/Correlation: These are the two fundamental implementations of this weighted sum.
• Gaussian Filter: Our go-to filter for smoothing, chosen for its desirable mathematical properties like rotational symmetry and separability.
• Scale Space: By repeatedly smoothing and down-sampling an image, we create a Gaussian Pyramid, a multi-scale representation that allows us to analyze features at different levels of detail.
• Integral Image: A clever data structure that allows for the extremely fast computation of sums within rectangular regions, enabling real-time applications.
• Image Gradient: By applying derivative filters, we can compute the image gradient ($\nabla f$), a vector at each pixel that points in the direction of the steepest intensity change. Its magnitude, $\Vert \nabla f\Vert$, tells us the edge strength, and its direction, $\theta$, tells us the orientation of the edge.

The Image Gradient: Quantifying Change

The most fundamental structure in an image is the edge, a location of rapid intensity change. Calculus gives us the perfect tool for measuring change: the derivative.

Edges and Derivatives

If we plot the intensity profile across an edge, we see a step-like function.

• The first derivative of this profile will have a peak (a maximum or minimum) at the location of the edge.
• The second derivative will have a zero-crossing at the location of the edge.

From Calculus to Convolution

For a discrete image, we can approximate the partial derivative with respect to $x$ using a finite difference:

$$\frac{\partial f(x,y)}{\partial x}\approx f(x+1,y)-f(x,y)$$

This operation is equivalent to convolving the image with the simple kernel [-1, 1]. Similarly, the partial derivative with respect to $y$ can be computed by convolving with the kernel [-1, 1] transposed. Filters like Prewitt and Sobel are slightly more sophisticated versions that incorporate smoothing to make the derivative calculation more robust to noise.

The Gradient Vector

The two partial derivatives can be combined into a vector called the image gradient:

$$\nabla f=\left[\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\right]$$

This vector has two important properties:

• Magnitude: $\Vert \nabla f\Vert =\sqrt{(\frac{\partial f}{\partial x}{)}^2+(\frac{\partial f}{\partial y}{)}^2}$. This measures the edge strength. High magnitude corresponds to a strong edge.
• Direction: $\theta ={\tan }^{-1}\left(\frac{\partial f/\partial y}{\partial f/\partial x}\right)$. This vector points in the direction of the most rapid intensity increase, perpendicular to the edge itself.

The Achilles’ Heel of Differentiation: Noise

A major problem is that differentiation is extremely sensitive to noise. A small, random fluctuation in a noisy image can create a very large derivative, swamping the true signal from the edges.

Solution: Smooth First!

The solution is elegant and powerful: smooth the image first, then take the derivative. By convolving the image with a Gaussian filter before applying the derivative filter, we suppress the noise, allowing the true edge structure to emerge.

A key mathematical property of convolution is that it is associative and differentiation is a linear operator. This leads to the Derivative of Convolution Theorem:

$$\frac{\partial }{\partial x}(h\ast f)=\left(\frac{\partial }{\partial x}h\right)\ast f$$

This means that smoothing with a filter $h$ and then differentiating is identical to convolving the image with the derivative of the filter $h$. We can pre-compute the derivative of our Gaussian kernel to create a Derivative of Gaussian (DoG) filter. Applying this single filter to the image accomplishes both smoothing and differentiation in one efficient step, giving us a robust way to find edges even in the presence of noise.

An Alternative Approach: The Laplacian of Gaussian (LoG)

Instead of finding the peaks of the first derivative, we can look for the zero-crossings of the second derivative. The 2D equivalent of the second derivative is the Laplacian operator, ${\nabla }^2$.

$${\nabla }^{2}f=\frac{{\partial }^{2}f}{\partial x^2}+\frac{{\partial }^{2}f}{\partial y^2}$$

Applying the same “smooth first” principle, we can convolve our image with the Laplacian of a Gaussian (LoG). This filter, often called the “Mexican Hat” filter for its distinctive shape, finds edges at the zero-crossings of its response. The width of the Gaussian, $\sigma$, controls the scale of the edges being detected.

The Canny Edge Detector: An Optimal Approach

The Canny edge detector, developed in 1986, is a classic and highly influential algorithm that embodies the principles of designing an optimal detector. It’s a multi-stage process designed to satisfy three criteria: good detection, good localization, and single response.

1. Smooth Image: Convolve the image with a Gaussian filter to reduce noise.
2. Compute Gradient: Compute the gradient magnitude $M(x,y)$ and angle $\alpha (x,y)$ at every pixel.
3. Non-Maximum Suppression: Thin the thick edges. For each pixel, look at its two neighbors along the gradient direction. If the pixel’s gradient magnitude is not greater than both of its neighbors, suppress it (set its magnitude to 0). This ensures that only the peaks of the gradient ridges survive, resulting in thin, one-pixel-wide edges.
4. Double Thresholding: Use two thresholds, ${\theta }_{high}$ and ${\theta }_{low}$. Pixels with magnitude above ${\theta }_{high}$ are marked as “strong” edges. Pixels between ${\theta }_{low}$ and ${\theta }_{high}$ are marked as “weak” edges.
5. Edge Linking (Hysteresis): Keep the weak edge pixels only if they are connected to a strong edge pixel. This clever step allows the algorithm to trace along weaker parts of a strong contour while discarding isolated noise responses.

From Edges to Fitting: The Hough Transform

An edge map is a good start, but it’s just a collection of disconnected points. How do we find the larger structures, like lines or circles, that these points belong to? This is a fitting problem.

The Hough Transform is a brilliant and general technique for solving this. It reframes the fitting problem as a voting process in a parameter space.

The Duality of Points and Lines

Consider the equation of a line: $y=mx+c$. This equation defines a relationship between image space $(x,y)$ and a parameter space $(m,c)$.

• A single line in image space corresponds to a single point in $(m,c)$ parameter space.
• A single point $(x_i,y_i)$ in image space corresponds to a line in parameter space, defined by the equation $c=-x_{i}m+y_i$. This line represents all possible lines that could pass through the point $(x_i,y_i)$.

This duality is the key. If multiple points $(x_1,y_1),(x_2,y_2),\dots$ are collinear in image space, their corresponding lines in parameter space will all intersect at a single point, the point $(m,c)$ that defines the line they all lie on!

The Hough transform algorithm is thus:

1. Create a 2D grid (an accumulator) representing the parameter space.
2. For each detected edge pixel in the image, trace its corresponding line in parameter space and “vote” for (increment the value of) every cell it passes through.
3. Find the cells in the accumulator with the most votes. These peaks correspond to the parameters of the most prominent lines in the image.

A Better Parameterization: Polar Coordinates

The $(m,c)$ parameterization has a major flaw: the slope $m$ goes to infinity for vertical lines. A more robust representation is the polar form:

$$x\cos \theta +y\sin \theta =\rho$$

Here, a line is defined by its angle $\theta$ and its perpendicular distance from the origin $\rho$. In this $(\rho ,\theta )$ parameter space, a point in the image maps to a sinusoid. The voting process remains the same: collinear points will produce sinusoids that intersect at a single point in the Hough space.

Examples

Generalizing to Circles and Beyond

This voting principle is incredibly general. To find circles with a known radius $r$, we can use the circle equation $(x-a{)}^2+(y-b{)}^2=r^2$. Here, the parameter space is the 2D space of circle centers $(a,b)$. Each edge point in the image votes for a circle of possible centers in the $(a,b)$ space. The intersection of these circles reveals the center of the circle in the image. If the radius is also unknown, the parameter space becomes 3D $(a,b,r)$, and the voting process becomes more complex, but the principle remains the same.

Examples

Local Image Features: The Building Blocks of Recognition

We now shift our focus from finding global structures like lines to identifying and describing local, salient regions. These local image features are the cornerstone of modern computer vision, enabling tasks like image stitching, 3D reconstruction, and object recognition.

Why We Need Features

Imagine trying to build a panorama from multiple photos. You need to find corresponding points between the images to align them. Or consider a robot navigating a room using a single camera (Monocular SLAM (= Simultaneous Localization and Mapping)). It needs to identify stable, recognizable landmarks in the video stream to track its own motion. In all these cases, we need to answer two key questions:

1. Where are the interesting, repeatable regions? (Detection)
2. How can we describe these regions in a way that is robust and distinctive? (Description)

Applications