1 Introduction

Most computer vision algorithms, particularly structure from motion algorithms, rely critically on the assumption of a linear pinhole camera model. However, most commercially available cameras introduce sufficiently severe optical distortion that the pinhole assumption is invalid, making distortion correction a must. Radial distortion is the most significant type of distortion in today’s cameras [28, 43, 54]. It is most evident in images produced with low-cost, wide-angle lenses [23]. Such lenses are being widely deployed, for example, in automotive driver assistance applications [22, 26]. But radial distortion is also significant enough in higher-quality cameras to introduce error into 3D reconstruction processes. Radial distortion bends straight lines into circular arcs [43, 50], violating the main invariance preserved in the pinhole camera model, that straight lines in the world map to straight lines in the image plane [17, 25]. Radial distortion may appear as barrel distortion, usually arising at short focal lengths, or pincushion distortion, usually arising at longer focal lengths. Besides radial distortion, another type of distortion is tangential distortion. We do not have experience with real cameras that introduce significant tangential distortion, so like most previous work [2, 28, 38, 43, 47, 54], we ignore tangential distortion.

Methods for radial distortion estimation fall into three major categories: point correspondence [7, 49, 54], multiple view autocalibration [4, 21, 24, 36, 42], and plumb-line [2, 8, 9, 17, 43, 44, 47, 50].

Point correspondence based methods [7, 49, 54] are ideal for distortion estimation during pre-calibration of a camera with a fixed focal length. They identify image points with known 3D positions in multiple images using a known pattern such as a chessboard and then estimate the parameters of an undistortion function. The parameterized undistortion function can then be used to undistort specific images or point positions. These point correspondence methods are highly reliable and accurate; radial distortion estimation and removal is a solved problem for cameras that are pre-calibrated at a fixed focal length.

Manual camera calibration, however, is a tedious process that is not always possible, for example, when we want to process an existing image sequence acquired with an unknown camera, when we want to change the focal length dynamically during image sequence acquisition, or when we want to get a mobile robot experiment up and running quickly.

Multiple view auto-calibration is an active area of computer vision research that aims to extract camera parameters automatically from natural images. Auto-calibration methods use a sequence of arbitrary natural images without any special pattern or information about the scene. Although many auto-calibration methods assume a pinhole camera, others do attempt to simultaneously estimate radial distortion parameters and pinhole parameters [21, 24, 28, 36, 42].

Auto-calibration is a mature area of research, but the main limitation of this class of methods is that it requires multiple images under camera motion. For fixed cameras and for situations where immediate online estimation is desirable, multiple view methods are inappropriate.

In view of the limitations of the point correspondence and auto-calibration methods, robust automatic distortion estimation and removal from a single natural image would be extremely useful for many applications, particular those in human-made environments containing abundant lines. For example, it could be used in place of an extensive calibration procedure to get a mobile robot or quadrotor experiment up and running quickly in an indoor environment. Plumb-line methods are the most promising for robust distortion estimation from a single image or a small number of images. Rather than using a known pattern or sequence of images under camera motion, they estimate distortion parameters directly from distorted straight lines in one or more images. Straight lines are frequent enough in most human-made environments to make distortion estimation from a single image possible [43, 47, 50].

The main limitations of this class of methods are that straight lines must be visible in the image and that images of actual curved lines may disrupt estimation. Some methods address these issues simply by utilizing human supervision to select the lines (see, e.g., [2, 9, 44]). But when human supervision is not used, plumb-line methods depend critically on the robustness and accuracy of the line detection algorithms. Some plumb-line approaches do not use all available lines for distortion estimation despite the fact that additional lines could minimize estimation error [43, 47, 50], or assume the distortion center as the center of the image [2, 8, 21, 28, 43], which is in contrast to some researchers’ recommendations [24, 46]. The Devernay and Faugeras [17] method is the only existing method that overcomes all of these limitations. However, it requires a complex process of polygonal approximation of the distorted lines. As we shall see, the distorted line detection process can be dramatically simplified by using an alternative distortion model.

We propose a new method based on the plumb-line approach that addresses the aforementioned limitations. The method works from a single image if the image contains a sufficient number of distorted straight lines. It does not require a calibration pattern or human intervention. We use Fitzgibbon’s division model of radial distortion [21] with a single parameter. Our estimator is similar to that of Strand and Hayman [43] and Wang et al. [50] in that we estimate the parameters of the distortion model from the parameters of circular arcs identified in the distorted image, based on the fact that distorted straight lines can be modeled as circular under the division model [4, 43, 50]. Our contribution is to make the process fully automatic and robust to outliers using a two-step random sampling process. For the first step, we introduce a sampling algorithm to search the input image for subsequences of contour pixels that can be modeled as circular arcs. For the second step, we introduce a sampling algorithm that finds the distortion parameters consistent with the largest number of arcs. Based on these parameters, we undistort the input image. Some preliminary results from our method have previously appeared in a conference paper [11].

