sue between any object model and the input image
can be derived even if they contain a different number
of surfaces.
This similarity measure is used to reduce the search
space. Based on the proposed simple features, a set
of object models most similar to the input image. is.se-
lected from the database. This process can be consid-
ered as a coarse search step because “good” candi-
dates as well as some “bad” candidates are selected
due to roughness of the feature set. However, this
proeess discards a large number of object models in
the database and significantly reduces the search
space.
N. HOPFIED NETWORKS FOR VERTEX
CORRESPONDENCE ESTABLISHMENT
After the surface correspondences between the un-
known object and the object model are confirmed,
the next step is to apply Hopfield networks to estab-
lish the vertex correspondences. In this section, the
features for vertex correspondence establishment are
first described. This is followed by the introduction
of row-column assignment. Next, the strength of in-
terconnection Cj; is defined. Then, a technique for.
systematically deriving the best vertex correspon-
dence is presented. Finally, the characteristics of the
networks are discussed.
A. Feature Selection and Row -Column Assignments
Before we start establishing the vertex correspon-
dences, the order of all the vertices in each polygon
must be determined. This is usually achieved at the
preprocessing stage by selecting the vertex of a poly-
gon with minimum z coordinate as the starting ver-
tex (oth vertex). If two vertices happen to possess
the same minimum z coordinate, the one with small-
er y coordinate is selected as the starting vertex. The
subsequent vertices are numbered sequentially in a
clock wise direction. The reason for making this or-
dering is to facilitate the subsequent row-column as-
signment process. A useful feature for vertex corre-
spondence establishment is the shape number pro-
posed in [16]. This feature is invariant to rotation,
translation, and scaling in 3-D space. The method of
deriving the shape number for each detected vertex is
as follows. Consider a polygon in Fig. 3 which has a
clock wise edge sequence of (E;E;,,E,,5:***) and a ver-
tex sequence eof (N;N;+1N;+2°°°). Point I; is the in-
tersection of vector N.N us with vector Na Niro:
Then, the ratio (distance from N; to Z;)/(distance
from N; to N;+2) which is assigned to vertex N; of
this polygon remains constant for any positioning of
the surface in 3-D space.
For the general case, consider a polygon of n edges
with a clockwise edge sequence of (E,E;*** E, ,E,).
where
iX. ifi-- ka
) = 14
(ak), J otherwise £14)
and
t+ EC 20
Let [A B] be the distance from point A to point B.
Then, the shape number for vertex N; can be ex-
pressed as
nep gendi d
[NS Note)
ES
where /; is the intersection of vector N;N (+2), With
Sh x 100,11 & *< (15)
vector N à+1alV G+3/a+ For a nonconvex polygon, the
intersection of the two vectors may be outside the
contour or may not occur at all. This means that
some Sh;s may be greater than 100 and some may not
exist. An upper limit of 100 is placed on the calcula-
tion for those shape numbers which are over 100 and
Os are assigned to those Sk;s which do not exist.
To establish vertex correspondences, we associate
a local feature and a relational feature with each ver-
tex. The local feature is its corresponding angle value
and the relational feature is its shape number. In or-
der to perform vertex matching, we select a reliable
and matched polygon pair obtained from the surface
matching process. Each vertex of the matched poly-
gon in the input image is assigned a row index identi-
cal to its label. Similarly, each vertex of the matched
polygon in the object model is assigned a column in-
dex identical to its label. The attributes of each row
or column include the local and relational features of
its corresponding vertex. An example of this assign-
ment is shown in Fig. 4.
N;.3
Net
Fig. 3 A surface patch.
B. Cay for Vertex Correspond ence Establishment
For vertex correspondence establishment, Cy; can
be expressed by an equation as follows:
C as = wı X F(I;,M,) + Ww, X F(7,,M,)
+ wi, F (II, MM,) + w, X F(II;,MM,) (16)
where 7, represents the shape number of the zth ver-
tex of a polygon in the input image, M, the shape
number of the yth vertex of the corresponding poly-
gon in the object model ,77, the angle of the zth ver-
1014
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
Edge FE; has a clockwise orientation of N; to N G4»,
ve
tex in a [
angle of t!
of the obj
from the
have been
weights (
following
1023» t0 3, 7—
weights 2
w,) are |
and w,).
C. Der:
Based
Section T
in the in
and the
the objec
Because :
responde
manner.
Before
logics wt
P repres
quenced
rotated
polygon
Cpopi***
Pn-1). I
clock wis
bug) f
respond:
0,—17* 5,
