Make your own free website on Tripod.com
Russian
1. BELL-APPROXIMATION

In this section the author considers the problem of jam-resistant segmentation of simplest contour figures consisting of straight-line segments.
1.1. - Physics of the base procedure of this problem - root-mean-square approximation is researched. The problem of such approximation - is interpreted in the descriptive terms of force and potential. The phenomenon of drawing off of approximating segments with extraneous contour points is accentuated.
1.2. - A general incorrectness - "sharpness" of an usual correction way of this disadvantage by means of threshold limitation of acceptible deviation is underlined.
1.3. - To correct this, it is suggested to use a gently bell-like function for an estimation of degree of a membership of contour points to an individual segment. Such function represents a smooth function trending to zero at increase of deviation from axial line of an approximating segment.
1.4. - Applying it, a measure of integral "fuzzy" confirmation of this segment with contour points is determined. As a resust, the problems of segmentation of contour configuration into individual segments and their approximation are commonly reduced to search of local maxima of such the measure. This method is named as bell-approximation.
1.5. - The place of the bell-approximation method among procedures of structural representation of linear images is considered.
1.6., 1.7. - The common guidelines on definition of the main parameter of bell-like membership function (steepness of its slopes, i.e. its width) are given.

1.1. PHIYSICS OF APPROXIMATION.

The majority of methods, algorithms and procedures of actual dada analysis are based on a search of minimum of root-mean-square deviation.  Root-mean-square approximation is classic in the analysis of experimental data. It "smoothes", averages a random dispersion of the obtained data. It determines their main - interference resistant - characteristics. With its help their generalized semantic images - models are selected.

However, the root-mean-square approximation, at the careless application, can to average - to generalize, what to average - to generalize basically does not correctly. Namely, it refers to not random, not statistical, but "individual" interferences. Let's suppose, it is necessary to solve the simplest problem of approximation of a point set with a straightline segment. Besides the view field takes not only the points belonging to individual segment, but also points adjacent to its neighborouh. In the similar case we shall obtain a senseless averaging - "planning" of a corner with a secant - fig.1A.


Fig.1A


Let's consider physical essence of this phenomenon. The formal statement of the given problem is determined by following expression:

 
Where
h   - 
the parameters determining the position of a segment;
H   -
area of admissible values of parameters h;
n   -
the number of points of an approximated set;
d_i -
a deviation of an isolated point from an axial line of a segment (fig.1B).


Fig.1B
The common character of the solved problem - the position of sought minima will not vary, if to omit the normalizing factor 1/n, and also the radical, playing the similar role. The formal expression will be simplified:
 
This problem can be interpreted as a problem of search of the minimum of potential energy of some physical system. This system is formed by a set of the motionless charged points and the thin mobile rod creating a some field around. In this case the potential of the field is proportional to quadrate of deviation from an axial line of the rod (fig.1a), and the energy is defined as the sum of potential values in those points.



Fig.1ab
The graph of this function obviously illustrates - be however strong influence remote - outside points on outcome of solved problem can. More precisely to estimate force of this influence, - we shall pass from integral - a potential picture, - to differential - force. Forces from which the field acts on charges, are defined by a strength of a field, that is in turn defined by a velocity of its decreasing. In this case the strength inversely proportional to a deviation from axial line of rod, - derivative of "x-square" with minus (fig.1b). The problem of searching of potential energy minimum is reduced to search of the rod position at which, forces acting on it are mutually counterbalanced. In our case, - the further point is from the rod the more force from which it attracts this point to itself (and, naturally, on the contrary).

Basically it should be so. At approximation the model should be tightened to the remoted points. However, all this defines the desirable outcome if the approximated points lay on the true places (defined by a form of model) or are scattered integrally symmetrically (in particular, under the normal law). Otherwise, as it was already marked, outside points can deform essentially necessary outcome, having led away an approximating segment on themselves.