In this paper, to evaluate the new algorithm, we perform a comprehensive quantitative study of its performance on distorted synthetic images and provide extensive examples of its ability to remove distortion from a large, challenging set of real images taken from Web sites and previous papers on distortion estimation. We find that the algorithm performs very well, with excellent reconstruction of the original synthetic images even under severe barrel distortion and pincushion distortion. We also find that the method is able to eliminate nearly all of the visible distortion in the real images, including those acquired with wide angle and fish-eye lenses. Finally, we perform a direct comparison of our method with that of Alvarez et al. [2], the only researchers who have provided a publicly accessible implementation of their method, on synthetic images. The Alvarez et al. method exploits user assistance in identifying points on straight lines, but we nevertheless find that our fully automatic method provides superior reconstruction of the original undistorted image. Our method is thus a practical solution to the important problem of radial distortion estimation and removal.

2 Mathematical Model

In this section, we outline the mathematical model of radial distortion assumed in the rest of the paper and show how to estimate the parameters of this model.

2.1 Distortion Model

The most commonly used radial distortion model is the even-order polynomial model

(1)

where (x u ,y u ) and (x d ,y d ) are the corresponding coordinates of an undistorted point and a distorted point, respectively. r d is the Euclidean distance of the distorted point to the distortion center. If the distortion center is the origin of the distorted image, we can simply write

(2)

However, if (x 0,y 0) is the center of distortion (in the distorted image), we write

(3)

and replace x d and y d in Eq. (1) with (x d −x 0) and (y d −y 0), respectively. In the model, x 0, y 0, λ 1,λ 2,λ 3,… are the distortion parameters, which must be estimated from image measurements.

There have been objections to the even-order polynomial model. According to Wang et al. [50], the model performs well for small distortion, but for severe distortion, a prohibitively large number of non-zero distortion parameters are required.

Fitzgibbon [21] proposes an alternative model, the division model, as a more accurate approximation to the typical camera’s true undistortion function:

The division model is preferred over the polynomial model because it requires fewer terms than the polynomial model in case of severe distortion [50]. It is also slightly easier to work with; inverting the single-parameter division model, for example, requires solution of a polynomial of degree two, whereas inverting the single-parameter polynomial model leads to a polynomial of degree three. In our work, we use the single-parameter division model (fixing λ 2=⋯=0), because for most cameras, a single term is sufficient [17, 21, 50, 51]. When the center of distortion is not the origin, we can write the single-parameter division model in the form

(4)

with \(r^{2}_{d}\) defined according to Eq. (3). Strand and Hayman [43] find that for the typical case of relatively small barrel distortion (small negative values for λ), the single-parameter division model is highly correlated with the single-parameter polynomial model.

2.2 Distortion of a Line Under the Single-Parameter Division Model

Wang et al. [50] show that under the single-parameter division model, the distorted image of a straight line is a circular arc. However, they use the slope-y-intercept form of the equation of a line, which we avoid due to its inability to model vertical lines and its undesirable numerical properties. However, it is also easy to show that the general line

$$ a x_u + b y_u + c = 0 $$
(5)

is also imaged as a circular arc under the single parameter division model. To avoid the degenerate case a=b=0, we impose the constraint that a 2+b 2>0. (When convenient we will further assume the line parameters are normalized so that a 2+b 2=1.) By substituting the image coordinates from Eq. (4) into Eq. (5), replacing \(r^{2}_{d}\) by its definition from Eq. (3), and simplifying, we obtain the circle

$$ x^2_d + y^2_d + ex_d + fy_d + g = 0, $$
(6)

where

(7)

It is also possible to come to the conclusion that straight lines are imaged as circles using the parametric form of a straight line [43].

2.3 Inverse Mapping

When undistorting an image, it is necessary to compute, for each pixel in the output undistorted image, the corresponding pixel position in the distorted image then perform interpolation to determine the actual pixel color or intensity in the output undistorted image (we use simple bilinear interpolation in all of the experiments reported on in this paper). However, while every distorted image point (x d ,y d ) is mapped to a unique undistorted image point (x u ,y u ) by Eq. (4), the reverse is not true. To invert Eq. (4) and find the value of x d and y d as a function of x u and y u , we first square and add the individual equations to obtain

(8)

