We consider the problem of analytically characterizing the set of all
2-D images that a group of 3-D features may produce, and demonstrate t
hat this is a useful thing to do. Our results apply for simple point f
eatures and point features with associated orientation vectors when we
model projection as a 3-D to 2-D affine transformation. We show how t
o represent the set of images that a group of 3-D points produces with
two lines (1-D subspaces), one in each of two orthogonal, high-dimens
ional spaces, where a single image group corresponds to one point in e
ach space. The images of groups of oriented point features can be repr
esented by a 2-D hyperbolic surface in a single high-dimensional space
. The problem of matching an image to models is essentially reduced to
the problem of matching a point to simple geometric structures. Moreo
ver, we show that these are the simplest and lowest dimensional repres
entations possible for these cases. We demonstrate the value of this w
ay of approaching matching by applying our results to a variety of vis
ion problems. In particular, we use this result to build a space-effic
ient indexing system that performs 3-D to 2-D matching by table lookup
. This system is analytically built and accessed, accounts for the eff
ects of sensing error, and is tested on real images. We also derive ne
w results concerning the existence of invariants and non-accidental pr
operties in this domain. Finally, we show that oriented points present
unexpected difficulties: indexing requires fundamentally more space w
ith oriented than with simple points, we must use more images in a mot
ion sequence to determine the affine structure of oriented points, and
the linear combinations result does not hold for oriented points.