3-D Inference From the Motion Parallax of a Conic Arc and a Point in Two Perspective Views

I. Introduction

Inferring 3-D information, such as motion or object surface structure, from multiple perspective views, has extensive applica­ tion in robot visual navigation, automated assembly of moving parts, computer aided manufacturing and tracking. Past work concentrated on using the 2-D coordinates of the image point features in several perspective views to estimate 3-D information [ 1-4,12-18]. The major drawback of using the point correspon­ dences exclusively in estimating 3-D information without the a priori knowledge of the relative position between the views is the difficulty of finding the corresponding points on all the perspec­ tive views and the sensitivity of the solutions to the error in finding the point correspondences. Since it is generally felt that edge correspondences are easier to identify than the point corres­ pondences, there would be significant advantage in using the edges rather than points to estimate 3-D motion parameters. In this paper, we present an efficient method for 3-D inference using the motion parallax of 3-D moving planar contour or coplanar edges in the form of conic arc segments and either one or two point features, depending on whether the correspondences of the two end points of the conic arcs are given or not. The necessary and sufficient conditions for the uniqueness of a key parameter, which is the ratio between the depths of one end point of the conic are before and after the motion over the ratio between the depths of the intersection of two tangents at the end points be­ fore and after the motion, is stated and proved. The theorem also gives rise to an efficient technique for estimating this param­ eter which takes only a few arithmetic operations. The eight pure parameters characterizing the projective transformation of both conic arcs defined in [1,2] can be determined readily from this key parameter.

II. Review of the Eight Pure Parameters

Let C' be a conic arc in frame 2 in projective correspon­ dence with C; C' can be parameterized as:

O.,;u-:;1

where p,'s are functions of K,X,',Y;, and w 0 ' and are given in [5 ,6].

Let y and r be defined as

y plays a key role in determining the pure parameters in (2), as can be seen in the next section.

IV. Review of Two Propositions Regarding the Determination of Motion and Object Surface Structure from y

The following two propositions were proved in [6] and will be used later.

Proposition I The point at the intersection of the two tangent lines at the end points is in projective correspondence with that for the corresponding conic arc segment.

Proposition II Let H ,H', and B, be defined as

and

If C and C' are not degenerate (i.e., not straight lines), then

Proposition II reveals the importance of y. From (6), one can see that given two conic arc segments in projective corres­ pondences, all the parameters on the right hand side of (6) can be determined except y, and that A is function of y only.

V. Necessary and Sufficient Condition for the Uniqueness of y

Theorem II Let C and C' be two corresponding conic arc segments parameterized by (3) and (4), P( = XP,YP)' and P'( = Xp',Yp') be the corresponding points in two perspective views, and let H and H 1 be defined as in Proposition II. Then the necessary and sufficient conditions for the parameter y in (5) to be unique is that

The solution for the parameter y can be computed from any of the following three equations:

where

where 7 is given by

By substituting (6) in Proposition II into (II), and replacing (X, Y) and (X', Y') with (XP,YP) and (Xp',Yp'). we have

When C and C' are not degenerate (not straight lines), it was indicated in [5] that !l,' and H are nonsingular. Thus, by premul­ tiplying (12) by H'T 'we have

Let g 7d 0 1 , then (13) is equivalent to

which gives

Furthermore, if P is colinear with any two but not coinciding with any one of the three points, then at most two among (8.1-3) are indeterminate, leaving still one equation left for uniquely deter­ mining y.

Proof

Sufficiency proof:

It is easy to see that (I) is equivalent to the following homogene­ ous equation

Substituting (14.1) into (14.2) and (.14.3) gives

By dividing (14.3) with (14.2), we have

We now show that if (XP,YP) # (X; ,Y;) and (X p', Yp') # (X;', Y;') for i=O, I ,2, then no ~ore than ~ne equa­ tion among (IS), (16) and (17) are mdetermmate (t.e. , 0 ).

From (14.1-3), it is easy to see that whenever /3; = 0, <I>; also vanishes and vise versa. From (15), (16) and (17), it is seen that if not more than one pair of (/3;, </>;) is zero, then at least one among (15), (16) and (17) is not indeterminate. We now show that (XP,Y) # (X;.Y;l and (Xp'.Yp') # (X;',Y;') if and only if not more than one pair of (/3;,</>;) is zero.

From (9) and (10) ,

