pythonopencvimage-processingstraight-line-detectionhoughlines

In what order, OpenCV's HoughLines lists the detected lines in the [rho,theta] matrix?


When a given image with lines is passed to OpenCV's HoughLine transform, it returns a list of rho and theta pairs, each pair defining an individual line. What is the order in which lines are listed in this list of rho,theta pairs.

for eg, when this image with 8 lines was uses in python, image with 8 line

following, rho,theta matrix was returned for the eight lines.

[[ 461.            1.48352981]
 [ 380.            1.48352981]
 [ 212.            1.48352981]
 [ 112.            1.48352981]
 [  65.            1.48352981]
 [ 334.            1.48352981]
 [ 269.            1.48352981]
 [ 508.            1.48352981]]

How is the order in which lines are listed here in this matrix, is determined by openCV?


Solution

  • From the OpenCV source code https://github.com/opencv/opencv/blob/master/modules/imgproc/src/hough.cpp

    function HoughLinesStandard implements the standard hough transform starting at line 80.

    If we scroll a bit further down (line 166) we find:

     // stage 3. sort the detected lines by accumulator value
        std::sort(_sort_buf.begin(), _sort_buf.end(), hough_cmp_gt(accum));
    

    Now the list of lines is sorted ascending by accumulator value. And the best linesMax results are put into the output buffer.

     // stage 4. store the first min(total,linesMax) lines to the output buffer
        linesMax = std::min(linesMax, (int)_sort_buf.size());
        double scale = 1./(numrho+2);
        for( i = 0; i < linesMax; i++ )
        {
            LinePolar line;
            int idx = _sort_buf[i];
            int n = cvFloor(idx*scale) - 1;
            int r = idx - (n+1)*(numrho+2) - 1;
            line.rho = (r - (numrho - 1)*0.5f) * rho;
            line.angle = static_cast<float>(min_theta) + n * theta;
            lines.push_back(Vec2f(line.rho, line.angle));
    

    In case you don't know what the accumulator value is, please read how the Hough Transform works. https://en.wikipedia.org/wiki/Hough_transform

    It basically says how many pixels contributed to that rho theta pair.