We then let r u be the distance of (x u ,y u ) to the distortion center:

$$ r^2_u = (x_u - x_0)^2+(y_u - y_0)^2. $$
(9)

This lets us simplify Eq. (8) to

$$ r^2_d-\frac{1}{\lambda r_u}r_d + \frac{1}{\lambda}=0. $$
(10)

For positive λ (pincushion distortion), given \(0 < r_{u}^{2} < \frac{1}{4\lambda}\), Eq. (10) has two positive real roots. We use the smaller of the two. For negative λ (barrel distortion), given any \(r^{2}_{u}>0\), there are always two real solutions, but one is negative. We use the positive solution. After solving for r d in terms of r u , the distorted image coordinates corresponding to (x u ,y u ) can be obtained as

(11)

2.4 Estimating Distortion Parameters from Circular Arcs

Strand and Hayman [43] and Wang et al. [50] show that it is possible to estimate λ from the parameters of circular arcs identified in an image. Wang et al. [50] further show how both λ and the distortion center (if not assumed to be the center of the image) can be estimated from the parameters of three circular arcs identified in an image. We use their formulation. In Eq. (7), multiplying the equation for e by x 0, the equation for f by y 0, and adding the equations for ex 0, fy 0, and g, we obtain

(12)

For each of the three arcs i∈{1,2,3}, we use Eq. (12) to obtain coefficients e i , f i , and g i , then the distortion center can be estimated by solving the linear system

(13)

and an estimate of λ can be obtained from

$$ \frac{1}{\lambda} = x^2_0 + y^2_0 + ex_0 + fy_0 + g $$
(14)

using any of the three arcs’ parameters in place of e, f, and g. See Wang et al. [50] for details.

3 Robust Radial Distortion Estimation

In this section, we provide a detailed algorithm for estimating the parameters of the mathematical model introduced in Sect. 2.

3.1 Identifying Circular Arcs

The first step in our method is to robustly identify as many non-overlapping circular arcs as possible in the distorted input image. Each arc is identified by a circle center, circle radius, and the contiguous sequence of pixels consistent with that circle.

To find arcs, we first extract edges and link adjacent edge pixels remaining contours. We discard any contour whose length is less than \(l^{\text{min}}\) pixels (we use \(l^{\text{min}}=10\) pixels) and then we attempt to find long pixel subsequences within each contour that can be fit by circular arcs. Our method is based on random sampling and inspired by RANSAC [20], but, rather than finding a single model for all the data, we preserve all models (candidate circular arcs) not overlapping with other arcs in the same contour that have more support. The termination criterion is to stop once the probability that an arc of minimal length has not yet been found is small.

In Algorithm 1, we provide the details of the method. To determine the number of sampling iterations required, the algorithm uses a function f(l,n), which gives the number of trials required to ensure that the probability of not sampling three of l inliers from a set of n points is small. This ensures that we sample a sufficient number of times to find, with high probability, all arcs with sufficient length in each contour.

Algorithm 1
figure 1

Robust arc identification

Full size image

3.2 Refining Circular Arc Estimates

After the initial arc identification process is complete, each resulting arc, whose parameters have been calculated directly from the minimum sample of three points, is refined using the inlier pixel contour subsegment supporting that model. The gold standard objective function for circle fitting is

$$ \varOmega(x_c, y_c, r) = \sum _{i=1}^N d(x_i,y_i,x_c,y_c,r)^2, $$
(15)

where (x c ,y c ) is the center of the circle, r is its radius, and d(x,y,x c ,y c ,r) is the orthogonal distance of the measured point (x,y) to the hypothetical circle. N is the number of pixels in a inlier contour. Since there is no closed-form solution for minimizing this objective function [1], we use an initial guess and the Levenberg-Marquardt (LM) iterative nonlinear least squares method to find a local minimum. To obtain the initial guess, we use a variety of methods as detailed in the next section.

3.2.1 Algebraic Circle Fitting Methods

As the initial estimate of the circle’s parameters, we use either the parameters calculated during the sampling procedure or one of three circle fitting methods, Pratt [35], Taubin [45], and Kukush-Markovsky-van-Huffel (KMvH) [29], based on algebraic error minimization. Both Pratt and Taubin use four parameters to specify a circle:

$$ a\bigl(x^2 + y^2\bigr) + bx + cy + d = 0, $$
(16)

with a≠0. The center of the circle is \((-\frac{b}{2a},-\frac{c}{2a})\) and the radius is given by \(r =\sqrt{ (-\frac{b}{2a})^{2} + (-\frac{c}{2a})^{2} - \frac{d}{a}}\). The Pratt method minimizes the objective function