Fig.1A illustrates this. The axial line of approximating segment is removed on a barycentre of the approximated set (if to consider this picture from the viewpoint of its projections to the direction, perpendicular to the axial line).
From physics it is know - as far as strongly can withdraw this center even small, single, but far located "weights"...

1.2. ORDINARY WAY OF FUNCTIONAL CORRECTION.

To avoid towing away influence of outside points, they usually limit area of an attraction of an approximating segment in some threshold distance (fig. 1c). However, such mode of restriction of influence of the remote points leads in substantional difficulties at build-up of steady procedures of approximation of actual data. In this case the points having the greatest attractive force, render jump-like influence on a position of approximating model.

Fig.1c


Outcomes of approximation are very sensitive to a choice of a threshold of a maximum deviation. In practice it is impossible to choose a threshold of the maximum deviation at which simultaneously there would be no the false subdivision of approximating segments caused by casual ejections, or cuts (averages) of not clear expressed angles of analysis contours. The outcome of application of root-mean-square approximation with threshold restriction of the maximum deviation [1] is shown in figure below. Here it is possible to find examples of both situations. And this best, that it was possible to obtain.


Fig.10c
 

1.3. ESSENTIAL MOTIVATION OF ADVANCED CORRECTION.

The force interpretation of the approximation problem directly prompts a natural exit from this situation. It is necessary to pass from the orthodox threshold limitation of influence (attraction) of remote points (Fig.1c) to gradual smooth one (Fig.1d).


Fig1d_  
Fig.1d,d_
In the frame of the such force dependence should will be solved a task of search of balance position in actual conditions, - at presence of essential interferences as which points neighboring - extraneous objects can act.
Let's look as this task in the frame of more conventional - potential - interpretation. We shall look at qualitatively process of integration of smooth force function. At the beginning, the integrated function will be gradually, with acceleration, increases (Fig.1d_), according to monotonous increase in the absolute size of force. The maximal speed of increase - the maximum of a steepness of integrated function, will be determined by a maximum - the top limit of force function. Then speed of increase will decrease up to zero; - in a point of intersection of the force function through zero. Then, the integral will smoothly fall, with acceleration, - the maximum of the
falling speed responds the bottom limit of force function. Then, integrated function will be smoothly, with deceleration, asymptotically to come nearer to the initial zero value. As a whole, it turns out a bell-like dependence (Fig.1d_). A potential function turns out from the obtained by its inverting (Fig.1e).
Fig1e
Fig.1e
It is done because the potential falls in the direction of force, therefore at integration its value it is necessary to take with minus, or then to invert the result (that has been chosen for greater presentation of the integration process).
Total potential energy of the system now is determined as the sum of values of such potential in approximated points. Minimization of this in the
its total value  gives a required decision of the approximation task based on gradual restriction of the influence of removed points.
An inverse bell-like function may be obtained directly from parabolas also (fig.1a), by unbending of its branches to some horizontal ceiling (Fig1a_).
Fig1a_
Fig.1a_
 It is on the base that fare points must be equally indifferent ones. / Such it was obtained in primary. / The application herein the force - differential - interpretation enables more distinctly formulating the problem and explain essentiality of its solving. Instead of reasoning about some ceiling, it is defined that force attraction must have a tendency to zero under increasing deviation. A force interpretation too more stringently explains the approximation role of the central part of potential curve (of  parabolas rest - potential pit).    Instead of (in addition to) reasoning about that points must roll down on its bottom,  it is given a direct representation about attracting force - it must be inversely proportional to deviation with changing of sign in pass through zero. In the frame of force interpretation it is logically easier to linke the root-mean-square approximation and threshold admittance of allowed deviation (Fig.1c).
Now we shall return the approximation problem from field of physical representations into its initial geometrical "surrounding". In geometry it is mote naturally to consider the points located closer to an approximating image (closer to the axial line of an approximating segment) with more "weighty - valuable", and - on the contrary farther - less "valuable". To result the physical interpretation in conformity with this position, it must be "inverted". At first, it is necessary to pass from the invert bell-like function to direct bell-like dependence (Fig.1f).

