Optical Engineering, March 2010
Opt. Eng. 49, 037202 (2010) (7 pages)
2010 Society of Photo-Optical Instrumentation Engineers. All rights reserved.

Up: Issue Table of Contents
Go to: Previous Article | Next Article
Other formats: HTML (smaller files) | PDF ( kB)

Homography estimation from planar contours in image sequence

Ming Zhai

Shanghai Jiao Tong University, School of Electronic Information and Electrical Engineering, 800 Dongchuan Road, Shanghai, 200240 China

Shan Fu and
Zhongliang Jing

Shanghai Jiao Tong University, Institute of Aerospace Science and Technology, 800 Dongchuan Road, Shanghai, 200240 China

(Received: 19 May 2009; revised: 18 January 2010; accepted: 26 January 2010; published online: 22 March 2010)

Homography can be estimated from corresponding points, lines, or textures. But in some scenarios these features are not always available. As a supplement, the newly developed contour-based method is presented, which can be used to estimate the homography between any two planar contours of an image sequence. The proposed method improves the random sampling consensus (RANSAC) method into an iterative form. In the iterations, the random sample process of RANSAC is constrained by the previous iteration results. It reduces the blind sample process and ensures fast convergence speed. The experimental results demonstrate that the proposed method is effective. 2010 Society of Photo-Optical Instrumentation Engineers


Contents

Introduction

Homography estimation takes an important role in many applications such as camera calibration, metric rectification, 3-D reconstruction, visual servo, image registration, and pattern recognition.1,2,3,4,5,6,7,8,9,10,11,12 Many researchers have put their efforts on homography estimation. Homography can be described by a 33 matrix, called a homography matrix, and the matrix can be formulated by parameterized equations. By solving the equations with the known corresponding features, the homography can be obtained. These corresponding features include points, lines, conics, contours, textures, etc. According to corresponding features, homography estimation methods can be roughly classified into several categories: frequency-domain-based methods, high primitives-based methods, and low primitives-based methods.

The frequency-domain-based methods often formulate homography in the frequency domain, and then utilize the known corresponding features in the frequency domain to compute homography. The Fourier transformation of corresponding textures is often used as features,12,13 and Fourier descriptors (FDs)14,15,16 of corresponding contours are also used as features to compute homography.17,18,19

Unlike those methods mentioned before, the high-order primitives-based methods use high-order geometrical primitives such as conics and polygons, to solve the homography estimation problem.20,21,22 These methods have demonstrated better results in many applications than low-order primitives-based methods. But in many scenarios these features are not always available, so it limits the applications of the high-order primitives-based methods.

Compared with the high-order primitives-based method, low primitives-based methods are widely used because low primitives, such as points and lines, are easily obtained in most cases. Within this category, direct linear transformation (DLT) has been popularly used. To enhance the numerical stability of DLT, normalization procedures are often needed.23 But due to noise, mismatch inevitably exists, which will deteriorate the result of DLT. So robust methods like maximum likelihood estimates and random sample consensus (RANSAC)24 are proposed. But accurate corresponding features are hard to obtain in real situations, so some nonlinear methods like Levenberg-Marquardt25,26 and Gauss-Newton25 are normally applied to refine the results of these robust methods.

Contours have many good properties for homography estimation, e.g., they exist in most scenarios, and are easy to abstract and match. Therefore, our emphases are placed on the research of homography estimation from planar contours. The RANSAC method can be applied to estimate homography from contours, as is suggested in Ref. 24. However, if RANSAC is directly used, the computation is huge. The huge computation often arises from the blind random sample processes of RANSAC. To reduce the blind sample processes and ensure precision of the result, we present a contour-based method that combines RANSAC with the iterative closest point (ICP) algorithm.27 The newly developed method takes an iterative form similar to ICP. However, unlike ICP, in the iterations of the proposed method, RANSAC is used to estimate homography. Moreover, the random sample processes in RANSAC of the current iteration are constrained by the result of the previous iteration. It reduces the blind sample process and therefore ensures fast convergence speed. The experimental results demonstrate that the proposed method is effective.

This work is organized as follows. Section I is the introduction; Sec. II describes the Iterative RANSAC homography estimation; Sec. III shows the implementation; and Sec. IV is the conclusions.

Iterative Random Sample Consensus Homography Estimation

A.Practical Issues of Directly Using Random Sample Consensus

Given two contours denoted by X and Y, respectively, the two contours are generated by the same planar object in two different views. The homography between the two contours can be formulated as

