Character Recognition System

Reference is made to a microfiche appendix of 3 microfiche containing 139 frames.

The present invention relates to a character recognition system (method and apparatus), and particularly to an optical character recognition system which is capable of automatical recognition of characters in a character set, which characters may be handwritten without restriction as to their shape or format.

This invention is related to and provides improvements in my invention which is described in U.S. patent application Ser. No. 07/626,517 filed Dec. 12, 1990 and entitled Character Recognition System, now U.S. Pat. No. 5,307,424, issued Apr. 26, 1994.

The invention is especially suitable for the recognition of handwritten characters, such as letters of the alphabet and numerals. The invention is, however, generally applicable for the recognition of symbols, and the term character, as used herein, includes other configurations or symbols which represent or communicate information by way of observable patterns.

Accurate and reliable character recognition requires that misrecognition of a character, erroneously as another character in the set to be avoided. It has been found that such false recognition is more disadvantageous than taking a character to be unrecognizable. While it is important in order to provide a system of character recognition which is commercially practicable to have the capability of recognizing 80 to 90 percent of characters in the character set, it is more desirable to maintain the rate of false recognitions below one percent.

From time to time patents have issued which relate to optical character recognition of handwritten characters (see U.S. Pat. Nos. 4,006,998; 4,628,532, and 4,837,842). At the present time, however, commercially practical handwritten character recognition systems of the type described in the foregoing patents or in accordance with any other known technologies have not been available.

The problem of accuracy and reliability of recognition is exascerbated by the vast varieties in which patterns representing characters in even a limited character set, such as arabic numerals, can be written. Accordingly presently known technology, which for the most part requires an immense memory of data and super high computational speeds, has been unable to bring automatic recognition of handwritten characters to the point of practical application.

The above referenced patent application provides advances in the technology which are needed and useful in automatic recognition of handwritten characters and like and enables the reduction of memory capacity and computational speed (the need for super computers and have enormous memory capacity) to be capable of recognizing handwritten characters which may be written with a large number of variations on a page (e.g., a business form), whether individually or in words or in multidigit numbers, with a high probability of recognition. The system of the above referenced application as well as this application is also capable of being operated with relatively low cost optical scanners, for example which have a resolution of 200 dots or pixels per inch. It is the principal feature of the present invention to enhance the recognition capability of the system described in the above referenced application in terms of the numbers of variations of the pattern in which the characters to be recognized are written and also in terms of reducing misrecognition of characters. It is a further feature of this invention to provide an improved character recognition system which can handle the recognition of handwritten or hand printed characters through the use of a computer of reasonable size and memory capacity, such as are commercially available at reasonable cost, such as a personal computer having a 32 bit (386-type chip) microprocessor. In accordance with this feature of the invention super or ultra fast computers and memories having the capacity to store sufficient data to provide matching patterns for the thousands of variations in which characters in a set can be written are not required. In summary, it is the object of the present invention to provide an improved character recognition system which advances the art of character recognition to the point where a commercially practicable system for automatically recognizing characters which can be handwritten in various shapes or formats may be achieved.

Briefly described, the system provided by the invention is operative upon a digitized pattern or bit map of individual characters which appear on a page which is read, as by an optical scanner, into computer memory. This bit map is translated or encoded into a plurality of recognition tables each describing the character in a different way. Each of these ways depends upon the relationship of the data representing pixels in a matrix of rows and columns (x-y coordinates) in which the pixels (data representing each pixel) are located in the bit map. These tables are obtained from the bit map and from a skeleton of pixel representing data which follows the center line of the character pattern of the bit map and may be obtained by a thinning computation as described hereinafter and also in the above reference U.S. patent application. One of these tables, which is preferably derived from the skeleton pixel matrix, is obtained by encoding the matrix into another matrix represented by connection codes indicative of the relationship of pixels in each row to pixels in adjacent rows. These connection codes are reduced, so as to encompass a plurality of character shapes, into further codes so as to define a string of digital signals which constitutes one of the recognition tables. The other recognition tables encode the relationship of pixels in successive rows along the borders of bit map and pixel map into strings of digital signals. These tables are utilized selectively in order to recognize characters in the set. Recognition proceeds by searching a recognition file containing blocks of successions of digital signals. These blocks are preferably arranged in hierarchal order with groups of blocks representing characters of the lowest level of recognition difficulty next and so forth. Each block contains instructions as to which table or which bit map to search for data in lines of the table (which correspond to rows in the bit map or pixel skeleton map) to search for a match with the block. Preferably the file for each character of each level of recognition difficult is proceeded by a block which, if matched, excludes that character. Then the searching of the file can proceed directly to the next character in that level or to characters of the next more difficult level of recognition difficulty. Once a character is recognized it is stored and the program proceeds to the next character on the page. If the character is unrecognizable, information to that effect is stored in the data file and the program proceeds to the next character on the page. Accordingly all of the characters on the page are processed for recognition. The system provides recognition with a high level of acccuracy and reliability, both recognized and unrecognizable characters being determined by the system.

