SEGMENTATION (APPROXIMATION) AND POSITIONAL
DETECTION OF ARBITRARY SHAPED CONTOUR
FOR ACTUAL CONDITIONS.
of classical root-mean-square approximation. Principles of functional
correction. Bell-like function of membership - the base of jam resistance.
Segments with fuzzy ends - the universal units of structural segmentation
of arbitrary shaped curves. Fast template matching trough registration
of unison of parametric (positional) hypotheses. Essential
interpretation of Hough transform. Positional detection of definite
configurations in close partly overlapping context.
regression analysis, interpolation, approximation, segmentation,
piecewise-smooth curves, splines, fuzzy sets; shape analysis, image
analysis, pattern recognition, image recognition, template matching,
Hough transform; computer vision, machine vision, industrial vision,
robot vision, drawing recognition, documents analysis; analysis
of schemes, maps, graphs, trajectories and signal processing as
a whole; applied geometry.
work deals with elaborate the problem of jam-resistant
representation of contour images as sets of elementary
line segments. It elaborates the problem of
following positional detection (detection with finding the position
and orientation) among these sets of specified configurations.
These configurations are determined therough their samples (templates)
which, herein, themselves represent the individual images of piecewise-smooth
objects. Origin materials were contour preparation of actual gray scale
The work consists of three sections. Their catalogs-comments
are following (were [X.X] - hyperreferece on corresponding piece of base
In the first 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.
with fuzzy ends.
Problem of structural segmentation (approximation) of arbitrary shaped
curves is solved.
[2.1] It is noted a non-adequacy
to the actuality of such the concepts as sharpen beginnings
and ends of segments in a gemeral case of smooth contour lines, when
one segment gradually passes into another one. The concept of segment
with fuzzy ends is developed. It is suggested to use a membership
function of bell-like shape also in the longitudinal (axial)
function enables to rest on the length of the contour lines
for a maximum degree when they are approximated with the
curves of some standard type, mainly in the center, with gradual
weakening in the periphery direction, according to their gradual divergence.
The obtained approximating segments are named as contiguous segment
because their non-sharp (fuzzy) ends are only adjacent, in the
general case, to contours under approximation.
contiguous segments - the segments with fuzzy ends - are themselves
a development of the concept of tangent comparison/juxtaposition
of curves. They lead up such the comparison to a maximum of a
geometrical definitiveness. The rigid conformity in the center and
gently at the ends, i.e. contiguity, is in the whole the maximum
of geometrical strictness, which can have the universal units
of primary segmentation/approximating of arbitrary shaped curve
lines. More stringent linear units equally rigidly resting
on approximated contour can not be universal, since there curves
of a standard kind do not exist, which comprehensive all diversity
of the elementary curvilinear shapes. It cannot be universal units
appealing to sharp ends of individual segments, since such ends basically
absent on smooth contours.
[2.2] Some particularities of program
procedure elaborated on this base are demonstrated. The results
of experiments are discussed.
[2.3] Some improvements are supposed.
[2.4] A general phenomenon of sliding
of approximating segments is pointed out.
3. Positional Detection via Registration
of Unison of Parametrical Hypotheses.
Problem of positional detection of contour objects in case of non-satisfactorily
explicit "sliding" initial features (approximating segments), that
take place on reality in general, is considered.
of the problem is illustrated.
[3.2] It brings to a focus the
phenomenon of mutual superposition of model patterns that
are generated by a individual acts of initial juxtaposition.
The using of this phenomenon
enable to reduce
together the detection
with a finding of position and orientation of sought object. Both
the problems here are reduced to a search of unison of parametrical
[3.3] That demands essentially smaller computing
expenses than a direct matching with the sample. It is used with effect
in present case.
[3.4] In practice, that approach
leads to the technique similar to the algorithms the majority
of which goes back to the know Hough transform. The suggested
conceptual enables to see the deep community of those algorithms. The
seeing of this community makes it possible to simplify the logic
of their elaboration and extension of the technique in the essence.
[3.5] Moreover, and what is above
all, the developed procedure is based on an application
of the universal initial elements, which limit the sets of the
hypotheses about the global (positional) parameters of the search
objects in the maximum. It is applied the described above tangent-contiguous
segments with fuzzy ends. It was an use of these initial units
that enabled us to draw the carried out search the hypothesis
unison principle up to a possibility of the constructive application
in the problem of positional detection of arbitrary form objects. In
the other hand, it was the use of such way of detection that enable
a principal way to "cut up" the "sliding uncertainty" of contiguous
segments that have its place in general. It may be told about
uncial unity of this conceptual pair.
[3.6], [3.7] At this base, the sequence of procedures
was created for efficient solving the problem of segmentation-approximation
and following positional detection (detection with definition
of the position and orientation) of arbitrary form flat contour
figures with respect to their samples in the case when one
figure may partially overlap another.
All these may be essentially advanced and widely applied as
the whole and individually.
The paper is a structural hypertext variant of
the following work with some specifications in the terminology:
Shulga V.I. "Complex (Collection) of Interference
Defended Procedures of Contour Boundary Approximation
and Recognition of Objects on Contour Images (research work)"
/ Glushkov Institute of Cybernetics, Academy of Sciences
of the Ukraine, Kiev, 1992, 75p. (In Russian) / Deposited in the
All-Union Institute of Scientific and Engineering Information
(Moscow), 04.01.92, N 12-B92.