One System for Simulation of Pattern Recognition Algorithms

ONE SYSTEM FOR SDIULATION OF PATTERN RECOGNITION A.IGORITIDIS

V.I.J:cybak, G.L.Gimelfarb1 E.F.Kusbner1 Institute of Cybernetics, Ukrainian Academy of Sciences, Kiev, U.s.s.R.

ABSTRACT

A. general purpose system for a computer simulation of pattern recogni­ tion algorithms is proposed that con­ sists of a universal scanner for opti­ cal images input to the computer, a display for visual output, and soft­ ware. A characteristic feature of the system is a blok structure of the hard­ ware and software. The system allows carr,ying out most of the data processing necessary for simulating the algorithms of recognizing the optical images of objects of various physical natures.

1. Present-day pattern recognition is developing several trends, one being different from another in the mathema­ tical formalism of formulating and solv­ ing the recognition problems. In parti­ cular one can point out among the trends a statistical learning and recognition theory, a theory of iterative learning procedures for linear or piecewise-line­ ar pattern separation, a structural (or linguistic) approach to pattern description and so forth. Anyone of t:Q.em has demonstrated significant achievements in solving individual problems or par­ ticular classes of the problems. Never­ theless, the general level of pattern recognition has not yet been sufficien­ tly high to warrant assuming the solv­ ability of most applied problems, The practical significance of the known algorithms is often vague due to com­ paratively small attention spared for their investigation. In practice we mostly encounter a situation when it is necess~ to combine different process­ ing and recognition methods for appro­ ximating the solution of a particular problem. The combining mode is more frequently selected on a "heuristic" base rather than as a result of a strict formal deduction. So the task of creating developed means for experimen­ tal investigation, oombination, and performance analysis of the various pattern recognition algorithms acquires even greater importance.

The main way of investigating the algorithms is a digital simulation, i.e. the simulation by means of a general­ -purpose digital computer equipped with necessary I/0 devices and a software. Let us enumerate the principal (in our opinion) points to be used for compar­ ing and choosing the simulation mode:

1. Expenditures of time, materi­ al, and man-power resources for design­ ing and constructing the simulation sy­ stem;
2. Expenditures for maltillg chan­ ges in and additions to the simulated algorithms in the process of investiga­ tion;
3. Possibilities of simulating the distinct classes of the algorithms;
4. Possibilities of comparing the performance of the different algo­ rithms using the same real material to be recognized;
5. Possibilities of working out the well-founded technical requirements for the recognizing devices that should realize the selected algorithm.

All the indices being taken on the whole, the advantages of the digital simulation become obvious in comparison with the competing investigation methods (e.g. with the direct modelling of the recognizillg device). To meet these re­ quirements the ideal simulation system should possess the following features:

1. Universality (i.e. an ability to real.ize any arbitrary path of pic­ ture scanning with a variable resolution power across the scanning field);
2. Possibility of picture inser­ tion from dif!erent carriers (paper, film, real-world scenes);
3. Effective means for experimen­ ter - system interaction that allow in­ terfering with the fUnctioning o! the simulated algorithm, making alterations and amendments on the base of the ana­ lysis of intermediate results an4 ob­ taining a visual representation of the­ se results in a convenient form (e.s., graphical) 1
4. Developed software which al­ lows simulating the investigated pic­ ture processing and recognition methods by means of the computer.

Completeness and flexibility of the software structure are the princi­ pal factors in estimation of the extent to which the particular simulation sys­ tem could meet the formulated require­ ments.

It should be noted at once that we have in mind a system being designed only for simulating the recognition al­ gorithms and investigating their per­ formance. These systems have been al­ most for sure found cumbersome and of little efficiency as the applied means for solving a practical recognition problem. Experience of adapting a simi­ lar system to introduce technical draw­ ings into the computer has provided a clear example: to work out the necessa­ ry and su!!iciently effective software for solving this problem turned out to be incredibly difficult(1). An inten­ tion to build up a special-purpose soft­ ware for simulating the algorithms which solve the recognition problems within the bounds of a !ixed method(2) seams also not to be justified enough.

The construction o! "general-pur­ pose" software including unified subro­ utines for the input, output, process­ ing, and recognition of a pictorial in­ formation shall answer the specific character of the simulation system to considerably greater extent. The prin­ cipal feature of such software should be its "multilevel" structure, the cur­ rent input, output, and prepocessing procedures being concentrated on the lower levels, and the more ramified and complicated picture processing and re­ cognition algorithms placed on the high­ er ones. The subroutines from the lower levels are used as components of the higher-level subroutines. This "multi­ level" structure allows building and modifying various algorithms by simply joining the separate blocka-aubrouti.D.ea and co-ordinating values of their para­ meters. Such a structure also permits extending easily the potentialities of the system by adding the corresponding procedures to each of the levels.

An analysis of the known trends both in pattern recognition theory and in the design of the recognizing devi­ ces shows that the aim o! creating the "general-purpose" software is quite practicable. In spite of all the pecu­ liarities of different approaches it seems to be possible to reveal in them a considerable number of common or uni­ form processing and recognition proce­ dures. The latter could serve as a base for the "standard" blocks o! the software.

