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

Abstract

Shapes such as triangles or rectangles can be defined in terms of geometric properties invariant under a group of transformations. Complex shapes can be described by logic formulae with simpler shapes as the atoms. A standard technique for computing invariant properties of simple shapes is the method of moment invariants, known since the early sixties. We generalize this technique to shapes described by arbitrary monotone formulae (formulae in propositional logic without negation). Our technique produces a reduced Grabner basis for approximate shape descriptions. We show how to use this representation to solve decision problems related to shapes. Examples include determining if a figure has a particular shape, if one description of a shape is more general than another, and whether a specific geometric property is really necessary for characterizing a shape. Unlike geometry theorem proving, our approach does not require the shapes to be explicitly defined . Instead, logic formulae combined with measurements performed on actual shape instances are used to compute well characterized least squares approximations to the shapes. Our results provide a proof that decision problems stated in terms of these approximations can be solved in a finite number of steps.