Algorithms for the recognition of 2D images of m points and n lines in 3D

摘要

Let α be an ordered collection consisting of m points and n lines, m+n≥6, in three-dimensional space. Let β be an ordered collection consisting of m points and n lines, m+n≥6, in two-dimensional space. Using α and β, we construct a matrix M(α,β) and, then, give two algorithms for determining whether β is an image of α taken with a pinhole camera. These algorithms apply to any configuration, degenerate or not, consisting of points and lines. The first algorithm depends on the calculation of the nullspace of M(α,β) and gives necessary and sufficient conditions for β to be an image of α, if the data can be read exactly. The second algorithm depends only on the rank of M(α,β) and can be used if errors arise in reading the data; this algorithm also gives equations which any image of α must satisfy. In the special case m+n=6, there is a single equation J(α,β)=0 which must hold if β is an image of α. We show that J(α,β) is simply the determinant of M(α,β). We conclude with a discussion of some computational aspects of the theory.