## 1.

## Introduction

Because of its large field of view (FOV), the fish-eye camera has been widely used in applications such as robot navigation, visual surveillance and three-dimensional (3-D) reconstruction.^{1} However, fish-eye lenses often introduce a large amount of radial distortion, which causes straight lines in the scene mapping to conics in the image. As a result, a calibration procedure is often required for distortion correction.^{2}

The calibration procedure typically consists of two components, model selection and parameter estimation. In the last decades a number of models have been developed for fish-eye lenses, such as the polynomial model,^{3} the division model,^{4} the rational function model,^{5} and so on. In order to estimate the model parameters, various methods using points, lines and conics have also been proposed in Refs. 6 and 7.

The ideal fish-eye lenses are constructed with the aim of complying with the equidistant projection function.^{8}^{,}^{9} It has been demonstrated that under this model, parallel lines are projected onto circular arcs and all the circles intersect at two vanishing points, thus the centers of the circles are collinear.^{10} This property is of great importance because it allows fish-eye camera to be calibrated using single image of two sets of parallel lines in the scene, which is very convenient for practical applications. As a result, fitting of center collinear circles lies at the core of fish-eye camera calibration.

Based on the center colinearity property, Geyer et al.^{11} proposed a two-step fitting approach. They first fitted the circles separately and then refined the centers of the circles using the colinearity constraint. However, its accuracy is limited due to the fact that the estimated center collinear circles do not necessarily intersect at two points. Recently, Hughes et al.^{10} proposed an iterative approach to solve the fitting problem. Instead of fitting the circles separately, they utilized the available data points to fit all the circles simultaneously. On each iteration, they fixed one vanishing point and updated the other one, and enforced all the circles to intersect at the two vanishing points. Obviously this approach is more robust against noise thus can greatly improve the accuracy.

In this paper we propose a direct approach for fitting of center collinear circles. First we build a coordinate system for the circles and give the objective function for nonlinear optimization. Then we use Levenberg-Marquardt (LM) algorithm^{12} to solve the optimization problem. The main advantage of our approach is that two vanishing points are updated simultaneously. Experimental results show that the accuracy of our approach is the same as reported earlier,^{10} while its speed is much faster.

The remainder of this paper is organized as follows. Section 2 briefly describes the equidistant fish-eye projection. Section 3 presents three fitting approaches, including two existing approaches and the proposed direct approach. Section 4 gives our experimental results on both synthetic and real data, and Sec. 5 offers our conclusion.

## 2.

## Equidistant Fish-Eye Projection

Ideal fish-eye cameras are manufactured to follow the equidistance mapping function such that the distance between a projected point and the optical center of the image is proportional to the incident angle of the projected ray, scaled only by the equidistance parameter $f$, as described by the projection equation:^{13}^{,}^{14}

^{15}Figure 1 illustrates the equidistant projection for a simple model of an equidistant camera system.

Due to the radial distortion introduced by fish-eye lenses, straight lines in the scene will map to conics in the image. It has been proved that under this model, parallel lines are projected onto circular arcs and all the circles intersect at two vanishing points,^{10} as shown in Fig. 2. It has also been demonstrated that if the parameters of two sets of circles are known, all the intrinsic parameters required for fish-eye camera calibration can be determined.^{10} As a result, estimating the parameters of the circles lies at the core of equidistant fish-eye camera calibration. In the next section, we will present three fitting approaches for parameters estimation, including two existing approaches and the proposed direct approach.

## 3.

## Fitting of Center Collinear Circles

Fitting of single circle using a set of data points is a well-investigated nonlinear least square problem.^{16} However, little attention has been paid to multiple circles fitting. In this paper, we will focus on the fitting of center collinear circles, i.e., a set of circles whose centers are collinear, as illustrated in Fig. 3. The most important property of center collinear circles is that all of them intersect at two points. Thus fitting of the circles is always coupled with the estimation of the positions of the two points. In this section, we will first briefly describe two existing methods in the literature, and then introduce the proposed fitting approach.