The foregoing and other object features and advantages of the invention as well as a presently preferred embodiment thereof and the best mode now known for practicing the invention will become more apparent from a reading of the following description in connection with accompanying in which:

FIG. 1 (consisting of FIGS. 1A, B and C) is a block diagram and flowchart showing an embodiment of the system in accordance with the present invention and the programming of the computer in which the system is implemented, on an overall basis;

FIG. 1D is an exemplary field of numerals in an exemplary character set which is subject to recognition by the system shown in FIG. 1;

FIG. 1E are diagrams showing exemplary bit maps, for the numeral 2 and for the skeleton of numeral 2 after pixel correction;

FIG. 1F are diagrams of pixels in rows and adjacent rows which may be found in the skeleton matrix and connection codes corresponding thereto;

FIG. 1G are exemplary diagrams of pixel skeleton matrixes for the numerals 2 and 8 showing some of the connection codes which are derived from the relative position of pixels in rows and adjacent rows of the skeleton matrix;

FIG. 1H is a pixel skeleton matrix for a pattern of the numeral 2 showing connection codes and combinations of connection codes for each row thereof;

FIG. 1I is a diagram similar to FIG. 1H showing connection codes obtained from the pixel skeleton matrix of a pattern representing the numeral 5;

FIG. 1J is a view similar to FIGS. 1H and B of a pixel skeleton matrix representing the numeral four and the connection codes for each row thereof;

FIG. 1K is a diagram similar to FIGS. 1H, B and C showing the pixel matrix skeleton for an exemplary numeral three and the connection codes for each row thereof;

FIG. 1L is a view of the bit map for an exemplary numeral four indicating the codes representing the borders on the left and right side thereof (front and rear views);

FIGS. 1M and 1N are respectively bit maps of exemplary numerals 4 and 7 showing codes representing an upper border and a lower border to the extent of holes therein which are open from the top and the bottom of the bit map, respectively;

FIG. 2 is a diagram schematically showing the scanning of a page on which characters to be recognized are written and showing the organization and allotment of computer memory space;

FIG. 3 is a flowchart of the scan page routine of the program for inputting the scanning data into the computer memory (input control on addressing as shown in FIG. 1A);

FIGS. 4 and 4C is another flowchart which shows the teach program which defines the fields or zones where the characters are placed in computer memory;

FIG. 4A is a diagramatic view of a page or paper sheet showing selected areas wherein characters are located by frames;

FIG. 4B shows an expanded view of the zones (boxes or fields) in a frame;

FIG. 5 is a flowchart which illustrates the program for thinning the bit map (the pixel pattern of a character in an exmplary 128 by 128 matrix in rectangular coordinates wherein the direction of movement in the matrix is from the upper left corner to the lower right corner, the thinning process providing a skeleton following the center line of the pattern of pixels in the bit map;

FIG. 6 is a flowchart showing generally the routine for obtaining the connection codes;

FIG. 6A is a more detailed version of the flowchart shown in FIG. 6;

FIG. 7A and B is a flowchart showing the routine for obtaining the direction codes constituting the data strings in the recognition tables defining the borders of the bit map;

FIG. 8 is a flowchart of the program for obtaining the direction codes defining the borders (front and rear views) of the pixel skeleton matrix;

FIG. 9 is a flowchart of the program for obtaining hole codes.

FIG. 10 is a flowchart of the program for developing the recognition table from the connection codes in the pixel matrix which the connection codes constitute;

FIG. 11 is a flowchart showing the recognized routine wherein recognition files are searched for matches with data from the recognition tables;

FIG. 11A is another flowchart showing a version of the recognition routine which illustrates the processes for data reduction of the connection codes and for searching through tables of data reduction (MT blocks) and rows and through blocks (MA blocks) and B blocks in the recognition file;

FIG. 12 is a flowchart illustrating the execution of the recognition routine in recognizing a typical character;

FIG. 12A is another flowchart showing the arrangement of the recognition file in a hierarchy in accordance with the level of difficulty of recognition, lowest level of recognition difficulty first, in a general way; and

FIG. 13 is a flowchart showing the program for the separation of character fields for recognition, which is an operation illustrated in FIG. 1A.

As shown in FIG. 1, the scanning of a page is carried out by an optical page scanner 10, which may be a low cost scanner having a resolution of 200 dots (pixels) per inch. The scanner provides digitized scanner data where each row is one pixel high and the length of the row is equal to the width of the scanned paper page. This data is inputted via the computer into computer memory. The computer may, for example, be a desktop terminal or personal computer which is capable of handling 32 bit, words, or bytes. The program proceeds through the input control and addressing of the digital scanner data and the control of the memory addresses which in effect overlays a coordinate system of rows and columns ("x") in the row direction and ("y") in the column direction) in the computer memory. As explained more fully below, characters are assigned fields on the page and data (e.g., in the scanner output) from the rest of the page is not used. The program proceeds through these operations of input control 12 and overlying coordinates 14. These operations will be more apparent from FIGS. 2 and 3.