<i>y</i>[<i>s</i><sub><i>y</i></sub>]  <i>H</i><i>x</i>[<i>s</i><sub><i>x</i></sub>] = 0,1

where H is a 33 matrix, called the homography matrix, the sx'th point of contour X and the sy'th point of contour Y are assumed to be a corresponding point pair, and y[sy] and x[sy] are the homogeneous coordinates of the two points. The RANSAC method can be applied to estimate the homography of the two contours, as is suggested in Ref. 24. The direct way to apply RANSAC to estimate the homography between contour X and Y is summarized as follows.

Step 1

Random sample four points A1, A2, A3, and A4 in X (any three of them are not on the same line), and find the four corresponding points B1, B2, B3, and B4 in Y using Eq. (1) with the initial homography estimation Hinitial.

Step 2

Define the neighborhood point set betas of point Bs (Bs[is-an-element-of]Y), [for all]P[is-an-element-of]betas satisfying P[is-an-element-of]Y and d(P,Bs)<d0, where d0 is a constant. In the neighborhood point set betas of Bs, randomly selected one point B<sub><i>s</i></sub><sup>[prime]</sup> (s=1,2,3,4). Assuming As and B<sub><i>s</i></sub><sup>[prime]</sup> (s=1,2,3,4) are a corresponding point pair, compute the new homography Hnew by solving Eq. (1).

Step 3

If Hnew satisfies the convergence conditions, then it ends and Hnew is the final estimation, otherwise go to step 1.

If the initial homography estimation Hinitial is not known, then B1, B2, B3, and B4 should be random sampled from the whole contour Y, and the neighborhood point set betas of point Bs (s=1,2,3,4) should be the whole contour. Therefore, when Hinitial is not known, the computation is huge. But if the two contours are abstracted from the two successive frames of an image sequence, and then the difference between the two contours is small, then it is reasonable to assume

<i>H</i><sub>initial</sub> = ((1, 0, <i>C</i><sub><i>X</i>1</sub> − <i>C</i><sub><i>Y</i>1</sub>; 0, 1, <i>C</i><sub><i>X</i>2</sub> − <i>C</i><sub><i>Y</i>2</sub>; 0, 0, 1)),

where (CX1,CX2) and (CY1,CY2) are the mass centers of contour X and Y, respectively. Denote the point number of the neighborhood point set betas by Nbetas (s=1,2,3,4). The value of Nbetas determines the convergence speed. If Nbetas is larger, the speed is slower because the blind random sample processes and the error computing in RANSAC waste most of the time. On the contrary, if Nbetas is smaller, the speed may be faster, but the correct corresponding point may not be included in the neighborhood point set, so it will affect the precision of the estimation. It is a dilemma to choose the value of Nbetas to balance the precision and computation complexity. Moreover, even if Nbetas is given, it is hard to judge whether the correct corresponding points are included in the neighborhood sets.

Usually the upper limit of the sample times of RANSAC can be estimated by the following equation:24

<i>k</i> = ((log(1 − <i>rho</i>))/(log(1 − <i>w</i><sup><i>alpha</i></sup>))),2

where rho is the probability that RANSAC in some iteration selects only inliers, alpha is the point number needed for estimating a model, and w is the probability of choosing an inlier. In our case alpha=4, and in a neighborhood point set, there is only one inlier point, i.e., the corresponding point, so with Eq. (2) the upper limit of the sample times of RANSAC in our case is

<i>k</i><sub><i>R</i></sub> = ((log(1 − <i>rho</i>))/(log[1 − (1/<i>N</i><sub><i>beta</i> 0</sub>)<sup>4</sup>])),3

where Nbeta0=max1<=s<=4(Nbetas). Because there is only one inlier point in one neighborhood set, the probability of the outlier is high and therefore the upper limit of the sample times of RANSAC computed from Eq. (3) is huge.

The upper limit of sample times in RANSAC determines the computation complexity and stability. To reduce the blind sample process and ensure the precision of the result, we present a method that combines the RANSAC with the iterative closest point (ICP) algorithm.27 The newly developed method takes an iterative form like ICP, and moreover, in the iteration process, the random sample processes in RANSAC are constrained by the result of the previous iteration. It reduces the blind sample and therefore ensures fast convergence speed.

B.Simplified Iterative Random Sample Consensus Homography Estimation

To illustrate the proposed method clearly, we first put forward the simplified method to estimate the homography between contours X and Y. The simplified method is summarized as follows.

Initial step

