edge detection

Introduction (Shree K. Nayar, Columbia University)

This lecture focuses on edge detection, a fundamental concept in computer vision, specifically using the gradient operator. Edges are crucial features in images, representing rapid changes in intensity.

1D Edge Detection

• Definition of an Edge: An edge is a rapid change in image intensity within a small region.
• Example: A 1D signal, $f(x)$, with a rising edge (intensity increases) and a falling edge (intensity decreases).
• Calculus Connection: The derivative of a continuous function represents the amount of change in the function. Therefore, the first derivative can be used to detect edges.
• First Derivative Response:
  • For a constant intensity region, the first derivative, $\frac{\partial f}{\partial x}$, is zero.
  • At a rising edge, the first derivative has a positive peak (local maximum).
  • At a falling edge, the first derivative has a negative peak (local minimum).
• Finding Edges: The local extrema (maxima and minima) of the first derivative indicate the locations of edges.
• Absolute Value for Simplicity By taking the absolute value of the first derivative, $|\frac{\partial f}{\partial x}|$, both rising and falling edges produce positive peaks.
• The magnitude of the derivative is used to determine the location and strength of the edge.

2D Edge Detection

• Partial Derivatives: For a 2D image, $I(x,y)$, we use partial derivatives (or “pure” derivatives) to represent the change in intensity along each dimension (x and y).
• The Gradient Operator (∇):
  • The gradient operator, denoted by $\nabla$ (also called “Del”), is a vector composed of the partial derivatives.
  • $\nabla I=[\frac{\partial I}{\partial x},\frac{\partial I}{\partial y}]$
  • The gradient represents the direction of the most rapid change in intensity.
• Examples of Gradient Vectors:
  • Vertical Edge: $\nabla I=[\frac{\partial I}{\partial x},0]$ (change only in the x-direction)
  • Horizontal Edge: $\nabla I=[0,\frac{\partial I}{\partial y}]$ (change only in the y-direction)
  • Tilted Edge: $\nabla I=[\frac{\partial I}{\partial x},\frac{\partial I}{\partial y}]$ (change in both x and y directions)

Gradient as an Edge Detector

• Gradient Magnitude: The magnitude of the gradient vector, denoted as S, represents the strength of the edge: $S=||\nabla I||=\sqrt{(\frac{\partial I}{\partial x}{)}^2+(\frac{\partial I}{\partial y}{)}^2}$
• Gradient Orientation: The orientation (angle) of the edge, denoted as θ (measured with respect to the horizontal axis), is given by: $\theta ={\tan }^{-1}(\frac{\partial I}{\partial y}/\frac{\partial I}{\partial x})$
• Gradient, magnitude of the image and the orientation gives complete information of the edge.

Discrete Gradient Operator

• Finite Difference Approximations: In digital images (which are discrete), we approximate derivatives using finite differences. Finite difference approximations can be written as: $\frac{\partial I}{\partial x}\approx \frac{1}{2ϵ}((I_{i+1,j+1}-I_{i,j+1})+(I_{i+1,j}-I_{i,j}))$ $\frac{\partial I}{\partial y}\approx \frac{1}{2ϵ}((I_{i+1,j+1}-I_{i+1,j})+(I_{i,j+1}-I_{i,j}))$
• Convolution Implementation: These finite difference approximations can be implemented as convolution operations with specific kernels. Finite difference approximations are implemented with Convolution, the below filters represents convolution filters, where the flips are already applied:

\frac{\partial I}{\partial x} \approx \frac{1}{2\epsilon} \begin{bmatrix} -1 & 1 \\ -1 & 1 \end{bmatrix}$ $\frac{\partial I}{\partial y} \approx \frac{1}{2\epsilon} \begin{bmatrix} 1 & 1 \\ -1 & -1 \end{bmatrix}

Comparing Gradient Operators The gradient operator’s are compared as:

Gradient	Roberts	Prewitt	Sobel(3x3)	Sobel(5x5)
$\frac{\partial I}{\partial x}$	$\left[\begin{array}{cc}0& 1\\ -1& 0\end{array}\right]$	$\left[\begin{array}{ccc}-1& 0& 1\\ -1& 0& 1\\ -1& 0& 1\end{array}\right]$	$\left[\begin{array}{ccc}-1& 0& 1\\ -2& 0& 2\\ -1& 0& 1\end{array}\right]$	$\left[\begin{array}{ccccc}-1& -2& 0& 2& 1\\ -2& -3& 0& 3& 2\\ -3& -5& 0& 5& 3\\ -2& -3& 0& 3& 2\\ -1& -2& 0& 2& 1\end{array}\right]$
$\frac{\partial I}{\partial y}$	$\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]$	$\left[\begin{array}{ccc}1& 1& 1\\ 0& 0& 0\\ -1& -1& -1\end{array}\right]$	$\left[\begin{array}{ccc}1& 2& 1\\ 0& 0& 0\\ -1& -2& -1\end{array}\right]$	$\left[\begin{array}{ccccc}1& 2& 3& 2& 1\\ 2& 3& 5& 3& 2\\ 3& 5& 0& 5& 3\\ 2& 3& -5& -3& -2\\ 1& -2& -3& -2& -1\end{array}\right]$

• Roberts Operator: A very small (2x2) operator. Provides good localization but is highly sensitive to noise.
• Prewitt Operator: A 3x3 operator.
• Sobel Operator (3x3): A commonly used 3x3 operator. It’s essentially a smoothed version of a smaller derivative operator, making it less sensitive to noise.
• Sobel Operator (5x5): A larger version of the Sobel operator, providing even more noise resilience at the cost of slightly poorer localization.
  • The operators increases in extent and serves to reduce noise, larger the operator, less noise sensitive and good detection, but poor localization.

Gradient Using Sobel Filter

• The video shows an example of applying the 3x3 Sobel operator to the Lena image. The results are:
  • $\frac{\partial I}{\partial x}$: The derivative with respect to x.
  • $\frac{\partial I}{\partial y}$: The derivative with respect to y.
  • Gradient Magnitude: The combined strength of the edge, highlighting edges.

Edge Thresholding

• Need for Thresholding: After calculating the gradient magnitude, a thresholding step is necessary to decide which pixels are truly part of an edge.
• Standard Thresholding (Single Threshold, T):
  • If $||\nabla I(x,y)||<T$: Definitely not an edge.
  • If $||\nabla I(x,y)||\ge T$: Definitely an edge.
• Hysteresis Thresholding (Two Thresholds, $T_0$ and $T_1$, where $T_0<T_1$):
  • If $||\nabla I(x,y)||<T_0$: Definitely not an edge.
  • If $||\nabla I(x,y)||\ge T_1$: Definitely an edge.
  • If $T_0\le ||\nabla I(x,y)||<T_1$: The pixel is an edge if a neighboring pixel is definitely an edge (using contextual information). This helps to connect broken edge segments.

Sobel Edge Detector (Example)

• The video shows the final thresholded edge map for the Lena image, demonstrating the result of the Sobel operator followed by thresholding. The teacher emphasizes that this results in a “scattered set of edges” and that further processing is often needed to connect them into clean boundaries, which will be covered in later lectures.
• The video shows an example by taking the Lena Image, and applying gradient operator, first derivative with respect to x and y, and finally, a thersholded edge map.