APPLIED PROBLEMS OF GEOMETRY OF LINES.

BELL-LIKE (FUZZY) MEMBERSHIP FUNCTION IN THE PROBLEM OF STRUCTURAL SEGMENTATION – APPROXIMATION OF ARBITRARY SHAPED – PIECEWISE-SMOOTH CONTOUR OBJECTS.

UNISON OF POSITIONAL HYPOTHESES AS INDICATOR OF DETECTION OF SPECIFIED CONFIGURATIONS.

SHULGA V.I.

http: // shulga.tripod.com/A_SAD2/R.htm

Russian

                  ABSRTUCT

Physical sense of root-mean-square deviation minimization - the classical basis of actual data approximation - is visually demonstrated. Necessity of application of the bell-like membership function is pointed, at problem of approximation (segmentation) in actual conditions.
A new geometric concept - the segments with fuzzy ends - is offered. Such segments are asserted as maximum steady (geometrically certain - strict) universal units of primary description of arbitrary shaped - curvilinear contour forms.
The procedure of fast positional detection via registration of a unison of parametric (positional) hypotheses is described. Semantic generalization of similar procedures, including those going back to the widely known Hough transform is offered.
The task of positional detection of arbitrary shaped contour objects in close - partially overlapping context is solved.

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.
Conceptual content.

The present work deals with 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 through their samples (templates) which, herein, themselves represent the individual images of piecewise-smooth objects. Initial materials were contour preparations of actual gray scale images. 

Line is one of primary geometrical concepts by means of which the man describes environmental actuality. An apparent ease - "evidence" - from which the man operates with his own abstract representations in this field makes false impression about simplicity of algorithmization (transposition into a computer) of such operation. One of key tasks here is a partition of registered linear shapes on individual components - the elementary segments. Difficulties start already in the elementary case - a case of "angular" polylines. It appears rather uneasy to pick out an angle in a actuality when lines are set discretely as a set of the individual points scattered around of their true positions.

In the first section of the present work, the arising here difficulties are systematically considered. The physical sense of minimization of mean-square deviation as the basic procedure of the analysis of actual data is considered. Necessity of usage of the bell-like (fuzzy) function of a membership of contour points to individual segment is obviously shown. Tasks of partition of contour configuration on individual segments and their approximation are reduced together - to searching local maxima of a "fuzzy" measure of likeness constructed on the basis of such function.

The second section considers a more complicated problem, namely, -  if we should divide into units a lines having the smooth shapes, when generally there are no precise angles, - one segment gradualy - smoothly pass into another. The example of the figure outlined by a similar line is shown on fig.I.

FigI
Fig.I

In a central area of this figure the quadrangular oval - ABCD (ContourI ) which can be interpreted both as an oval tetragon (an outline of a kitchen blister, and the screen of a kinescope with the rounded angles 35LK …) is presented. Precisely to fix the moments of deviations of an outline of such figure from approacting shapes (approximating segments) basically is impossible. The situation is aggravated also with that there is no limited gang of the simplest curves exhausting all diversity of forms of elementary curves - curves of minimum curvature. Generally it is possible to rely only on more or less precise conformity an approximating segment - simplest curves - on centre (middle), with gradual divergation to a periphery.

The gradual divergation is the basic moment which is necessary for including in a model of approximating shapes. The function estimating a membership of points to a individual segment should have the maximum in the centre of a the segment, and gradually reduce the value on its periphery. Such bell-like 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. On fig.I, the linear images defined by the given concept are schematic shown. The diminution of their width (their thinning) responds to diminution of their geometrical determinancy - to clearness. Appropriate shapes of the bell-shaped membership function are figured from the exterior side of each segment.

It is visually possible to represent that approximating is carried out with certain arcs - small arcs with “thinning” to their ends (the association with typographical round brackets is also pertinent). Such segments, or small arcs, are named by contiguous segments because their branches, in common, only adjoin to approximated lines. Their other semantic title is segments with the fuzzy ends.

To the concept of contiguous segments - segments with the fuzzy ends it is possible to approach on the other hand too - not from a diminution of their determinancy on periphery, but, on the contrary, - its magnifications to the centre. Magnification of a geometrical determinancy to the centre - the middle - with adjoin of branches is just that ensures a maximum of determinancy in a definition of the tangential direction. Here, abstract differential feature - a direction of a line in a point (the first derivative) obtains, in face of contiguous segments, the stable foundation for the definition in actual conditions. There is a potential possibility of wider practical usage of this feature at the analysis of actual data.

It is seem rather probable, that in a similar way contiguous segments transfer the differential feature of the second order - curvature from the world of abstraction in actuality. Though directly it was not explored, nevertheless, the common character  (an aspect of outcomes of experimental researches) definitely showed that the contiguous segments can be a stable foundation too.
In the second section the common principles and technique particularities of implementation of the concept of contiguous segments are considered. The general view of the likeness function, which local maxima define these segments, is represented. The outcomes of experimental examination are discussed.

In the third section, the problem of practical usage of contiguous segments in the task of positional detection of arbitrary formed contour objects under their samples is considered. The offered solution is based on a procedure of registration of unison of parametric (positional) hypotheses about probable positions of sought configuration, which are independently generated by separate primary features - fragments. As such indicators (fragments) the contiguous segments here appear. A common ontological (essential) scheme of such procedure is offered. Practical implementation of this approach leads to the procedure of detection similar to procedures in which basis the known Hough transform lays. The offered summarizing enables to see their depth generality, to simplify logic of their development and the further development.

Moreover, and what is above all, the developed procedure is based on an application of the universal primary 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 unique unity of this conceptual pair.

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
.

TABLE OF CONTENTS:

1.     BELL-APPROXIMATION.

2.    CONTIGUOUS SEGMENTS.

3.    THE UNISON OF PARAMETRIC HYPOTHESES AS THE INDICATOR OF POSITIONAL DETECTION.

SUMMARY.

REFERENCES.

APPENDIX.

The paper is an otherwise accented 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

In its turn, this work summarizes the author's investigations, the first publications are dated 1981 [2] and 1982 [19] years. In the scientific literature, there is a lot of papers, thematics of which intersects with the subjects of the present investigation. In Internet there is a wide set of sites, which is searched under enquiries:  «weighed least squares», «fuzzy lines», «generalized Hough transform» … Definition of relationship degree  of these materials with the present work and determination here author's superiority  is a subject for another examination. To not passing virtues of the present work, it is possible to refer that instead of scrappy hints and sacral appeals to higher mathematics, semantic  physical explanations are given, which are a basis of any science. Besides, all procedures are integrated in the unique technological line-up showing a place of each concepts in the common problem of positional detection - recognition as a whole.

sos