Skip to content

Fix angle discretization in Hough transforms#22164

Merged
asmorkalov merged 1 commit intoopencv:3.4from
lamm45:hough-angles
Aug 31, 2022
Merged

Fix angle discretization in Hough transforms#22164
asmorkalov merged 1 commit intoopencv:3.4from
lamm45:hough-angles

Conversation

@lamm45
Copy link
Copy Markdown
Contributor

@lamm45 lamm45 commented Jun 26, 2022

This aims to fix the bug that occurs in Hough transform (e.g., HoughLines) when 1) The user-supplied max_theta parameter is equal to or barely larger than the true value of theta, 2) The threshold parameter is not very small, and 3) min_theta and theta parameters are chosen such that cvRound in the existing code rounds its argument down.

The bug was discovered in #21983

Here is an ad hoc test that illustrates the modification:

#include <iomanip>
#include <iostream>
#include <opencv2/core.hpp>

int main() {
    double min_theta = 0.0;
    double max_theta = 1.0;
    double delta_thetas[] = {
        0.01,
        0.0999, 0.1, 0.1001,
        0.15,
        0.666, 0.667,
        0.9,
    };

    std::cout << std::setprecision(4) << std::fixed;
    std::cout << "min_theta=" << min_theta << ", max_theta=" << max_theta << "\n";

    for (auto t : delta_thetas) {
        int numangle_old = cvRound((max_theta - min_theta) / t);
        int numangle_new = cvFloor((max_theta - min_theta) / t) + 1;

        std::cout
            << "\ndelta_theta=" << t << "\n"
            << "numangle_old=" << std::setw(3) << numangle_old
            << ", last_theta_old=" << min_theta + (numangle_old-1) * t
            << ", next_theta_old=" << min_theta + numangle_old * t
            << "\n"
            << "numangle_new=" << std::setw(3) << numangle_new
            << ", last_theta_new=" << min_theta + (numangle_new-1) * t
            << ", next_theta_new=" << min_theta + numangle_new * t
            << "\n";
    }
}

And output:

min_theta=0.0000, max_theta=1.0000

delta_theta=0.0100
numangle_old=100, last_theta_old=0.9900, next_theta_old=1.0000
numangle_new=101, last_theta_new=1.0000, next_theta_new=1.0100

delta_theta=0.0999
numangle_old= 10, last_theta_old=0.8991, next_theta_old=0.9990
numangle_new= 11, last_theta_new=0.9990, next_theta_new=1.0989

delta_theta=0.1000
numangle_old= 10, last_theta_old=0.9000, next_theta_old=1.0000
numangle_new= 11, last_theta_new=1.0000, next_theta_new=1.1000

delta_theta=0.1001
numangle_old= 10, last_theta_old=0.9009, next_theta_old=1.0010
numangle_new= 10, last_theta_new=0.9009, next_theta_new=1.0010

delta_theta=0.1500
numangle_old=  7, last_theta_old=0.9000, next_theta_old=1.0500
numangle_new=  7, last_theta_new=0.9000, next_theta_new=1.0500

delta_theta=0.6660
numangle_old=  2, last_theta_old=0.6660, next_theta_old=1.3320
numangle_new=  2, last_theta_new=0.6660, next_theta_new=1.3320

delta_theta=0.6670
numangle_old=  1, last_theta_old=0.0000, next_theta_old=0.6670
numangle_new=  2, last_theta_new=0.6670, next_theta_new=1.3340

delta_theta=0.9000
numangle_old=  1, last_theta_old=0.0000, next_theta_old=0.9000
numangle_new=  2, last_theta_new=0.9000, next_theta_new=1.8000

It looks like there might also be other issues related to the use of cvRound in hough.cpp. However, this PR should fix all issues related to angles (thetas).

Pull Request Readiness Checklist

See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request

  • I agree to contribute to the project under Apache 2 License.
  • To the best of my knowledge, the proposed patch is not based on a code under GPL or another license that is incompatible with OpenCV
  • The PR is proposed to the proper branch
  • There is a reference to the original bug report and related work
  • There is accuracy test, performance test and test data in opencv_extra repository, if applicable
    Patch to opencv_extra has the same branch name.
  • The feature is well documented and sample code can be built with the project CMake

@asmorkalov
Copy link
Copy Markdown
Contributor

asmorkalov commented Jun 29, 2022 •
edited
Loading

C++ and OpenCV version diverges:

 [  FAILED  ] OCL_HoughLinesFixture_HoughLines.HoughLines/0, where GetParam() = (640x480, 0.1, 0.0174533)
