[CV] 6. Structure Extraction with Hough Transform (line, circle)

Published in

Learning

8 min readNov 23, 2020

1. Motivation of Structure Extraction

In the last chapter, we saw how edges in an image are detected using image gradients, e.g. Canny Edge Detector. In computer vision, the edge detection is just the beginning for image processing. Let’s take a look at the following example, Fig 1.

**Figure 1. Visual comparison of object boundary (human segmentation) and detected edge (using gradient), from [1, 5]**

Given image (left panel in Fig 1), human can easily distinguish an object from other objects and background, meaning we are capable of extracting object boundaries (middle panel). However, this is not the case for computers. In order for computers to find object boundaries, they need something more than a simple edge detection (right panel).

For this purpose, we will take a look at a popular method to extract objects in an image, so-called ‘Hough Transform’.

2. Difficulty of Structure Extraction

Among many structures, let us focus on a line here for the sake of simplicity. Assume the left panel in Fig 2 is an given image and the lines we are interested in are marked with light blue. As a starting point, we first detect edges, which is shown in the right panel. The reason why extracting line (note the difference from an edge) is difficult is because it is hard to answer the following questions:

Which point (i.e. edge point in right panel) belongs to which line?
How many lines are there in given image?
How should we manage missing edge parts (shown in the yellow ellipse) and noise in edge points (orange ellipse) ?

Figure 2. Input image (left) with interesting lines (light blue) and extracted edges (right), from [1,2]

3. Hough Transform

The Hough Transform is designed to answer all of them by using a voting technique. Its well-defined main idea, according to [2], is:

Vote for all possible lines on which each edge point could belong
Look for line candidate that get many votes
Noise features will cast votes as well, however their votes should be inconsistent (meaning, valid lines will get larger number of votes compared to noise lines)

Its idea can be applied to any types of structure, but in this article, we will mainly focus on the line and circle.

4. Line Detection with Hough Transform

**Figure 3. Illustration of Hough Transform on a line and a point in image space, from [1, 3]**

Let (x, y) be a coordinate in an image and (m, b) be a coordinate in Hough space. We can observe that a line (defined by m₀ and b₀) in the image space ( where axis is x and y) corresponds to a point in Hough space (where axis is m and b), and Vice Versa (point in image space corresponds to a line in Hough space). More specifically, Hough Transform finds all possible lines which pass a point (x₀, y₀), and each line can be parametrized by a point (m₀, b₀) in Hough space. Therefore, the collection of all (m₀, b₀) becomes a line in Hough space.

4.1 Then how exactly the Hough Transform of line detection works?

Let’s say there is a line in image space, which is shown in below. By using an edge detector, we get two edge points (x₀, y₀) and (x₁, y₁). Afterward, by performing Hough Transform for (x₀, y₀) and (x₁, y₁), we obtain two red lines in Hough space as is shown in the following figure.

Recall our goal with Hough Transform: detecting a line that contains both (x₀, y₀) and (x₁, y₁). Surprisingly, this can be achieved by computing the intersection of two red lines.

Once we compute the line parameter (m, b) for given two equations, we can find the line: y = m·x + b.

Note that, the term ‘vote’ for certain point in Hough space refers to the number of lines in Hough space which pass the point. In above image, all point (in red lines) in Hough space get 1 vote except for the intersection point which gets 2 votes.

Described process of Hough Transform for line detection can also be applied to further complex cases with more edge points in image such as the following figure. Key idea, regardless of number of edge points, remains the same.

For each edge points in image space, again Hough Transform maps it to the line in Hough space, which is a set of line parameters (m, b) of all possible lines that pass the given edge point. Then find points (m, b) with the most votes and, subsquently, construct lines in image space with found points (m,b).

4.2. Polar representation of lines and corresponding hough space

While the idea of Hough Transform for line works, there is a computational issue that b takes infinite value in Hough (parameter) space (m, b) when it comes to vertical lines. In order to resolve the problem, another parameter space with line parameter (ϴ, d) is applied where d is perpendicular distance from line to origin, and ϴ is an angle with the x-axis. Then, now, the line can be defined: x·cosϴ + y·sinϴ = d.