## 3.1.

### Two-Step Approach

Geyer et al.^{11} proposed a two-step approach to estimate the parameters of center collinear circles for catadioptric camera calibration. The approach is briefly described as follows.

1. Separating the data points into several sets of points. Fitting one circle to each set of points.

2. Fitting a line to the centers of all the circles. Updating the centers by projecting them onto this line.

This approach first estimates the parameters of each circle separately, and then enforces the centers of the circles to be collinear. Note that it does not update the radii of the circles, and therefore, it cannot guarantee that all the circles intersect at two points.

## 3.2.

### Iterative Approach

Recently, Hughes et al. proposed an iterative approach to alternately update one point by fixing the other.^{10} This approach consists of the following steps.

1. Separating the data points into several sets of points. Fitting one circle to each set of points.

2. Calculating the intersect points of the circles and determining the initial positions of the two points.

3. Fixing one point and updating the other using LM optimization.

4. Repeating step (3) until convergence is observed or the maximum number of iterations is reached.

It is obvious that when the algorithm terminates, we could obtain the positions of the two points as well as the parameters of the circles. Note that this approach enforces the circles to intersect at two points, thus it is expected to be more accurate than the two-step approach. However, since each time the approach updates only one point, it would take a number of iterations for convergence.

## 3.3.

### Direct Approach

In this subsection, we present a direct approach for fitting of center collinear circles. We first build a coordinate system to facilitate derivations, and then give the equations of the center collinear circles using the vanishing points constraint. Next we propose to solve the fitting problem using LM optimization, and give the objective function as well as its Jacobian. Finally we discuss some issues related to its implementation.

Assume the center collinear circles intersect at two vanishing points ${v}_{1}$ and ${v}_{2}$. After translation $\mathbf{T}=\mathbf{T}(x,y)$ and rotation $\mathbf{R}=\mathbf{R}(\theta )$, we define the midpoint of line segment $\overline{{v}_{1}{v}_{2}}$ as the origin, and the line determined by ${v}_{1}$ and ${v}_{2}$ as the X-axis, as shown in Fig. 3. In this coordinate system, the center of the circle ${C}_{i}$ is $(0,{b}_{i})$, and the coordinates of ${v}_{1}$ and ${v}_{2}$ are $(-a,0)$ and $(a,0)$, respectively. The equation of circle ${C}_{i}$ can be expressed as

where the radiusIn order to fit $N$ circles, we should estimate $N+4$ parameters, i.e., $x$, $y$, $\theta $, $a$, ${b}_{1},\cdots ,{b}_{N}$.

After translation and rotation, a data point $p$ is transformed from $(m,n)$ to $({m}^{\prime},{n}^{\prime})$, which satisfies

## (4)

$$\left[\begin{array}{c}{m}^{\prime}\\ {n}^{\prime}\end{array}\right]=\mathbf{R}(\mathbf{P}-\mathbf{T})=\left[\begin{array}{cc}\mathrm{cos}\theta & -\mathrm{sin}\theta \\ \mathrm{sin}\theta & \mathrm{cos}\theta \end{array}\right]\left[\begin{array}{c}m-x\\ n-y\end{array}\right]\phantom{\rule{0ex}{0ex}}=\left[\begin{array}{c}(m-x)\mathrm{cos}\theta -(n-y)\mathrm{sin}\theta \\ (m-x)\mathrm{sin}\theta +(n-y)\mathrm{cos}\theta \end{array}\right]\mathrm{.}$$## (5)

$${d}_{i,k}=\Vert {p}_{i,k}^{\prime}-{C}_{i}\Vert =\sqrt{{({m}_{i,k}^{\prime})}^{2}+{({n}_{i,k}^{\prime}-{b}_{i})}^{2}},$$## (6)

