Premium
Utilizing Moment Invariants and Gröbner Bases to Reason About Shapes
Author(s) -
Schweitzer Haim,
Straach Janell
Publication year - 1998
Publication title -
computational intelligence
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
ISBN - 1-55860-363-8
DOI - 10.1111/0824-7935.00072
Subject(s) - mathematics , invariant (physics) , monotone polygon , shape analysis (program analysis) , simple (philosophy) , representation (politics) , algebra over a field , algorithm , pure mathematics , geometry , computer science , static analysis , philosophy , epistemology , politics , political science , law , mathematical physics , programming language
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 formulas 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 1960s. We generalize this technique to shapes described by arbitrary monotone formulas (formulas in propositional logic without negation). Our technique produces a reduced Gröbner basisfor 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 specifying a shape. Unlike geometry theorem proving, our approach does not require the shapes to be explicitly defined. Instead, logic formulas 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.