of N; to N G+Da 
i+tk<n 
otherwise 
(14) 
nt A to point B. 
¢ N; can be ex- 
1 C ix (15) 
———— 
r N;N G4», with 
ex polygon, the 
7 be outside the 
"his means that 
id some may not 
d on the calcula- 
are over 100 and 
o not exist. 
es, we associate 
e with each ver- 
ding angle value 
number. In or- 
select a reliable 
rom the surface 
e matched poly- 
ow index identi- 
c of the matched 
ed a column in- 
ites of each row 
ional features of 
e of this assign- 
Ni.3 
tablishment 
hment, C;; can 
=. 
F (I;, M) 
[1;,,MM,) (16) 
of the zth ver- 
; M, the shape 
esponding poly- 
of the zth ver- 
  
  
  
  
  
  
  
  
0 1 / 3 
e o e 9 
e o 9 e 
e o 9 e 
e e o 9 
  
  
  
Fig. 4. Row-column assignment for 
vertex correspondence establishment. 
tex in a polygon of the input image, and M M, the 
angle of the yth vertex in the corresponding polygon 
of the object model. The two selected polygons. one 
from the image and the other from the object model; 
have been matched at the previous stage. As to the 
weights (w;s) on the right-hand side of (16), the 
following restrictions must be satisfied, i. €. » w,= 
4 
wo, wy = wy, and NO! w;- 1. In general, the 
weights assigned to the relational features (w3 and 
w,) are higher than those of the local features C 
and w,). 
C. Deriving the Best Vertex Correspond ences 
Based on the row-column assignment mentioned in 
Section IV-A , the vertex labels of a matched polygon 
in the input image are arranged as the row indexes 
and the vertex labels of its corresponding polygon in 
the object model are arranged as the column indexes. 
Because of this particular assignment , the vertex cor- 
respondence problem can be analyzed in a systematic 
manner. 
Before we proceed, we will define some termino- 
logics which wil Ibe frequently used in the sequel. Let 
P represent an 2-sided polygon whose vertices are se- 
quenced clockwise as (p oP1°**P,—1)- If polygons P is 
rotated clockwise by m-vertex (m <n) into a new 
polygon P' , then the vertex sequence is updated from 
(popittt Pai) to. (PaP oia P ona *** Pa—iP07** Pn—2 
Pn-1). Let A and B be two n-sided polygons with 
clockwise vertex sequences (aga,***a,—,) and (bob,** 
b,_1). respectively. Suppose the original vertex cor- 
respondences between A and B is a9—59,a1—b,,***, 
a, ,—b,—,. If polygon A is rotated clockwise by m- 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
vertex distance into A’, then a new vertex correspon- 
dences between A' and B is a,—- bo; amp. 7 bi» 
 (n-E2)4 7 02» *** »4n —2 b. 2541 b 1 
The simplest way to determine the correspon- 
dences between the vertices of two polygons is to fix 
one of them. rotate the other in 2-D space each time 
by l-vertex (either clockwise or counterclock wise ) 
and calculate the total error by accumulating the dif- 
ferences between all the corresponding node pairs. 
The comparison continues until the rotated polygon is 
brought back to the original position. For two n-sid- 
ed polygons, there are n sequential comparisons to be 
performed. By using a Hopfield network , the com- 
parisons can be executed concurrently and the results 
shown explicitly in the network. 
Given two n-sided polygons with vertex labels pre- 
arranged as described before, we can construct a 
Hopfield networks in the form of an n Xn neuron ma- 
trix in which the row and column indexes correspond 
to the vertex labels of the two polygons, respective- 
ly. The two polygons will be referred to as row poly- 
gon and column polygon, respectively. Let neuron G, 
j) represent a neuron at position (5, j). Because the 
vertex orders of a polygon is preserved under rotation 
in 2-D space, the degree of match between a fixed 
polygon and each of the n rotated instances of the 
other polygon can be analyzed systematically as fol- 
lows. Suppose we rotate the row polygon clock wise 
k-vertex (kz50) and fix the column polygon. Then, 
the degree of match between the column polygon and 
the rotated row polygon can be computed from the 
following set of neurons: 
{neuron (i,j) | where © = (j-k)mod n, 
0xli,j «n, Lek n) (17) 
where 
: j-k , ifj=k 
lene LL nr r m +n, Adu 
The degree of match between the fixed column 
polygon and the rotated row polygon can be deter- 
mined by counting the number of active neurons (af- 
ter the network stabilizes) in the neuron set repre- 
sented in (17). Generally, the set of ncurons in (17) 
with different k values can be represcnted by the u- 
nion of neurons in two diagonals parallel to the main 
diagonal of the matrix. Using the main diagonal as 
basis , the upper-right diagonal starts from neuron (0, 
k) and ends at neuron (n — k — 1,2 — 1). The lower- 
left diagonal starts from neuron (n — k, 0)and ends at 
neuron (n — 1,k— 1). When k=0,only one diagonal 
starting from neuron (0,0)and ending at neuron (ar 
1,n — 1)exists. This happens if neither row nor col- 
umn polygon is rotated. Based on this arrangement, 
the degree of match between the fixed column poly- 
gon and each of the n instances of the rotated row 
(18) 
1015