Pose characterization by independent moment-based image features

RWC - Technical Report

Pose characterization by independent moment-based image features of planar objects
Huseyin Hakan Yakal , Leo Dorst and Ben Krose

RWCP Novel Functions: SNN Laboratory Faculty of Mathematics and Computer Science, University of Amsterdam Kruislaan 403, 1098 SJ, Amsterdam, The Netherlands. e-mail: yakali@fwi.uva.nl
For a unique characterization of the relative position between a 2-D planar object (target) and a camera, the following two mappings have to be singlevalued: mapping from the relative position to the image plane and from the image plane to the feature domain. We consider only white planar targets located in a black background and designed a special target which allows a unique perspective from any relative position. From the image of this target, the 6 relative position and orientation parameters can be characterized by means of 6 independent features. We use moments to extract these features and choose the proper representation to make them independent.

Abstract

1 Introduction
Characterization of the position and orientation of a camera relative to an object based only on the image features has wide application in the robotics eld. This is done in two steps: rst, the relative position is converted in to the image and, then, a set of independent features are selected from the image. In order for a unique characterization, both of these steps have to be single valued mappings. Solution to this problem depends on the set of features that are being used to characterize the relative pose. Determination of the relative position and orientation parameters with respect to an external coordinate system is the well known exterior orientation problem in the photogrammetry and stereo vision literature 1]. All the solutions presented, however, use a set of points as the features, provided that the correct point correspondence is established. It has been shown that three points give up to 8 solutions to this problem. Assuming that the camera is always located at the same side of the planar surface where the points are located, the number of solutions can be reduced to 4. Four points on a plane (non-three of which are collinear) gives a unique solution to the exterior orientation problem 3]. However, in order to obtain that unique solution, the 4-point-correspondence needs to be established explicitly between the imaged and the actual target points. This correspondence has to be established externally initially, but it can be maintained afterwards by keeping track of the the points. Note that tracking algorithms may restrict the motion of the camera to satisfy the assumptions that is based on. Using other features may eliminate some of these problems that are inherent in point-based features. For the use of other features, we rst need to design a target with a unique view. We focused our attention to planar white polygons located in the black 1

RWC - Technical Report background and their binary images. The projection from the target onto the image is a perspective transformation with 6 unknown parameters. We desire to design the target in such a way that all can be characterized from the image of the target, without additional information and without degeneracies or ambiguities. The detailed reasoning and the resulting target design are new. Dimensionality reduction from image to feature domain is done by means of using moment based image descriptors. In order to characterize the relative pose, we need 6 independent moment based image descriptors. We are interested in using lower order moments because of the computational load and the noise sensitivity 5] issues . We rst want to nd a 6 independent moment based feature. If we see however that these 6 features are derived from 6 moments, we prefer to use moments directly instead. The detailed reasoning for selecting the proper moment set is also presented. The target design is described in section 2. Moment-based visual features and the problems regarding using them are addressed in sections 3. In order to solve these problem, we investigated using Legendre moments and moment invariants in sections 4 and 5, respectively. Finally, we suggest a method for selecting the proper moment set and present our conclusions.

2 Target Design
As stated, we focused our attention on planar white polygons located in the black background and their binary images. Therefore, the problem becomes the determination of the number of the sides or the points which forms the target. From the results of the exterior orientation problem, we know that four points on a plane (non-three of which are collinear) gives a unique solution to this problem 3]. In order to void the point correspondence requirement, we organized the points to form a concave shape (Fig. 1a) (since convexity is preserved under perspective transformation 4]). However, when both sides of the target plane are considered, this 4-point polygon will not su ce. In order to disambiguate the two sides of the target plane, a fth point is added such that line L25 intersect with line L34 (Fig. 1b), another projectively invariant construction. This 5-point polygon has a unique view from the either side of the target because it has su cient complexity to establish point correspondence by itself. As a result, every view of the target characterizes a unique perspective transformation. The nal shape of the target is shown in Fig. 1c.
1 a b 54 L 3 34L25 2 c

Figure 1: Target objects with enough complexity.

3 Moment-Based Visual Features
In order to use moment based visual features for characterizing the relative pose, the mapping from the image domain to the momenta domain has to be a single valued mapping. This is satis ed by the uniqueness theorem of the momenta 2]. This theorem states that the momenta sequence mpq is uniquely determined by the density distribution function, i.e., the image of the target in our case. Since the 2

