Edge Detection and Image Gradients

Edge Detection

• Transforms a 2D image into a set of curves.
• Isolates the important parts of a scene.
• More size efficient than pixels.

Edge Origin

• Edges originate from various factors that affect image properties.
• Surface normal discontinuity.
• Depth discontinuity.
• Surface color discontinuity.
• Illumination discontinuity.

Edge Characterization

• Edges are characterized by rapid changes in the image intensity function.
• Edges correspond to extrema of derivative.

Image Gradient

• Image gradient's formula: ∇f = [∂f/∂x, ∂f/∂y].
• Gradient vector points towards the direction of the most rapid increase in intensity.
• In 2D, the gradient is expressed with x and y components: ∇f = [∂f/∂x, 0] OR ∇f = [0, ∂f/∂y].
• Edge strength equals the gradient magnitude whose formula is: ||∇f|| = √((∂f/∂x)² + (∂f/∂y)²).
• The gradient direction is given by: Θ = tan⁻¹(∂f/∂y / ∂f/∂x).

Digital Image Differentiation

• Discrete derivative is a finite difference approximation.
• The formula for discrete derivative is expressed as: ∂f/∂x[x,y] ≈ F[x + 1, y] – F[x, y].

Effects of Noise

• Noise interferes with accurately pinpointing edge locations.

Smoothing

• Smooth first to solve noise issues.
• To find edges, look for peaks in d/dx (f * h).

Simplified Solution

• A useful identity for smoothing: d/dx (f * h) = f * d/dx h.
• The identity is useful as it results in fewer operations.

2D Edge Detection Filters

• Gaussian filter.
• Derivative of Gaussian (x)

Sobel Operator

• Sobel operator serves as a practical approximation of the Gaussian derivative.
• The formulas for Sobel operator are: 1/8 * [[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]] OR 1/ 8 * [[1, 2, 1], [0, 0, 0], [-1, -2, -1]].

Requirements of a Good Edge Detector

• Reduce multiple detections.
• Reduce probability of false detection.
• Reduce distance between reported and true edge location.
• David Canny (1986), identified these criteria.
• The derivative of Gaussian is optimal in 1D.
• Heuristics were developed to satisfy criteria in 2D.

Non-Maximum Suppression

• Check if pixel is local maximum along gradient direction.
• Requires interpolating pixels p and r.

Canny Thresholding

• Low thresholds can generate more edges, but it comes at the cost of more spurious edge pixels
• A edge pixel's gradient magnitude must exceed a low threshold, connecting it to another edge pixel.
• Begin with classifying any candidates higher than the high threshold as edges.
• If a pixel is above the lower threshold and next to any edge pixel, recursively keep said pixel.

Summary: Canny edge detector

• The steps in a Canny edge detector:

1. Filter image with derivative of Gaussian.
2. Find magnitude and orientation of gradient.
3. Non-maximum suppression.
4. Linking and thresholding (hysteresis).

Canny edge detector settings

• Need to set sigma, low threshold, high threshold.

Implementation Issues

• The rectangular pixel grid creates subtle issues when computing discrete derivative estimates.
• Discrete derivative estimates exist at different points in each direction if use x,y directions.

Estimating Discrete Gradient

• Gradient at u,v with 45° axes.
• Down-right: ∂I/∂x' ≈ I[u+1,v+1]-I[u,v].
• Down-left: ∂I/∂y' ≈ I[u,v+1]-I[u+1,v].
• Handle image border, e.g., no change.

Line Detection

• Edge detection is used in line detection.
• Sobel, and the more sophisticated Canny are popular ways of edge detection.
• All algorithms are imperfect because edge detection is an ill-defined task.
• Algorithms must be robust to small differences in edge detector output.

Finding Straight Lines

• Challenges include, missing edge pixels, background clutter and multiple lines.
• Try all possible lines and count how many points each line passes through.
• Choose the line with the most support.
• The Hough transform provides an efficient way of doing this

Hough Transform

• Every pixel casts a vote for all lines that could have generated it.
• Votes are tabulated to find the most likely line(s).
• Voting is conducted in a parameter space.
• For lines, parameterize in terms of slope and y-intercept, i.e. y=mx+b.

Better Parameterization

• A better parameterization is to use polar coordinate, in order to avoid unbounded slopes(m).
• The polar coordinate formula reads: ρ = -x cos θ + y sin θ.
• A point in image space corresponds with a _____ in Hough space.

Discretization

• In practice, both image space and Hough space are discretized.

Practical Issues Regarding Hough Space

• How should the Hough space be discretized.
• If cells are too big, lines are merged together; if too small noise causes lines to be missed.
• The number of lines.
• Peaks in the Hough array should be thresholded.
• Treat adjacent peaks should be handled as a single maximal peak, using, non maximal suppression.
• Locate which points belong to each line.
• Search for points that lie near the identified lines.