How to prove the convergence of iterative algorithm in cvUndistortPointsInternal?

Hey guys, I’m really curious about why this algorithm works?It bothers me for a while.
Can anybody show me the proof? Thanks a lot!

so you’re talking about this:

this algorithm seems to invert the distortion function (the thing described by distCoeffs). you will probably find the distortion function described in literature/books, as well as the docs.

“why” it works? you’d first have to know what algorithm it is. since the distortion function is some type of polynomial, it’ll use the usual math to solve that (y = f(x), solving for x).

simple answer: default termcrit specifies at most 5 iterations, so that’s when it’ll stop.

emm…Not exactly. Maybe I don’t state my problem clearly.
I understand the function you put in the picture.
The algorithm initialized with the distorted point, then calculate a new point by the inverted distortion function, finally using the new point to iterate until satisfy the terminate condition.
During every iteration, we get a new point by the function, why this algorithm guarantee the new point closer to the ground truth than last iteration point? How to prove this algorithm converges to the ground truth.

As shown above, the code in last line, why the variable error guarantee to decrease in every loop.

I understand your question. I just don’t have the inclination to hold a college level math course. you do need that to understand the math. maybe you don’t realize the complexity of what you’re asking.

basically, numerical/iterative methods for solving polynomials (and anything else you can use a taylor approximation on) work with “fixed points”, and there are criteria (Banach fixed-point theorem) to the fixed point equation that guarantee convergence (if the criteria are met).

the screenshot you posted only calculates values related to the EPS termcrit condition, nothing actually part of the fixed point iteration. that happens earlier.

if you look carefully, these expressions look like derivatives of something that is probably the distortion polynomial:

I appreciate your patience.
After reading the related math materials, my confusion disappeared!
Thanks a lot!

These aren’t derivatives but the tangential distortion.

I grant you, it’s not derivatives, but it’s also not just tangential distortion, but the whole equation, which also contains radial distortion.

Inverse Radial Distortion Formula « Less Than Optimal describes the iterative fixpoint algorithm to inverse the distortion.
An Exact Formula for Calculating Inverse Radial Lens Distortions provides an exact inversion and lists related articles that proposed the iterative solution.

1 Like