$${f}_{i}={\displaystyle \sum _{k=1}^{{N}_{i}}{({d}_{i,k}-{r}_{i})}^{2}}={\displaystyle \sum _{k=1}^{{N}_{i}}{[\sqrt{{({m}_{i,k}^{\prime})}^{2}+{({n}_{i,k}^{\prime}-{b}_{i})}^{2}}-\sqrt{{a}^{2}+{b}_{i}^{2}}]}^{2}},$$## (7)

$$F={\displaystyle \sum _{i=1}^{N}{f}_{i}}={\displaystyle \sum _{i=1}^{N}{\displaystyle \sum _{k=1}^{{N}_{i}}{({d}_{i,k}-{r}_{i})}^{2}}}\mathrm{.}$$Substituting Eqs. (4) and (6) into Eq. (7), we get

## (8)

$$F={\displaystyle \sum _{i=1}^{N}\sum _{k=1}^{{N}_{i}}{\displaystyle {[\sqrt{{({m}_{i,k}-x)}^{2}+{({n}_{i,k}-y)}^{2}+{b}_{i}^{2}-2{b}_{i}({m}_{i,k}-x)\mathrm{sin}\theta -2{b}_{i}({n}_{i,k}-y)\mathrm{cos}\theta}-\sqrt{{a}^{2}+{b}_{i}^{2}}]}^{2}}}.$$LM algorithm^{12} is very efficient for the above optimization problem. In order to apply LM algorithm, we should derive the first partial derivative of the objective function, i.e., the Jacobian.^{17} After some mathematical manipulation, we get the Jacobian

## (9)