$$ \varOmega(a, b, c, d) = \sum_{i=1}^N {a\bigl(x_i^2+y_i^2 \bigr)+bx_i+cy_i+d}^2, $$
(17)

subject to the constraint that b 2+c 2−4ad=1, to ensure that the parameterized equation represents an actual circle. The Taubin method minimizes the same objective function as the Pratt method, but imposes the constraint \(4a^{2}\overline{z}+4ab\overline{x}+4ac\overline{y}+b^{2}+c^{2}=1\), where \(\overline{x}\) is the mean of the sample points’ x coordinates, \(\overline{y}\) is the mean of the sample points’ y coordinates, and \(\overline{z} = \frac{1}{N} \sum_{i=1}^{N} ( x_{i}^{2}+y_{i}^{2} )\). The additional constraint improves the convergence of the optimization [15].

We use one other algebraic method, the Kukush-Markovsky-van-Huffel (KMvH) consistent conic fitting method [29], which minimizes the objective function Ω(a,b,c,d)=A T M A, where A=[a b c d]T and M is an unbiased estimate of the data covariance matrix. The method guarantees convergence to the true parameters as the number of sampled points approaches infinity.

3.2.2 Geometric Circle Fitting methods

Researchers have proposed several circle-specific parameter refinement methods based on LM. In addition to generic LM, in this paper, we also experiment with Trust-Region-LM, Chernov and Lesort LM (Chernov-LM), and Reduced-LM.

In the Reduced-LM method [15], only two parameters are adjusted; i.e., x c and y c (the coordinates of the center of the circle). The method minimizes the objective function

$$ \varOmega(x_c, y_c) = \sum _{i=1}^N \bigl[\overline{r} - \sqrt{(x_i-x_c)^2 + (y_i-y_c)^2} \bigr]^2, $$

where \(\overline{r}= \frac{1}{N}\sum_{i=1}^{N} \sqrt{(x_{i}-x_{c})^{2} + (y_{i}-y_{c})^{2}}\).

The Chernov and Lesort LM method [16] guarantees convergence to a minimum of the objective function from any initial guess. They redefine the circle parameters with respect to Eq. (16) as \(A = -\frac {b}{2a}, B= -\frac{c}{2a}\), and \(R^{2}=\frac{b^{2} + c^{2} - 4ad}{4a^{2}}\). Their objective function is

$$ \varOmega(a, b, c, d) = 2 \frac{P_i}{1 + \sqrt{1 + 4aP_i}}, $$

where \(P_{i}=a(x_{i}^{2} + y_{i}^{2}) + bx_{i} +c_{i} + d\).

The Trust-Region-LM method [32] guarantees proper initialization of LM’s learning rate or control parameter λ and also provides an efficient rule for updating λ’s value.

We coded all the geometric and algebraic circle fitting methods in C++ using OpenCV [6], with reference to Chernov’s [14] MATLAB implementations.

3.3 Experimental Design for Circular Arc Estimation Methods

We have found that different circle fitting methods provide very different performance in terms of radial distortion estimation. In the experimental evaluation (Sect. 4), we therefore perform a comprehensive study of the effect the circle fitting algorithm has on radial distortion correction. We use 10 different variations of the fitting methods described in the previous section. For a comparative summary of the different circle fitting algorithms, refer to Table 1, and for more detailed discussion of the methods, refer to Chernov [15].

Table 1 Comparison of different circle fittings methods. LM = Levenberg-Marquardt, KMvH = Kukush-Markovsky-van Huffel; IURAT = Invariant Under Rotations And Translations. \(r_{i} = \sqrt{(x_{i}-x_{c})^{2} + (y_{i}-y_{c})^{2}}\), \(\overline{r}= \frac{1}{N}\sum_{i=1}^{N} r_{i}\); \(A = \pm \frac{1}{2R}\), B=−2Aa, C=−2Ab, \(D = \frac{B^{2} + C^{2} - 1}{4A}\); \(\overline{z} = \frac{1}{N} \sum_{i=1}^{N} ( x_{i}^{2}+y_{i}^{2} )\). (x c ,y c ) is the center and R is the radius of the circle. A is a vector representing the parameters of a circle
Full size table

