Edge Detection

An edge is a set of pixels where the intensity changes abruptly.

Edge detectors are used to locate such changes in the intensity function.

Changes in a function are defined by their derivatives. Images are functions of two parameters (x,y). Therefore, operators describing edges are expressed using partial derivatives.

An edge has magnitude (edge strength) and direction. The magnitude is equal to that of the gradient and the direction is perpendicular to that of the gradient. Note that the gradient points in the direction of the most rapid change in the intensity.

The gradient is given by $\triangledown f = [\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}]$

The magnitude of the gradient (and thereby of the edge) is $||\triangledown f|| = \sqrt{(\frac{\partial f}{\partial x})^2+(\frac{\partial f}{\partial y})^2}$ and the direction of the gradient is $\theta = tan^{-1}(\frac{\partial f}{\partial y}/\frac{\partial f}{\partial x})$.

Edges are usually used to find region boundaries. If a region has homogeneous brightness, its boundary/border will be the pixels at which the image function (brightness) abruptly changes.

The following denotes common edge profiles:Edge detectors are tuned to detect a specific type of edge profile.

Criteria for Optimal Edge Detection

• Good Detection: Minimize false positives and false negatives

• Good Localization: Detected edges must be as close as possible to the actual edges

• Single Response: Minimize the number of local maxima around the true edge

Commonly Used Edge Detection Operators

Gradient operators (edge detectors) can be approximated using convolutions. Operators that detect edge direction are represented by a collection of masks (one for each direction), while those that don't detect direction are represented by a single mask.

A few edge detection operators are discussed below:

Sobel Operator

$M_x = \begin{bmatrix}-1 & 0 & 1\\-2 & 0 & 2\\-1 & 0 & 1\end{bmatrix}, M_y = \begin{bmatrix}-1 & -2 & -1\\0 & 0 & 0\\1 & 2 & 1\end{bmatrix}$

$M_x, M_y$ are used to calculate the partial derivatives $\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}$ respectively. They represent the vertical and horizontal detectors respectively.

The sobel operator is used to detect horizontality and verticality of edges.

Prewitt Operator

$M_x = \begin{bmatrix}-1 & 0 & 1\\-1 & 0 & 1\\-1 & 0 & 1\end{bmatrix}, M_y = \begin{bmatrix}-1 & -1 & -1\\0 & 0 & 0\\1 & 1 & 1\end{bmatrix}$

Roberts Operator

$M_x = \begin{bmatrix}0 & 1\\-1 & 0\end{bmatrix}, M_y = \begin{bmatrix}1 & 0\\0 & -1\end{bmatrix}$

Disadvantage: It is highly sensitive to noise.

Kirsch Operator

$M_x = \begin{bmatrix}-5 & 3 & 3\\-5 & 0 & 3\\-5 & 3 & 3\end{bmatrix}, M_y = \begin{bmatrix}-5 & -5 & -5\\3 & 0 & 3\\3 & 3 & 3\end{bmatrix}$

Laplace Operator ($\triangledown^2$)

While all the previously mentioned operators compute the first derivative, the Laplace operator is used to approximate the second derivative. Another important point to note is that this operator only gives the magnitude of the edge, not the direction. It is rotationally invariant.

The following are the masks for 4-neighborhood and 8-neighborhood:

$M_4=\begin{bmatrix}0 & 1 & 0\\1 & -4 & 1\\0 & 1 & 0\end{bmatrix}, M_8=\begin{bmatrix}1 & 1 & 1\\1 & -8 & 1\\1 & 1 & 1\end{bmatrix}$

Disadvantage: It responds doubly to some edges in the image.

Zero-Crossings of the Second Derivative

The issue with the previously discussed operators is that they depend on the size of the object and are sensitive to noise.

The Marr-Hildreth operator uses the concept of zero-crossings of the second derivative to detect edges.

We know that a step edge corresponds to a sudden change in the image function. The first derivative of the image function should have an extremum at the position corresponding to the edge in the image. This implies that the second derivative at that position will be zero.

Since it is much easier to detect 0s when compared to finding extremums, detecting edges using zero-crossings is more convenient.

The image shows a step edge with its first and second derivatives. Clearly, the first derivative depicts an extremum at the edge location while the second derivative becomes 0 at that location.

Before computing the derivatives, we must smooth the image (to reduce noise). To do so, we use Gaussian smoothing. Now, we know that the Laplace operator computes the second derivative. So, all we need to do is to compute the Laplacian of the Gaussian (LoG).

This is denoted by $\triangledown^2 G$ and is approximated by convolving an image with the following mask:

$\begin{bmatrix}0 & 0 & -1 & 0 & 0\\0 & -1 & -2 & -1 & 0\\-1 & -2 & -16 & -2 & -1\\0 & -1 & -2 & -1 & 0\\0 & 0 & -1 & 0 & 0\end{bmatrix}$

Due to its shape, the inverted LoG operator is commonly called a Mexican Hat.

After convolving an image with the above operator, the locations in the convolved image where zero is crossed correspond to the edges in the input image.

The advantage of using this approach instead of the previously discussed (smaller) operators is that a larger area surrounding the pixel is taken into account, and the influence of distant pixels is reduced according to the $\sigma$ of the Gaussian.

Sidenote: The LoG operator can be approximated by a convolution with a mask that is obtained by
subtracting two Gaussian masks with significantly different sigma values. This method is called
Difference of Gaussians (DoG).

Disadvantages of LoG operation:

• it may smooth the shape too much (sharp corners may be lost)

• it tends to create closed loops of edges

Pattern Matching

This is an approach where we use a "matched filter" containing the shape of the object that has to be detected in the image. We then slide the filter over the image and correlate the image with the "matched filter" to detect objects.

This doesn't generalize well; we need a separate filter for each object. It is also not invariant to scale (size; different sizes of same object in the image) and orientation (rotation) of the object.

Canny Edge Detection

The Canny edge detector is an optimal edge detector (good detection, good localization, single response). It is especially good for step edges corrupted by white noise.

Canny Edge Detection Steps:

1. Use a Gaussian filter to reduce noise (smoothing)

2. Find the intensity gradient of the image; this is done using the Sobel operator (or any other operator such as Prewitt, Roberts etc). The operator will give the first derivative in the horizontal and vertical directions. These can be used to determine the edge gradient (magnitude) and direction. The gradient direction is then rounded to one of the 4 angles representing horizontal, vertical and two diagonal directions

3. Non-Maximum Suppression is performed: the image is scanned to remove any pixels that may not constitute an edge; each pixel is checked to determine if it is a local maximum in its neighborhood. If not, it is suppressed.

4. Hysteresis Thresholding is performed: this stage decides which pixels actually form edges. Two thresholds (low and high) are used. Pixels with intensities greater than the high threshold are said to be strong edge pixels and are retained. Pixels with intensities lower than the low threshold are discarded. Pixels with intensities between the low and high thresholds are retained only if they are connected to strong edge pixels. The final result is strong edges in the image.