RWC - Technical Report designed target has a unique view from every relative pose, it has a unique momenta sequence for every view. In order to characterize 6 perspective transformation parameters, we need 6 independent moment or moment-based terms. It is desired that the features are computed from the lowest order moments to reduce the noise sensitivity and the required computing power. The standard and central geometric moments are de ned by:

mpq =

XX
x y

xp yq (x; y); p; q = 0; 1; 2; :::
00 00

(1) (2) (3)

pq

=

XX
x y

(x ? x)p (y ? y)q (x; y); p; q = 0; 1; 2; :::

m m x = m10 y = m01

where, mpq and pq are the standard and central moments, (x,y) is the center of gravity of the imaged target object, and (x; y) is the imaged target de ned as: (x; y) = 0 outside the target boundaries, (4) 1 otherwise The relation between the standard and the central moments is also given below: 00 = m00 = 2 20 = m20 ? x 11 = m11 ? xy 2 02 = m02 ? y (5) 3 30 = m30 ? 3m20 x + 2 x 2y 21 = m21 ? m20 y ? 2m11 x + 2 x 2 12 = m12 ? m02 x ? 2m11 y + 2 y x 3 03 = m03 ? 3m02 y + 2 y Next, we will discuss the meaning of some of the moment terms. Zeroth order moment gives the size of the target in the image plane. The rst order moments, together with the zeroth order, gives the center of gravity of the target. The location of the target can be characterized with this coordinate. The second order moments gives us the distribution of the target. They approximate target by an ellipse and they have some nice properties. Using the second order moments, the minimum and maximum radii of the ellipse can be calculated. They are the Eigen values of the following matrix:
20 11 11 02

(6)

The rotation angle between the x-axis and the closest (minor or major) axis of the ellipse can be calculated from: 2 11 1 (7) = 2 arctan 20 ? 02 The range of the orientation measurement is ?45; 45]. Since the target is approximated as an ellipse, this is expected. For a unique orientation determination we also need the following conditions: if 020 > 002 and 030 > 0 (8) 3

RWC - Technical Report
y Y
2 1

X

(x; y)
x

Figure 2: Image plane and the view of the target object. where 0 represents the moments with respect to the principal axes. In Figure 2, the principal axes are denoted by X and Y . Note that, since the image of the target is approximated as an ellipse, 20 + 02 , called spread, gives the size information similar to 00 . Another commonly used feature in pattern recognition is the slenderness and given as p ( 20 ? 02 )2 + 4 11 . Third order moments are rarely used for characterizing the image, mainly because of the computational and noise considerations. The orientation of the image of a target can also be computed using these moment terms: = arctan 2 (
21

+

30

;

30

+

12

)

(9)

Another property of the third order moments is that they can form an absolute orthogonal set which will be described later. Next, we will try to devise a method for selecting a feature set for characterizing the relative pose. Since the center of gravity determines the location of the image of the target, there is no doubt about the independence of this information. Therefore we would like isolate them as the rst step. Now, consider all the cases where the coordinates of the center of gravity of the imaged target is xed. In other words the camera is xated on the center of gravity of the imaged target at a predetermined image location. As the second step we also assume that the relative roll rotation between the image of the target and the image coordinate system is xed (let us ignore how we do it for the time being). As a result, there are only 3 degree-offreedom (dof) motion left: relative orientation (pitch and yaw) and depth. Next, we consider all the positions which have the same 00 (area). The result is a smooth two dimensional surface around the target. In order to determine a location on this surface, we need two features. Since second order moments approximates the target as an ellipsoid, there could be up to four positions which would give the same second order moment terms. Hence, we need features with higher order moment terms. Considering the noise issues, the third order moments are the natural choice. One of the problems that we have not yet addressed in this section is how to determine the side that the target is viewed from. The target that designed earlier has su cient complexity to indicate the viewed side as well. When either side of the plane on which the target is located is considered, the number of solutions found by the second order moments will double. However, the skew-invariant, a third order moment based invariant derived by Hu 2], can detect the viewed side of the target. We will also look into using moment invariants as features as well.

4

RWC - Technical Report