In our experiments, the “Ransac” method means we simply accept the circular arc model computed from three sample points, without any refinement after calculating inliers. “Ransac-Taubin”, “Ransac-Pratt”, and “Ransac-KMvH” are the results of using the Taubin, Pratt, or KMvH methods to refine the arc models computed from three sample points. The names “Ransac-LM”, “Ransac-TR-LM”, “Ransac-Chernov-LM”, and “Ransac-Reduced-LM” denote the application of general LM, Trust Region LM, Chernov’s LM, or the Reduced LM methods previously described directly to the models computed from three sample points. Under the hypothesis that starting LM from the sample-based estimate might not work as well as an initial estimate closer to the optimum, we also performed two series of experiments in which we first applied either the Taubin or the Pratt methods to the sample-based models then applied general LM to the Taubin or the Pratt estimates respectively. The results from these methods are shown as “Ransac-Taubin-LM” and “Ransac-Pratt-LM”.

3.4 Estimating Distortion Parameters

Once we have obtained a set of circular arcs as candidate distorted straight lines, we use the estimator of Eqs. (13) and (14) and a RANSAC procedure to find the set of distortion parameters with maximal support. However, we use a modified notion of support; rather than counting the number of arcs fit by a particular model, we count the sum of the lengths (in pixels) of the arcs. Longer arcs provide much more accurate parameter estimates than shorter arcs. The weighted support strategy emphasizes models that fit as many long arcs as possible rather than models that fit many small arcs. In the sampling loop, we sample three arcs, calculate the model, then classify each arc as an inlier if, after undistortion, the arc’s pixels fit a straight line.

The details are presented in Algorithm 2. In the sampling loop, we use adaptive calculation of the number of iterations required based on the highest number of pixels in inlier arcs seen so far. The termination criterion uses the same function f(l,n) previously introduced to determine the number of trials required to ensure that the probability of never sampling three arcs from a consensus set of size (in pixels) at least the size of the current support set is small.

Algorithm 2
figure 2

Robust distortion parameter estimation

Full size image

To judge whether an arc is an inlier for distortion parameters (λ,x 0,y 0), we first perform orthogonal regression to determine the line best fitting the pixels of the arc before and after undistortion using the candidate parameters. We use two criteria: the undistorted arc should be very close to the straight line in terms of RMSE, and the RMSE for the undistorted arc should be smaller than that of the original distorted arc. The second criterion is necessary to handle arcs that are already very close to straight lines in the original distorted image. We require that these arcs should not only be nearly straight after undistortion, but that they should also be more straight than they were before undistortion. This avoids situations in which incorrect distortion parameters make nearly straight contours less straight but still close enough to straight to be counted as inliers.

Once the required number of iterations have been performed, we obtain a final least squares estimate of the distortion parameters based on all inlier arcs and Eqs. (13) and (14). From each possible pair of inlier arcs, we form the linear system described by Eq. (13) and find the least-squares solution for the distortion center (x 0,y 0). After estimating the distortion center, we estimate λ using Eq. (14) and all inlier arcs.

3.5 Undistortion

The last step in our procedure is to undistort the input image. We use the optimal distortion parameters computed per the previous section and the inverse of the distortion model in Eq. (11) with bilinear interpolation and appropriate translation and scale factors to produce the output undistorted image.

4 Quantitative Results on Synthetic Images

In this section, we describe a detailed quantitative study of the performance of our method on synthetic images. A sample of the synthetic images we use with results is shown in Fig. 1. We used the same original image (Fig. 1(a)) for all synthetic image experiments. In each experiment, we distort the original image using particular ground truth values for λ,x 0, and y 0 (Fig. 1(b)), extract Canny edges (Fig. 1(c)), link the edge pixels into contours (Fig. 1(d)), identify circular arcs among the contours (Fig. 1(e)), estimate the distortion parameters, and then use those parameters to undistort the image.

Fig. 1
figure 3

Example experiment with synthetic image size 640×480. (a) Original image. (b) Distorted image with λ=−10−6 and (x 0,y 0)=(320,240) (the image center). (c) Canny edges (d) Extracted contours. (e) Estimated arcs. (f) Undistorted image using estimated values of λ=−1.00419e −6, x 0=319.352, and y 0=238.009. Using true parameters RMSE = 3.27813 and PNSR = 37.8183 dB; Using estimated parameters RMSE = 3.86511 and PNSR = 36.3876 dB

Full size image

To evaluate the quality of reconstruction of the original synthetic image, we use root mean-squared error (RMSE) and peak signal-to-noise ratio (PNSR), the most commonly used image quality metrics for cases in which the original undistorted image is available for comparison.

4.1 Synthetic Images

We performed two series of experiments with synthetic images. For edge extraction, we modified OpenCV’s Canny edge detector to automatically select a low gradient threshold and a high gradient threshold based on a cumulative histogram of magnitudes, similar to the Matlab implementation of Canny’s method [31].

4.1.1 Experiment 1 (Varying λ)

