se
re
divided. This division is dependent on the parcels size, form,
and the number of partitions this parcel was subjected to
already. With a statistical analysis an estimation of these
dependencies and parameters, accompanied with an estima-
tion of the probability of each rule is gained.
Global parameters like maximal and minimal parcel size,
maximal and minimal ratio of shorter side of a rectangle to
larger side, and maximal hierarchy level can be estimated in
a first step. These parameters determine when a subdivision
stops.
The dependency of the partition on the parcel attributes is
modelled in terms of a Renewal Process.
In this paper, only the outline of the estimation process is
given. In order to reliably estimate the model parameters, a
big sample of exemplary data has to be evaluated. Further-
more, the functional dependencies of the different parameters
have to be examined carefully. For simplicity in the follow-
ing example dependencies on the size and form of the parcel
and on the direction of the partition are neglected, and the
following simplification is made:
e Parcels are divided along their longer side.
e The partition of a parcel only depends on the hierarchy
level, namely the number of previous partitions. This is
a fact that is easily verified with visual inspection of the
data: the first cuts of a parcel try to generate a few big
parcels, while the following split these parcels into the
final individual fields, by higher number of cuts. The
parameter A in equation 3 corresponds to the number
of successors n. Different parameters A are estimated
depending on the hierarchy level.
The result of the estimation are both the functional depen-
dencies and the corresponding probabilities. These values
for the relation between hierarchy level level and number of
cuts n for the above example (see Figure 3) are given in the
following table:
level 1 2
n 3 5 2
P(n|level) || 1.0 || 0.67 | 0.33
These values are gained by simply counting the possible num-
bers of successors of a level. On level 2 e.g. there are 3 par-
cel to divide. Two of them are cut into 5, one is cut into 2
parcels. Thus result the probabilities of 2/3 and 1/3 resp..
In order to rate an existing aggregation structure, the prob-
abilities of the individual steps of its generation have to be
evaluated in common. To this end the whole chain of depen-
dencies has to be formulated. The probability of partition
P(part) of a parcel N; with parcel sides wg and ho into n
subparcels depends on:
Wı Wo W3
ho N;
Wo
e P(N,): the probability of ,father“-parcel NV;
e P(n|level): the probability of n cuts given hierarchy
level level
861
e the probability of dividing parcel N; into n cuts with
widths w;
P(w;,ws,::-,w4|Ni, n) 2 P(w|Ni,n)-
P(w;|w;, Ni, n) es
P(w,|wi, wa, --- ws 1, 1, n)
Due to the ,lack of memory“-property of the Renewal
Process, the probabilities of the individual cuts w; can
be considered independent from each other, i.e. depend-
ing only on the ,father“-parcel and the number of pre-
vious partitions n, resulting in
P(w;,ws,--- , wa |. N1, n) = P(wi|Ni,n) >
P(w»|Ni,n) --- P(w,|Ni, n)
e the probability of the width w; of a parcel given the
number of partitions n is computed with equation 3:
P(w;|N,,n) 2 P(X = 21 = n)
Wi
The probability of partition P(part) is then:
P(part) = P(N,) - P(nilevel) -
-P(w,|N,,n) - P(wa|N,,n)--- P(w,|N;,n)
All the other dependencies have to be considered correspond-
ingly.
6.3 Representation in attributed
stochastic grammar
After estimating the model parameters, the stochastic gram-
mar can be set up.
e Vocabulary:
Vv = PARCELA,
Vr = parcel,,relation
relation = |, —
e Startsymbol S — PARCEL,
e Production rules P:
PARCEL, "€" PARCELarelationPARCEL,
PARCEL, PUUP parcel,
Nonterminal symbols (denoted in uppercase letters) stand
for intermediate parcels; terminal symbols (lowercase letters)
give the final parcels or the spatial relations between the
parcels resp. (| — left-right; — — top-bottom connection).
Each parcel has corresponding attributes A.
This grammar represents a compact model description. It
can be used in an algorithmic way to produce new objects,
ie. new parcel aggregations. Given a startparcel, new par-
cel are generated by applying the rules of the grammar. An
example is given in the next subsection. On the other hand,
the grammar can be used to object recognition: if an un-
known object can be explained by the grammar, then it is
recognized.