hree 
jusly 
uted 
juent 
ihich 
been 
ming 
ject 
ption 
ated 
rrain 
the 
n the 
je of 
mine 
also 
mine 
/ious 
only 
the 
don’t 
es in 
t will 
een 
ned 
y Fit, 
Itiple 
nera 
| the 
the 
dels 
je is 
nate 
high 
Irces 
esa 
uss- 
near 
are 
10t0- 
d for 
own 
a Of 
d 3) 
tage 
Based on results received from GE's Simulation and 
Control Systems Department (SCSD), which builds 
databases for their COMPU-SCENE line of CIGs, 
PolyFit provides a 10 to 1 speed improvement over 
previous manual methods. The database for which 
SCSD employed PolyFit was later used to 
demonstrate the performance of their COMPU- 
SCENE VI CIG at the Interservice/Industry Training 
Systems Conference held in Orlando, Florida in 
early November of 1990. 
In addition to using the database as input to a CIG, 
further exploitation of the data can be achieved 
through PolyFit's mensuration capabilities. This 
facility allows the operator to query the database 
interactively to extract geometric information useful 
for applications such as mission planning. For 
example, one could request the distance between 
buildings or the height of a window from the ground. 
A future enhancement will perform reasoning on the 
data to compute, for example, the least detectable 
path in moving from point A to point B, given the 
location of likely sentry positions. 
3.0 THE SOLVER 
The essence of PolyFit is to rely on the human to 
surmise the general layout of the scene and to 
designate within the images the locations of the 
scene features, functions for which a human is 
extremely adept, while the computer solves a least 
square error optimization to recover the scene 
geometry with high accuracy, a function best 
performed by the computer. This section describes 
the latter component, the PolyFit solver, which 
simultaneously computes the camera parameters 
and scene geometry based on the principle of 
maximum likelihood, treating the measurements of 
the human user as noisy observations. 
The inputs to the solver are the scene topology, 
scene geometric constraints, and for one or more 
images, a list of designated vertex positions in the 
images. The positions and focal lengths of the 
cameras are generally unknown. The problem is to 
recover the scene geometry from the positions of 
features in the images. 
3.1 Scene Model 
The scene model consists of some number of 
objects. The position of each object is represented 
by a coordinate frame consisting of a rotation matrix 
and translation vector. Objects themselves are 
modeled as a constrained polygonal mesh, 
consisting of vertices, lines, and planar faces. The 
polygonal mesh represents the visible side of object 
surfaces. Each object consists of a number of 
vertices: vj, i2 1,...n (3-D vectors). Each face of an 
object is defined by a sequence of vertices 
clockwise around the face when viewed from the 
visible side. Lines connect adjacent vertices on the 
boundary of a face. By introducing another 
geometric entity, direction vectors, constraints can 
be placed on line directions or face normals. 
The information describing the relationships of all the 
geometric entities is stored in a scene structure 
graph. The structure graph consists of a list of 
objects; objects contain lists of vertices, faces, and 
447 
lines; faces contain lists of vertices and lines; etc. 
The structure graph is the topological description of 
the scene. 
The parameters which instantiate the topology into 
completely specified models are the scene 
parameters. Each geometric entity in the model is 
defined by some number of parameters, which may, 
for convenience, exceed the minimum number of 
parameters or degrees of freedom (DOF) needed to 
specify the entity. Vertices are defined by a 3 
vector, v. Lines are defined by a line direction 
vector a and a vector offset p. Points satisfying x = 
ka + p for some scalar k lie on the line. Faces are 
defined by a face normal a and any point on the 
plane p. Points satisfying a * (X - p) = 0 lie on the 
plane. Direction vectors are represented by vectors. 
Determination of the scene variables (all the 
parameters together) is the crux of the reconstruction 
problem. 
3.2 Scene Geometric Constraints 
Some constraints arise implicitly from the definition of 
object models as a planar mesh because all vertices 
in a face must lie in the plane of the face. This 
constraint is expressed as a * (v - p) = 0 for each 
vertex in a face. 
Additional explicit constraints on the scene 
geometry are needed when the camera model and 
scene geometry are underspecified. For example, 
constraints may be used to fill in parts of a scene not 
viewed in any image. Also the user will often desire 
to force scene models to satisfy particular 
conditions, such as walls being vertical. The current 
system provides four types of constraints: 1) point 
constraint - the user directly specifies the 
coordinates of a vertex, 2) direction constraint - line 
directions or face normals are constrained to lie 
along a particular direction, which can be fixed or 
free to vary, 3) length constraint - the length of a line 
is fixed, and 4) coincidence constraints - a vertex, 
line, or face is constrained to be coincident with 
another vertex, line, or face. 
3.3 Constraint Elimination 
Our approach to handling scene geometric 
constraints has been to eliminate them while 
simultaneously reducing the number of scene 
variables. To accomplish this, the variables are 
grouped into subsets, called elements, associated 
with the basic geometric entities of the model: 
coordinate frames, vertex points, lines, face planes, 
and direction vectors. The constraints (point, 
direction, length, coincidence) each define a 
relationship between two elements. As an example, if 
a face contains a vertex, then the face plane and the 
vertex point must intersect. To eliminate this 
coincidence constraint, the symmetry is broken and 
one of the elements is placed as a constraint on the 
other. Either the face is free and the vertex must lie 
in the plane of the face, or the vertex is free and the 
face must intersect the vertex. The constrained 
element has reduced degrees of freedom (fewer 
variables) due to the constraint. Continuing the 
example, if the face is constrained by the vertex, 
then the face is no longer represented by a free 
plane with 3 DOF but by a plane with 2 DOF which 
is attached to a fixed point in space. In effect, the