The Textural Analysis

THE T:U:TURAL ANALYSIS

V.M. Krol and L.I.Tannenholz The Institute of Control Sciences, Moskow, USSR

This paper contains an algorithm and a computer programm for a natural from the human point of view splitting into sections of a two -dimensional pic­ ture. Contemplating a picture, a human being draws in his imagination borders, sorting out sections, which he supposes to be homogeneous for the time being,in spite of their posessing an internal structure Some times such borders are drawn following some qualities of an object,which he expects to find in the picture, for example, when completing a partly detected image. In other cases the borders are drawn by analysing the characteristics of the picture itself. The sections, being separated in the la­ tter case are usually known by the name of textures. An example of a picture, contEJ,ining three textures, is shown on Fig. I.

D

An example of human textural ana­ lysis. A. 'l'he initial picture. B. Smal­ ler fragments, inclined to the left. C. Smaller fragments, inclined to the right. D. Bigger fragments.

Figure I.

'rhe main procedure of the appro­ ach applied in the present paper impli­ es the measutement of a certain charac­ teristic on each elemantery fragment,in which the basic picture was initially broken and then conbining the fragments posessing similar characteristics into one area. ·rhe necessity of analysing each single fragment separately in that case, seems to contradict the intuitive conception of textures and the ma~ aim of the textural analysis, that is to say not taking into consideration the internal structure of separated ar~a.But the possibility of disregarging the inter­ nal structure is to be considered only as the aim or the result of textural ana­ lysis, but not as a procedure of it. The illusion of disregarding internal struc­ ture in the process of perception deri­ ves probably from the fact that the amount of information about the internal structure necessary for splitting the picture into sections is much lesser than the whole amount of in formation contain­ ed in the picture.

The most important problem in this case is the establishing of bondaries, in shich the characteristics of similar fragments can change, ~.g the establis­ hing of the system of thre sholds.

For solving this problem, in the present paper the phenomenon of "sepa­ ration into groups" is used. The effecen­ cy of using this phenomenon in solving the problems of recognition was analy­ sed in M.M.Bongard·s book (I) and the phenomenon itself was applied by M.M.Ma­ ksimov for a learning programm of recog­ nizing pictures (2). Ele fact that the human being does really use the pheno­ menon of "separation into groups" was shown in psychological experiments (3).

For establishing the threshold values, histogramms of elementary frag­ ment's distribution according to the values of certain characteristics were drawn. Among the characteristics only those, the histogramms of which have a distinct separation of columns into groups were chosen. Examples of separab­ le and non - separable histogramms are shown on Fig. 2

'·

An example of histogramms. A.Separing into groups. B. Not separa­ ting into groups.

Figure 2

Thus the threshold values separating each groupare fixed.

We prtsume that there does not ex­ ist a way of measurement of elementary fragment's characteristic or distinguis­ hing the fragments themselves equally suitable for sorting out all kinds of textures. But a criteria of suitability of a certain characteristic or a certa1n way of measurement does exist. So it is necessary to try all the ways of split­ ting into frag menta and measurement of characteristics, naturally according to the order in which their complication is increasing.

From this follows that the textu­ ral analysis is a protracted process, which takes place simultaneously with the proces of recognition, independent­ ly, or in connection with it.

The textures, which for their se­ paration demand a little amount of cal­ culation are discerned earlier, whe­ reas more complicated-later. For example, in the separating textural areas with different brightness only a minimal initial information is required. So this procedure certainlly can precede the process of recognition as a whole (it is possible that such an analysis is conducted in the level of ganglion cells of retina periphery, which have large receptive fields. One can presume that after averaging by such fields, a pattern with a small number of e~re­ ma can appear, which may be used !or the final separation). On the other hand, for discerning two areas which have the same medium brightness, the same statis­ tics of the first and the second order but which consist of different forms: e.g. the first of triangular forms the second of square forms, many stages of recognition are necessary& namely iden­ tification of triangular and square forms, analysis of their respective po­ sition e.t.c.

'rhe general structure of algor~thDi

Fig.3 represents in the most ge­ neral form the succession of operations used in solving the textural analysis problems.

'fhe block-system of the algorithm.

Figure 3.

rhe presented picture is splitted into elementary sections.

'fhe most simple and natural way of splitting seems to be discerning the continuous areas, posessing an almost identical brightness or colour. The allowed fluctuatuins of brightness or colour inside a single field depend on the number of used gradations and are considered as constants of algorithm, determining its discerning capacity. In case when only two gradations of bri~­ htnese are used, and this carried out by the programme based on the proposed al­ gorithm, one may confine in discerning only connected areas.

Some other ways of i~itial separa­ tion which imply more complicated pro­ ceding of picture may prove to be neces­ sary too. Particularly, the program can fulfill the separating of lines between the knots.

l'he elementary fragments obtained as a result of analysis are numbered in a certain order. The numeration is used for connecting the values o! characteris­ tic with ~he fragments for which they are obtained, but the final separation of areas does not depend on the numera­ tion.

'.fhe second stage of the analysis is the measurement of fragments& to each fragment is applied the same measure opt; rator (the same measurement procedure) · From the logic of the approach follows that there are no measurement equally suitable for all cases. In all cases we use the same criteri o! suitability& the criteria of separation into groups. So a successive examination of operators is necessary, which is conducted in the order of increasing complication of ope­ rators. Actually only simple operators were used in the program: measurement of the area, of the abscess and ordinate of the centre of gravity, of the length of greater and smaller half-axis, and of the angle of horizonta~ inclination of greater axis. J.s the number of operators used was rather small, so all the opera­ tors were used and the applicability of every one was examined.

