Archive for the ‘Machine Vision’ Category


Preface

This article is addressed to developers dealing with image processing.

In this Article I will present a technical ( and not theoretical ) perspective of the Hough Transform for the detection of lines and all of the related transformations.

Introduction

One of the basic problems in machine vision is line detection, Given a noisy Image or a video feed the application should automatically detect optimal straight lines in an unsupervised manner, all this, w/o any prior knowledge of the image.

The Algorithm

The first step would be to detect the edges; Since the human brain is much more sensitive to intensity changes a YUV color space will be preferred as the image capture format.

The YUV image would then be traversed though an edge detection filter ( eg. Sobel operator ).

In order to reduce the algorithm execution time and the lines detection resolution, it is important that the resulting edges will contain as less pixels as possible, and thus, Will be as thin as possible, This, can be achieved using eg. The canny algorithm.

Once we have an image with fine edges we have to figure out which set of edge points form a line, This is where the Hough Transform comes in.

Using the Hough Transform, the monochrome edge image is transformed from image coordinates to the Hough space, At the Hough Space, each line is expressed as a point whose cordinates are the angle of the line (in the image plane) relative to the horizontal axis of the image coordinates and the length of a perpendicular to the line intersecting the Cartesian coordinate system origin (in the image plane).

Figure 1

Figure 2

Figure 1 above present the source YUV image, Figure 2 present the image after executing the Canny edge detector, In green, is one of the dominant image lines, in blue is the perpendicular to the line, and, in red is the angle.

In the Hough space, all lines are expressed as points whose coordinates are angle and radius ( red and blue in Figure 2 above ).

The Hough Space is used to present lines only, How then can we convert the set of edge pixels presented in Figure 2 above into Hough Space? We simply assume all possible straight lines going though each of the edge pixels, For each different line we create a counter, Each pixel, having the same line passing through, will increment the counter for the same line, and thus, multiple edge pixels located on the same line will result in Hough Space pixel with higher Counter value, This is demonstrated at Figure 3 bellow.

Figure 3

In dashed yellow are ~all possible~ lines going through the two red dots, In green, is the only line going through both of the points, The counter for each of the yellow lines will be 1 while the counter for the green line will be 2 indicating higher probability that a straight line is passing through the edge pixels presented by the two red dots.

The Hough transform is 2D to 3D transformation where the input is a binary 2D edge image and the result is a 3D image where orientation present the angle and the radius, and intensity present probability for existence of a straight line.

Lines in the hough space are expressed using this line formula: int radius = (int)(x*cos(angle) + y*sin(angle)), the derived ‘radius’ and ‘angle’ form a single hough space point ( pixel ).

Intensity present the amount of edge pixels sharing a common line having the same orientation, Figure 4 bellow presents the result of the Hough transform ( the Hough space ).

Figure 4

The three most dominant peaks are surrounded with red circles, These, indicate the three most dominant lines, specifically, the left road border, the Horizon, and, the right road border ( from left to right ).

The next step is to resolve the specific lines, As noted, these lines are reflected by the most intense pixels, Figure 5 bellow present the lines whose Hough Space pixel brightness is above 80%.

Figure 5

As we can see there is allot of noise in the form of multiple lines, This noise is the result of the rough classification approach mentioned above, The features ( lines ) in this form are not usable.

Redundant lines ( noise ) must be dramatically reduced in order for the extracted features to be usable, Our algorithm should extract the most probable 3 lines described in Figure 4 above.

There are more than few methods to reduce the noise presented in Figure 5 above, One of the most robust is the mean-shift algorithm, This algorithm is used to find local stationary points where the 1st order derivative is equal to zero, we will use this algorithm to find local maxima, and thus, resolve the three most probable lines.

Figure 6 bellow illustrates the result of executing the mean-shift algorithm at the Hough space, This, result in considerable reduction of the amount of lines detected.

Figure 6

We can see that by using the mean-shift algorithm we were able to remove all noise, resulting in the exact three lines that were expected.

Line detection flow diagram

Figure 7

Final words

The Hough Transform is a robust unsupervised algorithm used to detect lines in an arbitrary image.

It enables detection of straight lines without resolving their start/end points, In addition, it is a relatively greedy algorithm, Optimizations of the Hough Transform include the Random Hough transform, the Hierarchical Hough transform and more.

Reducing the resolution of the Hough Space can dramatically improve it’s performance on count of results granularity.

References

Sobel operator, Canny edge detector, mean-shift algorithm, OpenCV