Fig.1f
Besides, the interpretation of the last one as functions rating a degree of membership of the  points to an approximating image (segment) is most natural. Secondly, it is necessary to pass from search of a minimum of a general rating functional to search of its maximum. The functional can be commented as a measure of "hit", "coincidence", "similarity", "confirmation" or "conformity" of approximating image. Other positive associations - opposite to negative term of deviation - are possible also.
 
It is possible to reach a bell-like membership function also directly by "smoothing" - "melting" of  -like - threshold function (Fig.1f_).
Fig1f_
Fig.1f_
However, additional explanations about the functional roles of various pieces of this smoothing are needed. First of all, it is necessary to pay attention to approximation role that begins to play center - top of such  smoothing. All these roles are directly illustrated by force interpretation. The force interpretation links together the operation principles of root-mean-square approximation, threshold limitation of permissible deviation,  -like membership function and their development - bell-like estimation of this membership. The force interpretation instead of a series of generally accepted reservations gives herein descriptive - force - causal sections.




1.4. GENERAL STATEMENT OF THE PROBLEM.


In a most general view the offered statement of the approximation problem of some point set by a line segment looks like this:
 
Where
h    -
the parameters defining the position and orientation of a segment (generally, and its shape);
H    -
area of admissible values of parameters h;
T(h) -     
subset of points of images, belonging to individual approximating segment (some ideal image of this segment, - "band" of points ambient its axial line);
T_o  -
set of contour points detected on the image;
S    -
measure of geometrical conformity of T(h) set (image) to T_o set.
 
In the present case this measure is calculated as follows:
 
Where
E(t,T(h)) -  the function indicating a degree of membership of an isolated point t to T(h) subset (here is meant, that the image is set with points of some discrete retina, on which it is projected).

The particularity of offered conformity measure is, that at its construction the bell-like membership function is used.
The provisional view of such function (axonometric projection), for a case of approximation by a straight line, is shown on fig.2a.

 
Fig.2

In the given work one of the simplest analytical expressions for such functions was used:
 

Where

d -
value of a deviation from the axial line of an approximating segment which position is defined by parameters h;
D -       
defines a deviation at which the value of function of a membership decreases twice (further the double value of such deviation we shall name its width).

The cross-section of a set of the bell-like functions defined by this expression is shown on fig.2b.

Further alongside with the term bell-like we shall use also the term fuzzy, proposed in [4] as a generalizing title for a similar sort of functions.

Mathematical expression for a general measure of geometrical conformity, basing on the expression of fuzzy membership function accepted in the given work, as a whole has the following view:


Were

h    -
parameters defining a position of an approximating segment,
T_o  -
a set of chosen contour points,
d_t  -
a deviation of the point - t from an approximating segment.

Thus, mathematical expression of such measure, for a case of approximation by straight lines, is defined as follows:

 

Where

teta    -
declination of the perpendicular radius-vector let down from the center of coordinates on an approximating line (fig.3a),
ro    -
length of this vector,
d_i  -
a deviation of i-th contour point from the axial line
= x_i * cos(teta ) + y_i * sin(teta ) - ro ,
x_i, y_i  -

coordinates of a point,

n    -
number of contour points.

Hereinafter in terms of a conformity measure we shall omit (implying its presence) parameter T_o designating a set of contour points.

Fig3  
Fig.3

The problem of approximation here is reduced to searching local maximums of such measure of the identity built with the count of all contour points. Lines of levels of this function, for a contour image of an angle (fig.3a), are shown on fig.3b. To improve a visibility of the obtained picture (to not cut maximums on teta = 0), it conventionally starts, that the length of a radius-vector can have a negative value that corresponds its to declination 
teta + pi. In the upper part fig.3a, the cross cut of used function of a membership is shown.
As it is visible, each segment of the initial picture here is respected with the local maximum of "gently selective" measure of geometrical conformity.

The similar example for a contour image of a rectangle is shown on fig.4.
Fig4
Fig.4


