Getting points of intersection of hough lines opencv c++

Question

This is not similar to this post, because in python we have numpy to solve all the problems. I have made a code in c++ to find the intersection of hough lines.

vector<Point2f> new_intersection(vector<Vec2f> lines) {
    vector<Point2f> intersections;
    float m1, c1, m2, c2;
    float x1, y1, x2, y2;
    float dx, dy, dx1, dy1;
    for (auto&& i : combinations(lines, 2)) {
        Point pt;
        float rho = i[0][0], theta = i[0][1];
        Point pt1, pt2;
        double a = cos(theta), b = sin(theta);
        double x0 = a * rho, y0 = b * rho;
        pt1.x = cvRound(x0 + 1000 * (-b));
        pt1.y = cvRound(y0 + 1000 * (a));
        pt2.x = cvRound(x0 - 1000 * (-b));
        pt2.y = cvRound(y0 - 1000 * (a));

        Point pt3, pt4;
        float rho1 = i[1][0], theta1 = i[1][1];
        double a1 = cos(theta1), b1 = sin(theta1);
        double x01 = a1 * rho1, y01 = b1 * rho1;
        pt3.x = cvRound(x01 + 1000 * (-b1));
        pt3.y = cvRound(y01 + 1000 * (a1));
        pt4.x = cvRound(x01 - 1000 * (-b1));
        pt4.y = cvRound(y01 - 1000 * (a1));

        dx = pt2.x - pt1.x;
        dy = pt2.y - pt1.y;
        m1 = dy / dx;
        c1 = pt1.y - m1 * pt1.x;

        dx1 = pt4.x - pt3.x;
        dy1 = pt4.y - pt3.y;
        m2 = dy1 / dx1;
        c2 = pt3.y - m2 * pt3.x;

        if (m1 == m2)
            continue;
        else{
            pt.x = (c2 - c1) / (m1 - m2);
            pt.y = m1 * pt.x + c1;
            intersections.push_back(pt);
        }
    }
    return intersections;
}

I have done this by using simple math formulas to find intersection between all the lines excluding parallel lines. Problem is this doesn't give all the correct intersections. Checkout original, hough and intersection points image below.

These are the intersection points i am getting

inter1: [-3345, 116]

inter2: [163, 177]

inter3: [-1527, 115]

inter4: [164, 87]

inter5: [163, 116]

inter6: [-2.14748e+09, -2.14748e+09]

Mathematically the formulas are correct and should give correct points.

The test `m1==m2` supposes that the lines are *perfectly* parallel, which is not actually the case, thus an intersection is reported very far away. You should consider a threshold around `m1` and `m2`. Moreover, when `dx` or `dx1` are very small `m1` and `m2` become very unstable. — prog-fh, Dec 30 '19 at 10:56
After you've pushed candidate points to the vector, you can filter out those points that fall out of the image bounds. — frogatto, Dec 30 '19 at 11:38
you could print all the "continue" cases and find out yourself, why they are skipped unexpected or whether some lines are not processed at all. I would expect 20 intersections for 5 lines if they are not perfectly parallel. — Micka, Dec 30 '19 at 11:49

score 1 · Answer 1 · answered Dec 30 '19 at 11:34

You should not rely on the formular c = y - m * x, as this formular - while mathematicly correct - fails to represent vertical lines (eg theta = 0) correctly, so your calculation either becomes unstable (due to limited precision, if the line is very close to vertical) or fails completly, since m becomes infinity if pt1.x == pt2.x.

Instead, you should calculate the intersection using vectors. This calculation may be a bit complexer, but does not have any problems with vertical lines. With vectors, you solve pt1 + lambda * (pt2 - pt1) = pt3 + alpha * (pt4 - pt3) for either lambda or alpha and then put that value in the corresponding side. In code, this would look like this:

float dx0 = pt2.x - pt1.x;
float dx1 = pt4.x - pt3.x;
float dy0 = pt2.y - pt1.y;
float dy1 = pt4.y - pt3.y;
//Solve for lambda:
float div = (dy0 * dx1) - (dx0 * dy1);
if(abs(div) < EPSILON) { continue; } //lines are parallel
float lambda = (((pt1.x - pt3.x) * dx1) + ((pt1.y - pt3.y) * dy1)) / div;
//put lambda back into pt1 + lambda * (pt2 - pt1) to calculate intersection point:
pt.x = pt1.x + (lambda * dx0);
pt.y = pt1.y + (lambda * dy0);

There's also a formular to calculate the intersection point using theta and rho directly, if you prefere that.

See https://stackoverflow.com/questions/383480/intersection-of-two-lines-defined-in-rho-theta-parameterization There's both the math and the code for that formular in the answers — Bizzarrus, Apr 03 '20 at 06:18

Getting points of intersection of hough lines opencv c++

1 Answers1