With the initial estimation Hinitial, calculate the initial error Einitial using the method showed in Fig. 1, and random sample four points A1, A2, A3, and A4 from contour X, of which any three points are not on the same line.

Figure 1.

Step 1

In contour Y, by solving Eq. (4), find the four corresponding points B1, B2, B3, and B4 of the four selected points A1, A2, A3, and A4.

<i>B</i>[<i>s</i>]  <i>H</i><sub>initial</sub><i>A</i>[<i>s</i>] = 0,  <i>s</i> = 1,2,3,4,4

where A[s] and B[s] are the homogeneous coordinates of As and Bs (s=1,2,3,4), respectively. If the point with coordinate B[s] calculated by Eq. (4) is not on contour Y, then choose the point of Y nearest to B[s] as point Bs.

Step 2

Find the neighborhood point set betas of Bs. In betas, randomly select one point B<sub><i>s</i></sub><sup>[prime]</sup> (s=1,2,3,4). Assuming As and B<sub><i>s</i></sub><sup>[prime]</sup> (s=1,2,3,4) is a corresponding point pair, compute the new homography Hnew by solving Eq. (5) and recomputing the new error Enew with the procedure shown in the flowchart of Fig. 1.

<i>B</i><sup>[prime]</sup>[<i>s</i>]  <i>H</i><sub>new</sub><i>A</i>[<i>s</i>] = 0,  <i>s</i> = 1,2,3,4.5

Repeat step 2 until Enew<Einitial.

Step 3

If Enew is small enough, then it ends and Hnew is the final estimation, otherwise let Hinitial=Hnew, Einitial=Enew, and go to step 1.

Equations (4),(5) are directly obtained from Eq. (1). By reorganizing Eq. (4) or (5), Eq. (6) is obtained.

[((0<sup><i>T</i></sup>,  − <i>V</i><sub><i>s</i></sub><sup><i>T</i></sup>, <i>U</i><sub><i>s</i></sub><sup><i>y</i></sup><i>V</i><sub><i>s</i></sub><sup><i>T</i></sup>); (<i>V</i><sub><i>s</i></sub><sup><i>T</i></sup>, 0<sup><i>T</i></sup>,  − <i>U</i><sub><i>s</i></sub><sup><i>x</i></sup><i>V</i><sub><i>s</i></sub><sup><i>T</i></sup>))][(<i>h</i><sub>1</sub>; <i>h</i><sub>2</sub>; <i>h</i><sub>3</sub>)] = <i>A</i><sub><i>s</i></sub><i>h</i> = 0,  <i>s</i> = 1,2,3,4,6

where Us=(U<sub><i>s</i></sub><sup><i>x</i></sup>  U<sub><i>s</i></sub><sup><i>y</i></sup>  1)T, Vs=(V<sub><i>s</i></sub><sup><i>x</i></sup>  V<sub><i>s</i></sub><sup><i>y</i></sup>  1)T are homogeneous coordinates of the s'th corresponding point pair and

<i>H</i> = [(<i>h</i><sub>1</sub><sup><i>T</i></sup>; <i>h</i><sub>2</sub><sup><i>T</i></sup>; <i>h</i><sub>3</sub><sup><i>T</i></sup>)]

is a homography matrix and

<i>A</i><sub><i>s</i></sub> = [(0<sup><i>T</i></sup>,  − <i>V</i><sub><i>s</i></sub><sup><i>T</i></sup>, <i>U</i><sub><i>s</i></sub><sup><i>y</i></sup><i>V</i><sub><i>s</i></sub><sup><i>T</i></sup>; <i>V</i><sub><i>s</i></sub><sup><i>T</i></sup>, 0<sup><i>T</i></sup>,  − <i>U</i><sub><i>s</i></sub><sup><i>x</i></sup><i>V</i><sub><i>s</i></sub><sup><i>T</i></sup>)],  <i>h</i> = [(<i>h</i><sub>1</sub>; <i>h</i><sub>2</sub>; <i>h</i><sub>3</sub>)].

Then h can be solved from Eq. (6) by some numerical methods like the SVD-based method.23