The data input from the scanner may be a multibit byte or may be thresholded so that the intensity of any dot is marked as set for a black point and nonset for a white point of intensity less than the threshold level. A typical page is shown in FIG. 2 as being 8" wide. Considering the resolution of the scanner is 200 dots (pixels) per inch, each row contains 8 times 200 or 1600 pixels. Since one 8 bit byte of memory can carry 8 pixels, one scanned row requires only 1600 divided by 8 or 200 bytes of RAM. The digitized, scanned data is organized in the memory by locating the scanned rows one after another in memory. For a typical character, 1 mm in height and with the 200 dots per inch resolution, 8 rows of pixels are needed. Therefore, if a character is, for example, 4 mm high it needs 4.times.8 or 32 rows to be stored in memory. A page 11" in length contains 11.times.200 or 2200 rows in the y direction, and if 8" wide contains 8.times.200 or 1600 pixels per row in the x direction. The total capacity to store an 8.times.11 sheet is then approximately 440 Kb of memory space. Such memory space is well within the capacity of RAM devices or hard disk memories which are commercially available at low cost. Such memories have additional space for work areas where bit maps representing the data can be stored. It is desired to store data in bytes rather than thresholded bits since the computers' operating systems are designed to work on a byte-by-byte basis. Thus, the working areas desirably consist of byte locations. In the herein illustrated system, there is provided a working area for a character bit map which defines a matrix of 128 rows in the x direction and 128 columns which extend in the y direction. One of these working areas stores the bit map defining the shape of the pattern forming the character as it is handwritten on the page which is scanned by the scanner. The other working area is another matrix of 128 rows (in the x direction) and 128 columns (in the y direction).

The characters to be identified are segregated into zones or fields through the use of the teach program, guided if desired by a display of the overall page bit map on a monitor as shown at 16. The characters are then separated out of their frames individually and one at a time for recognition as shown at 18. Fields may also be defined each for different kind of characters, e.g., "handprinted numbers", "handprinted capital letters", "printed number", "printed capital letters", "printed small letters", "handprinted small letters" or "script" . . . starting from the first character . . . of each field and then field by field in a predefined sequence, e.g., from the field nearest the upper left corner of the page to the field nearest the lower right hand corner of the page.

The character field which is selected for recognition is converted into the 128.times.128 byte bit map. The term bit map is used because the bytes which represent the dots (pixels) may be 8 bits all set or ones. The bytes representing the absence of pixels in the matrix are all clear, i.e. are zeros. Thus, the bytes in effect constitute a bit map. This bit map is stored in one work area of memory as shown at 20. After pixel correction 22, which aligns the pixels in the map which extend along rows at the top and bottom and in the middle of the map, the map is converted into a pixel skeleton map 24 by the thinning program (FIG. 5). The pixel skeleton map is also a 128.times.128 byte matrix. It is stored in the second work area (2) of the memory.)

The scanning program is stored with the other programs which carry out the operations shown in the flowcharts in the working memory of the computer (in RAM). As shown in FIG. 3, the operating system of the computer provides the start address where data is stored. Then the digitized data is transferred from the scanner. The transfer occurs one row at a time until all of the data is stored. For example, if the start address for the first row is 1,000, then the next row will start at the start address plus the length of one line of bytes of 1,000 plus 200 which equals 1,200. Because the length of each line is known, the digitized pattern is effectively drawn in an x, y coordinate system. This coordinate system in the above example has its base point at memory address 1,000 where the pixel data for the upper left-hand corner of the page may be found. Generally, the addresses of a pixel in the memory is equal to the start address plus the number of the column, multiplied by the length of the row, plus the number of the row divided by 8. The position of the pixel in the 8 bit byte (the bit position) equals the row number in octal or modulus 8 code.

The segregation of the zones or fields will become more apparent from FIG. 1D. A frame consisting of a string of numerals is shown enlarged in FIG. 1D. The program separates such a frame from other fields on the page and then proceeds to separate individual characters into character fields. These character fields are shown enclosed by boxes 26 and 28 in FIG. 1D. A bit map for an exemplary character, the numeral 2, which is provided by the conversion of the field into the 128.times.128 bit map matrix is shown in FIG. 1D. The skeleton matrix for the same character as shown in FIG. 1D is depicted in FIG. 1D. The bit map has undergone pixel correction of its bottom row before the conversion into the pixel skeleton shown in FIG. 1D. This conversion effectively smooths the bottom and top of straight lines. The base of the pixel pattern for the 2 in FIG. 1D has a misaligned partial row of pixels on the top thereof and two misaligned rows of pixels on the bottom thereof. The pixel correction operation searches the pattern for such misalignments and smooths them. When the pixel skeleton is calculated, it follows the center line of the pattern. Therefore, the base of the numeral (2) in the pixel skeleton is formed as a straight line of pixels.

