Make your own free website on Tripod.com
STRUCTURAL  SEGMENTATION  (APPROXIMATION)  AND  POSITIONAL
DETECTION  OF  ARBITRARY  SHAPED  CONTOUR  OBJECTS.
SOLUTIONS  FOR  ACTUAL  CONDITIONS.
Last_Variant
Russian
                  SHULGA V.I.

http://shulga.tripod.com/SAD/E.htm

ABSTRACT
Physical substance 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.
Keywords:
data modeling, 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.


INTRODUCTION

The present 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 images [examples].

The work consists of three sections. Their catalogs-comments are following (were [X.X] - hyperreferece
on corresponding piece of base text).

1. Bell-approximation.

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.

2. Segments 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) direction.
 
Such the 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.

In general, 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.

[3.1] Essentiality 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 (positional) hypotheses.
[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.

[S] All these may be essentially advanced and widely applied as the whole and individually.

:) [Acknowledgments]

[References]

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.
http://shulga.tripod.com/GEOLIN/glnfl1.htm