[  FAILED  ] OCL_HoughLinesFixture_HoughLines.HoughLines/2, where GetParam() = (640x480, 1, 0.0174533)
[  FAILED  ] OCL_HoughLinesFixture_HoughLines.HoughLines/4, where GetParam() = (1280x720, 0.1, 0.0174533)
[  FAILED  ] OCL_HoughLinesFixture_HoughLines.HoughLines/6, where GetParam() = (1280x720, 1, 0.0174533)
[  FAILED  ] OCL_HoughLinesFixture_HoughLines.HoughLines/8, where GetParam() = (1920x1080, 0.1, 0.0174533)
[  FAILED  ] OCL_HoughLinesFixture_HoughLines.HoughLines/10, where GetParam() = (1920x1080, 1, 0.0174533)
[  FAILED  ] OCL_HoughLinesFixture_HoughLines.HoughLines/12, where GetParam() = (3840x2160, 0.1, 0.0174533)
[  FAILED  ] OCL_HoughLinesFixture_HoughLines.HoughLines/14, where GetParam() = (3840x2160, 1, 0.0174533)

@lamm45
Copy link
Copy Markdown
Contributor Author

lamm45 commented Jun 30, 2022 •
edited
Loading

Right. So now there seems to be an issue when 1) min_theta=0 and max_theta=pi, 2) The discretization and threshold parameters satisfy certain condition, and 3) There is a vertical line in the image. If all these hold, then it may happen that a line is detected twice, first with rho>0 and theta=0, and then with rho<0 and theta=pi. In the old code, these cases were less likely to yield two separate detections, because the discretized theta was often missing one point, so essentially theta did not always reach pi even in cases where it should have been.

Let me try to check how the removal of duplicate detections is usually done in literature.

By the way, there is no difference in C++ and OpenCL code in this regard. It just happens that the OCL performance tests provide better test cases for this particular situation, which is why the issue was found during performance testing. Here starts the relevant test setup with three horizontal and three vertical lines:

opencv/modules/imgproc/perf/opencl/perf_houghlines.cpp

Line 42 in 2a4926f

line(src, Point(0, 100), Point(src.cols, 100), Scalar::all(255), 1);

@lamm45
Copy link
Copy Markdown
Contributor Author

lamm45 commented Jul 4, 2022

The updated version seems to pass all the tests and also fix the original problem. I quite arbitrarily chose the discretization such that when min_theta=0 and max_theta=pi, then the last angle is always at most pi - 1/2*theta_step (and thus at least pi - 3/2*theta_step. As I wrote in the commit message, I think that a better way in this situation would be to adjust theta_step such that the discretization is uniform between 0 to pi. However, I will leave that for future work.

@asmorkalov asmorkalov requested a review from vpisarev July 5, 2022 18:39
@vpisarev
Copy link
Copy Markdown
Contributor

vpisarev commented Aug 26, 2022

@lamm45, the fix looks reasonable, thank you for the contribution! Could you, please, add a test that reproduces the above-mentioned bug?

@asmorkalov asmorkalov added the pr: needs test New functionality requires minimal tests set label Aug 26, 2022
@lamm45
Copy link
Copy Markdown
Contributor Author

lamm45 commented Aug 28, 2022

Test added.

asmorkalov
asmorkalov reviewed Aug 29, 2022
View reviewed changes
@asmorkalov
Copy link
Copy Markdown
Contributor

asmorkalov commented Aug 29, 2022

Thanks a lot for added test!

@asmorkalov asmorkalov removed the pr: needs test New functionality requires minimal tests set label Aug 29, 2022
@asmorkalov asmorkalov self-requested a review August 30, 2022 15:58
asmorkalov
asmorkalov reviewed Aug 30, 2022
View reviewed changes
Copy link
Copy Markdown
Contributor

@asmorkalov asmorkalov left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

👍 Looks good. Thanks a lot for the contribution. Could you squash the commits to have single commit patch in the history.

@lamm45
Fix angle discretization in Hough transforms
1f0bfc8 
In some situations the last value was missing from the discrete theta
values. Now, the last value is chosen such that it is close to the
user-provided maximum theta, while the distance to pi remains always
at least theta_step/2. This should avoid duplicate detections.

A better way would probably be to use max_theta as is and adjust the
resolution (theta_step) instead, such that the discretization would
always be uniform (in a circular sense) when full angle range is used.
asmorkalov
asmorkalov approved these changes Aug 31, 2022
View reviewed changes
Copy link
Copy Markdown
Contributor

@asmorkalov asmorkalov left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

👍

@asmorkalov asmorkalov merged commit a72074b into opencv:3.4 Aug 31, 2022
@alalek alalek mentioned this pull request Oct 15, 2022
Merged
@alalek alalek mentioned this pull request Jan 8, 2023
Merged
@asmorkalov asmorkalov added this to the 4.7.0 milestone Jan 23, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@asmorkalov asmorkalov asmorkalov approved these changes

@vpisarev vpisarev Awaiting requested review from vpisarev

Assignees

@vpisarev vpisarev

Labels

bug category: imgproc

Projects

None yet

Milestone

4.7.0

Development

Successfully merging this pull request may close these issues.

HoughLines: min_theta behavior

4 participants

@lamm45 @asmorkalov @vpisarev @alalek