$$\frac{\partial {f}_{i}}{\partial x}=\frac{-(m-x)+{b}_{i}\mathrm{sin}\theta}{d}\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\frac{\partial {f}_{i}}{\partial y}=\frac{-(n-y)+{b}_{i}\mathrm{cos}\theta}{d}\phantom{\rule{0ex}{0ex}}\frac{\partial {f}_{i}}{\partial \theta}=\frac{{b}_{i}}{d}[-(m-x)\mathrm{cos}\text{\hspace{0.17em}}\theta +(n-y)\mathrm{sin}\text{\hspace{0.17em}}\theta ]\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}\frac{\partial {f}_{i}}{\partial a}=-\frac{a}{{r}_{i}}\phantom{\rule{0ex}{0ex}}\frac{\partial {f}_{i}}{\partial {b}_{j}}=\{\begin{array}{cc}\frac{{b}_{i}-(m-x)\mathrm{sin}\theta -(n-y)\mathrm{cos}\theta}{d}-\frac{{b}_{i}}{{r}_{i}}& \text{if}\text{\hspace{0.17em}\hspace{0.17em}}i=j\\ 0& \mathrm{otherwise}\end{array}$$Setting the initial estimation properly is very crucial for LM optimization. Since the fitting error increases with the radius of circle, we propose to first fit each circle separately, and then use the intersect points of two smallest circles as the initial estimation of the vanishing points. The initial values used for LM optimization then can be determined by the two vanishing points and the parameters of the circles. After convergence of LM algorithm, we can compute the parameters of the circles. The complete approach is given as follows:

1. Separating the data points into several sets of points. Fitting one circle to each set of points.

2. Finding two smallest circles and calculating the intersect points of them.

3. Calculating the initial estimation of the parameters $x$, $y$, $\theta $, $a$, ${b}_{1},\cdots ,{b}_{N}$.

4. Updating the parameters using LM optimization until convergence.

5. Calculating the parameters of the circles using the optimization result.

Note that our method is also an iterative approach because LM algorithm is used for parameter estimation and LM algorithm often requires a number of iterations. However, in the iterative approach presented in Sec. 3.2, the vanishing points are estimated sequentially, while in our approach they are estimated simultaneously. Thus our approach is expected to be faster than the iterative approach. In addition, our approach also enforces the circles to intersect at two points, thus it is expected to be more accurate than the two-step approach.

## 4.

## Experimental Results

We have evaluated our method on both synthetic and real data and have compared it with those proposed.^{10}^{,}^{11} We use speed and accuracy as performance indicators for comparison. The platform is a PC with Intel CPU i5-2400 3.10 GHz and 8 G RAM. The software environment is Windows 7 Ultimate and Visual Studio 2005. All the testing programs are written in C++ language.

## 4.1.

### Synthetic Data

In order to stimulate the fish-eye camera calibration, we generate eight center collinear circles (denoted as $C1$ to $C8$), and use only arcs of them for parameter estimation, as shown in Fig. 4. The resolution of the synthetic image is 640 × 480, and the parameters of the circles are listed in Table 1.

## Table 1

Parameters of the synthetic circles.

C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | |
---|---|---|---|---|---|---|---|---|

(Cx,Cy) | (31.55, 0) | (107.61, 0) | (240, 0) | (600, 0) | (−462,0) | (−194.44,0) | (−79.80,0) | (−10.16,0) |

r | 321.55 | 337.61 | 400 | 680 | 562 | 374.44 | 329.80 | 320.16 |

Note: (Cx,Cy) is the center of the circle. The center of the image (320, 240) is regarded as the origin. r is the radius of the circle.

On each arc we randomly choose 100 points. Gaussian noise with zero-mean and $\sigma $ standard deviation is added to the points. The noise levels $\sigma $ are 0, 1, 2, 3, 4, 5, respectively. For each noise level, we perform 100 independent trials, and the mean values and standard deviations of these recovered parameters are computed over each run. The errors compared to the ground truth are defined as

## Table 2

Fitting results of Cx when σ=3.

C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | |
---|---|---|---|---|---|---|---|---|

GT | 31.55 | 107.61 | 240 | 600 | −462 | −194.44 | −79.80 | −10.16 |

meant | 33.46 | 108.84 | 240.29 | 611.15 | −462.04 | −194.54 | −81.28 | −10.35 |

meani | 31.10 | 107.11 | 240.34 | 601.35 | −461.62 | −195.56 | −79.53 | −10.41 |

meand | 31.09 | 107.10 | 240.32 | 601.27 | −461.64 | −195.56 | −79.53 | −10.41 |

stdt | 6.20 | 6.81 | 11.40 | 37.41 | 24.38 | 9.23 | 7.31 | 7.20 |

stdi | 0.69 | 0.93 | 1.63 | 5.88 | 4.33 | 1.64 | 0.90 | 0.71 |

stdd | 0.69 | 0.93 | 1.63 | 5.88 | 4.33 | 1.64 | 0.90 | 0.71 |

errort | 5.40 | 5.48 | 9.57 | 31.42 | 20.59 | 7.21 | 6.01 | 6.14 |

errori | 0.63 | 0.83 | 1.26 | 4.69 | 3.29 | 1.59 | 0.73 | 0.57 |

errord | 0.64 | 0.83 | 1.25 | 4.65 | 3.29 | 1.59 | 0.73 | 0.57 |

## Table 3

Fitting results of Cy when σ=3.

C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | |
---|---|---|---|---|---|---|---|---|

GT | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

meant | 0.013 | −0.086 | −0.253 | −0.769 | 0.684 | 0.324 | 0.172 | 0.072 |

meani | 0.003 | −0.008 | −0.028 | −0.080 | 0.075 | 0.036 | 0.019 | 0.009 |

meand | 0.003 | −0.008 | −0.028 | −0.080 | 0.075 | 0.036 | 0.019 | 0.009 |

stdt | 0.91 | 1.04 | 1.39 | 2.68 | 1.91 | 1.09 | 0.90 | 0.89 |

stdi | 0.16 | 0.19 | 0.27 | 0.55 | 0.41 | 0.22 | 0.17 | 0.16 |

stdd | 0.16 | 0.19 | 0.27 | 0.55 | 0.41 | 0.22 | 0.16 | 0.16 |

errort | 0.74 | 0.85 | 1.14 | 2.19 | 1.56 | 0.88 | 0.73 | 0.72 |

errori | 0.13 | 0.15 | 0.21 | 0.42 | 0.33 | 0.18 | 0.14 | 0.13 |

errord | 0.13 | 0.15 | 0.21 | 0.42 | 0.33 | 0.18 | 0.14 | 0.13 |

## Table 4

Fitting results of r when σ=3.

C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | |
---|---|---|---|---|---|---|---|---|

GT | 321.55 | 337.61 | 400 | 680 | 562 | 374.44 | 329.80 | 320.16 |

meant | 323.73 | 338.87 | 400.29 | 690.83 | 562.18 | 374.34 | 331.33 | 320.21 |

meani | 321.58 | 337.54 | 400.31 | 681.31 | 561.66 | 375.03 | 329.77 | 320.23 |

meand | 321.57 | 337.53 | 400.29 | 681.22 | 561.67 | 375.03 | 329.77 | 320.22 |

stdt | 4.94 | 5.49 | 9.83 | 35.97 | 22.90 | 7.89 | 5.92 | 5.64 |

stdi | 0.59 | 0.79 | 1.48 | 5.74 | 4.19 | 1.45 | 0.78 | 0.56 |

stdd | 0.59 | 0.79 | 1.47 | 5.73 | 4.19 | 1.45 | 0.78 | 0.56 |

errort | 1.34e-2 | 1.30e-2 | 2.04e-2 | 4.43e-2 | 3.43e-2 | 1.65e-2 | 1.48e-2 | 1.48e-2 |

errori | 1.39e-3 | 1.82e-3 | 2.83e-3 | 6.75e-3 | 5.67e-3 | 3.24e-3 | 1.81e-3 | 1.35e-3 |

errord | 1.39e-3 | 1.82e-3 | 2.82e-3 | 6.70e-3 | 5.67e-3 | 3.24e-3 | 1.81e-3 | 1.34e-3 |

From Tables 2Table 3–4, we can see that the fitting results are almost the same for the iterative and the direct approaches, and both of them are much more robust and accurate than the two-step approach. The error and standard derivation of the two-step approach are around 5 to 10 times larger than those of the other two approaches. Thus we can conclude that in terms of fitting accuracy both the iterative and the direct approaches are superior to the two-step approach.

Another observation from Tables 2Table 3–4 is that for all the three approaches, the error and standard derivation increase with the radius of the circle, which is consistent with previous studies.^{18}^{,}^{19} The reason is that for a larger circle, the arc in the image corresponds to a smaller angle. As a result, the accuracy decreases due to a larger amount of occlusion of the circle. On the other hand, because the iterative and the direct approaches use all the data points for parameters estimation, the adverse effect of noise and occlusion can be greatly reduced by the vanishing points constraint. Hence these two approaches are more robust and accurate than the two-step approach.

The time requirements of the three approaches are reported in Table 5. It can be observed that the two-step approach is the fastest one, which only requires less than 16 ms on average when $\sigma =3$. The other two approaches are much slower. The time required by the iterative and the direct approaches are about 700 and 30 times more than that of the two-step approach, respectively. It is reasonable because nonlinear optimization is adopted by the direct approach using all the data points and the center collinear constraint, which costs much more time than just estimating the parameters of each circle separately. The iterative approach often requires several tens of iterations for convergence (as listed in Table 6), and there is also a nonlinear optimization step on each iteration. As a result, the iterative approach is the most time-consuming of all. Our method is more than 20 times faster than the iterative approach, and its average running time is less than half a second, which makes it very promising for practical calibration procedures.

## Table 5

The average time (ms) required by the three approaches.

σ | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

Two-step approach | 8.27 | 11.55 | 13.01 | 14.35 | 14.88 | 15.73 |

Iterative approach | 5490 | 7440 | 8845 | 9563 | 11364 | 11467 |

Direct approach | 285.7 | 349.5 | 386.6 | 403.9 | 424.4 | 438.4 |

## Table 6

The average iterations required by the iterative approach for convergence.

σ | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

Avg. Iters | 21.53 | 24.19 | 29.03 | 31.25 | 36.76 | 37.01 |

## 4.2.

### Real Data

In this expirment, we take an image using a fish-eye camera with FOV about 170 deg. A chess board is placed in front of the camera for calibration. The size of each block in the chess board is $15\times 15\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\mathrm{mm}}^{2}$, and the resolution of the image is $640\times 480$, as depicted in Fig. 5. Curve extracting is accomplished by a software package developed by our lab. On both horizontal and vertical directions, only six arcs with the largest lengths are selected for parameters estimation. After the fitting of center collinear circles, we can obtain the positions of horizontal vanishing points ${v}_{x1}$ and ${v}_{x2}$ and the vertical vanishing points ${v}_{y1}$ and ${v}_{y2}$. If the line joins ${v}_{x1}$ and ${v}_{x2}$ is denoted as ${l}_{x}$, and that joins ${v}_{y1}$ and ${v}_{y2}$ is denoted as ${l}_{y}$, then the optical center can be determined as the intersect point of ${l}_{x}$ and ${l}_{y}$, and the focal lengths on horizontal and vertical directions are given by

