APPENDIX
1.6.A. Estimation of the Bell-Approximation Resolution.
Let's
consider the simplest case of two parallel segments placed on distance 2*x_0
from each other. The cross-section of the considered picture is shown on
fig.5a. On this picture the position of the approximating segment axial
line is determined by parameter x. In this case
Where k - number
of points in each segment.
Extrema of such
measure are determined by zero values of its derivative:
The denominator
of resulting expression is positive at any values of entering variables.
The numerator can be transformed to the view
This equation
has five solutions, one of which is x_1 = 0, and four others :
Two solutions
which are determined by a difference of the expressions placed under sign
of exterior square root, have imaginary values at any values of entering
variables (as x_0> 0, under the initial agreement - see fig.5a). Others
two have real values, when
Simplifying this
expression, we shall obtain that at D < sqrt(3)*x_0 investigated conformity
function has three extremums: one central and two symmetric side ones.
It is easy to show, that:
It is obvious,
if D < sqrt(3)*x_0, then S"(x)|_0 > 0, i.e. the central extremum is
a local minimum of considered conformity function of and, hence, adjacent
side exremums are local maximums of this function (see fig.5b). At D >
sqrt(3)*x_0, these maximums merge in one (see fig.5c). Positions of maximums
depending on a value of parameter D are shown on fig.5d (see the formula
for an evaluation of x_2... x_5).
1.7.A. Adding to
the Problem of the Automatic Correction of the Width of the Membership Function.
As it is affirmed,
the maximum of the function of conformity that is determined by expression
is reached at
the finite value of parameter D, when the exponent in which it is raised
in numerator - g (governing the amplitude growth rate) lays in the interval
1 < g < 2.
Let's prove this
statement.
Let's consider
an approximated segment (see fig.6b) as a continuous point set. In this
case the conformity measure is determined by an integral
Here the variable
v = d is entered to avoid confusion with differential label. The behaviour
of this measure depending on width of membership functions is defined by
a derivative on D:
Equating this
expression to zero, and introducing the variable gamma = V/D, we obtain:
In a range of
interest for us (0 < gamma < oo) this function has the maximum value
2 at gamma = 0 and asymptotically comes nearer to 1 at gamma -> oo (see
fig.6d).
|
Fig.6d
|
Its decrease
monotonicity is confirmed by that its derivative everywhere is negative
in the interval 0 < gamma < oo:
A graph of the inverse
function D/V=1/gamma (g), our actual subject of interest, is represented
on fig.6c. This graph shows, what will be the width of memberships functions
(in comparison with the flowing relative width of the approximated segment)
at reaching by the considered conformity measure of its maximum value depending
on index g, governing amplitude growth rate of memberships functions.
2.2.A. Choice of
the Step of the Start Positions for the Procedure of the Contour Boundary
Representation in Terms of the Contiguous Segments.
A beforehand
value of the least radius of neighbourhoods R_min among radii of neighbourhoods
R_c of all contour segments of the treated image was estimated. The radius
of the neighbourhood is a radius of the greatest circle with the center
on the given segment, intercrossed by it and not containing points of other
segments (fig.27).
|
Fig.27
|
Parameters of
X, Y initial sets were defined by nodes of some grid on the image plane.
Density of the grid was chosen so that in any circle in radius R_min/2
one node of this grid hitted even. In the case of a square grid its step
should be less, than R_min/sqrt(2). Remaining parameters were prescribed
identical to all sets. A value of parameter B corresponding to length of
initial contiguous segments was chosen smaller than (R_min/2)*sqrt(3). This
choice is caused by the obtained theoretical estimation for a resolving power
of the suggested approximation method. Parameter D was chosen equal 0.5*B,
A - arbitrary, P1 = P2 = 0.
2.2.B. Particularities
of the Gradiet Procedure of the Local Maximum Detection of the Bell-Conformity.
During
the given work several gradient procedures of search of local extremums
have been tested. Their principal means consist in deployment of
the frame corresponding to displacement of the central point of an approximating
segment, along ridges of the conformity function. A characteristic example
- the procedure circumscribed in [34].
However, use of such universal (that is why rather bulky) procedures does
not justify itself in a situation when the preliminary count of specificity
of the variables is possible,that simplifies extremum search. Specificity
of the variables consists here in their well defined hierarchy. First of
all the angle and cross position of a contiguous segment are arranged, a
after them - parameters of branches. And only then moving in the longitudinal
direction is carried out.
Such specificity
of variables has allowed to use effectively at the second stage of experiments
the gradient procedure in which moving on all variables of eight-parametrical
conformity measure is carried out simultaneously and basically is independent.
During searching delays are possible (misses of steps on some variables)
if parameters with higher priority were not arranged yet. In final variant
the following system of priorities was used: (+, A), (P1, P2), (D), (B1,
B2, =) where - "+" and "=" designate moving in cross and longitudinal directions
accordingly. The step on any variable increases half (with the count of restriction
on maximum value - see further) if the it is executed in the same direction,
as previous, and decreases otherwise. Thus it is considered, that those variables
were arranged, the step on which became less, than 1/4 from the maximum admissible
value on the given variable.
The last values
were chosen from the most common reasons so that as a result of each step
the new approximating segment not too overstepped the bounds of old onethe.
Steps in a longitudinal direction (and on length of the branches) were limited
to value B/2, and in cross - D/2. Steps on the angle and curvature should
not oscillate ends of the segment on value bigger than D/2, i.e. 
A*MAX(B1, B2)/0.7 and
P * (B/0.7)/2 should not exceed D/2. In order to prevent discretization
disclosures of analysed contours, the value of parameter D was limited
from below to the value ranging 0.5 - 2.5 distances between adjacent points
of the raster. From above parameter D was limited by value B/2.
Particularly
such restrictions are organized so, that at the approach to one of them
it is authorized to make the following step only on half of the distance
before this restriction. It simply enough ensures a possibility of increase
of a step if a necessity of movement in the opposite direction exists.
Initial steps on separate components were chosen equal to the half of their
greatest possible values. Thus initial values of parameters B and D were
accepted equal 10 and 4 accordingly, and as much as the possible admissible
step value on D equal 0.5. Search procedure of the next conformity measure
maximum stopped when steps on all variables became smaller, than 0.2 of their
maximum possible admissible values.
As a rule, search
of the maximums corresponding to contour segments required on the average
60-80 steps on theof declination angle and position in the cross direction
at 8-12 steps in the longitudinal direction.
2.2.C. Estimation of quality - filling ratio of
contiguous segments.
The property
of filling ratio of a resulting segment is defined as follows:
Where
t_1, t_2... t_m
- coordinates of points of the raster;
E (t_i, h) -
|
membership function which is determined
by parameters of the found maximum
(h = {X, Y, A, D, P1, P2, B1, B2});
|
e (t_i) -
|
the indicator function marking contour
points:
= 1 if the
given raster point is included into the number of contour points;
= 0, otherwise.
|
In the first
series of experiments those segments were only considered acceptable which
have filling ratio over 0.5.
According to
sparsed representation, the filling ratio criterion of contiguous segments
was modified also. The essence of such modification consists in the following.
The axial line of a tested segment is divided into the intervals equal to
a step of tracking of contour boundaries. Within the limits of each interval
there is the contour point nearest to the axial line. Values of memberships
functions to these points are summarized, and the obtained outcome is divided
on the greatest possible value of this sum when within the limits of each
interval there is a point laying on the segment axial line. In the second
series of experiments the segments which filling ratio exceeded 0.8 were
considered as acceptable ones.
2.2.D. Additional
techniques.
To
avoid a repeated finding of segments and to simplify searching less expressed
maximums,
the contour
points laying inside the image piece corresponding the found segment, were
excluded from the further reviewing. Each of such pieces represents a corridor
in width 2D/0.7, enclosing the axial line of the given segment; length of
branches of this corridor - B1/0.7 and B2/0.7 (fig.9).
|
Fig.9
|
To avoid superfluous losses
of time, the operation of rough choice of the contour points concerning
to the flowing contiguous segment was applied. In the beginning for an evaluation
of coincidence measure gradient of chosen contour points (the list of references
to their initial set is formed) which lay inside a wide rectangle enclosing
the contiguous segment in its flowing position (such neighbourhood is shown
by fat primes on fig.12).
|
Fig.12
|
Further, on each step a
possibility of build-up of new, narrower neighbourhood for a flowing
position of the contiguous segment (thin primes on fig.12), not passing
out of former wide neighbourhood is checked. If it is impossible, a list
of references is made on a new wide neighbourhood.
Operations
of deletion and preliminary choice have not only engineering sense.
A solution of basic problems depends on their organization too. In particular,
ability of the procedure to understand complicated situations depends on
their organization, - at processing of false concentrations of contour
points, in the case of capture of several segments. In similar cases
the number of steps noticeably increased (sometimes so, that it was necessary
to discontinue compulsorily process of searching). Detection of such situations
was carried out by criterion of filling ratio of resulting segments by contour
points. An example of such situation is shown on fig.11. On this picture
it is shown the initial (dotted line) and finite (solid line) positions of
the contiguous segment, corresponding to process of search of one local maximum.
Apparently, the right branch of the initial contiguous segment has not had
time to be rounded along the corresponding piece of the contour line
and intersected an adjacent contour.
|
Fig.11
|
Thus it is obvious, that
deletion of the piece of image corresponding to the finite position of such
segment is wrongful. The contiguous segments started from other initial
positions can correctly interpret an observed picture. The solution accepted
in this occasion is based on this reason. The elementary contours laying
in a neighbourhood of the contour movement from which led to an unacceptable
segment, were excluded from candidates in initial approximations. So the
situation shown on fig.11, for example, was treated - as an initial approximation
the elementary segment was chosen, the distance from which up to an outside
contour exceeded the corresponding distance for the initial segment which
had led to false outcome.
This example illustrates
common logic of solution of complicated situations. To solve them
it is necessary to begin from the outside - from the "free" ends of
entering lines.
3.5.A. Some Details
of the Procedure of the Accumulation of the Hypotheses.
In the
program realizing hypotheses accumulation procedure information only about
the marked zones is stored. For this purpose some array is assigned, the
entry in which is made with help of L-hashing [35] at which zone number is a key, and
the hashing function is a remainder of division of zone number on array size.
In the carried out experiments this array consisted of 4096 cells. Thus the
initial search address of the cell corresponding to a zone with given number
(hashing function) was obtained by zeroing of top digits of this number
(since 13-th). In each cell, except for a zone key (number in a common hypothetical
three-dimensional array of the zones), a reference to a description of the
given zone is stored. The zone description too is one cell of some array
in which the bites are marked corresponding to numbers of those hypograms
which marked the given zone. Thus the zone mark with a separate hypogram
is reduced to logic addition of its descriptions to the cell in which bite
is marked that corresponds to the current hypogram number(an array of such
cells is prepared beforehand). After the termination of marking process with
all hypograms, operation of transformation of contents of each description
into number of hypograms which marked it (for each description it is one
machine command by estimation of units in the given cell) is started.
At execution
of smoothing procedure numbers of neighboring zones are not calculated anew
but d are calculated by addition to components translating the number of
the central zone into number of one of 27 adjacent zones (3x3x3). These
components are calculated beforehand. The logic of their evaluation is defined
by logic of an evaluation of common linear number of an element (zone) in
a multivariate (three-dimensional) array.
To reduce number
of contiguous segments tracing a reference contour at build-up of its hypogram,
the next reference hypogram points are under construction on a forward branch
of last contiguous segment. It is possible to tell, that on this branch
the fictitious tangential contiguous segment moves ahead, and in its frame
positions of the basis vector are registered. The boundary of such construction
is defined by mismatch of positions of the basis vector in frames of actual
and fictitious segments. Thus a movement step of actual segments is continuously
arranged with the help of feed-back so that to keep the mismatch value within
the limits of a zone quarter, and a step of fictitious segments have to
keep adjacent points of the reference hypogram within the limits of one zone.
The zone, as well as earlier, is meant as an element of subdivision of parametrical
space. If it is not possible to be made, it is accepted, that in this place
the hypogram has a rupture and its construction proceeds from other place
of the standard contour.
3.5.B. Illustration
rationality of smoothing operation.
|
Fig.26
|
The initial histogram of
the most powerful cluster (fig.24a and fig.26b) is shown on fig.26a. Here
weight of the zone is a number of hypograms marking its. Rationality of
smoothing operation in this case is confirmed by a view of the initial
histogram of the same cluster at size of zones reduced in one and a half
time (fig.26c). Thus also the centers of zones of the space of search parameters
accordingly have somewhat moved. This example shows that relatively big
weight of a collateral ejection (fig.26a) is caused, first of all, by accidents
of distribution of hypogram points within the limits of adjacent zones.
In [3] the operation of multiple smoothing
has been suggested. In this case smoothing is done{made} iterativelly until
the condition will be satisfied that at two sequential stages the same zone
(besides the unique one) has the maximum sum (among all zones at the given
stage). The center of this zone is accepted as a search cluster point. Though
such the procedure has not shown crucial advantages in comparison with once
made smoothing, it is expedient to have its in a collection of tools of the
analysis of hypogram intersection. Multiple smoothing will coordinate a
cluster point (zone) with its environment. If this point is on a cluster
boundary it is gradually shifted in its center. The stability of this point
(zone) at several sequential stages of smoothing is some performance of
its common reliability. Besides, if the cluster top is not acute, i.e. consists
of several zones that (due to the count of neighboring zones) one zone of
maximum weight will be allocated which position will depend on a context
(i.e. weightinesses of enclosing zones).
In last version
of program realization of hypotheses accumulation process an attempt has
been undertaken to limit an amount of the zones participating in the subsequent
procedure of smoothing. For this purpose so-called areas of intersection
were selected, which represent set of the zones marked more than two hypograms,
and also one time marked zones directly adjoining to this set (the neighbourhood,
as well as earlier, the nearest 3*3*3). However, in spite of the fact that,
for example in the circumscribed experiment, execution time of the smoothing
procedure on the average was reduced with 1.5 up to 0.5 s, it was additionally
required about 0.5 s for detection of these areas (thus the number of analysed
zones was reduced on the average in 5 times). Probably, this procedure will
have essential advantages at more rigid restrictions on entrance in an area
of intersection. Naturally, the operation of restriction of number of analysed
zones has an essential importance at multiply repeated smoothing.