Obtaining Surface Orientation from Texels under Perspective Projection

1. INTRODlX:TION

The recovery of three dimensional (3-Q) scene information from a two dimensional (2-D) picture is an importent tesk in image understanding. Horn [Horn, 1977] reported 1 method to obtain surface orientation from intensity information recorded in a picture. In stead of intensity, it is possible to use textures as a cue for surface orientation.

A texture is constituted by the repetition of small patterns which are called texels (texture elements). The shepe of a pattern drawn on a 3-0 surface is distorted by the projection onto a 2-0 picture. Under orthoaraphic projection, the distortion depends only on the orientation of the 3-0 surface. This means that it is rather easy to obtain surface orientation from the distortion of texel patterns under orthographic projection [Kender, 1979; Kender & Kanade, 1980; lkeuchi, 1980).

It is well known that the imaain& process of a camera is perspective transformation; parallel lines in the 3-D scene are mapped onto lines in a 2-D picture which intersect at a point called vanishin& point. This simple property can be utilized to obtain the orientation of a 3-D plane surfece from the imaaes of parallel edges drawn on it [Kender, 1978; Kiteheshi, 1980]. The distortion of texel patterns under perspective projection, on the other hand, is not so simple as that under orthographic projection and it is not intuitive to use them as a cue for 3-0 surface orientation.

In this paper, we propose a way to approximate the distortion of 1 texel pattern under perspective projection by a In section 2, we explain the method to analyze the distortion of texel patterns under perspective projection by approximating perspective transformation with 2-0 Affine transformation. In section 3, we derive a simple relation between the vanishing line of a plane and the distortion of the texel patterns drawn on it. This relation is utilized to obtain the surface orientation of the plane. Section 4 presents an algorithm to solve the 2-0 Affine matrix between two patterns. When a peir of texel patterns are given, the algorithm decides whether one of which is a 2-D Affine transformation of the other. In that case, 1 2-0 Affine matrix is obtained as the solution. The algorithm reinforces the method described in section 3 to be applicable to a texture which is constituted from more than two kinds of texel patterns. Experiments are performed by using artificially generated textures and the results are described in section 5.

2. APPROXIMATION OF PERSPECTIVE TRANSFORMATION BY 2-D AFFINE TRANSFORMATION

In this chapter, we propose a way to approximate the distortion of a texel pattern under perspective projection by 2-0 Affine transformation whose parameters depend on the position of mass center of that texel in the picture.

Figure 1 illustrates a model of perspective projection. The imaae of each point in the te:r:el drawn on the object 1u.rfQCe is determined by the intersection of the imore plone with the projecting ray defined by that point and the Lens center. The centrol projectinr rct-y is a projectin& ray which goes through the mass center of the texel. The imore center is determined by the intersection of the image plane with the opticctl ct:r:il. The optical axis is perpendicular to the image plane. The origin of the coordinate system is the lens center and the negative z-axis is alligned with the optical axis. Let assume the distance from the lens center to the image plane is one, then the equation of the image plane is -z·l. x and y coordinates of the intersection of the image plane with the (centre!) projecting rey, whose direction is (P, Q, -1), is P and Q, respectively. The surface normal of the small plene, -z·pK+qy+c, on which the texel is drewn is (p, q, 1). If let -d be the z coordinate of the mass center of the teKel (or the intersection of the small plane with the central projecting ray), then clearly d-e/( 1-pP-qQ) (2- 1)

Figure 2 (a) shows an image obtained by perspective transformation of a texture which is generated by the repetition of small squares. The surface normal (p, q, 1) of the textural plane was set to p·O and q>O. The distortion of each texel differs to those of the others.

We think the distortion of teKels under perspective transformation is the composition of the following four factors.

1. When the -z coordinate of the (object) texel is greater than 1 (i.e, d> 1 in Fig. 1 ), the (image) texel is reduced.
2. When the small plane, on which the (object) texel is drawn, is not parallel to the image plane, the (image) texel is distorted.
3. When the mass center of the (image) texel is not identical to the image center, the texel is distorted.
4. Because the projecting rays for the points in the texel are not identical to the central project ing ray of the! texel, the (image) teKel is distorted.

The distortion caused by the fourth factor is negligible when the size of (image) texel is small. Figure 2 (b) illustrates the image to be obtained when the fourth factor is neglected. Our approximation for perspect ive transformation is equivalent to neglecting the distortion caused by the fourth factor.

Under perspective projection, as described before, a point on the object surface is projected onto the image plane by a projecting ray defined by that point and the lens center. Our approKimation is done by dividing the process into two steps. Figure 3 illustrates the cross-sectional view of the projection process sl iced by a plane which includes the central projecting ray and is perpendicular to x-z plane. The steps are as follows.

Fig. 2 Approximation of perspective transformation by 2-D Affine transformation