The computation of the simplified iterative RANSAC homography estimation method can be estimated. Denote B<sub><i>s</i></sub><sup>0</sup> as the correct corresponding point of point As (s=1,2,3,4). Assume there are Ds point intervals between the correct corresponding point B<sub><i>s</i></sub><sup>0</sup> and the assumed corresponding point Bs or B<sub><i>s</i></sub><sup>[prime]</sup> (s=1,2,3,4). Denote Dmax=max1<=s<=4(Ds). In step 2, there are two possible choices to select the assumed corresponding point B<sub><i>s</i></sub><sup>[prime]</sup> (s=1,2,3,4). One is nearer to the correct corresponding point, and the other is farther away from it. Usually three of the four points chosen nearer to the correct match points will make step 2 finish. We assume that three of the four points are chosen nearer to the correct match points, so with Eq. (2) it needs at most log(1−rho)/log[1−0.53] times of samples to make Step 2 finish. Assume Dmax only decreases one point when step 2 finished. Then the upper limit of the sample times of the simplified method is

<i>k</i><sub><i>S</i></sub> = ((log(1 − <i>rho</i>))/(log[1 − 0.5<sup>3</sup>]))<i>D</i><sub>max</sub><sup>0</sup> + (<i>N</i><sub><i>beta</i> 0</sub> − 1)<sup>4</sup>,7

where we assume Nbeta0=max1<=s<=4(Nbetas) and D<sub>max</sub><sup>0</sup> is the value of Dmax in step 1. The value of Nbeta0 in the traditional RANSAC should be selected large enough to ensure that the corresponding points are included in the neighborhood point set, but in the proposed method, Nbeta0 is smaller and therefore the proposed method needs less computation. For example, if rho=0.99 and D<sub>max</sub><sup>0</sup>=7, for the traditional RANSAC Nbeta0 should be at least 2D<sub>max</sub><sup>0</sup> to ensure that the corresponding points are included in the neighborhood point set and the upper limit of the sample times computed with Eq. (3) is huge. The huge upper limit of sample times indicates unstable computation complexity. For the proposed method, usually Nbeta0=3 is enough, and therefore with Eq. (7), the upper limit of the sample times of the simplified method is 261. The smaller upper limit of sample times of the proposed method indicates more stable computation complexity.

In every new iteration, the points B1, B2, B3, and B4 in the second contour are recomputed according to the previous estimation. It ensures the right searching direction. The random sampling process used to search the corresponding points is limited in the small point sets, which are determined by the estimation of the previous iteration. It reduces the blind sample processes, so the iterative form of RANSAC converges fast and the computation is stable.

C.Practical Issues of the Proposed Method

Although the simplified method can reduce computation complexity, some practical issues needed to be noticed when applying it. Above all, how to choose Nbetas (s=1,2,3,4), the point number of the neighborhood point set, needs to be arranged because Nbetas is related to the computation complexity. The Monte Carlo test28,29 is used to illustrate the relationship between Nbetas and the amount of computation. With the two contours generated by computer without noise, the simplified iterative RANSAC method is tested by the 100-run Monte Carlo tests, that is, to carry out the simplified method 100 times respectively and calculate the average error with the sample times. The results are shown in Fig. 2. The sample times can be considered as the index of computation complexity. Figure 2 shows that larger Nbetas leads to more computation. On the contrary, if Nbetas is too small, for example Nbetas=3 (s=1,2,3,4), if all the three points are stained by noise and all the tried samples cannot satisfy the ending condition, then the simplified method will be probably trapped in an endless loop in step 2. So it is important to choose a proper Nbetas for reducing computation, and some techniques are needed to deal with the occurrence of endless loop.

Figure 2.

If we randomly select a point in the neighborhood set betas (s=1,2,3,4), there exist two choices: nearer to the correct match point and farther away from it. The first choice may make the estimation more accurate, and this direction is considered to be a correct direction. The probability of randomly selecting a point in the set betas lying in the correct direction is 1/2, so if we randomly sample four points from the four neighborhoods, the probability of all the four sampled points lying in the correct directions is 1/16. Assume the probability that one point in contour Y is stained by noise and becomes an outlier point epsilon. An outlier point is the point that will cause large error if used to compute homography.

The probability that the successive Nbetas/2 points of betas (s=1,2,3,4) lying in the proper direction are all outliers is

<i>p</i> = (((<i>epsilon</i>)/2))<sup><i>N</i><sub><i>beta</i><sub><i>s</i></sub></sub>/2</sup>.8

For less computation, Nbetas should be smaller; however, Nbetas should be big enough to make p tend to zero to avoid endless loop. When epsilon is 0.1, 0.2, and 0.3, respectively, the relationship of p and Nbetas is shown in Fig. 3. Figure 3 shows that p decreases sharply when Nbetas increases, so when endless loop occurs it is effective to increase Nbetas a little to help it jump out of endless loop. Given p and epsilon, a reference to choose Nbetas is given in Eq. (9).

