our approach, the relational description comprises four
binary relations (subsets of the Cartesian product A
AxA): parallelism, perpendicularism, connection and
collinearity.
A more suitable type of relation, called star structure, can
be used in the matching procedure. According to Cheng
and Huang (1984), a star structure rooted at node / is
node i itself plus all its links (binary components of star, i.
e. r1, ..., rj) and neighbouring nodes (n1, ..., nj). Figure 1
illustrates this concept This structure allows the
definition of the matching between two homologous
straight features. A star structure is defined to each
straight feature that is named root. As already
mentioned, a star structure is also a relation.
Consequently, a star structure is defined similarly, but
each of its components must contain the root straight
feature. The relational description based on star
structures is a list of these structures having the same
root, which in our approach are based on parallelism,
perpendicularism, connection and collinearity.
No N3
My
Figure 1 - Star structure.
Transformation fram entity space to relational space is
applied to straight features both in the image and object
spaces. The relational descriptions of image and object
straight features are constructed in the 2D-space.
Although ground control is defined in the 3D-space, the
object straight features are projected to the image space
by collinearity equations. Approximated parameters of
exterior orientation are required at the beginning of the
matching process. Since the exterior orientation
parameters are successively refined after the third
correspondence, the ground controls are also
successively re-projected to the image space by
collinearity equations. Therefore, the relational
description of re-projected image is continuously refined.
2.3 Matching Strategy
The matching strategy is performed in the search space
(search tree). This space consists of nodes and arcs
connecting nodes. Each node represents a possible
assignment of one image straight feature to one object
straight feature. The set of image straight features is
called Unit and the set of object straight features is
called Label. The latest set includes a special primitive
CE a Te ae EE TE ee
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
named NULL, which is used to label an image straight
features that have no correspondences in the object
space. Each possible path from root node to some leaf
node is a possible solution or a possible mapping. Then,
the question is how to obtain the correct mapping. Each
node of correct mapping must satisfy the following
conditions: the uniqueness constraint, the rigidity
constraint, a limit to normalised relational distance and,
the self-diagnosis.
2.3.1 Uniqueness Constraint: If an image straight
feature and an object straight feature are homologous,
both straight features correspond to a unique
phenomenon in the real world. In other words, each
feature of the label set that was used in some
correspondence is taken out of the search space in the
following searches. This simple operation reduces the
search space.
2.3.2 Rigidity Constraint: The rigidity constraint is
based on a photogrammetric model relating straight
features both in the image and object spaces. One
photogrammetric model that relates image and object
straight features is presented in Tommaselli and Tozzi
(1993, 1996). In this model the observations are straight
line parameters extracting in a vectorization process. The
rigidity constraint is used in a paradigm called matching
while locating. It was adapted from another similar
paradigm called recognising while locating (Faugeras and
Helbert, 1986). Given an image straight feature, the aim
of this paradigm is to restrict the number of object
straight features to be analysed in the matching process.
In other words, the search space is drastically reduced.
2.3.3 Application of Normalised Relational Distance:
The relational matching is applied at this step. The
normalised relational distance is applied if the node of
the search tree being analysed satisfies the uniqueness
and the rigidity constraints. The normalised relational
distance is a metric that measures the similarity between
two relational descriptions and is defined in the range [0;
1]. In our case, they are constructed from unit and label
sets and are based on star structures. In an ideal case, if
the normalised relational distance is zero, the node
being analysed is considered compatible. In practical
applications, however, it will be necessary a threshold.
2.3.4 Self-diagnosis: Self-diagnosis is based on
detection of gross errors. Due to the need of redundant
data to apply least squares adjustment, only after the
fourth correspondence it could be feasible the application
of the self-diagnosis. An alternative would be to apply a
recursive estimation method, e. g. Kalman filtering
(Tommaselli & Tozzi, 1993, 1996). At this moment, only
Chi-Squared test has been implemented.
3. RESULTS
The approach summarised in the previous sections was
implemented in C language.
In order to illustrate the application of the method, an
1:10.000 aerial photograph was simulated. Random
errors were introduced in the data. The spatial view of the
simulated straight features are showed in figure 2.
The simulated data are listed in table 1. One image
132
II
Figure 2 - S
space straig
(b) parame
were introc
No ER
a
(x1C
0 3
1 3
2 E
3 27
4 17
5 18
6 -1t
7. 1
8 EC
9 1C
10 -2:
11 1C
12. 4
Üimage