Further, measure conformity built-up on base of bell-like function will be named also as bell-conformity analogously as procedure of finding the maxims of such measure - bell-approximation.



1.5. BELL-APPROXIMATION IN THE CONTOUR BOUNDARY DESCRIPTION.

Naturally, the search of local maximums of the geometrical conformity, based on bell-like membership function, represents in essence a more complicated problem, than classical search of a root-mean-square deviation minimum. It is defined by simplicity of a parabola in comparison with a handbell. In particular, there is an analytical solution for approximation by straight lines. One of examples of an analytical solution of the searh problem for the minimum of a root-mean-square deviation is the Hueckel's operator [5, 6], used in the present work for the search of elementary contour edges on half-tone pictures. Besides it is known, many cases of effective realization of the search process for maximums of mutual correlation for patterns of various kind (thus, in essence, the minimum of a root-mean-square deviation is searched [7]).

Therefore, in general the desire to remain, whenever possible, within the framework of the problem solution (i.e finding of the minimum of a pure root-mean-square deviationis) is natural.

However, the minimum of a standard deviation as it has been shown, inherently reflects globally averaged conformity of the model (a tried on pattern) with analysis pattern. In this case the conformity measure monotonically decreases with increase of a deviation of any element of the analysed pattern from a corresponding element of the tried on model.

Derivation of the adequate description of any picture with the help of such conformity measure can be obtained only in a case when among compared models there is a model of all analysed pattern. In this case, minimizing a summarized deviation, we can obtain search outcome, i.e. to find a corresponding model. Otherwise, we shall obtain an averaging of an analysed pattern of one of available models that can not have anything common with necessary outcome - an adequate description of the given pattern or even of its part.

Effectiveness of use of the criterion of summarized (root-mean-square) deviation directly depends on as far as we can legiblly select an approximated pattern from its environment or as far as we can fully reflect an analysed picture with any integral model. From this viewpoint it is possible to select two approaches in a solution of the problem of the description of pictures of various kind on the basis of minimization of a root-mean-square deviation:

- Sequential independent detection and approximation of individual included as the parts in the analysed picture [1, 5, 6, 13], in particular, of separate segments of contour boundaries.

- Approximation of input data with integral models (see, for example, [8 - 12]), in particular, contour boundaries with chains of segments;

Adequacy descriptions obtained on the basis of last approach to theanalysed pictures is ensured, first of all, with that here elements (points) of input data in a result will be distributed between corresponding elements (segments) of tried on models and will not render so negative towing away influence on adjacent elements (segments) of the tried on model. For example, if to approximate an angle (see fig.1A, fig.3) with a corresponding integral model (a chain of two segments), basically, it is possible to obtain an adequate outcome even within the framework of pure standard approximation.

However, such approach is effective only as fine tuning when a priori there is an initial approximation - a model already enough well reflecting an analysed picture, a model which needs to be ajusted only. The prerogative of definition of such initial models remains behind the first approach - sequential contextual independent detection and approximation of separate subpatterns.

In a solution of this problem, in turn, also it is possible to select two approaches, depending on a detection mode of elements belonging to separate subpatterns:

- A priori detection - unguided by tried on models during approximation [5, 6, 13];

- Detection controlled during approximation (see, for example, [1]), - a rejection of the elements allocated far from corresponding elements of the tried on model.

A virtue of the first approach consists that at its application the root-mean-square approximation is used in the pure view, with computing simplicity implying from here. However, such approach can be used only for representation of analysed pictures with the simplest ones , i.e. with elementary patterns. These patterns should represent adequately enough any arbitrarily chosen piece of a described picture (anyway,the majority of such pieces). Such requirement can be satisfied only for representation in terms of the simplest patterns were at a discretization level of the representation of input data. For images such elements are pieces of several raster points (about 5 - 10). Only on such pieces, contour boundaries with an adequate accuracy can be described by rectilinear segments - the simplest universal patterns in which terms the arbitrary contour configuration basically can be circumscribed.

