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

Question

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?

Richard

Answer 1

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.

Bois

I made a simple test on the order of returned lines. It gives longer lines first. It should be because sort function uses hough_cmp_gt. – Tucker

Answer 2

It might be that they are returned in lexicographical (r, Θ) or (Θ, r) order, so your parallel lines will occur either by increasing distance from the origin or randomly (the order of the angles is unpredictable).

The designer of the function have no reason to enforce a particular order, as there is no logical of the lines in the general case (parallel or quasi-parallel lines are an exception).

If you want a specific order, it is up to you to specify and implement it. For example by sorting in increasing r, taking care to assign a negative sign when Θ made a half-turn. You can also sort on the ordinates of the intersections with a vertical.

---

After Piglet's finding, they are returned by strength. My previous paragraph still applies.

Conformal