Edge Detection and Hough Transform
Objective:
- Detecting Edges using Canny Edge Detector.
- Understand and display the outputs of all steps in the canny Edge Detection process.
- Effect on the output on changing the parameters of the Non-Maximum Suppression.
- Understand Hough Transform and Lane Detection using Hough Transform.
Steps Follow in the Discussion:
- What are Image Gradients?
- Gradient Magnitude, Gradient Orientation.
- Usage of Filters over Manual Gradient calculation, [Performance, resource efficiency]
- What is Convolution?
- First Order vs Second Order derivatives? [Importance of Gaussian Filtering]
- Laplacian Of Gaussian.
- Usage of the Edge Detection/ Image Gradients.
- Then Canny Edge Detector.
- Hough Transform Displaying.
- Line Detection using Hough Transform.
Image Gradient contain two important information,
1. Gradient Magnitude, is the amount of change in the pixel intensity along that dimension.
2. Gradient Orientation, Which direction the change in intensity is pointing.
Image Gradients are the Building Block of many Computer Vision Application,
- we use them as inputs for quantifying images through feature extraction — in fact, highly successful and well-known image descriptor
such as Histogram of Oriented Gradients and SIFT are built upon image gradient representations
- Gradient images are even used to construct saliency maps, which highlight the subjects of an image
The Main Application of the Image Gradients is Edge Detection, detecting the edges which describe the structural Information of the Object in the Image, Which can be used for Image Classification
Image Segmentation, Reduces the Usage of resources since, extracting the required Information from the structure.
Understanding the Gradient Calculation Manually,
1. In Practice, we use Filter to do the Gradient Operation, which gives a better approximation by using the Numerical Differentiation (Forward, Backward, and central Difference).
2. In Opencv, Computer Vision, We use the Left Hand Co-ordinate System. {CW = +ve | ACW = -ve}
Here, we want to calculate the Gradient on the center red pixel.
Lets Define as,
- North: I(x, y-1)
- South: I(x, y+1)
- East : I(x+1, y)
- West : I(x-1, y)
Remeber while using the Array Index Notation,
i repsent the row number, along the X-direction.
j represent the column number, along the Y-direction.
- Center : I(i,j)
- North : I(i-1, j)
- South : I(i+1, j)
- East : I(i, j+1)
- West : I(i+1, j)
Think about the indexes in the "?" below,
Let's Define the Variables as `G_x`(gradient along x), `G_y`(gradient along y), G (Manitude of Gradient, norm)
`G_y = I(i+1, j) - I(i, j+1)`
`G_x = I(i, j+1) - I(i, j-1)`
`G = sqrt((G_x)^2 + (G_y)^2 )`
Now, we have the Gradient Magnitude.
Fror Gradient Orientation,
`theta = arctan2(G_y, G_x) * (180/pi)`
Let's Consider an Example,
`G_x = 0 - 0 = 0` and `G_y = 0 - 255`, so `G = sqrt((0)^2 + (-255)^2 ) = 255`
`theta = arctan2(-255,0)*(180/pi) = -90^0`
Gradient Mangnitude is 255, which represents the Huge change in Intensity, In the direction of -90 degress.
Think about this Example,
But as said In practice we use Filters,
Filters is the matrix who values are calculated by using the spacial Function, perform convolution operation on Input Image.
To understand about convolution much use this tool, https://deeplizard.com/resource/pavq7noze2
Some of Edge Detector Filters,
1. Sobel Filter.
- Veritcal filter (or) Mask:
`[[-1, 0, 1],[-2, 0, 1], [-1, 0, 1]]`
- Horizontal filter (or) Mask:
`[[-1, -2, -1],[0, 0, 0], [1,1, 1]]`
2. Scharr Filter.
- Veritcal filter (or) Mask:
`[[-3, 0, 3],[-10, 0, 10], [-3, 0, 3]]`
- Horizontal filter (or) Mask:
`[[-3, -10, -3],[0, 0, 0], [3,10, 3]]`
3. Prewiit Filter.
- Veritcal filter (or) Mask:
`[[-1, 0, 1],[-1, 0, 1], [-1, 0, 1]]`
- Horizontal filter (or) Mask:
`[[-1, -1, -1],[0, 0, 0], [1,1, 1]]`
4. Laplacian Filter.
- Filter (or) Mask:
`[[0, -1, 0],[-1, 4, -1], [0, -1, 0]]` `[[0, 1, 0],[1, -4, 1], [0, 1, 0]]` `[[-1, -1, -1],[-1, 8, -1], [-1, -1, -1]]` `[[1, 1, 1],[1, -8, 1], [1, 1, 1]]`
5. Laplacian Of Gaussian.
`[[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]]`
Sobel, Prewitt, Scharr are the First order derivatives.
Laplacian and Laplacian Of Gaussian (LoG) are second order derivatives.
The Fundamental Principle,
In First order Gradient, Stationary points Indicate the Possibility of an Edge, If a value above the Threshold is considered.
Threshold selection, is Manual process, changing for Input to Input, So, the second order is used Majorly over First Order.
In Second Order Gradient/derivatives, Zero-crossing is considered as Presence of Edge.
Before Calclating the Gradient, Pre-processing Step is Manditory for good results.
1. Image Filtering, using Gaussian Filter. (Weighted Filter)
In real, there will be always Noise present in the Input, as can see the gradient Representation under Noise, Not possible to Detect the Edges.
So, we apply the Gaussian Filtering.
By convolution principle, which reduce the compution cost.
`d/dx(f*g) = f*d/dx(g)`
So, we understood, why Second order derivative is preferred over the First Order and Gaussian Filtering as a pre-processing step.
LoG - Laplacian Of Gaussian, which contains both the functionality of both,
By the convolution principle,
`d/dxd/dx(f*g) = d/dx(f*g') = f*g''`
Double derivative (Laplacian) on the gaussian, so called the laplcain of Gaussian.
The values of the LoG Depends on the standard deviation (defines the spread of the values).
Canny Edge Detector, is the Better Edge Detector Among all.
important thing to mention, is that the algorithm is based on grayscale pictures.
Therefore, the pre-requisite is to convert the image to grayscale before following the above-mentioned steps.
Canny Contain 5 steps.
1. Gaussian Smoothing/Filtering.
2. Image Gradient using, Sobel Operator.
3. Non-Max Suppresssion.
4. Double Thresholding.
5. Hysteresis.
After applying these steps, you will be able to get the following result:
Let's understand with both theory and code,
Importing the Package,
cv2 - Library For computer vision.
numpy - For mathetical operations, in a matrix form.
import cv2
import numpy as np1. Gaussian Smoothing,
As already discussed above the Importance of the gaussian Smoothing.
Remove the Noise in the Image.
Values of Gaussian Filter, calclated from the Gaussian Function,
`G(x,y) = 1/(2*pi*sigma^2)*e^((-x^2 + -y^2) / sigma^2)`
cv2.GaussianBlur(image, (filter_size, filter_size), sigma)
Image - Image on which gaussian Filter to be applied.
filter_size - size of the Filter/Matrix (3 X 3) (5 X 5) ...
sigma - standard deviation, which defines the spread of the data, Importance of pixels from center pixel.
def gaussian_smoothing(img, filter_size, sigma=1.4):
gaussian_img = cv2.GaussianBlur(img, (filter_size, filter_size), sigma)
return gaussian_img
After Applying the Gaussian Smoothing,
2. Sobel Filtering,
Outputs, gradient Magnitude, Gradient Orientation.
def sobel_filtering(img):
# horz_filter, detect the vertical Edges.
# vert_filter, detect the Horizontal Edges.
horz_filter = np.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]], dtype = np.float32)
vert_filter = np.array([[-1, -2, -1], [0, 0, 0], [1, 2, 1]], dtype = np.float32)
# Applying the filters on the Image
horizontal_filtered = cv2.filter2D(img, cv2.CV_64F, horz_filter)
vertical_filtered = cv2.filter2D(img, cv2.CV_64F, vert_filter)
# Gradient Magnitude.
grad = np.hypot(horizontal_filtered, vertical_filtered)
# Squeezing into the range of [0, 255]
grad = (grad / grad.max() )* 255
grad = grad.astype('uint8')
# Gradient Magnitude
theta = np.arctan2(vertical_filtered, horizontal_filtered)
return grad, theta
The result is almost as the expected, but contains the thick and thin edges, Non-max suppression will thin all the edges detected.
Moreover, the gradient intensity level is not uniform, The edge image should contain 2 values (0, white pixel=255)
3. Non-Maximum Suppression.
Non-maxima suppression an edge thinning process.
After computing our gradient magnitude representation, the edges themselves are still quite noisy and blurred,
but in reality there should only be one edge response for a given region, not a whole clump of pixels reporting themselves as edges.
To remedy this, we can apply edge thinning using non-maxima suppression.
To apply non-maxima suppression we need to examine the gradient magnitude G and orientation at each pixel in the image and:
- Compare the current pixel to the `3X3` neighborhood surrounding it
- Determine in which direction the orientation is pointing:
- If it’s pointing towards the north or south, then examine the north and south magnitude
- If the orientation is pointing towards the east or west, then examine the east and west pixels
- If the center pixel magnitude is greater than both the pixels it is being compared to, then preserve the magnitude; otherwise, discard it
In the above picture, the center pixel contain the gradient direction,
Check the values of other pixels, (i, j-1) and (i, j+1) compare with the value of center pixel.
If center pixel, is greater than both the pixels, No change else zero.
def non_maximum_suppression(img, angles):
size = img.shape
suppressed_edges = np.zeros(size)
for i in range(1, size[0]-1):
for j in range(1, size[1]-1):
if (0 <= angles[i, j] < 22.5) or (157.5 <= angles[i, j] <= 180):
q = img[i, j-1]
r = img[i, j+1]
elif (22.5 <= angles[i, j] < 67.5):
q = img[i-1, j-1]
r = img[i+1, j+1]
elif (67.5 <= angles[i, j] < 112.5):
q = img[i-1, j]
r = img[i+1, j]
else:
q = img[i+1, j-1]
r = img[i-1, j+1]
if img[i, j] >= q and img[i, j] >= r:
suppressed_edges[i, j] = img[i, j]
suppressed_edges = np.multiply(suppressed_edges, 255.0/suppressed_edges.max())
return suppressed_edges
The result is the same image with thinner edges, but the intensity is not uniform at all, Rectify this with other post processing steps.
4. Double Thresholding
Double Thresholding classify the pixels as strong, weak and not-relevant pixels,
- Strong pixels are pixels that have an intensity so high that we are sure they contribute to the final edge.
- Weak pixels are pixels that have an intensity value that is not enough to be considered as strong ones, but yet not small enough to be considered as non-relevant for the edge detection.
- Other pixels are considered as non-relevant for the edge.
Thresholding,
- High threshold is used to identify the strong pixels (intensity higher than the high threshold)
- Low threshold is used to identify the non-relevant pixels (intensity lower than the low threshold)
- All pixels having intensity between both thresholds are flagged as weak and the Hysteresis mechanism (next step) will help us identify the ones that could be considered as strong and the ones that are considered as non-relevant.
def double_thresholding(img, lowThresholdRatio=0.01, highThresholdRatio=0.09, weak):
highThreshold = img.max() * highThresholdRatio;
lowThreshold = highThreshold * lowThresholdRatio;
M, N = img.shape
res = np.zeros((M,N), dtype=np.int32)
weak = np.int32(weak)
strong = np.int32(255)
strong_i, strong_j = np.where(img >= highThreshold)
zeros_i, zeros_j = np.where(img < lowThreshold)
weak_i, weak_j = np.where((img <= highThreshold) & (img >= lowThreshold))
res[strong_i, strong_j] = strong
res[weak_i, weak_j] = weak
return (res, weak, strong)The result of this step is an image with only 2 pixel intensity values (strong and weak):
5. Hysteresis,
Based on the threshold results, the hysteresis consists of transforming weak pixels into strong ones,
if and only if at least one of the pixels around the one being processed is a strong one, as described below:
def hysteresis(img, weak, strong=255):
M, N = img.shape
for i in range(1, M-1):
for j in range(1, N-1):
if (img[i,j] == weak):
try:
if ((img[i+1, j-1] == strong) or (img[i+1, j] == strong) or (img[i+1, j+1] == strong)
or (img[i, j-1] == strong) or (img[i, j+1] == strong)
or (img[i-1, j-1] == strong) or (img[i-1, j] == strong) or (img[i-1, j+1] == strong)):
img[i, j] = strong
else:
img[i, j] = 0
except IndexError as e:
pass
return img 
Main Clause,
if __name__ == "__main__":
img = cv2.imread('./Data/car.png')
gray_img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
cv2.imwrite('gray_img.jpg', gray_img)
gaussian_filtered = gaussian_smoothing(gray_img, 5, 1.4)
cv2.imwrite("gaussian_filtered.jpg", np.hstack((gray_img, gaussian_filtered)))
sobel_filtered, theta = sobel_filtering(gaussian_filtered)
cv2.imwrite('sobel_filtered.jpg', np.hstack((gaussian_filtered, sobel_filtered)))
nms_matrix = non_maximum_suppression(sobel_filtered, theta)
cv2.imwrite('nms_img.jpg', np.hstack((sobel_filtered, nms_matrix)))
double_thresholding, weak, strong = double_thresholding(nms_matrix, lowThresholdRatio=0.09, highThresholdRatio=0.17, weak=100)
cv2.imwrite('final_step.jpg', np.hstack((nms_matrix, double_thresholding)))
final = hysteresis(double_thresholding, weak).astype('uint8')
cv2.imwrite("final.jpg", np.hstack((double_thresholding, final)))
Effect of changing the parameters of the Double Thresholding,
Parameters of Double Thresholding, High Threshold and Low Threshold
highThrehold = 43.35
lowThreshold = 3.9015
highThrehold = 43.35
lowThreshold = 5.202
highThrehold = 63.75
lowThreshold = 5.7375
As can observe from the above results, on increasing the Threshold values, the surface texture on the bonnet, unable to capture, loss of information.
Canny on other Inputs:-
Conclusion:-
- Discussed about the Image Gradients, Use of Edge Detection.
- Importance of pre-processing Before applying Edge detector Filters.
- Performed the canny Edge Detector on the Image.
- Tracked the result of Image of all all steps in canny.
- Effect of Threshold values on the result Edge Image.