Vladimir I. SHULGA

Ph.Dr., Senior Research Scientist, National Academy of Sciences of the Ukraine, Kiev .

E-mail: shulga@altavista.net

About the work.

ABSTRACT

Whole recognition (singling-out) of the contour samples is realized with help of the accumulation of hypotheses about their parameters that are generated independently by separate primary signs (segments) singled out on the analyzed picture.

Index Terms (Key Words) - computer vision, image analysis; segmentation, approximation of contours, recognition (singling-out) of samples.

1. INTRODUCTION

This procedural sequence is based on:

1) the interference defended method of segmentation-approximation of contour boundaries;

2) the general-purpose method for description of the contours of an arbitrary (curvilinear) form within the terms of the segments of any standard form;

3) the fast manner for account of the integral verification of the contour samples.

The paper represents the base concepts (Section 2) and main peculiarities of the realization (Section 3) of these methods. Its details has been described in [1].

2. MAIN CONCEPTS

To relax this conflict one should leave conception of the threshold (“rude jumping”) points belonging and go to its “soft” (fuzzy [2]) estimation. Namely, the function of assignment of contour points to a separate segment should have the bell-like form (Fig.3). This function is the smooth symmetrical function tending to zero when the deviation from the approximating segment axis increases.

If such kind of the assignment function is used, this also lets (simultaneously with singling-out of subsets of the contour points that belong to separate segments) to solve the problem of approximation of these sets as the problem of maximization of estimation of the degree in which the approximating segments are verified by the contour points.

Such operative unity (which unites approximation with gently extraction) enables to avoid a false leading away of the approximating segments, their false subdividing and planing of the contour corners by this segments.

2.2. The main peculiarity of the representation of the arbitrarily shaped contours as the group of separate segments is essential absence of the legible ends of some line segments. Here one should operate with the linear elements that have fuzzy ends. The function estimating the degree of assignment of contour points to this element must have the bell-like form in longitudinal direction too (Fig.4).

Such function permits to rest on the length of the contour lines in proper way and for a maximum when they are approximated by the curves of some standard type (in the most rigid degree in centre, with gradual weakening in the periphery direction, according to their gradual divergence). In the present work the curves of the simplest type are used as the axial lines of the approximating segments, so they are the central part of the parabolas each branch of which may have its own curvature and “fuzzy length” (see Section 3.1.). Such segments are called contiguous (because their branches have only a “contiguity” with the approximated contours in general). Figure 1 shows the result of representation of the contour picture with such segments (here the thickness of each segment is reduced in the periphery direction in accordance with drops in its “distinctness”)

The contiguous (fuzzy end) segment conception application makes it possible to obtain the description of contour boundaries by means of the maximally stretched and, therefore, maximally stable standard linear elements. Here singling-out of such elements is the essentially simpler problem than the next one associated with recognition-matching of contour objects as a whole. When considering this aspect, it is possible to speak about the highly possible (optimally maximum) complicacy of the description of contour boundaries within the framework of the segments with fuzzy ends as the basis for further integrated recognition-matching of the contour objects of arbitrary shapes.

2.3. Complicacy of solution of the arbitrary-shape object recognition problem consists in that in general case of smooth contour boundaries it is in principle impossible to fix approximating segments in efficient way in definite places of the contours that are matched. The problem of elaboration of the constructive procedure which can choose the model image of an object that corresponds to the observations, under such fuzzy (sliding) primary segmental representation of contours is a rather non trivial issue.

When the sought objects are the figures of the definite fixed shape, the problem of the recognition such object can be solved constructively by way of accumulation (vote-count) of hypotheses about parameters of the objects and by registration of the hypotheses that are independently generated by the highest number of primary facts-features. The role of such facts is played by the elements of the segmental representation of an initial picture. Each of these facts-segments generates a set of hypotheses about a possible position of the desired object in analyzed image. Here, the most probable fact position is defined by the maximum crossing - clustering of sets which correspond to different facts - segments. Thus, the recognition-matching problem can be solved under computational costs that are much lower than for the direct contour matching case.

In practice that approach lead to technique (see Section 3.2.) similar to the algorithms the majority of which goes back to the famous Hough transform [3], [4]. The proposed ontological approach to the object recognition enables to see the deep community of this algorithms. The seeing of this community makes it possible to simplify the logic of elaboration and extension of such technique in essence.

Moreover, and what is above all, the developed algorithm is based on application of the contiguous segments with the fuzzy ends which are the most characteristic (informative) and at the same time they are the universal units of initial generation of the hypotheses about the global parameters of the arbitrary curvilinear contour objects. It was the use of the initial units like described above that enabled us to draw the search performed according to the hypothesis accumulation principle up to the possibility of the constructive application in the problem of recognition of such objects.