A virtue of the second approach is the possibility to work with the extended patterns giving more intelligent description of analysed pictures. However, in this case the solution technics of the approximation problem becomes essentially complicated. The problem becomes multiextreme, demanding basically for its solution to use the initial approximations obtained outside of this approach. Besides, an usual use of the threshold memberships functions leads to instability of the approximation process...

And if the problem of choice of initial approximations basically is solved on the base of the first approach - detections of the simplest patterns - the problem of incorrectness of threshold rejection of outside points till now practically was not solved.

Here the bell-like (fuzzy) memberships functions play the main role. Replacement of threshold function on the bell-like one, at build-up of the conformity measure of approximating models (segments) and described data (contour boundaries), allows to loose criticality at definition of a membership of elements of input data to an individual approximated pattern. The bell-like memberships functions smooths ruptures of the conformity function caused by discretization of representation of contour boundaries, and also by random interferences that allows to apply simple gradient procedures at search of its extremums. Besides,expansion of the foundation of searched maximums (caused by branches the of bell-like memberships functions) causes smaller criticality in a choice of initial approximations. Experiments (including ones with actualon) have confirmed validity of these ideads (see section 2.2.).

As a whole, the analysis of particularities of various approaches to a solution of the problem of approximation of contour boundaries leads to a conclusion about expediency of their complex, sequential use. In the beginning, with the help of procedures of pure root-mean-square approximation the contour image can be described in terms of the simplest linear elements. Then, best of them (values of a deviation defined by minimum values) should be used as initial approximations for the subsequent procedure of maximization of the "gently selective" conformity measure, obtaining in outcome the description with extended segments. Then, in a case of need, it is possible to arrange parameters of these segments as an integral set, redistributing contour points between them.

In conclusion of this chapter it is necessary to point on common methodological virtues of the concept of bell-like - fuzzy - memberships functions. Basically, in the problem of the description of real contours, application of probability estimations of a membership of contour points to an individual pattern [14, 15, 16] is possible. However, as the experiments show, the statistical model of contour boundaries (being the base of this approach) in which signals are rectangular edges (ideal segments), deformed by normal noise, is the theoretical idealization rather far from the reality. Actual distortions of contour boundaries are various curvatures, stains, extractions, etc. which count in statistical models calls essential difficulties, and abstract from the essence of the solved problem. The essence of this problem in this case consists in leading an approximating segment on the axial line of the representatede piece of contour boundaries, with correct restriction of influence of outside points.

The solution of the problem of description of contour boundaries in terms of segments of axial lines as problems of search of maximums of bell-conformity, with postulation of fuzzy - bell-like memberships functions, seems to be more fruitful, than designing of strict models of researched signals. Thus, concerning these signals the most common properties are assumed only, namely - a significant sparseness of a set of segments of lines , each of which can be deformed by individual ejections, curvatures, etc.

Told above it is possible to supplement with the statement expressed in work [17] : "... Inclining of many contributors that the theory of statistical solutions gives any more strict and objective classification, than other algorithms of a decision making, is formalistic fallacy... The objective measure (proximity) is not present due to subjective character of statement of the problem of pattern recognition... More important, evidently, is the problem on simplicity of definition of of proximity (conformity) measure...". For many problems there is enough to use concepts of fuzzy (bell-like) memberships functions and based on it a measure of geometrical conformity, as, for example, in the Thus, build-up and modification of procedures of segmentation-approximations become much simpler.

For example, quite naturally the necessary on the course of problem solution changes of memberships functions width and illegibility of ends of the approximating segments (see the subsequent sections), are introduced naturally enough.


1.6. CHOICE OF THE WIDTH OF THE BELL-LIKE MEMBERSHIP FUNCTION.

One of the basic problems at use of fuzzy membership function is the choice its width. Obviously, the less width of function of a membership, the more precisely resulting axial lines correspond contour segments. However with decrease of this value the collateral local maximums caused by a discretization of representation and interferences can appear, and their occurrence far from the basic (search) maximums is the most probable.