<i>N</i><sub><i>beta</i><sub><i>s</i></sub></sub> >= ((2  lg  <i>p</i>)/(lg   <i>epsilon</i>/2)).9

Figure 3.

For detecting and dealing with endless loop, the threshold Nt is used. If in an iteration the sample times exceed Nt, then the endless loop is considered to occur. Increasing Nbetas a little will help to jump out of endless loop. The maximum sampling choice in step 2 for an iteration is N<sub><i>beta</i><sub><i>s</i></sub></sub><sup>4</sup>, so Nt can be set to N<sub><i>beta</i><sub><i>s</i></sub></sub><sup>4</sup>. In fact, N<sub><i>beta</i><sub><i>s</i></sub></sub><sup>4</sup> is too large; in our experiments, Nt is set to N<sub><i>beta</i><sub><i>s</i></sub></sub><sup>4</sup>/16.

If at least one of the four sampled points A1, A2, A3, or A4 in contour X in step 1 is an outlier, endless loop may occur too. If after adjusting Nbetas the endless loop occurs again, then it can be considered that at least one of the four sampled points A1, A2, A3, or A4 is an outlier. If so, we need to resample four points in contour X and restart the estimation. It will help to skip the outliers in contour X.

To improve the precision of the estimation, interpolation is needed. The B-spline interpolation is suggested. In theory, denser interpolation leads to more accurate results, but from our experience, when the density of interpolation reaches a certain level, increasing the density of interpolation is no good but increases computation. In our experiments, three interpolation times are used.

D.Whole Iterative Random Sample Consensus Homography Estimation

The whole iterative RANSAC homography estimation considering noise, endless loop, and other problems is summarized as follows.

Initial step

Set Hinitial and computed Einitial; set Nbetas according to Eq. (5); set Hcurrent=Hinitial, Ecurrent=Einitial.

Step 1

Random select four points A1, A2, A3, and A4 in the first contour, any three of which are not on the same line; let count=0.

Step 2

With Hcurrent using Eq. (4), compute the four corresponding points B1, B2, B3, and B4 in the second contour; let N<sub><i>beta</i><sub><i>s</i></sub></sub><sup>[prime]</sup>=Nbetas.

Step 3

Find the neighborhood point set betas of Bs with N<sub><i>beta</i><sub><i>s</i></sub></sub><sup>[prime]</sup> points (s=1,2,3,4). Randomly select one point B<sub><i>s</i></sub><sup>[prime]</sup> in the neighborhood point set betas (s=1,2,3,4), respectively. Assuming As and B<sub><i>s</i></sub><sup>[prime]</sup> are a corresponding point pair, obtain the new homography Hnew by solving Eq. (5) and compute the new error Enew.

Count=count+1

if Enew is small enough then end and Hnew is the final estimation

if Enew<Ecurrent, then Ecurrent=Enew, Hcurrent=Hnew, count=0, go to step 2

if count>N<sub><i>beta</i><sub><i>s</i></sub></sub><sup>[prime]4</sup>/16, then N<sub><i>beta</i><sub><i>s</i></sub></sub><sup>[prime]</sup>=N<sub><i>beta</i><sub><i>s</i></sub></sub><sup>[prime]</sup>+2, count=0

if N<sub><i>beta</i><sub><i>s</i></sub></sub><sup>[prime]</sup>>Nbetas+4, then go to step 1

if Enew>=Ecurrent then repeat step 3.

Unlike the simplified method, some techniques are added to deal with endless loop and to dynamically adjust the point number of the neighborhood set. In fact, step 3 is the process using RANSAC to find the corresponding points. A new iteration begins if and only if the current error in step 3 is smaller than the error of the previous iteration. It ensures that the error is not increasing with the iterations, so the proposed method will converge.

Compared with the normal RANSAC method, we need not care whether the correct corresponding points are included in the neighborhood set, because the neighborhood point sets refreshed in the iterations will move toward the correct corresponding points gradually. Therefore, Nbetas can be set smaller than in the normal RANSAC method, and accordingly the computation is smaller.

Implementation

Supposed an image sequence of a planar object has been obtained. Denote the homography between any two successive frames by Hm,m+1 (m=1,2,3,…). Hm,m+1 can be estimated by the proposed method from the two contours in the m'th frame and the (m+1)'th frame with the initial estimation

