Edge & Corner Detection

Published in

K. R. I. S. S

8 min readJun 1, 2020

Edge detection refers to the extraction of the edges in a digital image. It is a process whose aim is to identify the points in an image where discontinuities or sharp changes in intensity occur. Conventional approaches include operators such as Prewitt Operator, Sobel Operator, Roberts Operator etc. The early stages of vision processing identify features in images that are relevant to estimating the structure and properties of objects in a scene . Edges are one such feature . Edges are significant local changes in the image and are important features for analyzing images . Edges typically occur on the boundary between two different regions in an image . Edge detection is frequently the first step in recovering information from images.Due to its importance,edge detection continues to be an active research area.An edge in an image is a significant local change in the image intensity , usually associated with a discontinuity in either the image intensity or the first derivative of the image intensity.

The Prewitt edge operator

The Sobel edge detector

DIFFERENCE BETWEEN FIRST AND SECOND ORDER FILTERS

In the first order filter, we take the 1st derivative of the intensity value across the image and find points where the derivative is maximum then the edge could be located. The gradient is a vector, whose components measure how rapid pixel value are changing with distance in the x and y direction.In second order filter we use the (2nd Order Derivative Operators) .The 2nd derivative of an image where the image highlights regions of rapid intensity change and is therefore often used for edge detection zero crossing edge detectors. The zero crossing detector looks for places in the Laplacian of an image where the value of the Laplacian passes through zero i.e. points where the Laplacian changes sign. The criteria used for comparison of results is (Root mean square error ) for different threshold values that explain the result obtain by 2nd order are best of the result obtain by 1st order for all values of threshold.It has been observed that there is more information loss in First order filter than in Second order filter.Sobel Derivative is an example of First order Filter and Laplacian operator is an example of Second Order Derivative.

DIFFERENCE OF GAUSSIAN

The Difference of Gaussian (DOG) function is a readily computed circular symmetric wavelet which approximates the Maxican hat wavelet. DOG bandpass filters an image and performs the edge enhancement operation on the objects present in the image. The DOG function is defined as the difference of two differently scaled Gaussian functions, g (x, y) i , where i = 1,2

Therefore the DOG function is given by :

The frequency domain of the DOG function is given by :

The Laplacian Operator

The Laplacian Of Gaussian Operator

To reduce the noise effect the image is first smoothed with a low-pass filter . In the case of LOG the low-pass filter is chosen as :

Kirsch edge operator

The kirsch edge detector detects edges using eight filters applied to the image. The eight filters are a rotation of a basic compass convolution filter.The 8 Kirsch masks, as used in LDP previously, are oriented in the direction of these 8 neighboring pixels in (n = 0, 1, . . . , 7) thus giving a measure of the strength of intensity variation in those directions, respectively. The Kirsch mask output in a particular direction provides an indication of the probability of occurrence of an edge in that direction.

To avoid over segmentation 5x5 kirsch convolutions are used which is referred to as extended kirsch operator.

The Canny edge detector

Canny Edge Detection is a popular edge detection algorithm. It was developed by John F. Canny in 1986.It is a multi-stage algorithm and we will go through each stages.

Noise Reduction:Since edge detection is susceptible to noise in the image, first step is to remove the noise in the image with a 5x5 Gaussian filter. We have already seen this in previous chapters.
Finding Intensity Gradient of the Image:Smoothened image is then filtered with a Sobel kernel in both horizontal and vertical direction to get first derivative in horizontal direction (Gx) and vertical direction (Gy). From these two images, we can find edge gradient and direction for each pixel as follows:

Edge gradient(G)= sqrt{Gx²+Gy²}

θ=tan ⁻¹(Gy/Gx)

Gradient direction is always perpendicular to edges. It is rounded to one of four angles representing vertical, horizontal and two diagonal directions.

3. Non-maximum Suppression:After getting gradient magnitude and direction, a full scan of image is done to remove any unwanted pixels which may not constitute the edge. For this, at every pixel, pixel is checked if it is a local maximum in its neighborhood in the direction of gradient. Check the image below:

Point A is on the edge ( in vertical direction). Gradient direction is normal to the edge. Point B and C are in gradient directions. So point A is checked with point B and C to see if it forms a local maximum. If so, it is considered for the next stage, otherwise, it is suppressed ( put to zero).In short, the result you get is a binary image with “thin edges”.

4. Hysteresis Thresholding: This stage decides which all are edges are really edges and which are not. For this, we need two threshold values, minVal and maxVal. Any edges with intensity gradient more than maxVal are sure to be edges and those below minVal are sure to be non-edges, so discarded. Those who lie between these two thresholds are classified edges or non-edges based on their connectivity. If they are connected to “sure-edge” pixels, they are considered to be part of edges. Otherwise, they are also discarded. See the image below:

The edge A is above the maxVal, so considered as “sure-edge”. Although edge C is below maxVal, it is connected to edge A, so that also considered as valid edge and we get that full curve. But edge B, although it is above minVal and is in same region as that of edge C, it is not connected to any “sure-edge”, so that is discarded. So it is very important that we have to select minVal and maxVal accordingly to get the correct result. This stage also removes small pixels noises on the assumption that edges are long lines.So what we finally get is strong edges in the image.

CORNER DETECTION HARRIS LAPLACIAN DETECTOR

Single scale Harris corner indicator

The Harris corner indicator is a well established technique making use of several linear filtering of an image. Given an image f, we denote by L(p,r) = g(p,r) * f(p), the low pass filtering by a Gaussian function g(p,r) of scale r, where p is the position in the image grid. Let Lx(p,rD), Ly(p,rD) be the respective horizontal and vertical image derivatives at position p, obtained with Gaussian filter of local scale rD (the differentiation scale). Then these intermediate results are composed to obtain three images

Þ, where the multiplicative operation is performed pixel wise. These images are then filtered by a Gaussian function

(the integration scale):

is the convolution operator. Finally the Harris corner detector is given by H:

Harris Laplace corner detector

As mentioned previously, the integration scale used for performing corner detection is crucial. In such a paradigm, the Harris corner indicator is applied at successive integration scales, before selecting locally the characteristic scales of image blobs. In (Lindeberg, 1998), the Laplacian-of-Gaussian (LoG) is used, as a scale space representation, for selecting the image blob characteristic scales, and the scale normalized Laplacian operator is defined by:

where Lxx, Lyy are the second image derivatives in the horizontal and vertical directions, respectively. The characteristic scale at some position p is defined by the scale σₙ which hits the maximum of |LoG(p,σₙ)|.We combine the Harris corner indicator and the scale normalized Laplacian operator in order to detect the salient positions in the scale space grid. First, a set of increasing analysis scales is chosen:

enabling them the computation of a multi scale stack of Harris indicators,

The local maxima of the Harris detector are computed.Secondly, these spatial locations are analyzed through the LoG operator, in order to discard the ones which are not salient in the scale dimension:

The spatial locations p which do not hit a scale maximum are discarded. The result of the Harris–Laplace corner detector is the set of retained scale space positions.