surfaces, the
ections. The
lges and the
ed from the
ides: model
se, polygon,
for a model
r values for
ximum and
objects are
dimension
dels whose
sion can be
orientations
of ellipses
y del, whose
An ellipse
coordinates,
erived from
all polygons
area and the
, Where the
umbers are
'ment is the
ordinates of
>
Sa
lirections
odels in the
tween their
in the same
ject in the
vill not be
faces in an
faces in its
s two steps:
) the given
object are excluded; and the graph matcher, which performs a
detailed comparison between the potential matching graphs and
computes the 3D transformation between them.
4.1 Screener
In principle, the number of models in the database may be
large, and evaluating each pair to find possible correspondence
would be prohibitively expensive. Instead, a simple comparison
between the dimensions of a scene object and models is used to
ignore most models whose size is different from the size of the
object. There are two elements used for dimension comparison:
length of lines and average radius of ellipses. Each model has
its maximum and minimum lengths of straight lines and size of
ellipse, if such features exist on the model. The size range of an
sensed object should be within the range of a matched model,
since the number of geometric features of an object is less than
that of a correspondent model. Considering the errors in image
processing, the maximum value of a model increases by 10%,
and the minimum value also decreases by 10%. This process
limits the candidates of matched model to a very small number
which are then performed in the next process.
4.2 Graph Matcher
The graph matching procedure consists of finding the pairs (in
the model surface and object surface) forming the largest set
consistent with a single rigid 3D transform. The process begins
by finding all the possible pairs «m, o» where m and o are the
model and object surfaces, respectively. The geometric compa-
rison of surfaces is depended on the perimeter, the area and the
number of lines which bound a polygon, or radius and ratio
when the surface is an ellipse. In measuring the similarity
between m of the model and o of the scene object, the
normalised measure of the difference is computed for each of
the following properties:
° dmo (1) = d(Am,Ao), where A „ and A, represent the
surface area of a polygon in a model and an object,
respectively.
° dmo (2) = d(Pın,Po), where P represents the perimeter
of a polygon.
* dmo (3) = dRm,Ro) where R represents the average
radius of an ellipse.
* dmo 3) = dRty,Rty) where Rt represents the ratio of
major axis and minor axis of an ellipse.
Thresholds are set for each of the differences to determine
whether to accept or reject the match. One surface of an object
may correspond to more than one surface of a model, as shown
in figure 7, where the size of all circles are the same, so that
one circle in an object may be found to correspond to eight
circles in the model. If one surface of an object does not match
with any surface in a model, however, it will indicate that the
model does not match with the object and is rejected. The
process results in each surface of sensed object having multiple
corresponding candidates in a model. It is obvious that only one
matching candidate is possible, if the object is corresponds to
the model. Therefore multiple candidates must be reduced to a
single candidate for each surface of an object. This process
involves a compatibility constraint using topologic relations.
Topologic relationships exist among planar surfaces of a model
or an object. If two pairs <m;,0;> and <m;,o;> satisfy
similarity measures respectively, the relation between m;
andm; should be the same as that between o, and o;.
Everytime a pair of nodes <mjo;> is selected, it is
compared to all of the already matched pairs < m;,0; > using a
compatibility constraint. If this constraint is not satisfied, the
chosen pair « m;,0; » is discarded. The constraint contains the
following relation checks.
e Orientation Relation ( £ 1 ): Planar surfaces of a model or an
object are grouped in terms of their normal directions. The
angle between the orientations of two surfaces reflects the
relations between their orientations. Let 0 ,, and 0 , denote the
angles between the orientation of <m;,m; > and <0;,0;>,
and let A0 - |0,,- 0,|, then the pairs «m;,o; » and
<m;,0; > are said to be & 1 compatible if and only if AO is
less than a certain threshold.
e Proximity Relation ( & 2 ): Proximity relations summarise the
distance between surface centres. Let Lm and Ly denote the
distance between centroids of the surfaces m; and m;, and
o; and O;, respectively, and let AL = [Lm - Lo|, then the
pairs < m;, 0; > and <m;, 0; > are said to be & 2 compatible
if and only if AL is less than a certain threshold. If two surfaces
are polygons and adjacent (ie. they share a common edge), the
adjacency relation is checked between the two surfaces.
After all surface nodes of an object match with the model nodes
and satisfy compatibility constraints, a geometric transforma-
tion is calculated between the coordinate systems of a model
and object. Computing the geometric transformation between
matched objects not only indicates how to bring the matched
objects into correspondence, but also helps to verify the
matching process. The estimate of the actual transformation
between model coordinate system and object coordinate system
can be given by a set of vertices of the polygons. If all elements
of the object after transformation are matched with the
elements of a model, the object is considered to correspond to
the model, and its position and orientation are determined.
S. EXPERIMENTS
The system has been tested on several industrial components.
The CAD models were constructed from physical prototypes
whose dimensions were measured by hand. AutoCAD system
designs of each model in terms of the data dimension were
generated, and output in a DXF file. The geometric inferencing
is then performed on models to create graphic representations
which are stored in a model database. Figure 8 displays the
models listed in the database.
A sensed object is captured using two CCD cameras as shown
in figure 9. The image processes are then applied on the images
to construct 3D objects (figure 10). The representation of the
object is described in the same way as the models. The
maximum and minimum of the line lengths in the object are
103 mm and 10.8 mm, and the maximum and minimum of the
circle radius are the same as 7 mm. The four values are used to
screen the models in the database and delete those whose
257
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B5. Vienna 1996