STEP 1: The (object) texel is projected onto the plane W which is parallel to the image plane and includes the mass center of the texel. This project ion is performed by using the rays which are parallel to the central projecting ra~· . (When the central projecting ray is perpendicular to plane W, this projection is the orthographic one. )

STEP 2: The image on the plane W is perspectively projected onto the image plano. Because plane W is parallel to the image plane, the perspective transformation under this projection is a simple reduction. The scaling factor is 1/d.

Now, we derive the 2-D transformation for teKel patterns under the projection in the above two steps. Let (p, q, 1) be the surface normal of the small plane on which an (object) texel is drawn (see Fig. 1). Let (P, Q, -1) be the direction of the central projecting ray. In order to represent the original pattern of the (object) texel, we use u-v-w coordinate system; its origin is the mass center of the texel and u-v plane is identical to the small plane. This means that the texel is drawn on u-v plane. In order to represent the image pattern projected on the plane W in the STEP 1, we use u'-v'-w' coordinate system; its origin is the same as that of u-v-w system and u', v', and w' axes are parallel to x, y, and z axes, respectively.

The 2-D transformation from (u, v) to (u', v') can be derived by combining the rotation of 3-D coordinate systems. The resultant 2-D Affine matrix T is obtained as

We use u"-v"-w" coordinate system to represent the pattern of the (image) texel; its origin is (P, Q, -1) in x-y-z system, mass center of the texel, and u", v", and w" axes are parallel to x, y, and z axes, respectively. The transformation by the STEP 2 is a simple reduction with scaling factor 1/d. From Eqs. (2-1) and (2-2), the transformation from (u, v) to (u", v") becomes

It must be noted that the relation represented by Eq. (2-3) is not the point-by-point projection but the are~-by-area one; it is the relation between two 2-D patterns, one is in 3-D space and the other is its image on the image plane.

3. VANISHING LINE OF OBJECT PLANE FROM AREAS OF TEXELS

In this chapter, using the relation of Eq. (2-3), we derive an interesting property with areas of texels under perspective projection. Then we propose a powerful scheme to obtain the vanishing line of a textural plane.

The vanishing line of a 3-D object plane is an important concept in perspective projection. lt is defined as the intersection of the image plane with a plane which includes the lens center and is parallel to the object plane. In Fig. 1, the equation of the vanishing line is given as px+qy·l. When the vanishing line is determined on the image plane, we can know the p and q of the surface normal of the object plane.

lt is well known that the determinant of a 2-D Affine matriK is equal to ratio of the areas of two patterns before and after the transformation. From Eqs. (2-2) and (2-1), we obtain

Then the determinant for the transformation of Eq. (2-3) becomes

Here, p, q, and c are the parameters of the object plane. Equation (3-2) means that the area of an (image) texel is inversely proportional to the cubic of the z coordinate of the mass center of the (object) texel.

Let h be the distance from the mass center, (P, Q), of the (image) texel to the vanishing line, px+qy·l. h is given as

Equation (3-3) shows that h is inversely proportional to d.

Now, we propose a simple method to obtain the vanishing line from the areas of texels. We assume that the texels in Fig. 4 are the perspect ive transformation of patterns drawn on a plane. We select an arbitrary pair of texels. Let 5 1 and 5 2 be the area of each texel. Let h 1 and h 2 be the distance from the mass center to the vanishing line (not obtained yet). Let f 1 and f 2 be the distances to the vanishing line measured along the line defined by the two mass centers. From simi lar triangles in Fig. 4, the relation h 1 th 2 -f 1 /f 2 holds. Using this relation with Eqs. (3-2) and (3-3), we obtain

When the areas and positions of a pair of texels ere known, we can determine one point on the vanishing line, a vanishing point, by using the relation of Eq. (3-4). In other words,. one vanishing point can be determined from an erbitrary pair of texels in the picture. When there are n texels, nc 2 vanishing points can be obtained and it is an easy tesk to fit a vanishing line to those points.

4. AN ALGORITHM TO SOLVE THE AFFINE MATRIX BETWEEN TWO PATIERNS

The method described in the previous section implicitly bases on an assumption. A pair of texels in the picture must be the projection of same patterns; i.e., the patterns can be overlapped by rotation and translation. When the method is appl ied to a texture which is constituted from more than two l<inds of texel patterns, the pair of texels should be examined to be satisfying the assumption.

As described in section 2, the distortion of a texel pattern under perspect ive projection can be approximated by 2-D Affine transformation. Then, a pair of texels whose patterns are originally same have patterns in which one is a 2-D Affine transformation of the other. Kender-Kanade [1980] call such pairs as Affine-transformable patterns. If we use their term, the pairs of texels used in the method of section 3 must be Affine-transformable patterns.