<i>H</i><sub>initial</sub> = ((1, 0, <i>C</i><sub><i>X</i>1</sub> − <i>C</i><sub><i>Y</i>1</sub>; 0, 1, <i>C</i><sub><i>X</i>2</sub> − <i>C</i><sub><i>Y</i>2</sub>; 0, 0, 1)),

where (CX1,CX2) and (Cy1,Cy2) are the mass centers of the contours in the m'th and the (m+1)'th frame, respectively. The homography between the first frame and the m'th frame (m>2), denoted by H1,m, can be estimated by the proposed method from the two contours in the first and the m'th frame with Hinitial=H1,m−1, where H1,m−1 can be estimated by

<i>H</i><sub>1,<i>m</i> − 1</sub> = [product]<sub>2</sub><sup><i>m</i> − 1</sup><i>H</i><sub><i>i</i> − 1,<i>i</i></sub>.

With the transitivity of homography, the homography between frame s and frame t (t>s) is Hs,t=H<sub>1,<i>s</i></sub><sup>−1</sup>H1,t. To obtain precise estimation of Hs,t, we estimate Hs,t from the contours in the s'th and the t'th frame using the proposed method with Hinitial=H<sub>1,<i>s</i></sub><sup>−1</sup>H1,t.

First we test the proposed method by estimating the homography from two successive contours, that is, to estimate Hm,m+1. Some example contours are used to generate the successive contours. The example contours used in the experiment are selected after carefully considering the complexity, the variety of curvature, the number of points, etc. Some of the example contours are shown in Fig. 4. A pair of successive contours, called a contour pair, is obtained by a virtual camera. Assume the virtual camera is moving-around the plane of example contour (which coincides with the Z=0 plane). Obtain one contour of the contour pair by imaging the example contour with the virtual camera at the three given rotation angles around axis X, Y, Z, denoted by theta, phi, and omega, respectively. After that, add three small angles Delta1, Delta2, and Delta3 to theta, phi, and omega, respectively, to obtain the other contour of the contour pair. Assume the frame rate of the virtual camera is more than 20  Hz and the rotation speed of the virtual camera around each axis is no more than 200  deg per second so Deltas (s=1,2,3) is limited less than 10  deg. Other contour pairs can be obtained by changing (theta,phi,omega) and Deltas (s=1,2,3). The advantage with this scheme of generating contours is that it covers the most realistic poses at which actual images are generally taken. For each example contour, at (theta,phi,omega)=(−60  deg+5  degm,−60  deg+5  degn,0  deg), where m=1,2,…24, n=1,2,…24, obtain contour pairs. It means 576 contour pairs are obtained for each example contour. We add Gaussian noise with standard deviation sigma[is-an-element-of]{2,4,6} pixels along each coordinate to alpha% (alpha[is-an-element-of]{2,5,8}) points of the contour pairs. For each example contour, the 576 contour pairs are used to estimate the homography by the proposed method with the initial homography estimation

<i>H</i><sub>initial</sub> = ((1, 0, <i>C</i><sub><i>X</i>1</sub> − <i>C</i><sub><i>Y</i>1</sub>; 0, 1, <i>C</i><sub><i>X</i>2</sub> − <i>C</i><sub><i>Y</i>2</sub>; 0, 0, 1)).

In the experiment, the proposed method converges fast and the average sample times at convergence times at different noise levels are shown in Table I.

Figure 4.

With some selected contour pairs, we compare the proposed method with the normal RANSAC method. If Nbetas is not properly set, the normal RANSAC method will not converge at the given precision. To make the comparison feasible, some contour pairs are selected, with which the normal RANSAC method does converge when Nbetas<=9. The average sample times of the proposed method and the normal RANSAC method are obtained by 50-run Monte Carlo tests, respectively. The results are shown in Table II. Table II showed that with the same precision, our method outperformed the normal RANSAC method.

We also use real image sequences to test the proposed method. The image sequences used in this experiment are obtained by translating and rotating a digital camera. Different combinations of rotation and translation with different speeds are considered when obtaining these sequences. In this experiment, the homography between the first frame and the m'th (m>90) frame, i.e., H1,m, is estimated. Some results are shown in Fig. 5.

Figure 5.

Conclusions and Discussions

A contour-based homography estimation method is presented. The newly developed method takes an iterative form, which combines RANSAC and ICP. The random sample process in RANSAC is constrained by the result of the previous iteration. It reduces the blind sample process and ensures fast convergence speed. The experimental results show that our technique is effective. It is found that the distortion caused by camera lens and the precision of the contour abstraction method will affect the estimation results. It will be our future work to improve the technique by considering these factors.