For example, a .vast variety of the recognition problems solutions could be easily shown(3,4) as reduced to the same linear separation in a mul­ tidimensional feature space. One pole of the such problems is joined to sta­ tistical recognition theory, the other one is associated with learning schemes like the Rosenblatt perceptron. The. distinctions between the competing trends which are represented by these algorithms become apparent in the mode of choosing the coefficients for the linear discrimi.D.ant !unctions. There are several such modee1 from the direct statistical estimation of the unknown values to the sequential corrections belonging to a family o! relaxation op­ timizing processes for the functions of many variables. J.n:y of them could con­ stitute the i.D.dividual block on the cor­ responding software level.

The like linear separation("mask­ -match~') plays first fiddle also in a number of modern optical reading de­ vices(5). The coefficient sets form he­ re so-called "templates" or "masks'' de­ fining the recognized classes of alpha­ numerical characters. For matching, the character should be placed in a certain position with respect to the template. This ope rat ion is called "character po­ sitio~'. One could distinguish bet­ ween several positioning methods, for example, by shifting the character un­ til its border black points ("edges") reach the given limits, or its "center of gravit;y" reaches the given point, or by finding the position of the best ma­ tching, etc. These procedures could be in turn considered as the blocks of the system software. Having combined the similar blocks one can simulate the most part of the recognition methods laid at the foundation of these reading devices. Such a detailed analysis is obviously possible for any known trend in pattern recognition.

The stated principle of the soft­ ware construction will close up in the end with the problem of developing spe­ cial-purpose languages for simulating the pattern recognition algorithms.

1. The proposed general-purpose system for the computer simulation of the pattern recognition and picture processing algorithms consists of the following parts:
2. Local control unit for inter­ connecting the computer and I/0 units;
3. Scanner for inserting picto­ rial information from film or paper ca­ rriers,
4. CRT display for multi-shade output of the pictorial information,
5. System software subdivided into three levels:
6. (a) input-output procedures;
7. sing I (b) basic picture preproces-
8. rithms. (c) certain recognition algo-

The hardware has been designed as sepa­ rate units(Fig.1). The local control unit receives from the computer control signals and co-ordinates codes of the picture point to be scanned, forms con­ trol signals for the scanner and dis­ play, encodes and transmits to the com­ puter grayness values of the scanned points and produces signals allowing the reception and transmission of the information obtained. The scanner is divided into two isolated units: for paper carrier processing and for film carrier processing. The scanner has the following featuresz

• -- field of vision of the paper processing unit (measuring a reflect­ ance in a scanned point): 10 x 10 and 40 X 40 mm. 2 ;

- field of vision of the film processing unit (measuriDg a transpa­ rency in the scanned point) z 16 x 22 mm2;

• maxjmal scanning raster: 1024 x 1024 points;
• -- maximal resolution power in the center of the field of vision: up to 40 lines per mm;
• -- controlled variation of the resolution power in the scanned point: up to .32 times;
• -- discernible values of the measu­ red grayness in the sc8.Ilned point: 32;
• maximal processiDg time for one scanned point (a complete cycle until readiness for the next point process­ iDg): 180 microsec;
• -- maximal time for setting the new value of the resolution power: 1 mWisec.

The magnetic-controlled CRl's have been used in the scanner units as sources of the scanning light spot. The settiDg of the resolution power bas been carri­ ed out by challgiDg the spot diameter on the CRr screen. The spot diameter and position on the screen are given by the computer as a part of the simu­ lation system, the corresponding 5-bit grayness code beiDg inserted directly into the computer core memory.

In spite of the small field of vision, the paper processing uni.t can scan sufficiently large pictures: up to 210 x 300 mm. 2 · lor this purpose the unit bas been equipped with a special movable carriage which the picture is fixed on, shifts of the carriage being controlled by the computer. A shifting rate (simultaneously in both directi­ ons) is about 25 mm/sec. An accuracy of the carriage setting in a given po­ sition is not worse than 0.1 mm. The computer has also controlled displace­ ments of the film frames, the rate of displacement being about 1 frame per sec and the accuracy of the frame set­ ting - about 0.02 mm.. A block diagram of the scanner units and connections with the local control unit is given in l!'ig.2. The display unit has been equipped with the CRl' having the scre­ en working area about 200 x 200 mm. 2 · Visually discernible gradations of the point brightness are about 12 to 14.

The system software possesses a block structure allowing an operative interference with the design of the simulated algorithms. The first-level

software includes:

• -- subroutine for the special modi­ fying of the computer supervisor which ensures the system functioning on the whole I
• subroutines for setting the nece­ ssary working rates and controlling the system units,
• subroutine for inserting parame­ ter values into the first-level batches in the process of system functioning by means of the computer control board;
• -- subroutines for forming scanning rasters with arbitrary parameters and searching for the separate images on the scanning field;
• -- subroutines for compressing and decompressing the digital information obtained by scanning during its inser­ tion into the computer memory and pro­ cessing;
• -- subroutines for geometrical trans­ formations (translation, rotation, scal­ ing) of the I/0 pictures, and so forth.

The second-level software accomp­ lishes the basic picture preprocessing:

• quantization, i.e. a changeover froa 32-gradation grayness scale to any lesser number of gradations:
• (a) the quantization with arbit­ rary given bounds or the new gradations;
• (b) the adaptive quantization where the bounds are variable and chosen to minimize a certain "distance" between

an initial picture and the picture ob­ tained as a result or the quantization (6)t

• discretization, i.e. a change­ over from an initial rectangular raster used for the picture representation to the new raster representation with any lesser number of the points:
• (a) the discretization with ar­ bitrary given bounds of the new raster cells;
• (b) the iterative discretization where the bounds are variable and chosen to provide a local minimum of a certain "distance" between an initial picture and the picture obtained as a result of the discretization;
• (c) the similar iterative dis­ cretization providing the local miniw1m of the "distance" between a given pro­ totype and a picture after the discre­ tization;
• digital filtering with an arbi­ trary rectangular filter. By assigning the definite weights to the filter po­ ints one could realize a number of the known procedures of isotropic and ani­ sotropic filtering, for example, a "co­ ntour line e:xtractioli' on the black­ white pictures.

Furthermore the second-level software covers geometrical transformations of the pictures given as numerical arrays, computations of a 2D autocorrelation function and 2D moments for these pic­ tures and so on.

The up-to-date third-level soft­ ware is less developed. It contains va­ rious modifications of the character recognition algorithms based on the co­ rrelation method, correlation algorithms for identification of the corresponding points on stereophotographs, algorithms for such identification using the di­ rected search through possible geomet­ rical transformations of the correspon­ ding parts on the stereophotos, etc.

In preceding years the first ver­ sion of the system described (7) was used to investigate a number of recog­ nition problems, e.g., for a comparati­ ve performance analysis of the correla­ tion and similar character recognition methods (8,9,10) 1 an examination of statistical models of typed characters (9,10), researches in different hand­ print recognition procedures (11), and the like.

Now the described system is ser­ ving as an experimental tool for rese­ arch in automatic stereophotogrammetry, cursive script recognition in the pro­ cess of writing, etc.

In the future the system is in­ tended to be supplemented with several modifications:

• introduction of pictures from broad film carriers (with a width up to 500 mm) 1
• -- TV input of real-world Bcenesi
• -- buffer memory (8 to 16K) to expand the system potentialities and im­ prove the interconnection with the com­ puter;

expansion of the software main­ ly towards the analysis of real-world scenes and the recognition of 3D obj­ ects.

REFERENCES:

1. S.M.Matsa. What has computer gra­ phics to offer. Computer Graphics, eds.R.D.Parslow et.al., Plenum Press, 1969
2. Y.Hoshimo, K.Kiji. Computer-aided design for a reader of hand-printed characters. Proceedings of the In­ ternational Joint Conference on Ar­ tificial Intelligence,Washington, D.C., 1969
3. r.: .!.linsky, S .Papert. Perceptrons, fUT Press, Mass., 1969
4. N.J.Nilsson. Learning Machines, McGraw-Hill, 1965
5. R.A.Wilson. Optical Page Reading Devices,Reinhold Publ.Corp., 1966
6. T.K.Vintsyuk. Optimal division of a sequence into subsequences. !1bernetika, no.4 1 1970 (in Russian)

• 7 ·. V.M.Gluahkov, V,A,Kova!evsky, V,I,R1bak. General-purpose device tor investigation ot pattern recog­ nition algorithms. Principles ot Selt-Leami.ng S:ratema Deaic, Kiev, 1962 (in Russian)
• 8, V,K,Rliseev, V,A,Kovaleva~. Inves­ tigation ot character recognition algoritba. J,CoaputatioD!l Math, Math, Pbzs., v.2, no.5, 1962 (in Russian)
• 9, G,L,GiMltarb, E,IP,Kuahner, Inves­ tigation ot statistical aodel ot
• ~d characters. Cybernetics and CoaputiQg Technique, v.~, Kiev, 1969 (in Russian)
• 10, G,L,Gimeltarb, E,P,Kuabner, Inves­ tigation ot statistical aodels ot t7Ped characters. Pattern Recogni­ tion and Deti59 ot Character Read­ !£!· v.1, Kiev, 1968 {in Russian)
• 11, E,P,Kuahner. IDYeatigation ot hand­ print character recognition algo­ ritha, Czberaetioa and Computing Teohniaue· v.3, Kiev, 1969 (in Russian)

Pig.1 Hardware ot the S~atem tor Simulation ot Pattern BecognitiDn A.lgoritbas

i - local control unit, 1i - paper processing unit, iii -- fila processing unit

.l - voltage-to-digital coDVerter, B - cOAtrol logic, C,B -- co-ordinate registers, D -- digital-t~oltage converter, P -- rocua r.gister, G - papel'-traneporting .. chanisa, H - !ila-traneporting ·chaniaa

~he !igurea 1,2,3,~,5 aark the conaectiODB to be oo .. uted when switching on the correapoDding unit