Undistort Point

hardFREELens DistortionsCamera ModelCV: Image Formation

Implement a function to remove radial distortion from a given point in an image. This process is crucial in computer vision to correct for distortions introduced by camera lenses.

The concept of radial distortion arises when a camera's lens bends light rays, causing straight lines to appear curved. This distortion can be modeled using a polynomial expression, where the distorted coordinates $x_d$ and $y_d$ are related to the undistorted coordinates $x$ and $y$ through a distortion factor.

To correct for this distortion, we can use an iterative refinement process, such as Newton's method or fixed-point iteration, which refines an initial estimate of the undistorted coordinates until convergence. The steps involved are:

Initialize the undistorted coordinates with the distorted coordinates
Compute the distortion factor using the current estimate of the undistorted coordinates
Update the estimate of the undistorted coordinates using the distortion factor
Repeat steps 2-3 until convergence

r^2 = x^2 + y^2

\text{factor} = 1 + k_1r^2 + k_2r^2^2

This technique is widely used in image processing pipelines.

Example

Input

undistort_point([0.4688, 0.4688], -0.1, 0.01)

Output

[0.5, 0.5]

Reasoning

Start with distorted point $\mathbf{x}_d = [0.4688, 0.4688]$ and radial model $r^2 = x^2 + y^2$ , $x_d = x_u(1 + k_1 r^2 + k_2 r^4)$ (applied similarly to $y$ ) with $k_1=-0.1$ , $k_2=0.01$ .
Assume the undistorted point lies on the same ray, so try $\mathbf{x}_u = [0.5, 0.5]$ and compute $r^2 = 0.5^2 + 0.5^2 = 0.5$ .
Compute the radial factor: $1 + k_1 r^2 + k_2 r^4 = 1 + (-0.1)\cdot 0.5 + 0.01 \cdot 0.5^2 = 1 - 0.05 + 0.0025 = 0.9525$ , and then the distorted coordinate: $0.5 \cdot 0.9525 = 0.47625 \approx 0.4688$ (the small mismatch is corrected by iteration).
Using Newton’s method or fixed-point iteration, the algorithm refines this guess until the forward distortion of $\mathbf{x}_u$ matches $[0.4688, 0.4688]$ , converging to the undistorted output $\mathbf{x}_u = [0.5, 0.5]$ .

Constraints

Use 10 iterations of fixed-point iteration
Return undistorted [x, y] rounded to 4 decimal places

Learn this in

Image FormationCV Study Plan Camera Models & Calibration3D Computer Vision

More from CV: Image Formation

Perspective Projection with Intrinsicsmedium Rodrigues Rotation Formulahard Compose 3D Transformationsmedium Distortion Center Offsetmedium Radial Distortionmedium

Concept primer

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

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).
Compute Radius: Calculate $r^2 = x_{u,n}^2 + y_{u,n}^2$ for the current estimate.
Apply Distortion Model: Compute the distortion factor $\text{factor} = 1 + k_1 r^2 + k_2 r^4 + \ldots$
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

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}$ ).
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.

solution.py

Python 3.13

Test results