elational 
objects, 
nal data 
hism in 
example 
of graph. 
of graph, 
Ocessing. 
scription 
1 include 
In the 
Its in the 
orphism. 
onstraint 
| labeling 
the main 
efficient, 
[, we can 
plify the 
nal data 
| describe 
ns, which 
problem. 
iluated to 
xample is 
2. Relational data structure describing 3D object 
A relational data structure is a two-unit graph D=(U,T), 
where: U is the basic unit set (each unit can has its 
attribution), shaped as a=(p,x) (p is the label of node, 
and x=(x;,X2....X,) is the feature vector). T=(T,,T2....Tx) 
is relational set. Each relation T;(i=1......k) is a subset, 
and T=(tintz.....tm), where: tjcU, and I«|tj| «lul, 
|U| is the cardinal number of set U. The subset of Ti 
may be sequential or unsequential, and can be involved 
some feature vectors. 
As to a simplifier object, its edges or surfaces can be 
considered as units of graph, and the geometric or 
structure constraints between units can be considered as 
the relations. Fig 1. is an overview of observed object 
and its model. Let us make a discussion about its 
relational data structure. Here, the edges are throughout 
as basic units, and each edges has its own attributions 
(category, parameters etc.). According to the geometric 
or structure constraint, the relational between units can 
be defined as: connecting relation T1, parallel relation 
T2, coplanar relation T3. 
Ti7((u1,u»....u,) | u;eU, connecting relation, n22j 
T27((u;,u,....u,) | u; €U, parallel relation, n22j 
T57((ui,u....u,) | u;eU, coplanar relation, n>2} 
Notice that: T;, T2, T4 are unsequential set. On the other 
hand, each relations can has its attributions. For instance, 
Angle, connecting method etc. All of those relation 
description are not unique. Indeed, too much relation 
description will benefit consistent labeling, but will bring 
many problems for low-level processing. Based on above 
relation description, we can conclude the relation 
description as Tab 1—6 for the object as Fig 1. Where: U 
is the unit set of object. T is its relation set. L is the 
unit set of model, and S is the relation set of model. Thus, 
relational data structure can be defined as D,=(U,T) and 
D,=(L,S) for observed object and model respectively. 
  
  
  
  
  
  
  
  
1 a 
2 3 b 
4 d C 
5 b £^ f 
8 ; i 
g 1° h 
10 K 
(a) (b) 
Fig.1 An overview of object and model using edges as units of graph 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
Notice that: because of the occluding, the edge k in 
object is lost. 
3. Trimming algorithm 
Consistent labeling problem can be expressed as a four-- 
unit group (U,L,T,R) where: U is the unit set of 
observed object, U=(u;,u,....u,); L is the unit label set of 
model, L=(l;,1,....1,) ; T is the unit constraint set, shaped 
as U=(u;,u,....u,) , that is a set of N--unit group, u-U. 
Usually, not all N constraint can be labeled for 
(U;,U2....Un). So, we involved unit--label constraint 
relation R which tells us which 1; is reasonable labeling 
for group (u;,u,....u,). R is composed of the structure 
constraints of object and model. 
Thus, we can use all methods of searching tree to consist 
labeling. There has been many algorithms"! !, but they 
almost put all constraints together to search. As the 
result, the computing spent is unbearable. So we 
developed a trimming algorithm as following. 
Precision match demands that all matched units have the 
same structure. So each structure constraints can be 
considered as knowledge to trim searching tree. The 
simplifier and efficient algorithm is using unit 
attributions to trim searching tree. So we can define a 
unit--label table as: 
H={H(), H(uy),..... Hum)} (1) 
Where: H(u;) is the set that can give labeling for unit u; . 
Then, we can take further step to trim searching tree 
based on all constraint relations. 
3.1 Trimming algorithm using relational subset 
Assume that, we have know the relation data structure of 
a object expressed as D.={U,T}, and the relational data 
structure of model expressed as D={L,S}, where: U, L 
are unit set and label set, respectively. T-(T|,T»....Ty), 
S-(S,,S,...Sy), T; and S; expresses a kind of relation. 
Thus we can define a relation subset table F as: 
F(ÿ={ seS;| |s [2] t |} (2) 
443