Next, consider the teach program as shown in FIG. 4. This program provides information as to where on the page the characters are written. The teach program marks the areas where the frames and zones (boxes or fields) containing the characters to be recognized are located. FIGS. 4A and 4B illustrate the frames, zones, and boxes or fields. There is a character field or box and more than one character is in a frame or zone as designated in FIG. 4B. FIG. 4B shows one of the frames on the page shown in FIG. 4B.

The teach program uses the digitized page in memory. The page is displayed in reduced form on a monitor. The reduced form contains only every 8th pixel; thus, only every 8th pixel is displayed. In this reduced form, the operator can define the zones by interactively putting frames around the parts containing characters utilizing a graphics program, forming a cursor on the monitor, to define the coordinates of the frames. The coordinates are stored in a file with the extension (name) "AUS". This file consists of coordinates for the upper left-hand corner and the lower right-hand corner of each frame. In the file, the coordinates can be separated by semicolons. The file, therefore, has the coordinates of the x upper left corner; y upper left corner, x lower right corner, and y lower right corner. An example of the AUS file is the addresses 524; 638; 1200; 920. Another AUS file safe for the second frame may be 767; 170; 845; 250.

After the AUS file is developed, another scan of the page is completed. Now the display on the monitor shows the defined areas and fields (zones) can be interactively placed around the areas in which the characters are located. For example, the adjacent numerals 1-0 shown in FIG. 1D constitute the zone where the file starts from the upper left of the numeral 1 on the first line and ends at the lower right at the numeral 0. The zoned marking step is used to mark and define the zones in memory. Every frame may be more specifically defined by the type of entry into the file. Possible types are: (1) for a marked area; (2) for numbers; (3) for letters; (4) for a group of numbers; and (5) for a group of letters. If the field type is a marked field, the program for recognition is somewhat different than for other characters. The number of pixels in the field is counted and compared with information about the zones which is stored in the file which is called by the name " rec" .

Each line of the rec file has the following structure: "x" upper left; "y" upper left; "x" lower right; "y" lower right; average pixel count (only for marked fields); maximum pixel count (only for marked fields); teach count (how often has the field gone through the teach program); text string (for later diagnostic purposes); and field type. By how often the field is taught is meant, how many times it is scanned in the operation of the scanner. It may be desirable to scan each zone 10 or 15 times and get the average count of the area of maximum pixels which can be contained in a zone. An example of an rec file is as follows:

1783; 243; 1833; 276; -1; -1; 10,000; 0; 525; 1;

1783; 202; 1831; 236; -1; -1; 10,000; 0; 526; 1;

1783; 164; 1832; 197; -1; -1; 10,000; 0; 527; 1;

1783; 123; 1834; 160; -1; -1; 10,000; 0; 528; 1;

If the field is a number field, that information is designated in the rec file by the -1; -1; which in this example are initialized values for the average values of the pixel count since this example is for number fields (FIG. 1D). 10,000 is the initialized value for the peak pixel count. The numbers referred to the coordinate system which is designated the addresses in memory from the rec file; i.e., the part of the page (image) to be recognized as being designated. Marked types (periods or other punctuation) can be recognized merely by a compare of the pixel counts for the fields with designated pixel counts; fewest for a period, slightly more for a comma, etc. Other marked fields are not considered in this example. Another feature of the teach program is to define fixed points (anchors) on the page which may not always be in the same position due to skew in the scanner. To correct displacement due to skew, the program calculates the distance from an anchor point to a fixed point on the paper. This distance is stored in the file with the name "jus". Corrections from the jus file may be used to correct each character field before separation of the individual character fields one at a time for recognition as shown at 18 in FIG. 1A.

