Line detection using Hough transform

The Hough transform is a feature extraction technique used in image analysis, computer vision, and digital image processing. It is a popular technique to detect any shape as long as that shape can be represented in a mathematical form. The technique will find imperfect instances of objects within classes of shapes by a voting procedure. This voting procedure is carried out in the parameter space, from which object candidates are obtained as local maxima is a so-called accumulator space is explicitly constructed by the algorithm for computing the Hough transform. In this post, we will see how the Hough transform works for lines.

1. Theory

A straight line in the Cartesian coordinate system is often written as

\begin{equation} y = mx + b. \tag{1} \end{equation}

For Hough transform, we will express lines in the Polar coordinate system. A line can be written in the Polar coordinate system as \begin{equation} y = -\dfrac{cos\theta}{sin\theta}x + \dfrac{\rho}{sin\theta}. \tag{2} \end{equation}

Where \(\rho\) is the perpendicular distance from the origin to the line (\(\rho \geq 0\)), and \(\theta\) is the angle formed by the perpendicular line and the horizontal axis measured in counter-clockwise (\(0^o \leq \theta \leq 360^o\)). Arranging the terms, we have \begin{equation} \rho = x.cos\theta + y.sin\theta. \tag{3} \end{equation}

Line equation

Figure 1. Line equation.

So any line can be represented in these two terms (\(\rho, \theta\)). The basic idea of the Hough transform is to calculate the curves that represent all possible lines through each pixel and to accumulate the results in the Hough space. Each edge pixel contributes one curve through the Hough space accumulator, and each accumulator cell through which the curve passes gets incremented. If each of \(n\) accumulated edge pixels lines on a perfect line \(L_1\), the Hough cell corresponding to \(L_1\) ends up with a value of \(n\). In most real images, the points will be close to but not perfect on \(L_1\), the Hough line cell for \(L_1\) will contain a local maximum smaller than N. The cell around the maximum cell drops down to smaller values. When the accumulation for all edge pixels in the image is finished, the Hough accumulator contains a peak for each line in the image. A peak selection algorithm, (in the simplest case, just search for the maximum value) finds the strongest line in the image.

To begin with the implementation, we create a 2D array accumulator to hold values of two parameters and set it to \(0\) initially. Let’s assume that rows denote the \(\rho\) and columns denote the \(\theta\). Suppose we want the accuracy of angles \(\Delta_{\theta}\) (which is the difference between two angles represented by two adjacent columns in the accumulator array) to be \(1^o\), we will need 360 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.

The following C++ code is to accummulate the results in the Hough space:

int rho_index_max = std::round(sqrtf((float)(image.rows * image.rows + image.cols * image.cols)));
int theta_index_max = std::round(2 * M_PI / delta_theta_);
cv::Mat accumulator = cv::Mat::zeros(cv::Size(theta_index_max, rho_index_max), CV_16UC1);
ushort* accumulator_data = (ushort*)accumulator.data;

// Run the accumulator
for (int row_index = 0; row_index < image.rows; ++row_index)
{
    for (int column_index = 0; column_index < image.cols; ++column_index)
    {
        // The edge pixels are black
        if (image.data[row_index * image.cols + column_index] == 0)
        {
            for (float theta = 0; theta < 2 * M_PI; theta += delta_theta_)
            {
                int rho = std::round(column_index * cos(theta) + row_index * sin(theta));
                if (rho >= 0)
                {
                    int theta_index = std::round(theta / delta_theta_);
                    ++accumulator_data[rho * accumulator.cols + theta_index];
                }
            }
        }
    }
}

You can find the complete version of the code here.

Below is an image which shows the accumulator. Bright spots at some locations denote they are the parameters of possible lines in the image:

Edges Accumulator

Figure 2. Accumulator.

To optimise the speed of the accumulator, we can replace the calls to \(cos(\theta)\) and \(sin(\theta)\) with lookup tables. The \(\theta\) values can be precalculated because they depend only on the step size.

2. Peak detection algorithm

The simplest peak detection algorithm simply searches for the cell with the maximum value in the accumulator and calculates the angle \(\theta_i\) and distance values from the cell index \(\rho_i\). Here’s how we calculate the angle and distance for the cell at row \(r_i\) and column \(c_i\):

\[\begin{align} \left\lbrace \begin{array}{lll} \rho_i & = & r_i\\ \theta_i & = & c_i\Delta_{\theta} \end{array} \right.. \tag{4} \end{align}\]

Usually, an image contains more than one line, though. You will need to way the successively finding peaks that are far enough away from previous peaks. Each peak in the Hough accumulator might be spread across several cells as the edge pixels in a typical image will not be on perfectly straight lines. The iterative peak detection algorithm follows these following steps:

Find the maximum cell in the accumulator;
Find the area around the maximum cell that belongs to the same line;
Mark or zero out the area;
Continue at step 1 until all cells are below some preselected threshold.

Step 2 is a tricky part. How can you determine how many neighbouring cells belong to the same maximum? You have to choose which range of \(\theta\) and \(\rho\) values should be merged with the maximum line.

The following C++ code is to select good peaks from the accumulator:

// Run the peak selection algorithm
int row_range = rho_range_;
int column_range = std::round(theta_range_ / delta_theta_);
std::vector<Line> lines;
while (true)
{
    // Find the maximum cell in the accumulator
    double max_cell_value;
    cv::Point max_cell_location;
    cv::minMaxLoc(accumulator, nullptr, &max_cell_value, nullptr, &max_cell_location);
    if ((int)max_cell_value < accumulator_threshold_)
    {
        break;
    }

    // Zero out the area around the maximum cell that belongs to the same line
    for (int row_index = std::max(max_cell_location.y - row_range, 0); row_index < std::min(max_cell_location.y + row_range, accumulator.rows); ++row_index)
    {
        for (int column_index = std::max(max_cell_location.x - column_range, 0); column_index < std::min(max_cell_location.x + column_range, accumulator.cols); ++column_index)
        {
            accumulator_data[row_index * accumulator.cols + column_index] = 0;
        }
    }
    float rho = max_cell_location.y;
    float theta = max_cell_location.x * delta_theta_;
    lines.push_back(Line{rho, theta});
}
return lines;

You can find the complete version of the code here.

References

← Previous Post Next Post →