'.l'he ways of getting more complica­ ted characteristics can be obtained, for example, from V.V.Maksimov·s program ( 2).

As a result of using one operator to the multitude of fragments one of se­ veral multitudes of numbers, one- t o-one connected with the multitude of operator are formed. The multitude of characte­ ristics are arranged according to the increase of fragment's numbers for re­ cording on the computer's memory. ·.rhus a line of characteristics is cons­ tituted.

x) Some operators can be unsuitable for certain ~ragments such fragments receive as the value of characteristics the number I0CO which is greater than any measured value of characteristic. All such fragments are sorted out in a se­ parate area.

Every lin~ of a characteristics

matrix is lireatr.d by the operator of

''sc~uratin~ into groups·: 'l'his operator des1gns a istogramm of fragments dist­ ribution according to the values of the exaJniued characteristics and decides wh€:ther it can be split 1.; int;o a small number of compact t;I·oups. For thiaim a following algorithm is used. First of all a system of threshold is formulated by fixing them in the points where the his togramm takes the zero value (or has a local minimum). l'his procedure splitts the histogramm into a number of groups of the zero level. Every group then is estimated by two parameters: namely the volume (tne relative number of comprised fra~:;ments) and comvactness. 'l'he compact­ ness is estimated by compar~i1~ the gro­ up's wid·th ( tihe standard deviation) with the distance between the centers of adjoinin6 groups. The smallest and the least compact group is fused with one of the adjoining groups by crossing out the corresvonding threshold.The operation is repeated untill the smallest of the re­ mained groups will surpass a certain value (in the program I/8 of the amount of fragments), and the least campact one will be sufficiently compact (its stan­ dard deviation will be less than half of the distance towards its nearest neigh­ bour). rhe criteria of size and compact­ ness are the constants of the algorithm. If as a result more than one group re­ main, the characteristic is estimated as such which is suitable for splitting in­ to groups, and the obtained system of thresholds is used for further preceding and sorting out the fragments. In other cases the characteristic is rejected.

The sorting of fra~ents is con­ ducted by means of compa~ing the values of characterictics of the examined frag­ ment with the threshold fixing the gro­ ups. As the result of sorting the multi­ tude of fragments is devided into seve­ ral submultitudes, the number of each is equal to the number of groups. Only if the multitude of sorted out fragments is solid e.g not containing the fragment from other groups, it constitudes a textural area. The examination by compac­ thess criteria was not conducted by us, but it could be done without and dif­ ficulty.

If as a result of separating pro­ cedure more one separating characteris­ tic is found, it becomes possible to form several variants of splitting. In that case, beside initial devisinns their local functiono are possible.

The second source of additional divisions is the splitting of the sepa­ rated area. For this purpose ~he sorted out multitude of :fragments is brought again to the entry of the program (the characteristics in that case are not evaluated again, but are taken from the previous material).

The possibility of obtaining dif­ ferent Kinds of partitions seems to be a great advantage of the model, as it permits to chose in the process of the analysie the most adequete partition for each given problem.

The discribed model was worked out as a program for the ICL-470 computer. L'he main part of the program was written in ~ORTRAN. The input rastr of the model is 80x80 units. The time of proceeding of one picture including the forming of all variants of partition is about; 3 mi­ nutes, but it grealy depends on the qualities of the picture (especially by the amount of fragments). Most of the time is used for the procedure of split­ ting the picture into initial fragments.

Fig.4 shows an example of computer separation.

An example of program operating. A.'l'he initial picture. B.Smaller frag­ ments. C. Bigger fragments. D.Smaller fra~ents, inclin~d to the left. E.Smaller fragments, inclined to the right.

Figure 4

It is obvious that the computer draws natural divisions from the human point of view. It is uncertain yet as to which de~ree the proposed algorithm is an universal one, and h0\'1 much it is close to the manner of proceeding of pic­ ture by the human vision. This can only be proved by further experiments with the program.

SUlJl:ii!ARY

A model of human proceeding of vi­ sion data for the tasks of splitting th~ pi·cture into areas of the same textures is proposed.

The model is based on the follo­ wing principles:

!.The textucal areas are formed by joi­ ning small, in a sense nomogeneous frag­ ments of the picture.

2. The characteristics used for compari­ ing the fragments are selected separate­ ly for each problem (each picture).

3. In order to examine the adequacy of the characteristics and to chose the thresholds the criteria of "separating into groups" is used.

An algorithm was elaborated and a computer program was written in FO.R'rRAN.

lurther experiments must abow: I. In what extent the proposed model reflects the process of the human vision?

2. In what extent the proposed algo­ rithm is applicable to real situations and real problems?

Literature

1. EoHrlp~ u.u. npo6neua y3H8B8Hift; HayKa, 1967.
2. U8KCHMBB B.B. nporpauua, o6yqa~ascs KISCCBWHKSUIB reouetpBqecKHX aao6pa­ zeHBI. Raux H 3KCD8PHM6H~. B c6. "CTPYKTYPHY6 M8TO~ OD03B8HHH I anoaaatnecxoe qteBHe". Y. ,1970.
3. BHimTH.