In a first series of runs, we varied λ while keeping the distortion center fixed at (x 0,y 0)=(320,240) but estimated all three parameters. For each level of λ, we compare 10 methods for circular arc estimation.

Figure 2 shows the distorted image and a sample undistorted result for each level of λ using the “Ransac-LM” method. For the extreme case of λ=10−5, undistorted image points map to multiple valid distorted image points, so we only map the points for which \(r^{2}_{d} < \lambda\), resulting in a circular valid region around the image center.

Fig. 2
figure 4

Undistortion of synthetic images. Image size is 640×480 and distortion center is (320,240). First row: distorted images at different levels of λ. Second row: corresponding undistorted images using parameters estimated by the “Ransac-LM” circle fitting method

Full size image

To precisely quantify the performance of each algorithm, for each level of λ and each circle fitting method, we performed 10 runs with different random seeds and collected three measurements in each case: the absolute relative estimation error for λ, i.e., \(|(\lambda_{\text{est}} - \lambda_{\text{true}})/\lambda_{\text{true}}|\), RMSE, and PNSR. For the extreme case of λ=10−5, we only calculated RMSE and PNSR over the circular valid region shown in Fig. 2. The mean measurements with 95 % confidence intervals are shown in Fig. 3(a)–(c).

Fig. 3
figure 5

Results of experiment 1 and experiment 2 using synthetic images. (a)–(c) Represent results with varying λ, with distortion center fixed at the image center. (d)–(f) Represent results with varying distance of the distortion center to the center of the image. λ Is fixed at −10−6. All graphs show averages over 10 runs with error bars showing 95 % confidence intervals on the mean. (a) True versus estimated λ. (b) Average RMSE. (c) Average PNSR. (d) True versus estimated distance of the distortion center from the image center. (e) Average RMSE. (f) Average PNSR

Full size image

The results in terms of relative estimation error for λ in Fig. 3(a) show quite clearly that our method is extremely accurate at estimating λ for moderate (λ=±10−6) or extreme (λ=±10−5) distortion but quite inaccurate for very small levels of distortion. The inaccuracy with small distortion levels reflects two factors. First, since the ground truth value is extremely small in the first place, small deviations between estimated and ground truth parameter values give large relative errors. Second, when our algorithm fails to find a sufficient number of contours that can be modeled as circular arcs, it defaults to an estimate of λ=0, which leads to a relative error of 1. Fortunately, as the RMSE and PNSR comparisons show, this relative inaccuracy for small λ does not affect our method’s ability to reconstruct the original undistorted image.

Since the RMSE and PNSR results shown in Fig. 3(b)–(c) are difficult to interpret, we performed a series of statistical analyses. As the dependent variables, we used pixel intensity RMSE and PNSR. As the independent variables, we used the algorithm and the different levels of λ.

For both RMSE and PNSR, a two-way analysis of variance (ANOVA) revealed main effects for both predictor variables and an interaction. To understand the main effect of differing ability of each algorithm to reconstruct the original image, we performed a post-hoc analysis using the Tukey correction for all pairwise comparisons among the 10 different algorithms.

For both RMSE and PNSR, the best numerical results were obtained with Ransac-Pratt, but statistically, according to both measures, four algorithms, namely Ransac-Pratt, Ransac-Pratt-LM, Ransac-LM, Ransac-Reduced-LM, Ransac-Taubin, and Ransac-Taubin-LM are equivalent to and better than the remaining four algorithms (we use a familywise α=0.05 for all significance tests). Next are Ransac-KMvH, Ransac-Chernov-LM, and Ransac-TR-LM. These three algorithms are statistically equivalent. The last method, Ransac, is statistically worse than all the other algorithms.

4.1.2 Experiment 2 (Varying Distortion Center)

In a second series of runs, we kept the distortion fixed at a moderate level of barrel distortion (λ=−10−6) while varying the distortion center, then we estimated all three parameters of the distortion model. We used the same 10 circle fitting methods as in the first series of experiments manipulating λ. For each run, we measured the Euclidean distance between the estimated and ground truth distortion center as well as RMSE and PNSR. The results are shown in Fig. 3(d)–(f).

To further understand the results, we performed statistical analyses with all three dependent measures. As the independent variables, we used the algorithm and the different levels of distortion center. To simplify the presentation, we name the distortion center levels as DC 1=0.0 (distortion center (320,240)), DC 2=14.1 (distortion center (330,250)), DC 3=28.3 (distortion center (340,260)), DC 4=42.4 (distortion center (350,270)), DC 5=56.6 (distortion center (360,280)), DC 6=70.7 (distortion center (370,290)), DC 7=84.9 (distortion center (380,300)), DC 8=99.0 (distortion center (390,310)).

