Solving the recognition problem for six lines using the Dixon resultant

The "Six-line Problem" arises in computer vision and in the automated analy sis of images. Given a three-dimensional (3D) object, one extracts geometri c features (for example six lines) and then, via techniques from algebraic geometry and geometric invariant theory, produces a set of 3D invariants th at represents that feature set. Suppose that later an object is encountered in an image (for example, a photograph taken by a camera modeled by standa rd perspective projection, i.e. a "pinhole" camera), and suppose further th at six lines are extracted from the object appearing in the image. The prob lem is to decide if the object in the image is the original 3D object. To a nswer this question two-dimensional (2D) invariants are computed from the l ines in the image. One can show that conditions for geometric consistency b etween the 3D object features and the 2D image features can be expressed as a set of polynomial equations in the combined set of two- and three-dimens ional invariants. The object in the image is geometrically consistent with the original object if the set of equations has a solution. One well known method to attack such sets of equations is with resultants. Unfortunately, the size and complexity of this problem made it appear overwhelming until r ecently. This paper will describe a solution obtained using our own Variant of the Cayley-Dixon-Kapur-Saxena-Yang resultant. There is reason to believ e that the resultant technique we employ here may solve other complex polyn omial systems. (C) 1999 IMACS/Elsevier Science B.V. All rights reserved.