REFERENCES


  1. R. Y. Tsai, “Estimating three-dimensional motion parameters of a rigid planar patch,” IEEE Trans. Acoust., Speech, Signal Process. 29(6), 1147–1152 (1981). first citation in article
  2. Y. Fang and D. M. Dawson, “Homography-based visual servoing of wheeled mobile robots,” Proc. 41st IEEE Conf. Decision Control, Vol. 3, pp. 2866–2871 (2002). first citation in article
  3. L. Lucchese, “Closed-form pose estimation from metric rectification of coplanar points,” in IEE Proc. Vision Image Signal Process. 153(3), 364–378 (2006). first citation in article
  4. E. Montijano and C. Sagues, “Position-based navigation using multiple homographies,” in Proc. IEEE Intl. Conf. Emerging Technol. Factory Automation, pp. 994–1001 (2008). first citation in article
  5. G. Cross, A. W. Fitzgibbon, and A. Zisserman, “Parallax geometry of smooth surfaces in multiple views,” in Proc. 7th IEEE Intl. Conf. Computer Vision, Vol. 1, pp. 323–329 (1999). first citation in article
  6. Z. Chuan and T. D. Long, “A planar homography estimation method for camera calibration,” in Proc. 2003 IEEE Intl. Symp. Comput. Intell., Vol. 1, pp. 424–429 (2003). first citation in article
  7. T. Ueshiba and F. Tomita, “Plane-based calibration algorithm for multi-camera systems via factorization of homography matrices,” in Proc. 9th IEEE Intl. Conf. Computer Vision, Vol. 2, pp. 966–973 (2003). first citation in article
  8. Z. Zhang, “A flexible new technique for camera calibration,” IEEE Trans. Pattern Anal. Mach. Intell. 22, 1330–1334 (2001). first citation in article
  9. S. J. D. Prince, “Augmented reality camera tracking with homographies,” IEEE Comput. Graphics Appl. 22(6), 39–45 (2002). [Inspec] first citation in article
  10. D. Q. Huynh, “Affine reconstruction from monocular vision in the presence of a symmetry plane,” in Proc. 7th IEEE Intl. Conf. Computer Vision, Vol. 1, pp. 476–482 (1999). first citation in article
  11. R. Y. Tsai, “Estimating three-dimensional motion parameters of a rigid planar patch, II: singular-value decomposition,” IEEE Trans. Acoust., Speech, Signal Process. 30(4), 525–534 (1982). first citation in article
  12. S. K. A. Calway, “Image registration using multiresolution frequency domain correlation,” in Br. Mach. Vision Conf. (BMVC), pp. 316–325 (1998). first citation in article
  13. M. P. Kumar, “Planar homography from Fourier domain representation,” in Proc. Intl. Conf. Signal Process. Commun. (SPCOM), pp. 560–564 (2004). first citation in article
  14. C. T. Zahn, “Fourier descriptors for plane closed curves,” IEEE Trans. Comput. c-21, 269–281 (1972). first citation in article
  15. D. Zhang and G. Lu, “Generic Fourier descriptor for shape-based image retrieval,” in Proc. 2002 IEEE Intl. Conf. Multimedia Expo, Vol. 1, pp. 425–428 (2002). first citation in article
  16. I. Kunttu and L. Lepisto, “Shape-based retrieval of industrial surface defects using angular radius Fourier descriptor,” IEEE Trans. Image Process. 1(2), 231–236 (2007). first citation in article
  17. M. P. Kumar, “Discrete contours in multiple views: approximation and recognition,” Image Vis. Comput. 22(14), 1229–1239 (2004). [Inspec] first citation in article
  18. S. Kuthirummal, “Planar shape recognition across multiple views,” in Proc. Intl. Conf. Patt. Recog. (ICPR), pp. 482–488 (2002). first citation in article
  19. P. K. Jain and C. V. Jawahar, “Homography estimation from planar contours,” in Proc. 3rd Intl. Symp. 3D Data Process. Visual. Transmission (3DPVT'06), pp. 877–884 (2006). first citation in article
  20. Y. Chen, “Planar metric rectification by algebraically estimating the image of the absolute conic,” in Proc. 17th Intl. Conf. Patt. Recog., Vol. 4, pp. 88–91 (2004). first citation in article
  21. M. P. Kumar, “Geometric structure computation from conics,” in Proc. Indian Conf. Computer Vision, Graphics, Image Process. (ICVGIP), pp. 9–14 (2004). first citation in article
  22. A. Sugimoto, “A linear algorithm for computing the homography from conics in correspondence,” J. Math. Imaging Vision 13, 115–130 (2000). [Inspec] first citation in article
  23. R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, Cambridge University Press, Cambridge, UK (2004). first citation in article
  24. M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” Commun. ACM 24, 381–395 (1981). first citation in article
  25. P. E. Gill and W. Murray, “Algorithms for the solution of the nonlinear least-squares problem,” SIAM (Soc. Ind. Appl. Math.) J. Numer. Anal. 15(5), 977–992 (1978). first citation in article
  26. D. W. Marquardt, “An algorithm for least-squares estimation of nonlinear parameters,” J. Soc. Ind. Appl. Math. 11, 431–441 (1963). first citation in article
  27. P. J. Besl and N. D. McKay, “A method for registration of 3D shapes,” IEEE Trans. Pattern Anal. Mach. Intell. 14(2), 239–256 (1992). first citation in article
  28. N. Metropolis and S. Ulam, “The Monte Carlo method,” J. Am. Stat. Assoc. 44(247), 335–341 (1949). [MEDLINE] first citation in article
  29. G. S. Fishman, Monte Carlo: Concepts, Algorithms, and Applications, Springer Verlag, New York (1995). first citation in article

VITAE

Ming Zhai is currently a PhD candidate in the School of Electronic, Information, and Electrical Engineering at Shanghai Jiao Tong University. He obtained his BS and MS degrees from An Hui University, Heifei, China, in 2001 and 2005, respectively. His major research interests include image processing, computer vision, and related system development.

Shan Fu is a professor in the School of Aeronautics and Astronautics at Shanghai Jiao Tong University. He obtained his first degree in electronic engineering from the Northwestern Polytechnic University in 1985, and PhD from Heriot-Watt University in 1995. His long-time research interest is in the area of computer vision/image processing and related system development, which has been closely linked to engineering/industry applications, such as computerized visual inspection and metrology, experimental mechanics, and structural material engineering.

Zhongliang Jing received his BS, MS, and PhD degrees, all in electronics and information technology, from Northwestern Polytechnic University, China, in 1983, 1988, and 1994, respectively. He was elected as a Cheung Kong Scholar in 1999. He is currently the Associate Dean of the Institute of Aerospace Science and Technology of Shanghai Jiao Tong University. His research interests include information fusion, optimal control theory, target tracking, and aerospace control.

FIGURES


Full figure (20 kB)

Fig. 1. The flowchart for computing the error. N is the point number of contour X, D0 is the threshold to judge the outlier, Nout is the counter for the outlier, and n0 is the max acceptable proportion of outliers. First citation in article


Full figure (12 kB)

Fig. 2. The result of 100-run Monte Carlo tests for the simplified iterative RANSAC when Nbetas is set to 5, 7, 9, respectively. Smaller Nbetas converges faster. First citation in article


Full figure (15 kB)

Fig. 3. The relationship of p and Nbetas when epsilon is given. First citation in article


Full figure (26 kB)

Fig. 4. Some example contours used in the experiments. The contours vary in their shape, curvature properties, number of points, etc. First citation in article


Full figure (47 kB)

Fig. 5. Some experimental results of real image sequences. Six groups of results are presented. Ai (i=1,2,…,6) is the first frame of the six image sequences, respectively, and the contours labeled by green are used to estimate the homography; Bi (i=1,2,…,6) is another frame of the six sequences, respectively; Ci (i=1,2,…,6) are the overlap result of Ai with Bi wrapped by the estimated homography, respectively. (Color online only.) First citation in article

TABLES

Table I. The average sample times in different noise levels.
alphasigma
246
224.625.126.0
539.343.245.5
880.587.190.3
First citation in article

Table II. Some average sample times of the proposed method and the normal RANSAC method for the selected contour pairs (the noise level is sigma=4, alpha=5).

The example contour used
to generate the contour pair
Fig. 4
(a)
Fig. 4
(b)
Fig. 4
(c)
Fig. 4
(d)
Fig. 4
(e)
Fig. 4
(f)
The average sample times
of the propose method
39.553.347.539.048.555.2
The average sample times
of the normal RANSAC
403.8588.2441.1503.9527.2602.9
First citation in article


Up: Issue Table of Contents
Go to: Previous Article | Next Article
Other formats: HTML (smaller files) | PDF ( kB)