arcs based on changing the height of their end points (estimated
by parallax in the two images) - border and skeleton lines of
roofs (with almost equal height), foundation lines of walls (with
almost equal height), border lines of walls (with high difference
of height along their length) and terrain lines (with smooth
change of height of line). The description of every arc contains
address information (pointers) to the subsequent arc in the outer
contour and in the inner contour. The isolated set of adjacent
contours contain outer contour of whole set and inner contours
of separate areas. For outer contours is used clockwise direction
of contour elements connection and counter clockwise direction
for inner contours. For such definition of contour following is
ensured the opposite direction of contour tracing on opposite
sides of the arc. For contours lying along the outside contour
such description produces the list of contours in cluster. For
inside contours is necessary to scan all inside lines of the areas.
The description of the correspondence between the areas and
the arcs and the topological state of connectivity and adjacency
and is ensured by pointers attached to every arc. For every arc
are used two pointers to the internal and the external contour.
The arc is presented as a vector with a head joint point (1) and
a' tail joint point (2). The pointer corresponding to node 1
ensure connection to next arc element of internal contour (in
counter-clockwise direction) and the pointer corresponding to
node 2 ensure connection to external contour (in clockwise
direction). The direction of outer contour arcs is corresponding
to internal contours (counter clockwise). If increasing the speed
of processing is necessary to every node of arc is possible to
attach two pointers to ensure bi - directional scanning of every
contour but this tends to enlarge the amount of used memory.
For the main arcs of the external contours the definition of
external and internal contour is obvious. For the non-main arcs
of the external contour and the arcs separating contours from
equal level the internal contour is an own contour and the
external is an adjacent to the arc. The pointer is used to point
the main arc of the internal contour. In such way the orientation
of the arc is defined and the appropriate pointer is used to form
a contour. It is assumed that the main arc of a scanned contour
is known when the contour is formed. For internal contours the
pointer of the main arc is used for a connection with the contour
from a higher level. For the non-main arc the pointer ensure a
connection to the main arc of the own contour depending on the
arc orientation. (own contour could be the contour from higher
or lower level). For every isolated cluster one of the external
contours is marked as a leading contour by its main arc. It has
connections to the next cluster (if exist) or to the previous
cluster (if it is not first) or to the higher level of included
clusters. Every contour from external ring is connected to the
next one by its external arc that is usual main arc. For internal
contours it is not always possible to define a ring of contours
but it is possible to find a path to them from some of the
external contours. For the non-main arcs of the external contour
is used an additional pointer to the main arc of the contour,
respectively to which the first arc pointer (node 1) is oriented.
The same rule is used for the main arcs of external contours but
for them such pointer is not necessary to be used. In such way
the clockwise following the external contour and the counter
clockwise direction for internal contours from the external ring
is used.
To produce a hierarchical description of the image it is
necessary to introduce additional information about contour sets
lying inside or outside from the defined contour. To describe
such relations it is necessary to formulate a restriction over the
sets of the clusters. Inside of every contour it is possible to exist
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
a set of separate clusters of adjacent contours. To describe such
type of information for every cluster is chosen a contour that is
marked by a leading arc element (start element in the arc list for
contour) For the leading arc elements are defined two
additional pointers - first to the next element in the list of the
isolated clusters that are lying inside the contour at a higher
level and a second pointer to the list of inside clusters.
Such approach is convenient for generation of a contour
description from arcs and gives possibility to generate high
level description convenient for usage in the relational data base
environment.
3. FORMULATION OF PICTURE GRAMMAR
The necessity of two dimensional elements description involves
usage of corresponding type of grammar. Suitable for that
purposes is PLEA-GRAMMAR (Feeder, 1971). A N-attaching-
point element (NAPE) is introduced in it. The grammar is
represented by the six-tuple (V. Vw. P, So, Q, qo), where
VT - is a finite non-empty set of terminal (non-
productive) elements;
VN - is a finite non-empty set of non-terminal elements
(productive);
VA VO:
P - is a finite set of productions (generating rules);
S € Vy isa special NAPE - initial;
Q is a finite set of symbols called identifiers that form joint lists
(of internal joint points of NAPE set) and tie-point list
(consisting of external points of NAPE set)- identifying the
links between elements; The identifiers could be represented by
integer corresponding to the number of tie-points of single
NAPE.
QI PUN: OE
qo € Q is a special NULL identifier, that is used to
show that corresponding NAPE from NAPE list is not
connected to the described joint or tie point.
An extension of grammar is used in which except traditional
joint point for which are necessary at least two non-zero
element in joint list a special type of joint is introduced that is
implied connected to the main arc of the contour. This
additional joint type is used for contour definition that could
involve only one connected non-zero element. According to the
above definitions the presentation for a set of four NAPEs with
five joint points (four for arc connection and one for contour
definition) and two tie-points is represented by set of
components and two lists (of joint and tie-points) of the form:
V,V2 V3 V4 (91929394 >91929394>41929344>9192939 43
41929394 )(91929394-9:1929394)
The terminal grammar elements are corresponding to the basic
elements of the topological description. They are defined based
on the order of the connectivity of the element. Two kinds of
links are present - direct links to consecutive arcs in contour
and links to the clusters of the same level or different levels
(upper or lower) and with their properties as boundary of plane
regions. It seems to be very attractive to separate the plane
region with finite arcs and edge line properties of three
dimensional objects but it is not possible due to the fact that
photogrammetric image is two dimensional projection of three
dimensional objects and the complexity of the solution is
498
respect
invisib|
solutio!
relative
planes
into ac
be forn
I. Arcs
relative
differe
II. Arc:
r - roof
v - wal
p-roo
W - wa
III. Ar
h - wal
t - tei
part of
e - visi
In situ:
than t
could :
of this
irish
| - left
u - arc
n - arc
f - left
g - rigl
The di
differe
k - ma
m - m
cluster
c-ma
b - noi
i - inte
S - nor
d - m:
the coi
0 - Sin
q non-
clustei
It is ne
differe
follow
that a
gramn
1. Nor
Se - en
2 Firs
sg-init
area c
3 Se
cluste:
dg - SC
