Background Knowledge

Lens Distortion Fundamentals

Lens distortion occurs when light rays bend non-uniformly as they pass through a camera lens, causing straight lines in the world to appear curved in the captured image. Radial distortion is the most common type, where distortion increases with distance from the optical center. The relationship between undistorted coordinates $(x_u, y_u)$ and distorted coordinates $(x_d, y_d)$ is typically modeled as:

$x_d = x_u(1 + k_1 r^2 + k_2 r^4 + \ldots)$ $y_d = y_u(1 + k_1 r^2 + k_2 r^4 + \ldots)$

where $r^2 = x_u^2 + y_u^2$ is the squared distance from the optical center, and $k_1, k_2, \ldots$ are radial distortion coefficients. The problem asks you to reverse this process: given distorted coordinates and distortion coefficients, recover the original undistorted coordinates.

Iterative Root-Finding Methods

This is fundamentally a nonlinear equation-solving problem. Newton's method and fixed-point iteration are two classical approaches for finding roots of nonlinear equations. Newton's method converges quadratically (very fast) near the solution but requires computing derivatives. Fixed-point iteration is simpler to implement but converges more slowly (linearly). Both methods work by repeatedly refining an initial guess until convergence.

Algorithm/Approach

The undistortion problem can be formulated as finding $x_u$ such that:

$f(x_u) = x_u(1 + k_1 r^2 + k_2 r^4) - x_d = 0$

where $r^2 = x_u^2 + y_u^2$ depends on the unknown $x_u$.

Newton's Method Approach: $x_{u,n+1} = x_{u,n} - \frac{f(x_{u,n})}{f'(x_{u,n})}$

This requires computing the derivative of the distortion model with respect to the undistorted coordinates.

Fixed-Point Iteration Approach: Rearrange the equation into the form $x_u = g(x_u)$ and iterate: $x_{u,n+1} = g(x_{u,n})$

For example, you might use $x_{u,n+1} = \frac{x_d}{1 + k_1 r_n^2 + k_2 r_n^4}$ where $r_n$ is computed from the previous iteration's estimate.

Step-by-Step Strategy

1. Initialize: Start with $x_{u,0} = x_d$ and $y_{u,0} = y_d$ (the distorted coordinates as initial guess, since distortion is typically small).

2. Compute Radius: Calculate $r^2 = x_{u,n}^2 + y_{u,n}^2$ for the current estimate.

3. Apply Distortion Model: Compute the distortion factor $\text{factor} = 1 + k_1 r^2 + k_2 r^4 + \ldots$

4. Update Estimate:

• For fixed-point: x_{u,n+1} = \frac{x_d}{\text{factor}}, y_{u,n+1} = \frac{y_d}{\text{factor}}
• For Newton: Compute the Jacobian and apply the Newton update formula

5. Check Convergence: Compare consecutive iterations. Stop when $|x_{u,n+1} - x_{u,n}| < \epsilon$ and $|y_{u,n+1} - y_{u,n}| < \epsilon$ for some small tolerance $\epsilon$ (e.g., $10^{-6}$).

6. Return Result: Return the converged undistorted coordinates.

Common Pitfalls

• Poor Initial Guess: Starting far from the solution slows convergence. Using distorted coordinates as the initial guess is usually effective since distortion is typically small.

• Insufficient Convergence Tolerance: Using too loose a tolerance may give inaccurate results. Use a small epsilon like $10^{-6}$ or $10^{-8}$.

• Divergence: Fixed-point iteration can diverge if the iteration function's derivative has magnitude greater than 1 near the solution. Newton's method can also diverge if started far from the solution.

• Numerical Instability: When computing $r^2$ and high-order terms like $r^4$, be careful with numerical precision, especially for large radii.

• Iteration Limit: Always set a maximum iteration count to prevent infinite loops in case of non-convergence.

• Handling Edge Cases: Points at or very near the optical center (where $r \approx 0$) may need special handling to avoid numerical issues.

Time & Space Complexity

Time Complexity: Each iteration requires $O(1)$ operations (a few arithmetic operations). Fixed-point iteration typically requires $O(n)$ iterations for $n$ bits of precision, while Newton's method requires $O(\log n)$ iterations due to quadratic convergence. Overall: $O(n)$ for fixed-point, $O(\log n)$ for Newton's method.

Space Complexity: $O(1)$ — only a constant number of variables needed to store the current and previous estimates, distortion coefficients, and intermediate calculations.