Utilizing Moment Invariants and Gröbner Bases to Reason About Shapes

1 Introduction

Like many natural language terms, the intuitive notion of a shape is not easily captured by a formal definition that can be translated into a computer program. For example, in grammar school we learn that a triangle is a polygon with three sides, and this definition can be easily applied to recognize two triangles in Fig. 1. Yet, a com­ puter program that implements this definition needs to determine first what is a polygon, and what is a polygon side. This appears to be much harder.

·Research partially supported by NSF grant IRI-9309135

Janell Straach

The University of Texas at Dallas P. 0. Box 830688 Richardson, Texas 75083-0688 straach@utdallas.edu

The commonly accepted formal (mathematical) defi­ nition of a shape relates the shape to properties invari­ ant under a group of transformations. See Section 2. This formal definition is independent of a language that may be used to describe the shape. Section 2.1 describes the method of moment invariants [Hu, 1962; Reiss, 1991] that gives a technique for transforming simple shape de­ scriptions into a computer code. Unfortunately, this technique can only be applied to shapes that are com­ pletely characterized by a single instance, e.g., a triangle. In spite of its limitations the method of moment invari­ ants was successfully used in many pattern recognition and image processing situations. (See, e.g., [Hu, 1962; Li, 1992; Wong and Hall, 1978]).

In this paper we generalize the method of moment in­ variants and describe a techriique for computing invari­ ants of shapes given by logic formulae. We view these invariants as shape descriptors and show how to use them in reasoning tasks. Allowing shapes to be described in a language (logic in our case) enables handling shapes that cannot be characterized by a single instance. (An example is a shape described as being either a triangle or a rectangle.) Our technique can be applied to arbi­ trary monotone formulae (formulae in propositional logic without negation) .

When the method of moment invariants is applied in practice, approximate characterizations of simple shapes are computed from a small number of moment invari­ ants. A straightforward approach of combining these in­ variants according to the relations expressed by a short monotone formula may produce a new set of invari­ ants of size exponential in the original formula length. Many of these invariants may be redundant . As de­ scribed in Section 4, the redundancy can often be elim­ inated by representing the set of invariants as a re­ duced Grabner base [Becker and Weispfenning, 1993; Buchberger, 1985]. This representation allows decision problems related to shapes to be easily solved. (The Grabner base algorithm guarantees that these problems are solved in a finite number of steps.) Unfortunately, it is known that there can be cases where a reduced Grabner base may contain a huge number of such invari­ ants [Huynh, 1986], but experimental evidence ([Buch­ berger, 1985]) seems to indicate that this does not hap­ pen too often.

2 Preliminary definitions

We refer to subsets of the 2D Euclidean space as fig­ ures. Thus, the four connected black regions in Fig. 1 describe four figures. A figure can also be described by a characteristic function. The function f(x, y) is a char­ acteristic function if f ( x, y) = 1 for points in the figure, and f(x, y) = 0 for points not in the figure. For exam-

function of a circular disc of radius 1 centered at the origin.

Specifying a figure in terms of its characteristic func­ tion must be done with respect to a coordinate system. Therefore, a figure may (and usually does) change when a coordinate transformation is applied. A shape is a ge­ ometric property of a figure . Its formal definition (see, e.g., [Veblen and Whitehead, 1967]) is given in terms of properties invariant under a group of coordinate trans­ formations.

Definition: Let 'l1 be a group of coordinate transfor­ mations (e.g., translations and rotations). The function I is invariant with respect to 'l1 if

for all characteristic functions f ( x, y) and all transfor­ mations 'lj; E 'l!.

Examples: The area of a figure is invariant under trans­ lation and rotation but not under scaling. The number of polygon edges is invariant under translation, rotation, and scaling.