and Then we can use Eq. (1) for distortion correction. The details about distortion correction are available.^{15}

Due to lack of the ground truth of parameters of the fish-eye camera, we just check the undistorted image to evaluate the calibration results and the proposed approach. The undistorted image is shown in Fig. 6. As can be seen in this figure, straight lines in the scene now map to straight lines in the image. We then extract the $8\times 8$ corners of the chess board^{20} and compute the reconstruction error. The average difference between the position of each corner and their true position is 1.631 pixel. Because the resolution of each block in the undistorted image is $63.267\times 63.267$, the reconstruction error can be computed as $1.631/63.267\times 15=0.387\text{\hspace{0.17em}}\text{\hspace{0.17em}}\mathrm{mm}$. Thus we conclude that our method is effective for fish-eye camera calibration.

## 5.

## Conclusions

In this paper we propose a novel method for fitting of center collinear circles for fish-eye camera calibration. We formulate the fitting problem as a nonlinear least square problem and solve it using LM optimization. Experimental results on synthetic data show that the proposed method is much more accurate than the two-step approach, and it requires much less time than the iterative approach while keeping the fitting performance unspoiled. Results on real data demonstrate its effectiveness for fish-eye camera calibration. Hence we can conclude that the proposed method is very promising for practical applications.

## Acknowledgments

