Undistort points convergence #27993
I have looked into the `undistortPoints()` problem of issue #27916 and have found a solution. The problem is, as @Linhuihang has correctly pointed out, that the fixed-point iterations do not converge. Here are the functions which are optimized for the undistortion problem:
$$
\begin{aligned}
r^2 &= x'^2 + y'^2 \\
f_1(x') &= \frac{1 + k_4 r^2 + k_5 r^4 + k_6 r^6}{1 + k_1 r^2 + k_2 r^4 + k_3 r^6} (x'' - 2p_1 x' y' - p_2(r^2 + 2 x'^2) - s_1 r^2 + s_2 r^4) = x' \\
f_2(y') &= \frac{1 + k_4 r^2 + k_5 r^4 + k_6 r^6}{1 + k_1 r^2 + k_2 r^4 + k_3 r^6} (y'' - p_1 (r^2 + 2 y'^2) - 2 p_2 x' y' - s_3 r^2 - s_4 r^4) = y'
\end{aligned}
$$
where $x', y'$ are the undistorted points we want to compute and and $x'', y''$ are the given distorted points. This problem is solved using fixed-point iterations like
$$
x'_{k+1} = f_1(x'_k),\quad
y'_{k+1} = f_2(y'_k)
$$
I guess the issue here is that the distortion function does not necessarily satisfy the [Banach fixed-point theorem](https://en.wikipedia.org/wiki/Banach_fixed-point_theorem), i.e. the slope of the function can be too large. This can be seen in @Linhuihang's comment https://github.com/opencv/opencv/issues/27916#issuecomment-3417883642 - the point series jumps around and doesn't converge.
A common solution is to instead do damped fixed-point iterations, so that the updates are "more smooth".
$$
x'_{k+1} = (1 - \alpha) x'_k + \alpha f_1(x'_k),\quad
y'_{k+1} = (1 - \alpha) y'_k + \alpha f_2(y'_k)
$$
I have implemented a simple logic which starts with $\alpha = 1$ (so just like it is now) and reduces $\alpha$ whenever the optimization error would increase. This seems reasonable to me: the initial logic is to do normal fixed-point iterations and to gradually become "more damped" when we notice that we don't converge. Perhaps there is a better way to ensure convergence, but this is the most straightforward modification to the current code that I have found.
This problem is not due to the $\tau_x, \tau_y$ parameters; it also occurs when they are zero. In fact, the fixed-point iterations are done when the tilt correction of $\tau_x, \tau_y$ has already been applied. I have added a test to reproduce the problem. This PR fixes#27916.
### 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
Add undistortImagePoints function
* Add undistortImagePoints function
undistortPoints has unclear interface and additional functionality. New function computes only undistorted image points position
* Add undistortImagePoints test
* Add TermCriteria
* Fix layout
Add distort/undistort test for fisheye::undistortPoints()
* Add distort/undistort test for fisheye::undistortPoints()
Lack of test has allowed error described in 19138 to be unnoticed.
In addition to random points, four corners and principal center
added to point set
* Add random distortion coefficients set
* Move undistortPoints test to google test, refactor
* Add fisheye::undistortPoints() perf test
* Add negative distortion coefficients to undistortPoints test, increase value
* Move to theRNG()
* Change test check from cvtest::norm(L2) to EXPECT_MAT_NEAR()
* Layout fix
* Add points number parameters, comments
- removed tr1 usage (dropped in C++17)
- moved includes of vector/map/iostream/limits into ts.hpp
- require opencv_test + anonymous namespace (added compile check)
- fixed norm() usage (must be from cvtest::norm for checks) and other conflict functions
- added missing license headers
Adrian Kretz
Victor
Kang Yifei
Alexander Alekhin
Vladislav Sovrasov
Tomoaki Teshima
Ilya Lavrenov
Roman Donchenko
OpenCV Buildbot
Alexander Shishkov