76 
2" d algorithm - Minimization of the width of a level structure 
When two level structures of equal depths are found, it is 
possible to merge them suitably, in order to get a new level 
structure of minimum width. To this aim, the nodes belonging 
to the same level in the two level structures have already a final 
destination. On the contrary, the nodes whose level are different 
should be definitively assigned to the level of one structure 
(between the two ones). The selected level is chosen taking into 
account, level by level, the structure whose local width is 
smaller. Notice that the new level structure could be unrooted. 
3 rd algorithm - Numeration 
Node numeration goes on, level by level, starting from a root. In 
the following it assigns, in a set of nodes a smaller number to 
the nodes connected to the nodes, whose number is the smallest 
one, in a previous set of nodes. In case of ambiguity, the degree 
of the nodes is taken into account. 
4 th algorithm - Dissection 
Nodes of a very high degree, of very long connections in a 
(hyper) spatial graph should be removed from the graph, so that 
the previous algorithms supply the expected results. In these 
cases, a preliminary dissection of the graph may be performed, 
if necessary dividing the graph in dissected parts. The ordering 
of these parts takes place thereafter, applying the above defined 
numeration and ordering algorithms. 
More sophisticated methodologies and procedures can be 
performed obviously, but their exposition is omitted for sake of 
brevity. 
4. RELATIONAL STRATEGIES (BELLONE, ET AL„ 
1996A) 
Relational strategies are based on relational data description 
techniques. A relational description is defined by a list of 
primitives and a list of relations. These lists are composed of 
some primitives, each described by attribute-value pairs. The 
lists represent the relational part of the data description. They 
provide the context information necessary for resolving the 
similarity problem. 
Applying principles of perceptual grouping to a high level of 
data structure, a description independent of the different 
viewpoints and high data reliability can be obtained. Graphs, 
composed of nodes that denote primitives and inter-nodal lines 
denoting relations, are used to represent relational data 
descriptions. Segmentation and matching are carried out on 
these graphs and are based on the criteria of seldomness and 
similarity. 
Notice that signal disturbances caused by various sources of 
noise during data acquisition have impact on the subsequent 
information extracting process. 
The labeling of nodes is performed so that every node ( or 
primitive ) of the graph is characterized by the number and type 
of relations associated to it. A numeric value (or label) is 
calculated according to rules able to represent the specific 
characteristic. Nodes with identical labels have the same 
relational characteristic. 
To obtain further distinctiveness, additional labels or sub-labels 
will be associated to each node. Once a label or sub-label 
distinction is obtained in this way and a value will be associated 
to the tuple of labels describing the node. 
Within the group of nodes, a sorting (in descending order) of the 
associated labels will then be performed and the labels will be 
identified. For each node associated with these labels, the 
algorithm will applied again considering now connected 
second-level nodes. It is difficult to obtain complete 
distinctiveness for all nodes of a graph by applying the 
procedure described above recursively, as repetitive elements 
are frequently found in real world environments. The algorithm 
is applied no further than the third level. 
Once the labeled graphs have been constructed for every set of 
data, the process if exact matching is relatively straightforward 
and can be performed in three steps. 
• For each set of data of the first pair, the appertaining 
graphs will be listed in descending order according to their 
complexity measures. 
• For every element (or graph) of one if the sorted list, the 
second list is searched for all elements with the same 
complexity measure. Among these element pairs, only 
those with the same number of nodes and the same sum of 
ranks over all nodes will be further analyzed. 
• For each of these graph pairs, a sorted list of every graph 
nodes will be produced in descending label order and for 
duplicate labels in descending sub-label order. Only graph 
pairs that provide a complete 1:1 identity between the rows 
of their node list will be further considered for analytical 
steps. Between the nodes of these graphs a precise 
correspondence has been found. 
All unmatched graphs from the above exact matching process 
will be analyzed in this step. For every graph of a first pair, the 
approximate position of the corresponding graph in the second 
set of data can be calculated by means of parameters obtained 
by some analytical steps of the pair based on points extracted 
from exactly matching graph nodes. 
Thus only a limited number of graphs in the second set of data 
has to be considered for matching, i.e. only those to be found in 
the second area of interest. 
The inexact matching process is an extension of the exact 
matching process and can be described as follows. 
• For each graph pair, a sorted list of nodes will be produced 
as described for the process of exact matching. 
• Each node pair of the sorted lists will be examined to 
identify pairs with identical labels and sub-labels denoting 
matched nodes. 
• For the remaining unmatched nodes in each list, the above 
described algorithm for obtaining further distinctiveness 
will be applied considering only those connected nodes 
within the related list that have already been successfully 
matched. 
• For these unmatched nodes, step 2 will then be performed 
again and, if additional matching could be found, step 3 
will be repeated once more. 
Inexact matching generally yields multiple correspondence 
solutions of which only the very first one encountered has been 
considered for the present approach. 
5. FORM DESCRIPTORS (CRIPPA, ET AL., 1994) 
Form descriptors furnish an analytical representation of data. 
There are different cases of geometric shape that can be studied 
by different form descriptors: 
• a line referred to an one-dimensional domain can be 
investigated by line interpolation.