Relational Structure Description and Matching Algorithm for 3D Objects 
Deren Li 
School of Remote Sensing and Informatics 
Xinhua Wang 
School of Electronic Engineering and Precision Mechanism 
Wuhan Technical University of Surveying and Mapping 
39, LuoYu Road , Wuhan 430070, P.R.China. 
KEY WORDS: Robotics, Vision, Matching, Recognition, Artifical Intelligence. 
Abstract: 
When relational data structure is used to describe 3D objects, matching problem results in the problem of relational 
isomorphism or relational homomorphism. This paper presents the relational data structure describing 3D objects, 
and the trimming algorithm. It uses the multi-constraints and one to one correspondence constraint of relational data 
structure as the knowledge to trim the searching tree, that simplifies the problem of relational isomorphism in 
matching. Then the relational matching is determinated, combined with the unit distance function. Finally, a example 
is presented. 
1. Introduction 
Photogrammetry, combining with Pattern Recognition, 
Computer Vision (CV), has been become an important 
research area. The key of it is the describing method of 
knowledge. How to describe object determents not only 
the task and the goal of low--level approach, but also the 
high--level processing algorithm. Relational data 
structure is one of important description method. In 
relational structure description, 3D objects are composed 
of labeling basic units(for example, edges, surfaces, etc.), 
and the characters and their relation of basic units give 
out the description of structure feature of objects. A 
simplest relation (two-unit relation) is a graph. If the 
basic units are expressed by the node of graph, the edges 
of graph are used to express the relation between units. 
Then, the object matching problem become the sub- 
graph matching problem. Indeed, the computing perplex 
of sub-graph match is by index law (exponential 
function). On the other hand, the simplifies description 
can not satisfy the practical needs. Tsai and Fulll 
presented the conception of attributed relational graph 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
which give some attributions for node and edge of graph. 
The description enhances the describing ability of graph, 
but it brings some problems for low-level processing. 
Shapirol2] presents a method of relational description 
and proposes a relational data structure, which include 
different relations and multi--unit relations. In the 
description, the problem of object matching results in the 
problem of relational isomorphism or homomorphism. 
As known, isomorphism is the well known constraint 
satisfactory problem. Indeed, it is the consistent labeling 
problem. Up to now, computing spend is still the main 
problem of: matching. Haralick's method [3] is efficient, 
but mathematically has to be processed. In fact, we can 
use the structure constraints of object to simplify the 
labeling problem. 
In this paper, the authors present a relational data 
structure which uses the structure constraint to describe 
objects, and then present the trimming algorithms, which 
use those constraints to simplify labeling problem. 
Finally, a distance function of unit feature is evaluated to 
realize the precision matching. In section 5, a example is 
presented. 
442 
   
2. Re 
A relati 
where: 
attributi 
and x=( 
is relati 
and T; 
lU] is 
may be 
some fe 
As to c 
conside 
structur 
the rele 
and its 
relation 
as basi 
(catego! 
or strug 
be defi 
T2, cop 
T 
T 
T 
Notice 
hand, e 
Angle, 
descrip 
descrip 
many p 
relatior 
descrip 
is the 1 
unit set 
relatio: 
D,=(L,