Fig.1A
| Russian |
|
|
|
Fig.1A |
| 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 |
|
|
| Fig.1ab |
|
| 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 |
|
|
| Fig.1d,d_ |
|
| Fig.1e |
An inverse bell-like function may be obtained directly from parabolas also (fig.1a), by unbending of its branches to some horizontal ceiling (Fig1a_).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).
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).
Fig.1a_
|
| Fig.1f |
It is possible to reach a bell-like membership function also directly by "smoothing" - "melting" of-like - threshold function (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,
Fig.1f_
| 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. |
|
| Fig.2 |
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.
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
- |
declination of the perpendicular
radius-vector let down from the
center of coordinates on an approximating line (fig.3a),
|
- |
length of this vector, |
| d_i - |
a deviation of i-th contour
point from the axial line = x_i * cos(
) + y_i * sin(
) -
, |
| 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.
|
| Fig.3 |
= 0), it conventionally starts, that the
length of a radius-vector can have a negative
value that corresponds its to declination
+ pi. In the upper part fig.3a, the cross
cut of used function of a membership is shown.
|
| Fig.4 |
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.
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.
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):
|
|
| Fig.6a |
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.
|
| 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).
|
| 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.