**Figure 4. polar representation of line, from [1, 3]**

For those who are not familiar with the polar representation of line, you can consider it as when the dot-product of (x, y) and (cosϴ, sinϴ) is d, where (cosϴ, sinϴ) is the normal of a line.

As now the Hough space has axis of (ϴ, d), a point in image space is mapped to a Sinusoid segment in Hough space. This might seem new and awkward, but all the other steps, including voting process and finding intersection point with most votes for detecting line in image, remains the same.

**Figure 5. Example of Hough space (*ϴ, d*) given image space, from [1, 8]**

4.3 Steps of Hough Transform for lines

In short, we can summarize the steps of basic Hough Transform for lines as follows:

However, this algorithm has a time complexity issue as it computes all possible lines that pass a point for each edge point in image. In order to reduce the number of computation, the advanced algorithm using gradient information was proposed as below:

**Advanced Hough Transform Algorithm using Gradient Orientation**

It improves the time complexity by only concerning the line which is in the same direction with the gradient orientation at edge point (x, y).

4.4 Retrieve line segments, instead of lines

The mentioned accumulator array H above only stores information of votes for each parameter (ϴ, d), and therefore, the algorithm will always return lines with infinite length. This is natural because the algorithm does not store any information about where the line starts and ends.

finite lines (left) vs infinite lines (right), from openCV

In case the finite lines are desired, we need one additional trick. In order to determine which area of the image contributes to a detected infinite line in length, H needs to store coordinate information for all points, and use this information to limit the lines by looking up which point votes to which line. However, this approach often consumes too much memory. Another way is to search along the detected infinite lines in the edge detection map to find the start and end points.

For more detail about line segments and an approach, so-called Progressive Probabilistic Hough Transform, please visit [8]

5. Circle Detection with Hough Transform

Similar to line detection, this time we define a Hough space for circle which is parameterized by (a, b, r), where the center is (a,b) and radius is r.

If r is known, then Hough space is two-dimensional and works almost in a same way as line detection. Hough transform of Circle draws, in Hough space, all possible locations of circle center for each edge point (x, y) in image space. The set of all possible circle centers, which is a Hough Transform output, given an edge point (x, y) with fixed radius r is again a circle in Hough space as is illustrated below. Then the circle center, what we are looking for, in image space is determined by parameter (a, b) at which the accumulator array H[a,b] gets the most votes.

**Figure 6. Illustration of Hough Transform for Circles when radius ‘r’ is known, from [1, 2]**

In most cases, however, the radius r is unknown. This indicates the degrees of freedom is 3 (a, b, r), and therefore Hough space also becomes 3D. As a result, a point (x, y) in image space is mapped to a cone in Hough space.

**Figure 7. Illustration of Hough Transform for Circles when radius ‘r’ is unknown, from [1, 2]**

As one can guess, the computation of Hough Transform algorithm for detecting circles when the radius is unknown is expensive. In order to reduce the computations, again the gradient orientation (direction) plays a significant role.

**Figure 8. Illustration of Hough Transform for Circles using image gradient orientation, when radius ‘r’ is unknown, from [1, 2]**

By taking the characteristic of circle and gradient direction at point (x, y) into account, we can assume that it is highly likely the circle center lies on the line which starts at (x, y) along with the direction ϴ.

Eventually, an edge point (x, y) is mapped to a line, as is shown in Fig 8, in Hough space and the algorithm gets much faster.

6. Pros and Cons of Hough Transform (Summary)

Advantages

all edge points are processed independently by Hough Transform, and therefore even a partially occluded object (image structure) can be detected.
some robustness to noise: noise point gets less vote and is unlikely to survive after thresholding.
can detect multiple instances of an object in a single pass

Disadvantages

time complexity (search space) increases exponentially with the number of object parameters (think of line -> circle).
edge points from non-target-shape objects reduce the detection quality.
quantization: hard to pick a good grid size (e.g. image orientation quantization: ϴ).