From (18), I= q, 1 + q, 2 + q, 3 and from (19), eq. I= beta sub I + beta sub 2 + beta sub 3

Thus the three pairs of (/3;.</>;l cannot vanish simultanuously in any condition. If two pairs of (/3;.</>;l vanish, say /3 0 = <1> 0 = 0 and /3 1 = q, 1 = 0, then (18) and (19) give

We have thus proved that (XP,YP) # (X;,Y;) and (X p', Yp') # (X;', Y;') for i=O, I ,2, only if no_t ~ore than one pair of (/3;.</>;l is zero. Conversely, if (XP,YP) comc1des w1th any pa1r of (/3;.</>;). say (XP,YP) = (X 0 ,Y 0 ) and (Xp',Yp') # (X0',Y0'), then from (18) and (19),

and

Thus (f3 2 ,q, 2 ) = (f3 3 ,q, 3 ) = 0. Therefore, if not more than one pair of (/3;.</>;l is zero, (X P' YP) and (XP', YP') cannot coincide with any one among (X; , Y;) and (X;', Y;' ) ,i = 0,1 ,2.

From the above proof, we conclude that the sufficient condi­ tion for the fact that not more than one equation among (15),(16) and (17) are indeterminate is that P does not coincide with either the end points or the intersection of the two tangents at the end points.

The necessity part can be easily proved by contradiction. In fact, if (XP,YP) and (Xp',Yp') were equal to any ·of (X;.Y;) and (X;', Y;' ), say, i=O, then, from (26), (/3 2 ,q, 2 ) = (/3 3 ,</> 3 ) = 0 forcing all three of (15), (16) and (17) to be indeterminate. The necessity part is thus proved.

We now proceed to show that even if P is colinear with any two of P .,i = 0 ,1,2,and P' is colinear with any two of P;',i = O,t,2, so long as if (XP,YP)#(X;,Y;) and (Xp',Yp')#(X;',Y;'), i=0,1,2, the solution for y is still unique. (In fact, this can already be deduced from the necessary and sufficient condition proved above. The following is .a more ex­ plicit and direct proof for this property.) The significance of this fact will be stated after the proof of the theorem.

If P is colinear with P 0 and P 2 , (which imply that P' is coli near with P 0 ' and P 2 ' ) , then there exist t (and t') such that

and

Notice that t in (21) is not equal to 0 or I when P does not coincide with either P 0 or P 2 . Therefore, when P is co linear with any two of P 0 ,P 1 ,P 2 , and does not coincide with any of then, not more than one among the pair (/3;.</>;),i = I ,2,3, can vanish. Therefore, at least one equation among (21-23) is not indetermi­ nate, forcing y to be unique.

Q.E.D.

After y is computed using either of (8.1-3 ), the eight pure parameters in (2) can be readily obtained using (6). Given the eight pure parameters, the 3-D motion parameters and object surface orientations can be estimated up to a common scale factor for the translations by computing the SVD of the 3 x 3 matrix A, as described in [1,2).

From [1,2), it was proved that given four coplanar point correspondences in two perspective views, the projective corres­ pondences of the whole image plane are determined if and only if no three points in either view are colinear. However, from Theo­ rem II, we see that given the correspondences of a conic arc (the correspondences of the intermediate points on the arc are not given) and a coplanar point, even when the latter is colinear with the end points and/ or the intersections of the two tangent lines at the end points, the solution is still unique .

1. Necessary and Sufficient Condition for the Unique­ ness of y Given the Correspondences of a Conic Arc (without knowing the correspondences of the two end points) and Two Point Features in Two Views

Since a complete second order curve is fixed given at least five points on the curve, in proving the following corollary, we assume that the conic arc actually is a complete second order curve without losing generality.

Corollary I Given the motion parallax of a conic arc C (without knowing the correspondences of the end points) and two point features Q 1 and Q 2 _ the necessary and sufficient conditions for the uniqueness of y (or the eight pure parameters) are that

not both points are on C and that Q 1 Q 2 is not tangent to C at Ql or Q2.

Proof Please see Ref. [20].

VI Experimental results

The following simulation experiments have been performed:

Simulated experimental setup

Test 1 (P not colinear with any two of P 0 ,P 1 ,P 2 ) Object surface patch: normal distance from the surface to the focal point 12.000 angles between the normal of the plane to the x,y and z axes respectively : 72.000°, 80.000°, 20.761 ° Conic arc C in view I (depicted in Fig. 2.1) K: 1.3093 , P 0 : (0.25000,0.10000), P 1 : (0.74000, 1.8700), p 2: ( 1.8700, 1.2000) Point P( = X p, YP): 3-D coordinates : (6.5450, -7.7000, 12.833) 2-D image coordinates : (0.51 000, -0.60000) Ideal y: 1.1559

3-D motion:

translations (~x.~y,.lz): (-2.6531, 3.0928, 4.0815) (~x/ ~z . ~y/ ~z): (-0.65003,0.75776) angle of rotation (1:1) : 14.000° angles between the rotation axis and the x,y,z axes : 82.500°,87.200°,8.0113°

Corresponding conic arcs C' and point P' transformed from C and P with the above 3-D motion and surface geometrical par­ ameters:

shown in Fig. 3.2.

Test 2 (P colinear with any two of P 0 ,PpP 2 )

The set up is same as those in Test 1 except for the 3-D and 2-D coordinates of P given in the following:

Point P( = Xp,Yp): 3-D coordinates: (11.742,8.9191,12.833)

2-D image coordinates : (0.91500,0.69500)

Corresponding conic arcs C' and point P' transformed from C and P in Fig. 3.1 with the above 3-D motion and surface geo­ metrical parameters:

shown in Fig. 3.2.

Experimental results (computed using the formula in Theorem II with single precision arithmetic)

Test 1:

y computed from (8.1): 1.1558

(/3p/3 2 ./3 3 ) = ( 1.0655 , - 0. 70040,0.63494) (</>p</> 2 .</> 3 ) = (1.0973,- 0.83377,0.73646) Object surface patch: angles between the normal of the plane to the x,y and z axes respectively : Solution I: (72.008°, 79.982°, 20.763°) Solution 2: (77.673°, 126.40°, 140.90°) 3-D motion: Solution I: translations : (~x/ ~z.~y/ ~z) : (-0.65025 ,0.75684) angle of rotation (1:1): 13.993° angles between the rotation axis and the x,y,z axes: 82.536°,87.139° '7 .9987° Solution 2: translations: (~x/~z.~y/~z): (0.14662, 0.31018) angle of rotation (1:1):24.978° angles between the rotation axis and the x,y,z axes : I 09.31°,121.15°,37.872° Test 2: y computed from (8.2): 1.1558 ((8.1) and (8.3) are indeterminate, as predicted) (/3p/3 2 ,/3 3 ) = (0.30000,0.45466*10- 7 ,0.7000) (</> p</> 2 ,</> 3 ) = (0.27568,- 0.140784032*10- 4 ,0.72436) Object surface patch: angles between the normal of the plane to the x,y and z axes respectively : Solution 1: (72.003°, 79.994°, 20.761°) Solution 2: (77.695°, 126.43°, 140.89°) 3-D motion: Solution I: translations: (~x/~z.~y/ ~z): (-0.65009, 0.75747) angle of rotation (1:1) : 13.998° angles between the rotation axis and the x,y,z axes: 82.512°,87.181°,8.0071° Solution 2: translations : (~x/ ~z.~y/ ~z): (0.14667, 0.30996) angle of rotation (1:1):24.981 ° angles between the rotation axis and the x,y,z axes: 109.32°,121.14°,37.872°

Note that in Test 2, since P is colinear with P 0 and P 2 ,/3 2 = <1> 2 = 0, while (/3 0 ,<t> 0 ) and (/3 2 ,<t> 2 ) are nonzero. In this case, the solution must be computed from (12,2) . Experi­ mental results support the theoretical findings.

As was mentioned in Sec. II, although the pure parameters a;. i = 1,.,8, are uniquely determined, there are still two possible solutions for the 3-D motion parameters and object surface orien­ tations, unless the matrix A in (2) has multiple singular values.

VII Conclusions

A new efficient algorithm for 3-D inference has been pres­ ented. The theoretical and computational aspects of the algor­ ithm are described in a theorem and an associated corollary. Based on the theorem, it takes very few arithmetic operations to compute the eight pure parameters characterizing the projective transformation of both conic arcs defined in [1,2] . With these eight pure parameters, it takes only computing the SVD of a 3 x 3 matrix for obtaining the 3-D motion parameters and object sur­ face orientations. Simulation results accurately support the theoretical findings.

Acknowledgements

The author would like to thank Mark Lavin and David Grossman for their helpful comments.