Line detection has many applications in image processing, computer vision, and machine vision. A very simple example of line detection's application is SUDOKU Solver. If you want to solve SUDOKU which locates in an image, first, you have to detect SUDOKU grid and extract digits to recognize those numbers. Hough Line Transform is one of the popular techniques to detect lines in images.
This article will explain how to detect lines in an image using Hough Line Transform with OpenCV library and Python code example.
Detecting line in SUDOKU grid
Note that we only can use Hough Line Transform after we detected edges on the image. The detected edges image is the input of Hough Line Transform. There are many techniques to detect edges on the image such as Sobel or Canny algorithms. I will explain the idea of these techniques when I have enough time :). But here are very good explanation video of edges detection on Computerphile Channel (Check the link below)
1. Finding the Edges (Sobel Operator) - https://www.youtube.com/watch?v=uihBwtPIBxM
2. Canny Edge Detector - https://www.youtube.com/watch?v=sRFM5IEqR2w
The image after detect edge will be like this (Check the image below). This image will be a grayscale image. Every pixel on the edge will have a value of 255 or 1(white lines), otherwise, the pixel not located on the edge will have a value of 0 (black area).
Image after apply edge detection
Now, let's see how Hough Line Transform can detect lines in the image.
Theory
We know that every point on the line always satisfies this equation: `rho = xcostheta + ysintheta` ` (1)`. If we know a pair (`rho, theta`), we always can draw a line.
So, the idea of Hough Transform is creating a 2D array `M` as a matrix to hold the values of two parameters (`rho` and `theta`). Let rows denote the `rho` and columns denote the `theta`. We assume there exists a line `d` with `rho = rho_1` and `theta = theta_1` on the image. If a point `A (x_1, y_1)` lie on `d` satisfies `(1)` `rho_1 = x_1costheta_1 + y_1sintheta_1`, we increase the value of `M[rho_1][theta_1]` by 1. We continue this process for every point on the line, increasing the value of `M[rho_1][theta_1]` by 1 if that point satisfies equation `(1)`. At the end, the value of `M[rho_1][theta_1]` will be must bigger than another cell in 2D array `M`. And the value of `M[rho_1][theta_1]` will be also the length of the line.
The size of the 2D array depends on the accuracy you need. Suppose you want the accuracy of angles to be 1 degree, you need 180 columns. For `rho`, the maximum distance possible is the diagonal length of the image. So taking one pixel accuracy, the number of rows can be the diagonal length of the image.
Example
Suppose we have an image with 20x20 pixels and contain 2 lines (black lines - d1 and d2) like this.
If you want the accuracy of angles to be 1 degree and the maximum distance possible is the diagonal length of the image, you will need a 2D array with 180 columns and 28 rows (`20sqrt(2)~~28`).
After running Hough Line Transform on that image, we will have `M[7][0]=15` and `M[12][90]=8` corresponding to the length of `d1` and `d2`.
So now, let's impement a simple Python code to see how Hough Line Transform actually work.
import numpy as np from sympy import * # Create image with 20x20 pixel img = np.zeros((20,20), dtype=np.int) # Draw 2 lines correspond with above image # Every pixel lies on a line will have value of 1 # Draw line d1, length = 15 for i in range(0,15): img[i+1][7]=1 # Draw line d2, length = 8 for i in range(11,19): img[12][i]=1 # Create a 2D array to holds the value of rho and theta M = np.zeros((28,91), dtype=np.int) # Scan image to find some lines for x in range(20): for y in range(20): if(img[x][y]==1): for rho in range(28): for theta in range(0,91): if(rho==y*cos(theta*pi/180) + x*sin(theta*pi/180) M[rho][theta] += 1 # Print the value of M[7][0] and M[12][90] to see the length of d1 and d2 print M[7][0] # Result: 15 print M[12][90] # Result: 8
Note that we will use cos, sin method and pi in sympy library instead of using numpy because pi in numpy (numpy.pi) is not actual pi value so you will get the wrong value when using numpy.cos(pi/2).
Try to run by yourself and see how Hough Line Transform works.
Hough Line Transform in OpenCV
In real problem, there are too many lines in image and quite complex to write a code and detect line by yourself. I prefer to use OpenCV - A strong Computer Vision library to deal with Line Detection problem.
We can simply use Hough Line Transform in OpenCV with cv2.HoughLines() function. It will returns an array of `(rho, theta)` values. `rho` is measured in pixels and `theta` is measured in radians.
The first parameter of cv2.HoughLines() function is a binary image, so apply thresholding or use canny edge detection before finding applying Hough Line Transform. The second and third parameters are `rho` and `theta` accuracies respectively. The final parameter is the threshold, which means minimum length of a line to be detected.
Here is the code I took from OpenCV online documents website with adding some explanations.
import cv2 import numpy as np # Loading image contains lines img = cv2.imread('lines.jpg') # Convert to grayscale gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY) # Apply Canny edge detection, return will be a binary image edges = cv2.Canny(gray,50,100,apertureSize = 3) # Apply Hough Line Transform, minimum lenght of line is 200 pixels lines = cv2.HoughLines(edges,1,np.pi/180,200) # Print and draw line on the original image for rho,theta in lines[0]: print(rho, theta) a = np.cos(theta) b = np.sin(theta) x0 = a*rho y0 = b*rho x1 = int(x0 + 1000*(-b)) y1 = int(y0 + 1000*(a)) x2 = int(x0 - 1000*(-b)) y2 = int(y0 - 1000*(a)) cv2.line(img,(x1,y1),(x2,y2),(0,0,255),2) # Show the result cv2.imshow("Line Detection", img) cv2.waitKey(0) cv2.destroyAllWindows()
I used this image to run Hough Line Transform in.
References:
[1] OpenCV: Hough Line Transform - http://docs.opencv.org/3.1.0/d6/d10/tutorial_py_houghlines.html
[2] Hough Line Transform - Wikipedia - https://en.wikipedia.org/wiki/Hough_transform
