Make your own free website on Tripod.com
 Russian
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).

Fig12
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.