3. REALIZATION OF THE BASIC CONCEPTS

where:

d is deflection of the contour point from the axial line of approximating segments;

D defines the deflection under which the assignment function is decreased twice;

In addition, this expression is modified by reduction of the upper exponent from 2 to 3/2. In this case, the amplitude of the assignment function is increased if its width - D is decreased, but the branches of this function are dropped down under this decreasing, and otherwise (Fig.6). Such assignment function shape change character enable to construct a measure of segment verification which has sensitivity to the width of the approximated contour points subsets. (Similar technique also is applied to longitudinal direction.)

Taking into account all of told above the general mathematical expression for the such measure has the following form:

where

T is the set of counter points extracted from the image;

n is the number of these points;

h = {X,Y,A,D,P1,P2,B1,B2}

are the parameters of the approximating segment;

X,Y are the coordinates of the segment centre, namely, its own coordinate system (Fig.7);

A is the segment slope;

D is the half-width of the assignment function;

P defines the curvature of the representing parabolas:

P1, if b_i >= 0 (right branch curvature),

P2, if b_i < 0 (left branch curvature);

b_i, d_i are the parameters, defining the position of the contour point in own coordinate system (bOd) of the approximating segment; these parameters are found from the coordinates of the point:

x_i, y_i with the transformations:

        d_i = -(x_i - X)*Ѕsin(A) + (y_i - Y)*Ѕcos(A);

B defines the longitudinal deflection under which the assignment function is decreased twice (similar as D defines “twice decreasing” across deflection (B>>D)):

B1, if b_i >= 0 (right branch length),

B2, if b_i < 0 (left branch length).

3.2. The contour shape recognition (singling-out) procedure was constructed under the consideration that it is impossible to strictly fix approximating segments on the smooth contours. The training part of this procedure imitates the moving of a formal contiguous segment along contour boundaries of the standard of the sought object (its separate full non-interfered image; see Fig.8).
 
 

In this time, the standard’s position in respect to the own coordinate system of the sliding segment is determined on each step of this process (is determined position and orientation of an unit (basic) vector which has been fasten attached to the gravity center of the standard’s contour). The obtained set of the coordinate angle parameters is called as reference hypogram (because it is the record of the hypotheses about possible positions of the sought object).

At the stage of the recognition itself, this hypogram is sequentially juxtaposed to each of the contiguous segments were obtained after finishing the substage of the segmental representation of the contour picture that is analyzed. Under this juxtaposition, reference hypogram (its points) is translated in own coordinate angle system of this picture (here, the slope of the segment is added to the angle values).

The solution of the present recognition problem is defined with point (zone) of this system has been marked with largest amount of juxtaposed hypograms. This point determines such position of the object standard under which the contour of this standard is attached to largest amount of facts-segments.

Figures 9 and 2 illustrate the result of the recognition of the insole within the context of the contiguous segments represented on the Figure 1. Figure 9 depicts the comparative weights of all separate marked-rising points (zones) were registered in this experiment.

Figure 2 shows the positions of the object’s standard which are defined by first three of them. Black dashes correspond to the most marked-rising zones and the lighter ones to the next coming. (The program, which realizes the proposed algorithm, use the rectangular zone representation of space of the sought parameters. The relative shift size of one of these zones is shown on the left bottom on the Fig.2.)

4. SUMMARY

There are several directions for further elaboration of this work. First of all, it must be set to any modern living computer visual system. Technique of the computation can and must be essentially improved. Functional possibilities can be significantly extended.

Probability of future improvement of the proposed procedure group makes it possible to speak about the real plans of constructive extension of the presented approach also to more complicated situation (larger number of desired parameters), in particular, in order to perform recognition of 3D arbitrary shape objects of an arbitrary orientation.

Note that the proposed general-purpose interference defended arbitrary form contour segmentation-approximation may be useful not only within the framework of the developed recognition procedure sequence. It may be used as a stable basis for many contour analysis versions.

REFERENCES

[2] L.A. Zadeh, “Fuzzy sets”, Information and Control, 1965, N 8, pp. 338 - 353.

[3] P.V.C. Hough, “Method and means for recognizing complex patterns”, Pat. 3069654 (US), 1962.

[4] D.H. Ballard, “Generalizing the Hough transform to detect arbitrary shapes”, Pattern Recogn., 1981, Vol. 13, N 2., pp. 111 - 122.

[5] M. Hueckel, “A local visual operator which recognizes edges and lines”, JACM, 1973, Vol. 20, N 4, pp. 634 - 647.