mirror of
https://github.com/opencv/opencv.git
synced 2026-07-21 19:33:03 +04:00
Adrian Kretz
dd214962a5
Better Durand-Kerner Initialization #29109 While investigating issue #23644, I have found [this paper](https://link.springer.com/article/10.1007/BF01935059) which presents a good initialization for the Durand-Kerner algorithm. Basically the idea is to put the initial points equidistantly on a circle on the complex plane. The radius of the circle is computed as <img width="607" height="178" alt="image" src="https://github.com/user-attachments/assets/ea31b002-c924-4b93-9334-3e59597c896b" /> Note that the $a_i$ coefficients in that paper are reversed compared to OpenCV. That's where the `(n - i)` in the code comes from. I have implemented just the mean of the $u_i$'s for the sake of simplicity. That's already enough to make the algorithm converge in all cases I have tested. I have used this to test for convergence for many polynomials of order 2 and 4 and coefficients of different magnitudes: ```cpp TEST(Core_SolvePoly, large_test) { cv::Mat_<float> coefs3(1,3); cv::Mat_<float> coefs5(1,5); cv::Mat r; double prec; for (int c0 = -20; c0 <= 20; c0++) { coefs3.at<float>(0) = c0; for (int c1 = -20; c1 <= 20; c1++) { coefs3.at<float>(1) = c1; for (int c2 = -20; c2 <= 20; c2++) { coefs3.at<float>(2) = c2; prec = cv::solvePoly(coefs3, r); EXPECT_LE(prec, 1e-6); } } } for (int c0 = -10; c0 <= 10; c0++) { coefs5.at<float>(0) = c0; for (int c1 = -10; c1 <= 10; c1++) { coefs5.at<float>(1) = c1; for (int c2 = -10; c2 <= 10; c2++) { coefs5.at<float>(2) = c2; for (int c3 = -10; c3 <= 10; c3++) { coefs5.at<float>(3) = c3; for (int c4 = -10; c4 <= 10; c4++) { coefs5.at<float>(4) = c4; prec = cv::solvePoly(coefs5, r); EXPECT_LE(prec, 1e-2); } } } } } for (int i = -10; i < 10; i++) { coefs3.at<float>(0) = pow(2, i); for (int j = -10; j < 10; j++) { coefs3.at<float>(1) = pow(2, j); for (int k = -10; k < 10; k++) { coefs3.at<float>(2) = pow(2, k); prec = cv::solvePoly(coefs3, r); EXPECT_LE(prec, 1e-6); } } } } ``` This test passes, but I have not committed it because it runs for a couple of seconds. This fixes #23644 and replaces #29055. I have checked #29055 and it does not pass the test above. It seems to be optimized to the precise polynomial of #23644. ### Pull Request Readiness Checklist See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request - [x] I agree to contribute to the project under Apache 2 License. - [x] 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 - [x] The PR is proposed to the proper branch - [x] There is a reference to the original bug report and related work - [x] There is accuracy test, performance test and test data in opencv_extra repository, if applicable Patch to opencv_extra has the same branch name. - [x] The feature is well documented and sample code can be built with the project CMake