The routine for separation or segmentation of a zone into character fields is illustrated in FIG. 13. For an exemplary zone of numerals, zero, 2, 6, 5, and 4. The coordinate system in memory is indicated by coordinates x(1), y(1) and x(2), y(2). The program searches for empty spaces between characters starting from the left and going right (i.e., from x(1) to x(2) in this example. When x=x(2), segmentation or separation of all the characters in the zone into their respective fields in the x and y directions has been completed and the x and y coordinates of the corners of each field are stored in the separated character file. The addresses in the file identify the characters on the page, starting from zones in the upper left-hand corner of the page to the end of the zone in the lower right-hand corner of the page. After each character is recognized, the program indexes to the next character at the next address in the file until all of the characters are recognized sequentially and individually. The program shown in FIG. 13 illustrates how the x coordinates are obtained. The y coordinates of the character fields are obtained similarly. The program continues until x=x(2) and the end of the zone is reached. Prior to the end of the zone, the start of a field is indicated by an empty column in the computer memory space in which the page is stored. By empty is meant that no pixels are set in the y direction as the memory is scanned in the x direction (along the rows). The number of the first column which is not empty is the address of the start of the character. Similarly, the number of the column succeeding columns which are not empty is the address in the x direction of the end of a character field. The separation program effectively embraces the characters by boxes such as shown at 26 and 28 in FIG. 1D.

The thin or thinning program as shown in FIG. 5 is also described in the above-referenced U.S. Patent application. The thinning process calculates the center line of the pixel pattern and is one pixel thick. The program follows the algorithm reported in the text authored by T. Pavlidis and entitled, "Algorithms for Graphics and Image Processing", published by Computer Science Press, Rockville, Md., U.S.A., 1982. The German edition was published by Heinz Heise GmbH of Hanover, Germany, and the Algorithm is in Section 9.2 of that text.

Returning to FIG. 1 and particularly FIG. 1B, the recognition operations are conducted utilizing the bit map matrix in work area (1) and the skeleton matrix in work area (2). The purpose of the recognition operations is to find characters in the ASCII alphabet of characters, numerals and other symbols which correspond to the patterns in the bit map images in these work areas. As a result of the recognition, a data file is obtained which defines the characters on the page starting from the upper left-hand corner, proceeding down the page line-by-line until the lower right-hand corner is reached. However, the sequence can be otherwise. For example, numeric field can be processed first, then letter fields, etc. These characters are then available together with their addresses on the page for automatic processing of the forms or documents which have been automatically read; thereby, avoiding the need for manual entry (keypunching) of the characters on the form. The recognition operations are discussed herein, particularly with reference to the recognition of a character set consisting of Arabic numerals, specifically the numerals 1-0. It will be appreciated that other characters such as alphabetic characters and special symbols may be recognized irrespective of the patterns in which they are handwritten or otherwise entered on the page.

The recognition process effectively starts by the computation of connection codes from the skeleton map which is stored in work area (2) in the memory to form a description of the memory space in terms of the pixels stored therein. The connection codes are then stored in an array which is referred to as the pixel matrix. The computation proceeds by scanning the skeleton row by row, starting from the top row of the 128 rows in the work area and ending on the bottom or 128th row. The connection codes are selected from prescribed codes which represent a combination of the length and number of columns over which the skeleton extends in a row and the connection of the pixels in that row (whether one or more) to the pixels in the adjacent rows, both above and below the row being scanned. The connection codes indicate either line length, hole length (the length in number of columns in a row which do not contain pixels), and directions. There are also special codes indicating the start and end of the line. These codes are represented by single or multiletter symbols and are shown in FIG. 6.

FIG. 1F illustrates some of these codes. There are single element codes such as "S" for a single unconnected pixel in a row and "O" for a single hole in a row. Where a hole is several columns long, it may be represented by the code "LO" followed by a symbol, ("<"). Following the code indicates the length of the element. Thus, LO<n is the connection code for a hole which is n elements long in a row of pixels. In summary, the following is a glossary of the connection codes:

Referring to FIG. 1.3.2, the special characters E and A are shown in the case of the (2). In the case of the (8), VA and VU connections are shown at the upper and lower parts of the (8). The lower loop of the (8) defines an "SOS" (or "LO") s connection. It will be apparent that a line can have a plurality of connection codes. Thus, the pixel matrix can be one dimensional, but is more likely to be two dimensional.

FIGS. 1.3H-K show three different characters and their connection codes. These codes define the pixel matrix of the particular characters illustrated. The pixel matrix of connection codes is two dimensional in these examples. It is desirable to present the pixel matrix in the form of a one dimensional character string, thereby reducing or compressing the connection codes for the character. This is done by computing one of the recognition tables which is the pixel matrix table. In computing the pixel matrix table, as shown at 30 in FIG. 1B, different codes are assigned which are referred to herein as MT codes. These codes then define a one dimensional matrix description of the character.

The recognition table of MT codes is generated in two operations. First, the computation of the connection codes to provide the pixel matrix, as shown at 29 in FIG. 1B, and then the assignment of the MT codes to form the MT code recognition table is shown at 30. These MT codes are selected, not only for reduction of the amount of data which is handled in recognition, but also for the purpose of enlarging the various patterns and shapes which can characterize particular characters in the set thereby reducing the number of operations (searching of recognition blocks in a recognition file, an exemplary file being reproduced below) needed in most cases to recognize a character. It is desirable to recognize a character without scanning the entire recognition file. The entire recognition file is scanned in its entirety only when a character cannot be recognized and is not found unrecognizable by a match with a block higher up in the file.

The system generates additional tables used in recognition so as to guard against misrecognitions as well as increase the recognition rate of the system. These tables contain front and rear view codes indicating the relationship in the direction in which the pixels are displaced along the left side (front view) and right side (rear view) of the bit map and of the pixel skeleton map. The bit map in work area (1) and the pixel skeleton in work area (2) are used to compute front and rear view codes from the bit map store and memory as shown at 32 and from the skeleton stored in memory as shown at 34. The direction codes are the letters A, L, X, M, Y, R and B for the front view. The same letters are used for the rear view. Each front view direction code is computed from the number of columns the end pixels in each row of adjacent successive rows are offset from each other. The computations also include limits which are parameters stored in memory upon initialization. The front view direction codes (ai) utilize the column location of successive lines (the i and i+1 lines) on the left side of the bit map in work area (1). The parameters are indicated as P1 and P2. These parameters set the limits or extent of change in shape and differentiate certain front and rear view codes.

FIG. 7A shows the front view codes and the computations thereof. It will be noted that these codes differ in terms of their relationship to the P1 and P2 parameters. The M code, as in the case of the connection codes, indicates a straight down connection. The direction codes obtained on scanning each of the rows in the work area are stored in a recognition table which is referred to as the FVDC Table A.

The rear view direction code RVDC Table B is obtained by the computations shown in FIG. 7B which are similar to those used computing the front view, but consider the location and column number of the pixels at the ends of successive adjacent rows starting from the top and going down to the bottom of the bit map in work area (1). As shown in FIG. 8, direction code strings defining the borders of the pixel skeleton are derived using the same equations as used in deriving the FVDC--Table A and RBDC--Table B. These recognition tables constitute direction codes (ci) and (di) and are strings contained in Table C and Table D of the recognition tables. For the bit map in work area (1) for a typical character, here the numeral 4 is shown in FIG. 1.4, adjacent each row on the left is a sequence of the codes which are in Table A for the front view string (ai). The string of codes on the right are the rear view codes which appear in Table B.

Referring to FIG. 6A, there is shown a program for the generation of the connection codes in the pixel matrix from the data in the pixel skeleton map. The rows of the map are scanned. These rows are referred to as lines in FIG. 6A. The first line scanned is the first line containing a pixel. Scanning continues until the last line containing a pixel is reached. This is denoted by the operation "while line not equal to last line of character". The lines are scanned from left to right as indicated by the operation "while current element not equal to last element (pixel) of line". The length of the elements are computed and the connection codes are computed from the line length codes and the current element (column position) of the pixels in the adjacent rows. The program loops until all of the lines are scanned. In addition to the single element codes, the following is a glossary of the connection codes. These codes may, in a computer which is capable of processing data in 32 bit bytes, be a byte position code which is set in one of the 32 bit positions for each of the connection codes. The single element codes were discussed above and are shown in FIG. 1F. The following is a more complete glossary of the direction codes.

Additional recognition tables of additional strings of bytes are also computed to represent holes in the characters depicted by the bit map in working area (1). These are for holes open at the top and closed at the bottom as is the case for a numeral 4 shown in FIG. 1M. A separate table is computed for patterns which are open on the bottom, such as is the case for the numeral 7, as shown in FIG. 1N. These computations are indicated by the operation shown at 36 in FIG. 1B. As shown in FIG. 9, the bit map area (working area (1)) is scanned from the top row down and a string (STR-1) is computed in terms of the number of columns in the space between pixels and rows along the side of a hole open at the top. This string is stored in memory as the HOAT--Table E and the HOAB--Table F. There are, therefore, six recognition tables as well as the bit map and pixel skeleton which depict the character and which are useful for recognition.

Referring to FIG. 10, there is shown the routine for reducing the pixel matrix to a one dimensional code referred to as the MT codes. There is one MT code for each line of the pixel matrix. However, if the pixel matrix is ready encoded with connection codes, such as discussed above in connection with FIG. 6A, including the single element codes O, S, and M, then the reduction routine is not used and the recognition table consists of the connection codes which then constitute a string in one dimension. The reduction or recognition table program proceeds first to initialize the system by entering variables representing the MT codes. There may, in a 32 bit computer system, be up to 32 of such variables. The following is a table of such variables which are used in the herein described system.

Also, entered are MT blocks which relate the MT codes to different combinations of lines on the pixel matrix. In addition to MT blocks, there are entered on initialization MT lines which corollate individual lines of connection codes (not successive as in the case for MT blocks) to MT codes. Exemplary MT blocks and lines are shown in the following table. The MT blocks are plural lines which use a number of lines of the pixel matrix of connection codes. The blocks start and end with open and closed brackets ({,}) which depict the beginning and end of each block, these brackets are shown in the table depicting the blocks. The MT lines can translate the connection codes which consists of MT codes and connection codes which are obtained by a plurality of loops through the recognition table program. The program proceeds until all connection codes are translated. As noted above, translation can be into the MT codes contained in the code table or single connection codes such as the LO and SM codes. These translations are dictated by the MT rows and blocks. Exemplary MT blocks and rows appear in the following table entitled MT blocks or rows.

In carrying out the recognition table program, the pixel matrix is scanned for combinations of adjacent connection codes for rows which match the MT blocks in the order in which the MT blocks appear in the code table. The code table is the table of MT rows and blocks which is entered upon initialization of the system. As shown in FIG. 11A, the recognition process may involve entering not only all of the MT blocks and rows which define the code table, but also the recognition blocks which are referred to as MA blocks and exclusion blocks which exclude different characters and are invoked from MA blocks. FIG. 11A shows that the recognition table which contains the connection codes is scanned line-by-line, first when switched to the MT blocks and rows so that the pixel matrix can be reduced to the single dimensional string constituting the recognition table corresponding to the pixel matrix. The reduced data in that recognition table as well as the data in the other recognition tables for the borders of the pixel patterns in the bit map and skeleton map and the hole recognition tables E and F and even the bit maps in both working areas are available for use to obtain recognition of characters even of the highest level of difficulty of recognition.

Returning to FIG. 10A, the program is shown in greater detail for the development of the recognition table of MT codes. This program involves scanning the matrix line-by-line in order to match the MT blocks, then MT codes are stored by substituting an MT for a connection code in the pixel matrix. The pixel matrix is then scanned with the substituted MT codes, line-by-line until all lines having several connection codes are replaced with a single code, either from the MT table or another connection code.

Referring again to FIG. 1 and particularly to FIG. 1C, the recognition files (MA files) which are entered in memory on initialization are scanned as shown at 38, define a match with lines from or the entirety of strings in the recognition tables these recognition files contain successions of digital signals. Each succession is headed by MA or B in the representative recognition file presented below. These files are grouped in blocks. There are referred to as MA blocks which are assigned to different characters. There may be several MA blocks for each character. The MA blocks are grouped first to direct the system to index to the next character when, for example, all or most of the recognition table corresponding to the pixel matrix shows empty rows (code EE). The same operation is then carried out as would occur if a match were obtained from a MA block and the character was recognized, or, all of the blocks were scanned and the pattern was found to be unrecognizable. In other words, the durchlaeufer (runthrough in English) provides a quick jump to the next character field. (See FIG. 11.)

Similarly, there is another MA block known as the fraglich (or uncertain in English) block for codes indicating that the character is in the first instance unrecognizable. Thereby, avoiding the need to examine any further MA blocks for that character field and causing the program to index to the next character field. By indexing to the next character field is meant the page bit map of the character field is written into the 128.times.128 byte working area (1) in memory. Then the map is thinned using the routine shown in FIG. 5 to provide the pixel skeleton map in working area (2).

The recognition files include blocks referred to as B blocks since they all start with a letter B. They are identified by a name in the first line thereof and may consist of several parts, each ending with the code BE. The blocks are invoked by calls in the MA block. The blocks are exclusionary in nature. If a match of the recognition table information with a B block occurs, generally the character described by the MA block invoking the B block is excluded. Exclusionary B blocks for other characters may be invoked to recognize a character of interest. As shown in FIG. 12A, the recognition process generally proceeds through different levels, each containing groups of MA blocks. As explained in greater detail below, the successions are examined successibly. Each succession in each block is represented by data in the form of digital signals in the memory where the recognition file is stored. The MA blocks are separated by exclamation points (!) in the recognition file. An MA block which calls a B block is generally invoked first via the recognition file, then directs a jump to the blocks for another character in the set of the same level of difficulty to recognize, or if all MA blocks in the group for that level of difficulty have been scanned without finding the character to jump to the next group for the next higher level of difficulty. The MA blocks can, as shown for the O block for the first character, an 8 or acht, may invoke the front and rear view tables. The lines which invoke these tables are headed F&R.

There follows a representative file of MA and B blocks with an index indicating the type of blocks. The blocks for the lowest level of difficulty are indexed under numbered tabs on the left in the index 3-12. Not all characters in this set are deemed easy to recognize. Therefore, the next level of difficulty which includes some characters not in the first level, start at index Tab No. 11 and continue to Index Tab No. 22. Interspersed are the B blocks which are called from MA blocks. When recognition is found, the last line of the MA block is reached. In this last line appears the word "ergebnis" or result followed by a less than sign (<) with the character which is found. ##SPC1##

A typical example of a search of the recognition file is illustrated in FIG. 12. The recognition table and if called for Tables A and B are compared line by line with the MA block. The MA block contains instructions dictating how the search is to be performed. The MA block may simply direct the search through a few lines of the recognition table representing the pixel matrix. For example:

There are other symbols which constitute instructions for the search. They include: ()--no limitation on the number of repetitions or times that the code or codes in the MA line appear in the table; (>n)--at least n lines with the same code must follow in the recognition table; (<n)--no more than two lines having the code or codes in the MA line are allowed to follow successively in the recognition table; and a $ sign means the last line of the recognition table.

There are also various function lines. For example the ? mark is a function which searches for a specified pattern from a particular line in the recognition table. For example the codes which must be found are indicated. For example: MA? SX, SM-LY+SY () means search from the line in the recognition table obtained from the skeleton pixel matrix which corresponds to this MA line for the pattern SX or SM, but a match will not be found if LY is encountered or if SY is not encountered. Another function is GO TO. The GO TO function allows skipping of lines or areas of the recognition table not of interest. For example B GO TO $ may be found in a B block and is an instruction to jump to the end of that block.

There may also be a jump function which moves the search up or down the recognition table. It can even be used as a double check.

The winkle or angle function instructs a search of the bit map in working area one and invokes a program to calculate the angle between two straight lines on the front side of the bit map. The limits of the angle are specified in the parenthesis after the word winkle. For example (68, 120) means that the angle must be greater than 68 degrees and less that 120 degrees. The LOCH function is used to instruct a search of the pixel skeleton and is used to distinguish numeral four from a nine. Five variables are checked namely (a) how many lines from a line where a hole starts to the first line of the skeleton; (b) how many lines from the last line of the skeleton to the end of the hole; (c) the length of the hole in the line where the hole starts; (d) the number of lines having the same hole length so as to pick up parallel holes; and (e) the number of lines where the hole length decreases.

The NOT function merely inverts the logic of the search. For example NOT SX SM is satisfied if the line does not contain an SX and also following an SM. If it contains any other code the line is satisfied.

The LOCHLAENGE function measures the length of a hole in a line of the pixel skeleton. For example LOCHLAENGE ($, 3, 5) means that the length of the third line in the bit map must be greater than five columns in the matrix.

The WENN function checks the entire recognition file corresponding to the pixel matrix. An inverted carrot or the roof symbol means the top of the recognition file. An N followed by a carrot means that the line is not at the top of the M key table, and as noted above a $ sign means that the code is the last line of the table. An N$ means the code is not in the last line of the table. Thus for example MA WENN LY SY SM N$ looks for a pattern LY SY SM and the SM must not be the last line of the table.

The WENNICH function reverses the logic of the WENN function.

The AWINKLE function scans the bit map for an interior angle so as to distinguish a one from a seven.

The GESCHLOSSEN function scans the pixel skeleton map in work area two for holes of certain length.

The ANZAHL function is operative when a previous MA line calls for a repetition of the M key codes; i.e. where the number of codes are present in a certain number of lines. This function scans the table to find the total number of M key codes which are found at least a certain number of times in the recognition table. Another function is PRUEFEU 1 and is used for distinguishing numerals patterns for ones and twos. The function goes to the bottom line of the pixel skeleton to find if the percentage of the line length to the left is in a certain range of the total line length. For example PRUEFE 1U (38, 100) means that the line length to the left is from 38 to 100 percent of the total line length thereby indicating that the pattern represents a two rather than a one.

The LOZ function interrogates the pixel skeleton for a closed hole. The LOO function interrogates the pixel skeleton for an open hole. The ANZAHLH function checks the pixel skeleton for the number of shifts to the right in a certain number of lines in the rear view of the skeleton and is used to distinguishes threes from fives. The NAZAHLV function again interrogates the pixel skeleton and is similar to the ANZLH function but looks at the front view of the skeleton.

The NEUNLOCH or nine hole function interrogates the bit map for the size of the opening of a hole thereby distinguishing nines from fives. The ROWN function interrogates the pixel skeleton work area (2) for the number of rows containing pixels and is used to limit the search for MA lines, thereby setting borders, which if exceeded, exclude that block as corresponding to a valid character. For example, B ROWN (<35) is true if the number of lines in the bit map in the work area is less than 35. The ROWNP function as opposed to the ROWN function checks the number of rows in the bit map work area (1), while the ROWN checks the number of rows in the skeleton work area (2).

The LINE function checks for special connection codes which were not reduced to a single MT code in the remote possibility that a connection code combination was not reduced to the MT code. The MT line function restricts the line function search to a particular line in the recognition table. The PARALLEL function looks for an open hole in the bit map. For example parallel (3, 7, 2) searches the bit map for a parallel section from the third line with a hole over seven consecutive lines with a tolerance of two pixel spaces (2 rows).

Returning to FIG. 12, it will be observed that the program can proceed to a B block when called for in an MA line. The program jumps to the file containing the B block. The MA block may be instructed to jump to the next MA block for this character when the command NEXT appears instead of the RESULT command, ergebnis, at the end of the MA block. When a NEXT command appears the table is searched until a + sign is reached. The + sign indicates the blocks for the NEXT search and are usually blocks representing the same character or another character at a higher recognition difficulty level. After all MA blocks have been searched following instructions therein, either a match is detected and the character is stored in terms of the ASCII code therefore in the data file or a ACSII character for a ? mark is stored indicating an unrecognizable character has been found at some stage of the search through the recognition file.

As shown in FIG. 1 by the decisions 40 & 41, the program loops and repeats the recognition program to repetitively separate individual characters and recognize them until all characters on the page are recognized or found unrecognizable.

The microfiche appendix contains source codes for programs which carry out the routines illustrated in the foregoing flowcharts. These source codes are presented solely for purposes of example and it will be appreciated that the routines can be expressed in other source codes. The code is presented below with a copyright notice indicating that all rights therein are reserved. A glossary of German words and their translation follows the source codes.

From the foregoing description it will be apparent that there has been provided an improved character recognition system especially adapted for recognizing handwritten characters which may be written in different shapes and formats. Variations and modifications and other applications of the herein described system, within the scope of the invention, will undoubtedly suggest themselves to those skilled in the art. Accordingly the foregoing description should be taken as illustrative and not in a limiting sense.