For all three dependent measures, two-way analyses of variance (ANOVAs) revealed main effects for both predictor variables and an interaction. We then performed post-hoc Tukey comparisons among the different algorithms and among the different distortion center distances.

For distortion center estimation error, Ransac-LM was numerically best but Ransac-LM, Ransac-Reduced-LM, Ransac-Pratt, Ransac-Taubin-LM, Ransac-KMvH, and Ransac-Pratt-LM were statistically equivalent and better than the other four algorithms. Distortion center estimation error was also affected by the distance between the distortion center from the image center. The results for DC 1 were significantly better than those for DC 2, and DC 7 was better than DC 8. However, DC 6 happened to be as easy as DC 4 and easier than either DC 5 or DC 7. Inspection of Fig. 3(d) indicates that the increasing trend is driven by just two or three algorithms.

For pixel intensity RMSE, Ransac-LM was numerically best but statistically equivalent to Ransac-Pratt. The next set was Ransac-Reduced-LM, Ransac-Taubin-LM, Ransac-Pratt-LM, Ransac-KMvH, and Ransac-Taubin. Statistically, these algorithms were equivalent to each other and better than the remaining three algorithms. There was also an effect of distortion center distance on RMSE; the results for DC 1, DC 2, DC 3, and DC 4 were statistically equivalent but the results for DC 6, DC 7, DC 4, and DC 8 were all significantly different with respectively increasing RMSE.

Finally, the ordering in terms of increasing PNSR was Ransac-LM, Ransac-Pratt, Ransac-Reduced-LM, Ransac-Taubin-LM, Ransac-Pratt-LM, Ransac-KMvH, Ransac-Taubin, Ransac-TR-LM, Ransac, Ransac-Chernov-LM. All differences were significant except among Ransac-Pratt-LM, Ransac-KM-vH, and Ransac-Taubin, which were statistically equivalent. Distortion center distance also had some effect, with DC 1, DC 2, and DC 3 yielding the best PNSR. These levels were significantly better than the others, for which the trend was DC 6, DC 4, DC 7, DC 5, DC 8, with significantly increasing PNSR, respectively.

4.1.3 Discussion of Synthetic Image Experiments

Over the two series of runs, we observe that with moderate or extreme distortion, our method readily identifies the parameters of the distortion model and is successful at reconstructing the original undistorted image with high accuracy. For lower levels of distortion, the model parameters are more difficult to estimate accurately, but this inaccuracy does not affect the reconstruction results by much: Ransac-LM introduces at most only 2.5 times the reconstruction error of bilinear interpolation with the ground truth parameters.

Although some sensitivity to distortion center distance is observed, we can see readily from the data that this is only for some algorithms. The best algorithms such as Ransac-LM and Ransac-Pratt are clearly not affected by this factor. This is an improvement over other work [2, 8, 21, 28, 43].

Statistically, Ransac-LM and Ransac-Pratt are the winning algorithms. It is difficult to choose between the two since they both yield excellent performance. Ransac-Pratt is more computationally efficient. Ransac-LM provides significantly better PNSR over varying distortion center distances, and it has a somewhat lower maximum RMSE over varying levels of distortion. For these reasons, we have a slight preference for Ransac-LM.

Our method selects the distortion model consistent with the largest possible number of arcs found in the image. It could certainly be fooled by a synthetic image contain a group of real world curves that happen to be consistent with each other, leading to incorrect distortion parameter estimation. However such egregious cases are extremely unlikely to arise in practice. So long as there are several distorted straight lines, our algorithm will find them and estimate a distortion model to undistort those lines ignoring the curves or outliers.

5 Qualitative Results on Real Images

Next, we present a qualitative evaluation of the proposed method’s ability to identify distortion parameters in several challenging real images from the Web and other papers on radial distortion estimation. The set contains images with severe barrel and pincushion distortion, showing the effects of fisheye lenses and wide angle lenses. Figure 4 shows step-by-step results for one of the images, from Ociepka [33]. Note that some contours in Fig. 4(c) cannot be modeled as circular arcs. The algorithm discards contours due to (1) our criteria for circular arc selection is that a contiguous sequence of pixels must be consistent with a circle, (2) the radius of an identified circular arc should be less than the five times the image width, in order to discard long straight lines in the distorted image, and (3) we discard any contour whose length is less than 10 pixels, as small arcs tend to give suboptimal estimates of the distortion parameters. Figure 5 summarizes the results for all of the images from the Web and previous papers on distortion estimation [3–5, 10, 12, 13, 18, 19, 27, 30, 34, 37–41, 44, 47, 48, 52, 53]. These results indicate the robustness and accuracy of our procedure. Many are difficult due to severe fisheye distortion and circular arcs that are not straight lines in the real world. Despite these challenges, our robust arc selection method is able to find consensus sets corresponding to distorted straight lines and is successful at removing most of the radial distortion from the images.

