lefined as: 
(6) 
(7) 
te for H, 
(8) 
from the 
nal sub- 
subset is 
trimming 
iming of 
pondence 
relational 
ther. The 
and the 
le. 
(u) based 
U,L,) is 
iat the n 
her units 
pondence 
H;(u)and 
Set s; are 
expressed 
nd define 
lel, 
n; Hu)-t lef()| 1e f(), ifu eQ(u)) (9) 
In practice, we always begin to execute m; algorithm for 
constituting and trimming unite--label table H;(u) and 
relational subset T; from the subset which has the least 
cardinal number in the unit--label table H;, and iterate it 
until the following equation is valid. 
n" H- n *H (10) 
It should be point out that the correspondence relation 
also exits the correspondence between relational 
attribution and unit-label table. 
4, Relational match 
In practice, the existence of relation isomorphism usually 
do not means precision match. So we involved relation 
distance function to evaluate the precision match. 
After above trimming approach, the deformation 
between two graphs (for object and model ) mainly - 
expresses as the deformation of units displacement. If we 
have two unit a=(s,x) and b-(t,y), where : s,t are unit 
labels, and x,y are the unit feature vectors shaped as 
(X1,X2.... Xm), (ynyo...ym) respectively. Thus relational 
distance function can be defined as: 
Doc Y gx, 7 1.) (11) 
i=l 
Where: g; is weight. 
Especially, if s=t, then Ds=(s=s)=0. 
Thus, when Ds-»min, the precision matching is 
determined . 
S. Example 
As to the object and model as Fig.1, the Table 1~6 are 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
the relational data structure. based on formula (2), the 
relational subset tables Fi, F?, F4 can be expressed as 
table 7-9 by using the constraints (Ti, T2, T3). Moreover, 
table 10-12 are the F; (i=1,2,3), after executing the 
trimming approach m; . Then according to the formula 
(3)(4), we can get every unit-label tables (H,,H;,H3) as 
table 13~15, based on relational constraints. Following 
formula (5), intersecting result of unit relational tables is 
the unit-label table expressed as Table 16. Continually 
executing the trimming algorithm of n2, we can get a 
new result as Table 17. Finally, we obtained the unit- 
label table expressed as Tab 18. after executing distance 
function (8). 
Above results express that, after executing n trimming, 
Table 17 has almost been a fully trimmed searching tree. 
precision match by means of distance function is easy. At 
the same time, the computing spent will obviously reduce. 
Fig. 2 is another example, and Fig. 2 (a) and (b) are the 
object and model, respectively. Here, we use surfaces as 
units, the relations between units can be defined as: 
adjacency and insect-surface relation T,, parallel relation 
T,, adjacency and insect--point relation T3. 
T,={(U,,U2..Un) |ujeU, adjacency relation with 
common surface, n23j 
T27((ui,u....u,) | u; €U, parallel relation, n22j 
T3={(U,,U2....Un) |ujeU, adjacency relation with 
common point, n23j 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
E 9 'a 
' 2 1 . 
: i 
|J iC 
1 h 1 
8 7 le 70 
du ----- ----- 
ik b ia f 
(a) (b) 
Fig. 2 An overview of object and model using surfaces as units 
For the similar reason, every units has its own 
attributions. Base on above relation description, we can 
get relational description as Tab.(19)-(22) (For the 
reason of simplification, we only make a discussion of 
relation matching using the relation description T, and 
T,). The unit-label table H; is expressed as Tab.(23), 
following formula (3) and (4). At the same time, H, is 
involved to trim the unit-label table H, . Tab.(24) is the 
result of H, which is trimmed by mn, algorithm. 
Continually executing the m» algorithm, finally we can 
445