Definition: A shape of a figure is a pair (I, 'l!), where I is invariant under the group of coordinate transforma­ tions w.

The two most common group transformations in the def­ inition of shapes are translation rotation and scale (or­ thogonal transformations), and the general linear trans­ formation. For example, a triangle is defined with re­ spect to arbitrary linear transformations, but a right tri­ angle is defined only with respect to orthogonal trans­ formations.

2.1 A review of moment invariants

The classic technique for generating invariants in terms of algebraic moments was originally proposed by Hu [Hu, 1962] . The algebraic moments of the characteristic func­ tion f(x, y) are defined to be:

These can be approximated in the discrete case by:

A figure is uniquely determined by its algebraic moments [Hu, 1962]. Therefore, instead of looking for invariants of characteristic functions one can look for invariants of moments. In practical applications only invariants of low order moments are used. (The order of the moment mpq is defined to be p + q.) Moment invariants are usu­ ally specified in terms of centralized moments, i.e., the moments measured with respect to the "center of mass":

The above equations can be expanded to an explicit ex­ pression giving the centralized moments in terms of the ordinary moments:

The specific formulae for the moments up to second order are:

Hu derived two second order moments invariants for translation and rotation:

The centralized moments in Equation (3) can be replaced by normalized moments, 'f/pq, to produce invariants for translation, rotation, and scale. The normalized mo­ ments are computed from the centralized moments as follows:

The only moment invariant under general linear transfor­ mations that can be described in terms of second order moments is [Hu, 1962; Reiss, 1991]:

In summary, the classic method of moment invariants can be applied to geometric shapes defined in such a way that all their instances can be generated by geo­ metric transformations (e.g., translations, rotations, and rescaling) of a single instance. In such a case, moment invariants are computed by formulae such as those given in Equations (3) and ( 4), applied to the characteristic function of a single figure with the desired shape.

3 Invariants of shapes described in propositional logic

It is often necessary to deal with shapes that are more complex than the simple shapes of Section 2. Suppose we are given the following shape description:

Since triangles are polygons this can be simplified to:

This simplification cannot be obtained from purely geo­ metric knowledge because of the logic connectives. How­ ever, it cannot be obtained directly from logic since the fact that triangles are polygons requires geometric knowledge. We also observe that in this case it is im­ possible to calculate moment invariants from a single example shape since the moment invariants of a rectan­ gle clearly differ from those of a triangle. In this section we show how to calculate moment invariants of shapes described in propositional logic.

3.1 Moment invariants as a system of polynomial identities

The central idea that enables the generalization of mo­ ment invariants to complex shapes is that moment in­ variants can also be viewed as a system of polynomial identities among the moments. Thus, for example, the moment invariants in (3) can also be written as:

The above observation, the results of Hu [Hu, 1962] about the relation between moment invariants and alge­ braic invariants, and Hilbert Basis Theorem imply the following:

Theorem: Let f be a figure. There exists a finite set of polynomial identities (among moments) that hold only for figures obtained from f by: (a) translation and ro­ tation, (b) translation rotation and scale, (c) arbitrary linear transformations.

This suggests the following generalization of moment in­ variants:

Definition: Let P = {p1 , .. . , Pm} be a set of polyno­ mial identities among moments. We say that P charac­ terizes the shape 5 if only the figures with the shape 5 satisfy all the identities in P.

3.2 Shapes as formulae with logic connectives

Using logic connectives, shapes can be defined in an anal­ ogous way to formulae in propositional logic:

• (i) If 51 and 52 are shapes then a figure f has the shape (51) V (52 ) if it has the shape 51 or the shape 52 .
• (ii) If 51 and 52 are shapes then a figure f has the shape (51 ) 1\ (52 ) if it has the shape 51 and the shape 52 .
• (iii) If 5 is a shape then a figure f has the shape -,(5) if it does not have the shape 5.

Formulae in propositional logic created without rule (iii) are called monotone formulae. Many interesting concepts can be described by short monotone formulae [Valiant, 1984], but it is known that some short formu­ lae may become exponentially long when described as monotone formulae [Valiant, 1983].

The moment invariants (as a set of polynomial identi­ ties) of shapes described by monotone formulae can be computed as follows. Let P = {p1 , .. . ,Pm} be the mo­ ment invariants of 51 and let Q = { q1 , ... , Qn} be the moment invariants of 52 then:

• (i) the mo111ent invariants of (51) V (52 ) are {PiQj : i = 1, ... ,m, j=1, .. . ,n}
• (ii) the moment invariants of (51 ) 1\ (52 ) are P U Q.

This defines recursively shapes described by arbitrary monotone formulae .

4 The Grobner Basis of shape invariants

If the system of polynomial identities describing the shape 51 contains m identities and the system of polyno­ mial identities describing the shape 52 contains n iden­ tities, the technique of Section 3.2 produces only m + n polynomial identities for (51 ) 1\ (52 ), but there are mn polynomial identities for (5t)V(52 ). Therefore, the num­ ber of polynomial identities may grow exponentially in the size of the formula. Many of these invariants may be redundant; the redundancy can often be eliminated by representing the set of polynomial identities as a reduced Grobner base [Buchberger, 1985]. Although it is known that there are cases where the number of polynomials in the reduced Grobner base is super-exponential in the number of the original polynomials [Huynh; 1986], this does not happen too often in practice. Specifically, the Grobner basis technique was applied successfully in work on automatic theorem proving [Kapur, 1989] and robot motion planning [Cox et al., 1992]. Both applications involve similar expressions to the ones described here.

4.1 The Grobner basis algorithm

The Grobner basis algorithm is based on associating a fixed ordering on the moments (the variables of the poly­ nomial identities) and then applying reductions between polynomials. The most common orderings are lexico­ graphic and total degree. Buchberger's algorithm for the computation of a Grobner basis is based on two principal operations:

Reduction: the polynomial f can be reduced to h with respect to g if there is a constant c such that:

where c is specified as follows: Let a 9 be the leading monomial (with respect to the fixed ordering of vari­ ables) of g then there is a monomial a f of f such that a1 = c · a9 ·

S_Folynomial: The s_polynomial of h , h is defined to be:

where u 1 , u2 , c1 , c2 are determined from h, h as follows : Let a1 , a2 be the leading monomials of h, h respectively, then c1 , c2 are the coefficients of a1 , a2 . Let a be the least common multiplier of a 1 and a2 . The monomials u1 , u2 are given by: u1 = a/a1, u2 = a/a2.

Let P be a set of polynomial identities. (In our case these identities define a shape.) The following algorithm calculates GP, the Grobner basis of P.

• Start with G 0 = P
• Repeat while Gi -:p G i+l

Take Gi+ 1 to be the set containing the polynomi­ als in Gi and the s_polynomials of all pairs of polynomials in Gi.

• GP = Gi

For complete details of the algorithm and termina­ tion/ correctness proofs see [Becker and Weispfenning, 1993; Buchberger, 1985]. The efficiency of this algorithm can be greatly improved; it can also be modified to com­ pute a reduced Grobner basis . A reduced Grobner ba­ sis is a Grobner basis where each polynomial is reduced with respect to all other polynomials in the basis, and all leading coefficients are 1. In [Buchberger, 1985] it is shown that the reduced Grobner basis is unique. Ef­ ficient algorithms for computing the reduced Grobner basis can be found in [Becker and Weispfenning, 1993; Buchberger, 1985; Mishra and Yap, 1989].

It is known that the Grobner basis algorithm always terminates after a finite number of steps. Unfortunately, it has also been shown that the number of resulting ele­ ments (and therefore, the worst case complexity) can be super-exponential in the size of P [Huynh, 1986]. Effi­ cient implementations of the Grobner basis algorithm are available with many computer algebra software packages such as MATHEMATICA, REDUCE, and MAPLE.

4.2 Grobner basis representation and reasoning about shapes

Invariants can be used to determine if a figure has a par­ ticular shape. This section shows how to use the Grobner basis representation of shapes to solve in a finite num­ ber of steps many higher level decision problems related to shapes. The ideas presented here are closely related to work on automatic theorem proving [Chou, 1988; Kapur, 1989].

Let S and T be two shapes, and let g be a geometric property. Consider the following questions:

1. Do SandT describe the exact same shape?
2. Is the shape S more general than the shape T? (Does the knowledge that a figure is of shape T imply that it is of shape S?)
3. Are there any figures with the shape S?
4. Is a geometric property g implied by S? (Does the knowledge that a figure is of shape S imply that it has the geometric property g?)
5. Are there any figures with both shapes S and T?

When the shapes are described in terms of polynomial identities these decision problems (and many others) can be directly translated to computational techniques uti­ lizing the Grobner basis representation. See [Becker and Weispfenning, 1993; Buchberger, 1985; Mishra and Yap, 1989] . We sketch the solution for the first four problems. Let as,ar,G(SuT), and G(SUg} be the reduced Grobner bases of the polynomial identities describing S, T, S U T, and S U {g} respectively.

1. S and T describe the exact same shape if and only if Gs=Gr.
2. sis more general than T if and only if as = G(SUT} .
3. There are no figures with the shape S if and only if 1 E as.
4. Being of shape S implies the geometric property g if and only if as= G(Sug) .

5 The vocabulary of low order moment invariants

In practical applications few invariants of low order are used (see, e.g.,[Hu, 1962; Li, 1992; Wong and Hall, 1978]). In this section we characterize the representa­ tion power of low order moment invariants and compute second order moment identities for several shapes and geometric properties.

5.1 Representation power of low order moment invariants

Let W be a group of transformations. Let Jk be the set of moment invariants (w.r.t. w) that can be computed from moments of order bounded by k. From the remarks in Section 3.1 it follows that ! 00 , the entire set of mo­ ment invariants, completely characterizes a shape with respect to translation and rotation. Specifically, for any two figures A, B there exists a transformation involving translation and rotation that transforms A to B if and only if i(A) = i(B) for all moment invariants i E [ 00 ·

Even though ! 00 is finite (as implied by the Hilbert Ba­ sis Theorem), invariants involving high order moments may be very complex and unstable. Most practical ap­ plications use 1 2 or ! 3 to approximate shapes. Clearly, for a small constant k the invariants in Jk cannot com­ pletely characterize shapes. Our goal is to show that they completely characterize well defined least squares approximations of shapes.

Let A be a figure and let f A(x, y) be its characteristic function. Let p~ (x, y) be a polynomial (in x, y) of total degree k that approximates fA by minimizing the least squares error:

The polynomial p~ is known to be uniquely determined from k and fA·

Theorem: Let A, B be two figures. Let Jk be the set of moment invariants with respect to a group of trans­ formations 'l1 that can be computed from moments of order bounded by k. Let p~, p~ be the least squares polynomial approximations to A, B respectively. Then:

• (i) If there is a transformation '1/J E 'l1 such that '1/J(p~) = p~ then i(A) = i(B) for all i E Jk .
• (ii) If i(A) = i(B) for all i E Jk, and 'l1 is the group of translations and rotations, or the group of transla­ tions rotations and scale, then there exists a trans­ formation '1/J E 'l1 such that '1/J(p~) = p~.

Proof:

To keep notation tidy we write Mk(g) for the moments of degree bounded by k of a function g, and Jk(g) for the moment invariants of g that can be expressed in terms of Mk(g). We need the following known facts from the theory of least squares approximations:

Fact 1: If pis a least squares polynomial approximating a function f and a;jxiyj is a monomial of p, then the m;j moments of p and f are identical. (Proof: since the derivative of the error E in Equation (5) with respect to a;j vanishes, we have l:x,y(f- p)xiyj = 0, so that " fxiyj = " pxiyj.) 0x,y L.x,y

Fact 2: Let p, q be two polynomials of total degree k.

(Proof sketch: the polynomials of total degree k form a vector space, and the moments of order bounded by k are known to be a basis.)

Lemma: If '1/J is a linear transformation then for any figure A,

Proof:

Since '1/J is linear, '1/J(p~) is a polynomial of total degree k and the proof is completed by applying Fact 2 to the above equality.

Proof of Part (i): We need to show that Jk(A) = Jk(B). From Fact 1 we have: Mk(B) = Mk(p~) and since p~ = 'lj!(p~) we have Mk(B) = Mk('lj!(p~)). There­ fore, Jk(B) = Jk('lj!(p~)). From similar arguments we have Jk(A) = Jk(p~) and to prove Part (i) it remains to show that Jk(p~) = Jk('l/!(p~)). This is true because by definition the expressions in Jk are invariant under '1/J E 'l!.

Proof of Part (ii): Hu [Hu, 1962] shows how to "nor­ malize" a figure with respect to translation and rotation,

or translations rotations and scale. The normalization of a figure A is achieved by translating and rotating A to obtain A such that

Normalization with respect to scale is achieved by apply­ ing scaling to A so that m00(A) = 1. Hu also shows that the moments of degree bounded by k of the normalized figure A uniquely determine its moment invariants and vice versa. In our notation this fact can be expressed as:

To prove Part (ii) let A, B be the normalizations of A, B with

We prove that p~ = ('l/!1 1 '1/J2)P~·

0

5.2 What can be characterized by second order moment invariants

The theorem in the previous section describes exactly how different shapes need to be so that they would have different finite order moment invariants. In this section we consider shapes that can be classified using invariants from ! 2 .

Once a particular figure is given, we can compute its second order moments by using Equation (1), compute the centralized moments from Equation (2), and com­ pute the following four numbers:

From the work of Hu [Hu, 1962] (see also [Reiss, 1991]) it follows that the following is a complete set of alge­ braically independent invariant polynomials under trans­ lation and rotation for moments up to the second order:

By normalizing (6) with respect to size (see Section 2.1), the following forms a complete set of second order mo­ ment invariants under translation, rotation, and scale [Hu, 1962; Reiss, 1991]:

Under a general linear transformation, the following in­ variant is the complete set of polynomial identities (up to second order) [Hu, 1962; Reiss, 1991]:

A figure has n-fold rotational symmetry if rotating it by 21r jn radians around its center leaves it unchanged. The property of 4-fold rotational symmetry can be char­ acterized by second order moment invariants as follows:

Equation (9) follows from the fact that normalized fig­ ures with 4-fold rotational symmetry must have m2o = m02 . Since they also have m11 = 0 it follows from Equa­ tion (6) that ! 2 = 0.

5.3 Moment Identities of specific shapes and properties

In this section moment identities are computed for sev­ eral shapes. They are based on moment values of the specific black figures shown on the left, which were com­ puted via Equation (1) (using definite integration).

.. A triangle is invariant under general linear transformations. Therefore, it can be characterized in terms of the polynomial in (8). Computing the value of Is for the triangle figure on the left gives Is = 1~8 . Thus, The least squares approximation of a triangle by a polynomial of total degree two is characterized by the following moment identity:

~ Since the shape of a right triangle is invariant under translation, rotation, and scale, it can be char­ acterized in terms of the polynomial identities in (7). Computing the value of ! 1, ! 2 for the right triangle on the left gives 11 = ~, 12 = 8 1 ~. Thus, the least squares approximation of a right triangle by a polynomial of to­ tal degree two is characterized by the following moment identities:

.. A rectangle (actually a quadrilateral) is in­ variant under general linear transformations. It can be characterized in terms of the polynomial in (8). Com­ puting the value of ! 3 for the rectangle on the left gives ! 3 = 1 1 4 . Hence, a least squares approximation of a rectangfe (quadrilateral) by a polynomial of total degree two is given by the following moment identity:

A square is invariant under translation rotation and scale. Therefore, it can be characterized in terms of the polynomials in (7). Computing the value of h, h for the square on the left gives 11 = i, ! 2 = 0. Thus, the least squares approximation of a square by a polynomial of total degree two is given by the following moment identities:

.. OR This shape is described as being a rectangle OR a square, and can be characterized by using Equation (12) for a rectangle, Equations (13) for a square, and applying the rules of section 3.2. This gives the following set of moment identities:

We show in the next section that these identities can be reduced to the identity of a rectangle by using the Grabner basis technique.

AREA. The area of a shape is invariant under trans­ lation and rotation, and is characterized by ! 0 . For ex­ ample, a shape having an area of 10 is characterized by the following moment identity:

ROTATIONAL SYMMETRY. The characteriza­ tion of 4-fold rotational symmetry by Equation 9 gives the following identity:

6 Examples utilizing the Grobner basis representation

The identities from the previous section are now used to describe examples of the Grabner basis algorithmic ap­ proach to reasoning about shapes, as described in Sec­ tion 4.2. Unless otherwise stated, a reference to a shape in this section is to be understood as a reference to a least squares approximation of the shape with a polyno­ mial of total degree 2. The examples here correspond to the problems outlined in Section 4.2.

To show that a rectangle with 4-fold rotational symmetry is a square we verify that the reduced Grabner basis of identities (14),(12) is the same as the reduced Grabner basis of (13).

To show that a rectangle is more general than a square we show that the reduced Grabner basis of (12) is the same as the reduced Grabner basis created from the iden­ tities (12),(13).

To show that there exists a rectangle of size 30 with 4fold rotational symmetry we compute the Grabner basis of the identities in equations (14),(12) with the addi­ tional equation J.Loo = 30. Since the Grabner basis does not contain 1, such a shape exists.

To show that a square has 4-fold rotational we need to show that the reduced Grabner basis of the identities in (14),(13) is the same as the Grabner basis of the iden­ tities in (13).

To show that there are no right triangles of size 10 with 4-fold rotational symmetry we show the Grabner basis of the identities in equations (14),(10), with the additional equation t-too = 10 reduces to 1.

To show that the shape described as:

(rectangle AND 4-fold rotational symmetry) OR square

reduces to a square, we build the moment identities fol­ lowing the procedure of Section 3.2 and show the reduced Grabner basis to be the identities of a square.

7 Concluding remarks

A simple generalization of the idea of moment invari­ ants enables computing moment invariants of shapes de­ scribed by formulae in propositional logic. Our tech­ nique is limited to monotone formulae. The representa­ tion power of low order moment invariants was shown to be directly related to least squares approximations of figures by polynomials of low degree.

The representation of invariants in a Grabner basis en­ ables reasoning about shapes in a way similar to geomet­ ric theorem proving techniques. The advantage of our technique over geometric theorem proving (e.g., [Chou, 1988; Kapur, 1989]) is that in our technique there is no need to explicitly describe the basic shapes. Instead, their description is extracted automatically in terms of moments. For example, a theorem prover can easily de­ duce that a square is a special case of a rectangle if it is given the definition of a square as a rectangle with even sides. Our technique does not require this information.

The fact that our technique uses finite measurements (moments) means that positive conclusions (e.g., the given figure is a rectangle) can only be verified for least squares approximations of the figure. On the other hand, negative conclusions (e.g., the given figure is not a rect­ angle) is verified with certainty.