This work is partially supported by Beijing Postdoctoral Research Foundation (2011ZZ-57), Postdoctoral Science Foundation of China (2011M500013), and Overseas Talents Attracting Plan of BJAST (OTP-2012-012).

## References

## Biography

**Feng Yue** received his BSc and PhD degrees in computer science from the Harbin Institute of Technology (HIT), in 2003 and 2010, respectively. He is now a postdoctoral researcher in the Pattern Recognition Research Center, Beijing Institute of New Technology Applications. His current research interests include computer vision and pattern recognition.

**Bin Li** received his MSc and PhD degrees in computer science from Harbin Institute of Technology (HIT), Harbin, China, in 2000 and 2006, respectively. From 2006 to 2008, he worked in School of Computer Science and Technology, HIT, as a lecturer. From 2008 to now, he has been working in Key Laboratory of Pattern Recognition of Beijing Academy of Science and Technology as a director, and in Beijing Institute of New Technology Applications as an associate research fellow and deputy director. So far, he has published over 15 papers and two books. His research interests include signal processing, pattern recognition and biometrics, etc.

**Ming Yu** received his BS degree from Beijing University of Post and Telecommunications (BUPT), Beijing, China in 1986, the MS degree from Hebei University of Technology (HUT), Tianjin, China in 1989, and his PhD degree in communication and information systems from Beijing Institute of Technology (BIT), Beijing, China in 1999, respectively. Since 1989, he has been with the Department of Computer Science and Engineering, Hebei University of Technology, where he is currently a professor. His current research interests include image/video understanding, intelligent media processing and pattern recognition.