1'1 this section, we present an algorithm to solve the 2-D Affine matrix between an Affine-transformable pair of patterns. Tht~ key idea of this algor ithm is to use an ellipse as a guide to solve the Affine matrix. We call the ell ipse as A-Ellipse. A-Ellipse is an approximation of a pattern. It is defined as an ellipse whose covar iance matrix (2nd order moments around the mass center) is the same as that of tho pattern. When we lake u-v coordinate system whose origin is the mass center of a texel pattern as illustrated in Fig. 5, the covar iance matrix of this pattern is given es

Here, mij 's are the moments of the pattern defined by

The parameters of the A-Ellipse are &iven es

where, e 1 and e 2 are the eigenvalues of C and e 1 ~ e 2 .

Concernin& A-Ellipse and Affine transformation, there is an useful property as follows.

The A-£Ui.pse of the Affine transform4t<on of a pattern <s equal to the Aff<n· transformat<on of the A-£Ui.pse of a pattern.

This property assures that we can use A-Ellipse as a subst itute of the pattern to obtain ths Affine matrix between two patterns. By the substitution, of course, the information about rotation between two patterns is lost. It is neccessary to solve the rotational factor after the Affine matrix for two A-Ell ipses is solved.

Figure 6 illustrates the three steps of the algorithm to solve the Affine matrix between a pair of patterns, Pattern- 1 and Pattern-2. The three steps are as follows,

computed. An Affine matrix, A 1 (A 2 ), to transform the A-Ellipse onto a circle with unit radius is computed.

STEP 2: The contour of Pattern-1 (Pattern-2) and that of its A-Ellipse are transformed by A 1 (A 2 ). The sequence of angles which are determined by the intersections of the circumference with the transformed contour of Pattern-1 (Pattern-2) is computed.

STEP 3: An offset angle needed to make one sequence of angles m1tch to the other is determined. A rotation m1tr lx A 3 is computed for the offset anale. The Affine matrix A to transform Pattern-1 onto Pattern-2 is computed 1s A·A;} A 3 A 1 . By usina the matrix A, the contour of Pattern-1 is m1pped onto Pattern-2 to examine the exact m1tching.

When this algorithm is applied to a pair of patterns which are not Affine-transformable, the offset angle cannot be determined or the final matching does not succeed. So, by using this algorithm, it is possible to detect the pairs which are not Affine-transformable patterns.

Determination of the offset angles is a neccessary condition for Affine-transformable patterns. The A-Ellipse, however, provides a new feature to make a more powerful neccessary condition. We call this feature, DE-parameter. As shown in Fig. 7, the DE-perimeter is the un-overlapped area of a pattern and its A-Ellipse normalized with the area of pattern. Concerning DE-parameter and Affine transformation, the following property exist.

DE -p~U"Qmeter i1 itwcvi4nt to 2-D Affine tromformotion.

This property leads to a neccessary condition for Affine-transformable patterns.

If o poi.r of pottern1 eve AffinHromformobt. one1, their DE-por11meter1 nuut be identtc11L

This condition can be examined at the STEP 1 of the algorithm without costly computation. For almost pairs which are not Affine-transformable patterns, the condition saves the useless execution of STEP 2 and STEP 3.

The two neccessary conditions, derived from DE-parameter and sequence of angles, enable the algorithm to detect efficiently a p1ir of patterns which are not Affine-transformable ones.

5. EXPERIMENTS

We have applied the method so far de&cribed, to artificially generated textures.

Fiaure 8 shows a texture with circular texels. The surf ace normal of the 3-D object plane on which the texels are drawn was set to (0.36, 1.27, 1 ). There are 80 texels in Fig. 8. In order to avoid noisy vanishing points, only the pair of texels whose area ratio is greater than 1.5 was used to determine a vanishing point. As a result, 1515 vanishing points have been obtained. The vanishing points within the picture frame are dotted in the upper right corner of the frame. A line was fit to the set of vanishing points as the vanishing line. p and q obtained from the equation of the vanishing line are 0.36 and 1.26, respectively.

Figure 9 \~) is a texture which is constituted from five kinds of texel patterns. 80 texels exist in the picture. The surface normal of the 3-D object plane was set to (0.36, 0.61, 1).

Fia:. 9 (a) A texture· with five kinds of texels

The algorithm described in section 4 was used to examine whether a pair of texels have originally a same pattern in 3-D space. As a whole, 223 pairs were selected and used to determine vanishing points. p and q, thus obtained, are 0.36 and 0.61, respectively. Figure 9 (b) shows 1 front view of the object plane constructed from Fig. 9 (a) based on the p and q.

6. CONCLUDING REMARKS

We ~ave proposed a method to analyze the distortion of texel patterns under perspective projection by approximating the perspective transformation with 2-D Affine transformation. A result of the analysis was applied to obtain surface orientation of a texlural plane.

The method of the approximation combined with the algorithm to solve the 2-D Affine matrix provides a lot of cues for surface orientation under perspective projection. Further work is beina: done to obtain the orientation of a curved surface.

ACKNOWLEDGEMENT

The authors thank Takeo Kanade for having many stimulating discussions while he was working with us at Kyoto University.