Russian |
|
Fig.7 |
These reasons
also have underlain a suggested method of the description of contour
boundaries in terms of segments with fuzzy ends. In the carried out
researches as axial lines of approximating segments curves of the simplest
analytical type, namely - the central pieces of parabolas were used.
And each branch could have own curvature. For fine length tuning of
branches the mechanism similar to fine tuning of width of segments
was used. The conformity measure builted according to these reasons,
has the following mathematical expression:
Where
b_i, d_i - |
the parameters defining a position of
a contour point in own frame of an approximating segment (fig.8);
these parameters are defined on coordinates of the point x_i, y_i
with the help of transformations |
b_i = (x_i
- X)*cos(A) + (y_i - Y)*sin(A), |
|
d_i = - (x_i - X)*sin(A) + (y_i - Y)*cos(A); |
|
Fig.8 |
X,Y - |
coordinates of the center of the segment; |
A - |
the angle of declination of the segment;
|
P = |
P1, if b_i >= 0 (curvature
of the right branch), P2, if b_i < 0 (curvature of the left branch); |
B = |
B1, if b_i >= 0 (length
of the right branch), B2, if b_i < 0 (length of the left branch); |
D - |
a half-width of the membership function.
|
A separate approximating
segment defined by such measure of conformity is symbolically shown
on fig.8. Here decrease of thickness of the segment reflects decrease
of its clearness, i.e. degrees of correspondence to an approximated
contour.
The contour image on which basic serviceability
of this procedure was checked is shown on fig.10a.
|
Fig.10a |
The size of an initial half-tone picture
is equal - 290x196 points. For detection of contour boundaries the
known Hueckel's operator [5,6] was used. In total, 800 contour points
were chosen approximately. Initial positions of contiguous segments were
defined by nodes of a regular grid with 12 raster points step (reasons
on the basis of which this step was set, are stated in Appendix_2.2.A). Values
of remaining parameters were accepted as the following: B1 = B2 = 5, D
= 2.5, A = 0, P1 = P2 = 0.
Initial approximations had the most
various positions concerning approximated pieces. Nevertheless,
in supressing majority, from 384 starts having here a place, procedure
of gradient "fine tuning" founded the maximum of the bell-conformity
measure defining an actual contiguous segment (fig.10b).
|
Fig.10b |
The experiments carried out in this
way have shown that the maximums corresponding to the segments in
search have pure slopes. Really, on these slopes there
are no ejections (they are swallowed by the basic extremums)
in which gradient procedure could "lose the way". These experiments
have proved a basic possibility of deriving of the description of contour
figures in terms of contiguous (tangents) of the segments corresponding
to our intuitive representations.
At the same time, the analysis of behaviour
of the gradient procedure originally used for search of local maximums
of a bell-conformity measure [2], has shown, that in neighbourhoods
of the maximums (i.e. at the final stages of search) the conformity function
looks like the long, narrow ridges prolated along axial lines of contour
boundaries. Thus, approximating segments can long oscillate in the
cross direction to these lines, with very slow movement in the longitudinal
direction. For fast transition of these ridges in [3] it was offered
to displace during search the central point of an approximating segment
not on axes of the image coordinate system but along and cross of flowing
direction of its axial line. As the axial line of an approximating segment
is gradually arranged under the axial line of the represantation piece
of contour boundary, longitudinal moving of the segment is carried out
directly along the axial line of the mentioned ridges. Such organization
of the search procedure of local maximums of the conformity measure enabled
rather fast and legiblly to pass the above mentioned ridges of this measure.
More in detail about the choice of value of steps it is said in Appendix_2.2.B.
Further. As initial approximations in
the subsequent experiments, the most legible elements of contour boundaries
selected by the Hueckel's operator were accepted. Besides, sparsed
representation of contour boundaries was used. As contour points
the central points of contour-boundary (edge) patterns of the
Hueckel's operator were assumed, instead of all raster points placed
under them as it was in the first series of experiments were accepted.
According to sparsed representation,
the criterion of filling ratio of contiguous segments [Appendix 2.2.C] was
modified also.
A contour image on which serviceability
of the advanced procedure of representation of contour boundaries
was checked by contiguous segments is shown on fig.13. A size of the
initial half-tone picture - 216x216. In this case, diameter of the
entering piece of the Hueckel's operator was equal to seven (7) points
of the raster. Overlapping at tracking of the contours was equal to a
half of diameter of this piece. Hence, a step between "sparsed" contour
points was 3.5. Contours of the exibited image contain 215 points.
|
Fig.13 |
On the same picture the outcomes of work
of new procedure (resulting contiguous segments) are shown.
The proposed organization of the procedure
of gradient searching, sparsing of contour points and choice of the
initial approximations defined on the best pieces of contour boundaries
enabled to increase essentially stability of the process of the description
of these boundaries in terms of contiguous segments. Necessary accounting
time was sharply reduced also. Representation of a contour picture
(fig.13) with contiguous segments has demanded 50 sec of computation
time, and a picture of the same order of the complexity shown on fig.10
(the first series of experiments [2]),
with the help of initial variant of this procedure - over 20 minutes.
The carried out experiments confirmed
a possibility of practical realization of the concept of contiguous
segments - segments with fuzzy ends.
In Appendix_2.2.D the some tactical
problems of the organization of the search process of local maximums
of the bell-conformity measure are considered.
Further researches
on size optimization of steps of gradient procedure seems to be expedient.
In the considered variant the choice of their value was carried out
on the base of the most common reasons.
Now for detection
of false situations (in particular, at capture of several
segments),the final, rather bulky property criterion of filling ratio
of contiguous segments is used only. For more operative estimation
of the situations arising during the bell-approximation process, a use
of the information on behaviour of the gradient procedure - character
and number of steps - is possible. For the same purposes it is possible
to use a mutual coherence (confirmation) of the approximating segments
related to the same piece of contour boundaries. There is that natural
reason, that if one contiguous segment confirms by its branch the cross
position and orientation of the central piece of other segment (and vice
versa), then, most likely, there is the set of contour points under these
approximating segments corresponding to our concept about an uniform line
segment.
The applied
mode of preliminary choice of contour points is deintended for work in the
conditions of full absence of information on topological connections between
individual elementary contours. However, as an operational experience shows
for actual images, contour boundaries are traced through the help of local
operators on rather extended pieces. In this connection treatment of the
connected pieces of contour boundaries instead of acnodes from some area
is prospective. By the way, it can facilitate approximation of close placed
contours too.
Use of the Hueckel's
operator for search of contour boundaries of analysed images is caused
by a necessity of simplification of experiments. Most likely, the
suggested approximation method will be efficient at use of more simple
operators too, for example at the use of the simplified Hueckel's operator
[18], the Sobel's operator and possibly
of the Roberts simplest operator [7].
Besides, a possibility is supposed to build-up of an operator of similar
outcomes quality (and of operation principle) to the Hueckel's operator,
but more fast-acting.
The basic share
of computation time in the procedure of detection of contiguous segments
is expended on a sequential evaluation of contributions of contour
points in a flowing value of the coincidence measure gradient. The
operating time of procedure can be reduced essentially if to calculate
these contributions in the parallel way using a specialized computer.
All evaluations
were carried out in format of numbers with floating point. There
are no principal difficulties in their transformation into integer
form. Thus byte (or slightly greater) representations would be enough
in most cases. Obvious replacement of direct analytical evaluations
by the table representation of bell-like (one-dimensional) functions
and their derivatives here will allow to reduce sharply calculation
time. Necessary for its products can also be determined employing tables.
Though the volume of such tables is great, but it does not exceed engineering
possibilities of used computing tools (for storage of these tables
memory about several tens kilobyte is required).
As a whole, the increase of operational
speed of the representation procedure of contour boundaries by contiguous
segments on several orders is quite real.
In this connection
an experimental examination of serviceability of the representation
procedure of contour boundaries by contiguous segments has revealed
the following problem. As appeared, parabolic contiguous segments tend
to run into smooth inflections of contour boundaries. The example
of representation of contour boundaries when movement of approximating
segments in a longitudinal direction is carried out in a direction of
corresponding component of conformity measure gradient is shown on fig.14.
|
Fig.14 |
And such
arrival is caused not by width of memberships functions as it was in
the case of root-mean-square approximation of contour boundaries by rectilinear
segments. In order to prevent a possible disclosure of structure delicacies
of the conformity function caused by sparsing of contour boundaries,
the minimum width of memberships functions was limited to a size approximately
equal to a step between sparsed contour points (D = 1.5). Experiments
have shown noncriticality of the obtained outcomes to a choice of
this size (trial experiments were carried out at D_min = 0.5 - 2.5).
The analysis
of this situation has allowed to draw a conclusion that arrival
here is defined by the form of approximating curves. Curvature of
parabolas is maximum in the center and decreases to the periphery,
therefore parabolas are easily entered in such pieces of contour boundaries.
In work [3] for restriction of the running tendency
of parabolas it was offered to move aside branches of smaller curvature.
However, as appeared, thus counteraction is required to slipping
of contiguous segments to the ends of representation pieces at fuzzy
expressed linearity maximums (fig.15). To solve this problem
correctly was not possible, - it was not possible to select univalently
any strategy of switching of longitudinal moving force which would
enable to avoid simultaneously slipping of approximating segments
and arrivals on smooth inflections.
|
Fig.15 |
In last version
of the procedure of approximation with contiguous segments a soft
restriction of width of rectilinear corridors, which these segments
can occupy, was suggested. Mathematically, such restriction expresses
that at an evaluation of individual components of a gradient of the conformity
measure the contour points are taken into account with weight computed
under the formula
Where
d_i - |
deviation of a contour point from a
straight line tangenting the contiguous segment in its central point,
i.e. from the longitudinal axis of its own frame; |
U - | a half-width of a rectilinear corridor occupied by the segment (fig.16). |
|
Fig.16 |
The second series
of the experiments described in the previous section (their outcomes
are shown on fig.13) carried out with the similar count of contour
points, i.e. contributions of these points to values of components
of the conformity measure gradient were multiplied on their weights
with the count of width of an admissible corridor. Thus for an evaluation
of the component corresponding to longitudinal movement, the corridor
with a half-width equal 2.5, and for all remaining components - a corridor
with a half-width equal 5 was used.
Smooth (gradual)
restriction of width of the rectilinear corridors occupied by contiguous
segments, has allowed to avoid their explicit arrivals on smooth
inflections and slipping to the ends of represantation pieces.
At the same
time, here again a legible solution of the problem of longitudinal fixing
of approximating segments to obtain it was not possible. At use of boundaring
rectilinear corridors the separate approximating segment can lose sensitivity
ends of a represented contour line. It can happen, if this line has a sufficient
expansion and curvature and consequently can leave for longitudinal boundaries
of the boundaring corridor. To increase width of the corridor it is impossible,
- the tendency of a parabola to run into smooth inflections begins to affect.
An example of such contour lines are contour boundaries of insoles
corresponding to its heel (fig.13), and also to lateral faces of an
iron when contours of this object are submitted full enough (fig.17).
|
Fig.17 |
In similar cases
the approximating segments should be fixed arbitrarily-compulsorily.
The mechanism of such fixing consisted in that longitudinal movement
of the approximating segment in one direction was authorized only on
half of the distance between two points in which there was a change of
movement direction (in the beginning this distance was set equal to
a diagonal of the analysed image).
It is necessary
to pay attention that width restriction of the rectilinear corridors
occupied by approximating segments leads also to respective breakage
of these segments (on cross corridorboundaries). In outcome the contour
line which without cross restrictions could be submitted by one segment,
will be submitted by several ones (see, for example, segments 4, 15
on fig.13).
Probably, to
resolve the problems of longitudinal fixing of approximating segments
is possible through the use of such curves (as the standards of the
simplest segments) which curvature will increase to their ends and
is minimum in the center (for example, curves of elliptic type). Apparently,
approximation of such type is capable to give objective (in our intuitive
understanding) subdivision of contour boundaries into pieces of minimum
curvature, but this problem demands the further researches.
The expediency
of further investigation in this direction as a whole is obvious.
In particular, legible longitudinal fixing of approximating segments
essentially would facilitate a solution of the subsequent problem of
integral recognition-matching. Obviously, the more precisely such fixing,
the less final verifications of standards of search objects
with analysis pictures is required.
At the same
time researches which would be based on pass of final fixing of approximating
segments directly on the stage of an integral recognition of contour
objects are of interest. The present research was developed in
this direction [3.].