Deriving of any strict analytical estimations describing these phenomena generally, is represented rather by a complicated problem. Here, obviously, experimental researches should play the principal role. As rough estimations it is possible to use outcomes of the analysis of the simplest case, namely a case of two parallel segments. The cross-section of the given picture is shown on fig.5a. The position of segments here is determined by points x0 and -x0, and the position of the axial line of an approximating segment is determined by parameter x.


Fig.5a      

The analytical researches, which have been carried out on the basis of proposed expression of function of a membership, have shown, that the conformity function in this case has the separate maximums corresponding two parallel segments if the width of membership function has value smaller than the distance between these segments, enlarged in sqrt(3) times (fig.5b).


Fig.5b    

If it not so, the maximums merge in one (fig.5c). The proof of this statement is reduced in Appendix 1.6.A.


Fig.5c    

Positions of maximums depending on a value of parameter D are shown on fig.5d. In this figure to keep correspondence of the horizontal axis to the previous figures, explanatory variable D is registered on the vertical axis. The error of an estimation of a position of search segments on maximums of the considered conformity measure sharply decreases with decrease of width of the.membership function. For example, already at D < x_0 does not exceed 0.1 values of distance between segments, and at D < 0.5*x_0 - 0.01 same values.


Fig.5d    

The exibited outcomes of analytical researches allow to estimate conditions of confluence of adjacent points of approximated contours. At width of the membership function exceeding a step of representation discretization of researched contour segments more than in sqrt(3) times, the conformity function will have one common local maximum for each two adjacent points, even at transition of an approximating line is perpendicular to a segment connecting these points.


1.7. AUTOMATIC CORRECTION OF THE WIDTH
 OF MEMBERSHIP FUNCTION.


As a whole, the organization of search process of local maximums of a bell-conformity measure at which the width of the membership function varies during searching seems to be natural. In the beginning it is necessary to set its enough the big segments providing only divisibility, and then to reduce its according to decrease of a mismatch between the axial line and a represented contour segment. Such organization of the process should provide a high exactitude of an estimation of a position of contour segments and thus to reduce probability of a finding of false maximums. In this case the initial width may be chosen rather approximately, being guided by the simplest obtained estimations for a resolving power of a bell-approximation.

Correction of the membership function is suggested to be realized by direct introduction of its width in the number of search parameters of conformity measure and a use of such membership function at which the amplitude at its width decrease will increase (fig.6a):

For7
Fig6a

Fig.6a

In a result, the expression defining the conformity measure obtains the following view:


In this case, at each fixed declination of the axial line, the local maximum of such measure is reached at D = 0.7*V, where V - a relative half-width of a representation segment (half of length its projections to a direction, perpendicular to a flowing direction of the axial line, fig.6b). During search of the next maximum of such conformity with decrease of a mismatch between a represantation segment and the axial line a width of membership function will decrease accordingly, ensuring thus a necessary exactitude of definition of a segment position.

Fig6b  
Fig.6b

Such measure of a conformity feels a relative segment width. It is related to that now, at increase of the width of membership function simultaneously with increase of the contribution of the remouted points in the value of conformity function, the contribution of the points close to the axial line decreases. And the equilibrium between changes of these contributions occurs at a final value of parameter D, when the numerator in expression for the conformity measure of D\g (governing growth rate of amplitude) has the exponent laying in an interval 1 <g <2 (fig.6c).



Fig6c  
Fig.6c

Here the graph of values of ratio D/V, at which the conformity measure has the maximum value depending on parameter g, is shown. This statement is proved in Appendix 1.7.A. In the given work the value of an exponent g = 3/2 was used, that simplifies evaluations and leads in steady tracing behind a relative segment width. Thus, as it was already marked, D = 0.7*V.







* * *
According to scientific elaboration canons here must be represent the results of experiments. But it was be clear that bell-approximation potential in principal higher then simple work with straight-line segments. It is was adopted solution to developed of it for arbitrary shaped contours approximation, and further carry out proper experiments. The next section illustrates such development and such experiments.