4 Legendre Moments
Since it is undesirable (due to noise and computational load) to use third order moments, we investigated using 6 independent Legendre moments up to the second order. The Legendre moments are based on the Legendre polynomials hence are orthogonal by de nition. Thus, any 6 Legendre moments should characterize the 6 parameters uniquely. The relation between the Legendre and the geometric moments is de ned as: 3 5 1 l00 = 4 m00 l10 = 4 m10 l20 = 8 (3m20 ? m00 )
3 9 l01 = 4 m01 l11 = 4 m11 5 l02 = 8 (3m02 ? m00 )

(10)

However, for the use of the Legendre moments we are faced with following paradox: even though they are independent (because orthogonal) the Legendre moments can not uniquely distinguish targets with di erent roll rotations. We illustrate this on the following situation. The camera image plane is kept parallel to the target plane and the center of image coordinate system is aligned with the center of gravity of the target. The Legendre and the centralized geometric moments are plotted for the roll rotation of the target about its center of gravity. Note that, for this motion, the area (or the zeroth order moment) is a constant and the rst order moments are zero.
x 10 10 5 0 ?5
?3

Second order central moments vs. Roll rotation angle.

?150

?100

?50

0

50

100

150

Second order Legendre moments vs. Roll rotation angle. 0.02 0.01 0 ?0.01 ?0.02

?150

?100

?50

0 50 Roll rotation angle

100

150

Figure 3: Centralized second order moments and the Legendre moments for a roll rotation of
the target.

As can be seen from the plots, all the second order moments, both the Legendre and the geometric moments, are periodic. Note that both of the moment features for the roll angle of and + 180 are identical. This also follows from Eq. 10. Since the relation between the geometric and the Legendre moments is a linear one, all the limitations that are true for the geometric moments are also applicable to the Legendre moments. We thus fail in trying to avoid the use of 3rd order moments: higher order moments are necessary to obtain a 6 independent moment terms.

5 Moment Invariants
The moment invariants of Hu 2] are yet another alternative as features since they are also orthogonal. They are invariant under only linear transformations, such as 5

RWC - Technical Report scale, translation and rotation, and they will vary under the nonlinear perspective transformation. The method of principal axes described by Hu gives the rotational relations among the same order moments terms. Using this expressions, a moment set can be rotated about its center of gravity. One of the third order moment-based expressions can be used for determining the orientation angle of the target uniquely, namely: (
0 30

+

0 12

) ? i(

0 21

+

0 03

) = ei (

30

+

12

) ? i(

21

+

03

)

(11)

where 0pq is the (p + q)th order principal moment. Eq. 9 follows from this expression. Hu also gives a list of rotation invariant combinations of moments which could be used to re ne some of the other relative pose parameters. Let us de ne the following variables which makes writing these invariants easier: = x =
x x

+ 12 30 ? 3 12
30

= 21 + 03 y = 3 21 ? 03
y

(12) (13)

and y are called the imbalance along x and y axes, respectively. The orthogonal moment invariants proposed by Hu are listed below: (1) (2) (3) (4) (5) (6) (7) = 20 + 02 = ( 20 ? 02 )2 + 4 2 11 2 2 = x+ y 2 2 = x+ y 2 2 2 2 = x x ( x ? 3 y ) + y y (3 x ? y ) 2 2 = ( 20 ? 02 )( x ? y ) + 2 x y 11 2 2 2 2 = y x ( x ? 3 y ) ? x y (3 x ? y ) (14) (15) (16) (17) (18) (19) (20)

The seventh invariant (7) is the skew invariant which can distinguish the mirror images of the target. For comparison, the rotation angle computed from x and y is also plotted ( Fig.4) for the case described in Legendre section. The same plot also shows the skew invariant( (7)).
Rotation discrimination moments invariants. 0.1 0.05 0 ?0.05 ?0.1 ?150 ?100 ?50 0 50 Roll rotation angle Skew invariant. 100 100 150

50

0 ?200

?150

?100

?50

0 50 Roll rotation angle

100

150

200

Figure 4: x ,
of the target.

y

and (7) are shown for the case described in Legendre section for a roll rotation

6

RWC - Technical Report