Fig. 4
figure 6

Example results on real image. (a) Original image. (b) Detected edges. (c) Extracted contours. (d) Identified arcs. (e) Undistorted image using parameters estimated via the “Ransac-LM” circle fitting method. The distorted image is taken from Ociepka [33]

Full size image
Fig. 5
figure 7

Undistortion of real images. Column 1, column 3, and column 5 represent original images. Column 2, column 4, and column 6 represent undistorted images using parameters estimated via the “Ransac-LM” circle fitting method. The distorted images are taken from several sources [3–5, 10, 12, 13, 18, 19, 27, 30, 34, 37–41, 44, 47, 48, 52, 53]

Full size image

6 Comparison with Alvarez et al.’s [2] Method

How do the results presented thus far compare to previous work? Since there is no standardized database with ground truth for radial distortion correction, it is difficult to say. However, Alvarez et al. [2] have deployed an excellent demo Web site for their method that allow users to submit an image for undistortion after manually selecting distorted lines from it. The method is also plumb-line based, with source code available online. We selected two synthetic images as shown in Fig. 6(a) and Fig. 6(b) for comparison with their method. In the first image, the distortion center is (320,240) and λ=−10−6; in the second image we moved the distortion center to (390,310) but kept λ fixed. For fair comparison, before submission, we selected the same number of lines while comparing our method with their method. To achieve this, we ran our algorithm to determined how many arcs are extracted by our method, then based on that we selected the same number of distorted lines, and as much as possible number of pixels for the Alvarez et al. method, and after obtaining the results, we manually scaled and translated the resulting images to be in the best possible alignment with the original undistorted image. Table 2 presents the results. When the image center is the distortion center, the Canny edge execution time is 0.6539 s, arc detection takes 1.5945 s, distortion parameter estimation time is 3.7980 s, and the total execution time is 6.0463 s. When the image center is not the distortion center, the Canny edge execution time is 0.6542 s, arc detection takes 1.6309 s, distortion parameter estimation time is 2.9320 s, and the total execution time is 5.2171 s. The Alvarez et al. method runs faster, even taking the Web service’s network latency into account, but requires manual intervention to select distorted straight lines. It took us around 1 hour to select 81 contours using their Web demo. When the image center is the distortion center, the Alvarez et al. method performs well, with a moderate 19.718 % increase in RMSE and 1.5 dB decrease in PNSR compared to our method. When the distortion center is not the image center, our method degrades only slightly, but the Alvarez et al. method degrades substantially. This is expected because the Alvarez et al. method is not designed to handle distortion centers that are not the image center. But our method still performs slightly better than the Alvarez et al. method even when the image center is the distortion center, even though our algorithm is estimating rather than assuming the location of the image center and even though the method is fully automatic with no user intervention.

Fig. 6
figure 8

Synthetic images used for comparison with Alvarez et al. [2]. (a) Distortion center is the image center (320,240). (b) Distortion center is at (390,310). Image size is 640×480 and λ=−10−6

Full size image
Table 2 Comparison with Alvarez et al. [2]. Image size is 640×480
Full size table

7 Conclusion

In this paper, we have introduced a new algorithm for automatic radial distortion estimation and removal using the plumb-line approach. The method works from a single image and does not require a special calibration pattern. It is based on Fitzgibbon’s division model, robust estimation of circular arcs, and robust estimation of distortion parameters. As our method is based on circles, we also provide a detailed study of circle fitting methods and have found that two circle fitting methods, namely “Ransac-LM” and “Ransac-Pratt” perform better than the remaining 8 algorithms. “Ransac-Pratt” is a non-iterative circle fitting method and performs nearly as well as “Ransac-LM”. Since “Ransac-Pratt” is computationally cheaper than “Ransac-LM”, it may be recommended for applications in which runtime is important. Robust automatic radial distortion estimation from a single natural image would be extremely useful for many applications, particular those in human-made environments containing abundant lines. For example, it could be used to get a mobile robot or quadrotor experiment up and running quickly in an indoor environment. In a series of experiments on synthetic and challenging real images, we have demonstrated the method’s ability to accurately identify distortion parameters and remove distortion from images. Data and source code based on OpenCV [6] is available onlineFootnote 1 for researchers interested in evaluating or extending our procedure.