ZX Review #7-8-9-10 08 ноября 1997

Forum - An algorithm for recognizing characters.

(C) Group 'Light', Serpukhov


     Recognition algorithm

            Character


   In recent years, increasingly
there is a problem of recognition
text by computer. Not
hide the complexity of the problem does not allow 100% to 
realize it, even on powerful computers, not to mention the 
ZX-Speccy. However, the problem itself is

so interesting, that does not reach it is not necessary.

   As an example, analyze
algorithm to recognize pre-
well-known characters, composed of
'*' symbol.

   For convenience, imagine that
the whole field consists of the points. Thus,
Let the rectangular box the size of X rows and Y columns of 
characters '*' shows the letters P, T, O, C, G. The letters are 
arbitrary size, form letters rectangular, thick line - 1 
character. Let's also say that the letters have

only the direct orientation (the slopes of letters are 
excluded). Letters between is not in contact, and the minimum 
width and height of the letters - three characters.



   Thus, a sheet with the data
letters will be as follows:



   ...........................

   .*****..***.****.****.***..

   ...*....*.*.*....*..*.*....

   ...*....*.*.*....*..*.*....

   ........*.*.*....****......

   ............****...........

   ...........................


             Fig. 1


   This sheet shows the letters: T, N, C, D, G.


   As we can see each letter
is a rectangle. Most logical to do so,
program to recognize
first thought the picture made up of characters, 
two-dimensional array, and then broke character recognition. Ie 
the letter 'C' in Fig. 1, written in the array as follows

as follows:



              1111

              1000

              1000

              1000

              1111



   We now turn to the algorithm
character recognition. Consider the corner points of each 
letter. 

1. Upper left corner:


   . .

  .** - .** M - n, c, o, r

   . *

2. Top right corner:


   . .

  **. - M, c, d **. - N, o

   . *

3. Lower left corner:


   *

  .** - With about .*. - M, n, n

   . .


   That is, if the upper left corner
letter is in the form


              .

             .**

              .


   this means that the figure
represented by the letter "T".


   The detailed disassembly shows
that analysis of these three angles is sufficient to detect any
In the above letter. In
array angle can be defined as follows:



            S [Y-1, X]

   S [Y, X-1] S [Y, X] S [Y, X +1]

            S [Y +1, X]


S [Y, X] - the central symbol of the angle


   This shows that it is necessary
find the angles drawn letters.
To begin with we find the upper-left
angle. It is characterized by
that it satisfies simultaneously three equations:

S [Y, X] = 1, S [Y, X-1] = 0, S [Y-1, X] = 0


   At this stage, is already uniquely identified by the letter 
'T'. In this case, search for other angles

letters are no longer produced. In
Otherwise, we observed one of the letters: P, C, D, F, and we 
must continue to analyze further. Right corner we find, if

will move to found
line to the right until
instead of '1 'will not meet '0'. Lower left corner you can 
find a symmetric way. Must only to draw attention to the fact

that the lower left corner for the letter
'T' - it was her leg.


   Algorithm presented here
recognition can be
as follows:



                    "Identified by the symbol"

                                v


                         identification of "P S O G"

             "T"