6 The Choice of Features
In this section we will give the reasoning for choosing the proper moment terms for characterizing the image of the target. As explained earlier, by xing the area, the relative roll rotation and the center of gravity of the imaged target, we can form a surface around the target. We need two features to specify a point on this surface. Since we prefer to use 3rd order moments, we can use any pair from (3), (4), (5) and (7). In our case, we choose to use (5) and (7) moment invariants for this purpose. At this point, we have the following feature vector: Area : Center of gravity along : Center of gravity along : Roll orientation : A moment invariants : Skew invariant :

f1 = 00 f2 = x f3 = y f4 = f5 = (5) f6 = (7)

As mentioned earlier, we prefer to use raw data when possible. Hence, for computing the relative roll rotation, we need 2 features: x and y . We replace with x and add another feature y . This makes total of seven features. Note that the moment invariants we are using are size variant and hence eliminates the need for the area as the feature. As a result we can use the following feature vector: Center of gravity along x : Center of gravity along y : Imbalance along x : Imbalance along y : A moment invariants : Skew invariant :

f1 = x f2 = y f3 = x f4 = y f5 = (5) f6 = (7)

The relative orientation is computed with respect to a coordinate system which is determined by the moment terms. In order for this feature vector to be comparable to the feature vectors from di erent locations, it is important that the coordinate system derived by the moments aligns always with the same part of the image of the target, for instance, with the extended part. This is tricky: since projective transformations can distort the shape severely, such a coordinate system is not projectively invariant. This is a fundamental problem that is just as unresolved in terms of moment invariants. Therefore we decide to use the 3rd order moments on which f3, f4 , f5 and f6 are based instead. Center of gravity for x axis : Center of gravity for y axis : Third order moment : Third order moment : Third order moment : Third order moment :

f1 = x f2 = y f3 = 30 f4 = 21 f5 = 12 f6 = 03

The correct alignment of the coordinate system with the target is still an open issue.

7 Conclusion
We investigated how to characterize the relative pose parameters from a set of image features. In order to achieve this goal, we rst design a target with a unique 7

RWC - Technical Report view from any relative position. Then, moments are used to obtain a set of image features. We have designed a target which has su cient complexity to establish the point correspondence by itself. It has a unique view from any relative position, hence enabling the use of global image descriptors such as moments. Use of global descriptors, such as moments, are convenient to use from the image processing point of view since it only requires computational power which is abundant these days. However, the problem rises from the selection of the geometric moment set or how to interpret the moment information. In order to characterize 6 relative pose parameters, we need 6 independent moment-based image descriptors. One can resort to experimental methods such as singular value decomposition to determine the linear dependencies in the moment sequence. However, non-linear dependencies will not be identi ed by this method. At rst, the Legendre moments seem to be natural way to select a set of independent moments because of their orthogonality. However, our investigation concluded that the rst six Legendre (0 to 2nd order) moments can not be used for determining the relative pose parameters. The moment invariants may o er a solution to this problem, due to their absolute orthogonality. However, it needs to be determined whether the principal axis on which the principal moments are de ned is always aligned with the same part of the target, an as yet unsolved problem. Nevertheless, they show that the third order moments can form an absolute orthogonal set. As a result we have decided to use all the third order moment terms as the features. The non-unique alignment of the coordinate system can be resolved by determining the corner points of the target and aligning the target with the correct part of the target. At rst this seems like a contradiction to our earlier statement in Introduction (about not wanting to keep track of the point correspondence). However, since the target has su cient features to establish the point correspondence by itself, it does not require tracking of these points and no extra information needs to be transferred. This solution of correspondence not quite satisfying. Currently, we are trying to extend Hu directly to projectively invariant combinations of moments.

References

1] B.K.P Horn. Robot Vision. MIT Press, Cambridge, Massachusetts, 1986. 2] Ming-Kuei Hu. Visual pattern recognition by moment invariants. IRE Transactions on Information Theory, 50:179{187, 1962. 3] Yubin Hung, Pen-Shu Yeh, and David Harwood. Passive ranging to known planar point sets. Technical Report CAR-TR-65, CS-TR-1408, Center for Automation Research, June 1984. 4] Z. Pizlo, A. Rosenfeld, and I. Weiss. The geometry of visual space: About the incompatibility between science and mathematics. Computer Vision and Image Understanding, Jan. 1997. in press. 5] Cho-Huak Teh and Roland T. Chin. On image analysis by the methods of moments. IEEE Transactions on PAMI, 10(4):496{513, 1988.

8