Method and Apparatus for Isolating Image Data for Character Recognition

This application is related to Application Ser. No. 452,563 entitled "Banking System and Method" which was filed on Dec. 23, 1982 and which is assigned to the same assignee as is this application.

This invention relates to a method and apparatus for segmenting image data associated with two characters, for example, so as to present the segmented image data to character recognition apparatus to effect machine character recognition.

In the continuing trend to automate business operations, like banking operations, for example, there have been efforts to read, automatically, machine and handwritten data. In banking operations, for example, efforts have been made to machine read handwritten "courtesy" or monetary amounts on documents, like checks. One of the problems in this regard is that individuals do not always write the numbers for monetary amounts in regularly-spaced areas without overlapping or touching adjacent numbers. While touching or overlapping numbers on a document can be read routinely by a human operator, such numbers cannot be read accurately by character recognition apparatus.

In the named co-pending application, there is disclosed a system for automatically reading the courtesy or monetary amount of a check from its associated digitized image. The present invention is useful in such a system.

An object of this invention is to provide a relatively simple and low-cost method and apparatus for processing image data associated with characters so as to facilitate character recognition.

In one aspect of the invention, there is disclosed a process of segmenting data bits derived in response to scanning characters, comprising the steps of: (a) isolating a discrete group of said data bits which may be associated with more than one character; (b) examining said discrete group of data bits according to predetermined criteria in search for a possible joint between first and second groups of data bits within said group; (c) selecting a segmentation vector according to second predetermined criteria to separate said first and second groups of data bits; and (d) separating said first and second groups of data bits at said joint along a selected said segmentation vector.

In another aspect of the invention there is disclosed an apparatus for facilitating character recognition, comprising: means for receiving image data bits derived in response to scanning characters; means for isolating a discrete group of said data bits which may be associated with more than one character; means for examining said discrete group of data bits according to predetermined criteria in search for a possible joint between first and second groups of data bits within said group; means for selecting a segmentation vector according to second predetermined criteria to separate said first and second groups of data bits; means for separating said first and second groups of data bits at said joint along a selected segmentation vector; means for recognizing characters; and means for forwarding said first and second groups of data bits to said recognizing means to effect character recogntion.

Other aspects and the advantages of this invention will become more readily understood in connection with the following specification, claims, and drawing.

FIG. 1 is a general schematic diagram, in block form, of a banking system, showing an entry processing unit (EPU) including a courtesy amount recognition (C.A.R.) module, data entry processor (DEP) with its associated image display terminals (IDT), and an encode and sort unit (ESU) which are all interconnected by a local area network;

FIG. 2 is a schematic diagram, in block form, showing more details of the EPU shown in FIG. 1 and the C.A.R. module which contains a preferred embodiment of this invention;

FIG. 3 shows an example of a document which is processed by the system shown in FIG. 1;

FIG. 4 is a schematic diagram showing additional details of the C.A.R. module shown in Fig. 2;

FIG. 5 is a diagrammatic showing of the various rows and columns of pixels comprising image data for the embodiment described;

FIG. 6 is a chart showing how image data associated with a monetary amount is received by the segmentation processor shown in FIG. 4;

FIGS. 7A and 7B taken together represent a schematic diagram of the image data associated with the monetary amount on a document;

FIG. 8 is a flowchart showing, very generally, the steps involved in the process of segmenting joined characters to facilitate character recognition at a subsequent operation;

FIGS. 9 and 10 show certain relationships which exist with records associated with an object;

FIGS. 11, 12 and 13 show certain situations associated with an examining window;

FIG. 14 shows a situation associated with a second type of examining window;

FIG. 15 is a diagram showing various segmentation vectors used to separate two records within an object;

FIG. 16 is a schematic diagram of image data associated with a courtesy amount in which two characters are joined;

FIG. 17 is a schematic diagram of the image data shown in FIG. 16 after segmentation is performed;

FIG. 18 and FIG. 19 show portions of the numeral "5" ;

FIG. 20 shows how the portions shown in FIGS. 18 and 19 are combined as one character in FIG. 20; and

FIG. 21 shows a particular combined object like a joined "57" which can be segmented by this invention.

FIG. 1 is a general schematic diagram, in block form, of a banking system which is designated generally as system 10. The system 10 includes an entry processing unit (EPU) 12, a data entry processor (DEP) 14 with its associated image display terminals (IDT) 14-1, 14-2, and 14-3, and an encode and sort unit (ESU) 16 which are all interconnected by a conventional, local-area network 18 as shown.

In general, the function of the EPU 12 is to receive documents such as checks and deposit slips, for example, and mechanically read certain data from the documents which are processed in batches of about 200-300 documents per batch. The EPU 12 includes a courtesy amount reader (C.A.R.) module 20 in which this invention is incorporated. The DEP 14, along with the IDTs 14-1, 14-2, and 14-3, in general, perform the function of using the output of the EPU and completing the data not mechanically read at the EPU 12, correcting mis-read data where necessary, and performing certain banking procedures such as proofing and reconciliation, for example. The ESU 16, in general, receives the completed data for a batch of documents from the DEP 14 and encodes the corresponding courtesy or monetary amount for a document on the associated document such as a check or deposit slip as it moves through the ESU 16. Certain other functions such as stamping, endorsing and microfilming are performed at the ESU 16 prior to having the documents sorted into various sorting pockets according to the bank's sorting instructions.

The EPU 12 is shown in more detail in FIG. 2, and it has a general construction which is similar to a reader/sorter which is used to process documents such as checks and deposit slips, for example, in "batches" as previously described herein.

A batch of such documents is placed in a stacker or hopper 22 (FIG. 2), and a conventional feed mechanism 24 is used to pick a document 26 from the hopper 22, and thereafter, a conventional transport mechanism 28 moves the document 26 along the document track 30 at a constant velocity and at a rate of 200 documents per minute in the embodiment described.

As each document 26 is moved along the track 30, it is brought into operative, reading relationship with a conventional, magnetic ink character recognition (MICR) reader 32. The MICR reader 32 is positioned along the track 30 so as to read the MICR line 34 (FIG. 3) on the document 26 as the document 26 is moved thereby. The MICR line 34 contains, for example, the identification of the associated bank number (transit routing number), customer's account number, and check number. The output of the MICR reader 32 is fed into conventional recognition circuitry 36 which interprets the data read.

There are sensors designated collectively as 38, for example, which are positioned along the track 30 (FIG. 2) to check on the status of each of the documents as it is moved along the track 30. The sensors 38 are coupled to a conventional controller 40 which may include a microprocessor (not shown) to perform the routine tasks associated with moving documents along the track, such tasks as controlling the feed mechanism 24 and the transport mechanism 28, for example. The controller 40 is coupled to the EPU processor 42 (FIG. 2) via the interface 44.

Continuing with the example being described, when the sensors 38 (FIG. 2) indicate that a document 26 approaches the MICR reader 32, the EPU processor 42 receives this notification from the controller 40 as just described, and the EPU processor 42 assigns a document reference number (DRN) to the data associated with the document 24 to be read by the MICR reader 32. This DRN is unique for each document and will be used by the system 10 to identify the various data associated with a document 24 and to facilitate the processing of the documents in the system 10. The MICR data from the MICR reader 32 is processed by the recognition circuitry 36. Typical MICR data such as bank number, customer account number, and check number, for example, coming from the recognition circuitry 36 pass through the interface 44 to the random access memory (RAM) 60 of the EPU processor 42 where it is stored therein according to the now-available DRN.

After a document 26 is read by the MICR reader 32, it is moved into operative relationship with a conventional imaging device 48 (FIG. 2) which is positioned along the document track 30.

The imaging device 48 is conventional and in normal operation, the document 26 is moved on its lower, long edge, with the front of the document 26 facing the imaging device 48 as it is moved thereby.

As a document 26 is moved past a vertical scanning line (shown as a dot 50 in FIG. 2), the right-most edge of the document 26 (as viewed in FIG. 3) is illuminated by sources of light (not shown), and light reflected therefrom is focused by a suitable lens system (not shown) on to the imaging sensor array included in the imaging device 48. In the embodiment described, the sensor array may be of a type which produces a fixed number of picture elements or pixels along the scanning line 50. One such array, such as RL-1024B, which is manufactured by Reticon Corporation, for example, produces 1024 pixels along the scanning line 50, although only 640 pixels are utilized to meet the resolution requirements of the embodiment described herein. As the document 26 (FIG. 2) is moved in the downstream direction shown by arrow 52, a new area of the document is presented to the scanning line 50, and a new set of 640 pixels is produced. Each pixel from the sensor array has an associated analog, gray-scale value which is converted or digitized by the processing circuitry 54 to produce, for example, a six bit byte of data for each pixel, thereby recording 64 shades of gray ranging from white to black. The 64 shades of gray may be reduced, for example, to two shades, i.e., either black or white, by the processing circuitry 54. As the scans are completed, a stream of bytes or bits of data is issued from the processing circuitry 54. Because this aspect is conventional, it need not be described in any further detail.

The stream of data or pixels from the scanning line 50 (FIG. 2) of the "image" of a document 26 is further processed by having the output of the processing circuitry 54 fed into a high pass filter/thresholder 56 (FIG. 2), hereinafter called thresholder 56, whose output, in turn, is fed into a compressor 58. The thresholder 56 is conventional and is a circuit which is used to eliminate unnecessary background information and to make the pertinent data stand out from background information, for example. The compressor 58 is a conventional circuit which receives the binary data from the thresholder 56 and eliminates that data which is "redundant" and thereby "compresses" the binary data to produce compressed, digitized-image data which reduces the amount of transmission time necessary to transmit the data associated with an image of a document 26 and which also reduces memory storage requirements. The output of the compressor 58 is fed via the interface 44 to the RAM 60 of the EPU processor 42, where this image data associated with a document 26 is stored temporarily by its associated DRN. As an optional feature, a second imaging device and associated circuitry (not shown) may be used to image the rear of a document 26 as described herein.

The EPU processor 42 (FIG. 2) includes the interface 44 already mentioned, the ROM 46, the RAM 60, a display such as a cathode ray tube (CRT) 62, a keyboard (KB) 64, a processor (MP) 66 and interface and control logic 68. The processing routines associated with the EPU processor 42 may reside in the ROM 46; however, the routines are loaded, more typically in the RAM 60 from disc or tape storage (not shown), for example, as part of a conventional start-up procedure. The CRT 62 is used to provide communication with an operator who uses the KB 64 to enter data or instructions. The interface and control logic 68 provides the interconnections among the various components of the processor 42 to enable it to function, conventionally, as an "intelligent" application processor. The form of the processor 42 shown in FIG. 2 is utilized to portray the various functions performed thereby, and the actual form of the processor 42 may be different.

Continuing with the movement of a document 24 along the document track 30, after a document 24 passes the imaging device 48 (FIG. 2), it is moved into operative relationship with a conventional printer (not shown) which prints the DRN on the front of the associated document 26. The DRN was assigned earlier by the EPU processor 42. Various other conventional elements such as an endorser, and microfilmers, (not shown) are positioned along the track 30 in operative relationship with each document 26 passing thereby.

Normally, the documents 26 (FIG. 2) are processed in a batch, as previously described, and after microfilming and endorsing, they are diverted sequentially into a single pocket 70 by a diverter 72 which is controlled by a pocket controller 74 which is coupled to the EPU processor 42 via the interface 44. If the processor 42 wishes to single out one or more documents 26 (for various processing reasons) at this point, the processor 42 then sends out the appropriate instruction to the pocket controller 74 which causes the affected documents to be diverted into the reject pocket 76.

As the documents 26 are moved, sequentially, past the imaging device 50 (FIG. 2), the associated image data is processed, enhanced, filtered, and compressed as previously described, and the compressed, image data for each document is buffered in the RAM 60. The DRN associated with the compressed image data is combined therewith, and this compressed, image data is immediately transferred out of the EPU processor 42 via its interface 44 over the network 18 to the DEP 14 (FIG. 1) via its interface 78. The DEP 14 then immediately transfers the compressed, image data via the interface 78 to an image disc file (I.D.F.) 80 where it is stored by the associated DRN. Because the documents 24 are processed in batches of about 200-300 per batch, for example, a batch header card may be used to identify each batch of documents being processed. The batch header card is the first document to be processed in the associated batch and a batch number associated with the header card may be used to identify the various document data associated with that batch of documents. In this regard, the compressed, image data in the image disc file 80 may be arranged by DRN within a batch number to facilitate the accessing thereof.

The image data derived from the imaging device 48 (FIG. 2) is also utilized to perform machine character recognition to ascertain the courtesy amount on the documents 24 being processed. The image data coming from the thresholder 56 (prior to compression) is fed into a courtesy amount recognition (C.A.R.) module 82 where courtesy amount recognition is performed.

The function of the C.A.R. module 20 (FIG. 2) is to perform automatic reading of the courtesy amount shown by reference numeral 82 in FIG. 3. The courtesy amount is the monetary amount of a check, which amount is written or printed in numerical form. The C.A.R. module 82 attempts to read the monetary amount 82 of each document 26 as it is moved along the document track past the imaging device 48. The output from the C.A.R. module 20 includes the monetary amount read along with a confidence level for each of the numbers read. For example, if a particular number of the monetary amount 82 cannot be automatically read at all, a confidence level of "0" may be applied to that particular number or digit. Correspondingly, if there is a high degree of confidence that a particular digit of the monetary amount 82 is read correctly, a confidence level of "9" may be applied to that particular number or digit. The numbers processed by the C.A.R. module 20 along with their associated confidence levels are routed to the EPU processor 42, from where they are routed to the DEP 14 for further processing as previously described. The IDT's 14-1, 14-2 and 14-3, and the ESU 16 are coupled to the local area network 18 via conventional interfaces 84 to provide conventional coupling among these named elements.

The C.A.R. module 20, shown in FIG. 2, is shown in more detail in FIG. 4. To perform automatic courtesy amount reading, the C.A.R. module 20 receives the binary image data (about a document 26) coming from the thresholder 56. It should be recalled that the data from the thresholder 56 comprises a stream of binary "ones" and "zeros" , and this data stream is fed through the interface 84 of an encoder processor 86, and is stored in the associated RAM 88. One of the sensors 38 (FIG. 2) is utilized to indicate the start of data for a new document 26 and this fact is utilized by the encoder processor 86 to initialize the counters 90 and 92. Counter 90 is used to count the number of pixels in a scan and counter 92 is used to count the number of scans associated with an image as shown in FIG. 5. In the embodiment described, there are 640 pixels in each scan ranging from row #0 through row #639 to handle documents 26 which are about four inches high. Counter 90 may be placed in a downcounting mode to facilitate having the bottom of the document referenced as #0. In the embodiment described, 364 scans are used to cover the portion of the document 26 where the monetary amount 82 is located. The encoder processor 86 is conventional, and it includes a ROM 94, a MP 96, and interface and control logic 98. The necessary instructions for operating the processor 86 may be stored in the ROM 94, or most likely, they are loaded daily into the RAM 88 as part of the normal start up procedure. In some situations, it may be desirable to encode the stream of data bits coming from the thresholder 56 so as to minimize memory requirements and processing time by the system 10. One encoding technique which may be used is the typical "run-length" encoding. Because this aspect is not important to an understanding of the present invention, it need not be described in any further detail.

Either the full matrix of data or the encoded data (if encoded by encoder processor 86 (FIG. 4) is transferred to the amount finding processor 100 via the interfaces 84 and 102 and is stored in the RAM 104 of the processor 100. The amount finding processor 100 is conventional and includes, also, a ROM 106, MP 108, and interface and control logic 110. The function of the amount finding processor 100 is to pick out the image data that is associated with courtesy or monetary amount 82 and to transfer this image data to the RAM 112 of the segmentation processor 114 via the interface 116. The techniques for picking out the image data associated with the monetary amount 82 may be conventional. If the image data were encoded at the encoder processor 86, it would be decoded at the amount finding processor 100 prior to being forwarded to the segmentation processor 114.

The image data associated with the monetary amount 82 is in the format shown in FIG. 6 when it is forwarded to the segmentation processor 114 from the amount finding processor 100 as previously mentioned. The chart 118 (FIG. 6) represents the encoding of the image data associated with a courtesy or monetary amount 82 on a document 26, and the encoding of chart 118 corresponds to the image data designated generally as 120 and as shown in FIGS. 7A and 7B. In the example described, the image data 120 consists of binary "zeros" and "ones", with a binary "zero" corresponding to a white pixel, and with a binary "one" corresponding to a black pixel. The binary "ones" are enclosed in solid lines to group together those black pixels which form a record associated with an object. A record as used herein means a collection of binary ones forming a discrete area, and an object may be comprised of several related records. For example, the records marked "3", "7", "14", and "15" in FIG. 7B comprise an object which is designated generally as 122. The object 122 appears to be the numeral "3", and all the image data 120 in FIGS. 7A and 7B comprises the courtesy or monetary amount coming from the amount finding processor 100. The function of the segmentation processor 114 (FIG. 4) is to analyze the encoded data as presented in chart 118 (FIG. 6) and separate those records which should be separated so as to facilitate character recognition by the recognition processor 124 shown in FIG. 4. For example record #4 should be separated from record #8 in FIG. 7A along the line 126 to facilitate the reading of the apparent "6" and "8" which make up the combined object 128. A feature of this invention is that when the image data 120 shown in FIGS. 7A and 7B is presented in the form shown in chart 118 (FIG. 6), the records and objects shown therein can be separated quite readily to facilitate character recognition at a subsequent operation.

It should be recalled that when the amount finding processor 100 (FIG. 4) finds the monetary amount 82 (FIG. 3), the associated image data 120 (FIGS. 7A and 7B) consist of about 150 columns of data which are about 50 rows high as discussed in relation to FIG. 5. The amount finding processor 100 has a row (R) counter 129 and a column (C) counter 130 for counting various row and column positions to be discussed hereinafter.

Some additional points need explanation prior to discussing the encoding technique associated with FIGS. 7A and 7B. Basically, the encoding technique used is simple run-length encoding. In the embodiment described, the image data 120 is examined along rows although the image data could be examined along columns; all that is needed is consistency in this regard. When the image data 120 (FIGS. 7A and 7B) for the monetary amount 82 is received, the absolute row and column numbers shown in FIG. 5 are not used; for convenience, the top row may be numbered zero and the left-most column in FIG. 7A is also numbered zero, for example. For the run-length encoding used, scanning (in search for black pixels) is done by starting at the top row in FIGS. 7A and 7B and proceeding from left to right as viewed in FIGS. 7A and 7B. After the top row is scanned, the scanning is performed on the next lower row while starting at the left side thereof and while proceeding again from left to right.

The encoding technique embodied in the chart 118 shown in FIG. 6 proceeds as follows. The top row (row #0) in FIGS. 7A and 7B is scanned from left to right in search for black pixels which are designated as "1"s. The next row (row #1) is also scanned from left to right and no black pixels are found. Again, the next row (row #2) is also scanned from left to right and the first black pixel encountered is marked 134 (FIG. 7B). In the example described, the column position for this pixel 134 is obtained from the C counter 130 (FIG. 4); this counter is reset to zero when the right-most column (as viewed in FIG. 7B) is reached in the scanning or examining process. Black pixel 134 is the first black pixel encountered by the scanning technique mentioned, and accordingly, the record with which pixel 134 is associated is referred to as record #1. The length of the run of black pixels in row 2 is seven prior to a white pixel being encountered. This means that the length of record #1 in row #2 is seven black pixels long. When the last column for the image data is reached, the C counter 130 is reset to zero and the R counter 129 is incremented by one.

This data just obtained from row #2 (FIGS. 7A and 7B) is recorded or encoded in the chart 118 (FIG. 6) as follows. A number such as 9991 that is enclosed in the rectangle 136 is used to indicate the start of a new character or object. The number 9991 and the other numbers shown in FIG. 6 are entered in the RAM 104 of the amount finding processor 100. In the embodiment described, a sixteen bit word is used for each of the entries to be made. The entries are entered into the RAM 104 as a single dimension memory; this aspect will be discussed hereinafter. The next entry after the 9991 in rectangle 136 is a "2"which stands for row "2". The next entry in chart 118 is "105" which stands for the column 105 in which the first black pixel 134 is encountered; this is column 105 counting from the left side of FIG. 7A. The next number which is "7" refers to the number of black pixels which exist in a row containing the first black pixel 134. The length of the row of black pixels starting from black pixel 134 and ending with black pixel 138 is obtained by using the counts from the C counter 130 (FIG. 4). Thus, the first row for record #1 is established at row 2, starting at column 105, and extending for 7 columns wide. The next scan relates to row 3, and the first black pixel encountered in this row is pixel 140 (FIG. 7B).

The method for recording these subsequent scans is to record a run's "growth" as compared to the prior run associated with that record. For example, the run starting with black pixel 134 (FIG. 7B) is seven black pixels long. The next run that starts with black pixel 140 starts at column 102 compared to column 105 for black pixel 134. This means that the row starting with black pixel 140 starts three columns before the row beginning with black pixel 134; accordingly a (-3) is entered in the next position in the chart 118. This (-3) is included under bracket 142. The last black pixel 144 in the row starting with black pixel 140 ends in the same column as does black pixel 138; accordingly, the record growth is (0), and the number 0 is placed on the right side under bracket 142. The remaining pairs of entries included in the brackets 146, 148, 150, 152, 154, and 156 show how the subsequent rows for record #1 are recorded. The entries included in bracket 156 (Fig. 6) relate to the row beginning with black pixel 158. The number 9901 on the first line of FIG. 6 is used to indicate the start of a new record which is associated with an object. In this case, this number 9901 relates to record #6.

A point should be made at this portion of the description relative to the encoding represented by FIG. 6. It should be recalled that the scanning to search for black pixels was done on a row basis while searching from left to right as viewed in FIGS. 7A and 7B. The assignment of record numbers is also done from left to right while proceeding from the top row to the bottom row shown in FIGS. 7A and 7B. When scanning along row 5, a black pixel 160 is encountered. This black pixel is part of record #2. When proceeding further to the right along the fifth row, the next black pixel encountered (after a white pixel) is black pixel 162 which represents the start of record #3. Normally, the data for record #2 is entered before the data for record #6; however, the chart 118 in FIG. 6 represents the final memory arrangement in RAM 104 after several manipulations of data (when necessary) are performed. For examp1e while the data for records #2 and #3 are entered prior to record #6, for example, record #6 is positioned in memory after record #1. This is done as to have all records associated with an object grouped together. A general rule is that all the records associated with a particular object are grouped, ultimately, with the first record encountered (by the scanning technique mentioned) for that object. In this regard, record #6 is grouped with record #1 because record #1 is the first record encountered by the scanning technique mentioned for the object 164 which includes records #1, #6, #12, and #13. Accordingly, the entry 9901 (shown by reference number 166 in FIG. 6) refers to record #6.

Continuing with the new record #6 indicated by reference numeral 166 (FIG. 6), the next number "7" refers to the row number in which record #6 starts (via black pixel 168 in FIG. 7B), and the number 103, shown by reference numeral 170, indicates the column number at which record #6 starts. The next entry on the same line as number 103 represents the "run length" or the number of black pixels for this record in row 7, and the "run length" is "8". The next two numbers "2" and "-1 " that are included in bracket 172 represent the record growth for row 8 of record #6 by the technique previously applied.

The next new object which appears in the chart 118 in FIG. 6 relates to object 128 which is shown in FIG. 7A. The first record encountered for object 128 is record #2, and accordingly, the new object code "9991" that is referenced by numeral 174 in FIG. 6 refers to record #2 shown in FIG. 7A. Similarly, the next object which appears in chart 118 in FIG. 6 relates to object 122 (FIG. 7B). The first record encountered for object 122 is record #3, and accordingly, the new object code "9991" that is referenced by numeral 176 in FIG. 6 refers to record #3 shown in FIG. 7B.

As previously stated, records associated with an object are recorded by the first record encountered (by the scanning technique mentioned) for that object. In this regard, the records shown in FIGS. 7A and 7B are encoded and presented by the arrangement shown in chart #118 (FIG. 6). The order of presentation of records associated with the various objects shown in FIGS. 7A and 7B is as follows:

Records 1, 2, and 3 in FIGS. 7A and 7B are the first records associated with objects 164, 128, and 122, respectively. For object 164, records #6, #12, and #13 are also associated therewith; a shorthand way of expressing this relationship is by the expression:

Similarly, those records associated with the second object 128 are:

Finally, those records associated with the third object 122 are:

Some additional comments with regard to FIGS. 6, 7A, and 7B appear appropriate. The portion of the RAM 104 (FIG. 4) associated with the amount finding processor 100 is arranged as a serial memory with each word being comprised of sixteen bits in the embodiment described. Anytime a new record is formed, its associated column and row positions are determined. Pointers are used to indicate where all the data is located in the RAM 104. If, for example, at the end of accumulating data for the objects shown in FIGS. 7A and 7B, the processor 100 finds that record #13 is associated with record #1 of object 164, and the processor 100 also finds that four bytes of data are required to record the data associated with record #13, then the following takes place. The data in the RAM 104 is examined until the last record for object #1 (or object 164 in FIG. 7B) is obtained, and when this last record is found, all the remaining records (like the entries in FIG. 6) are "shifted down" by four word positions to make room for the four bytes of data associated with record #13 which are entered into the just-cleared, word positions in the RAM 104.

The arrangement of data in the chart 118 in FIG. 6 facilitates the reconstruction of data. For example, when it is desired to reconstruct image 164 in FIGS. 7A and 7B from the records or encoding shown in FIG. 6, the data on the first line of FIG. 6 is read serially, beginning with the start of new object code 9991 that is referenced by numeral 136 and ending with the start of new object code 9991 that is referenced by numeral 174 in FIG. 6. This data is built up according to the + and - designations for record growth or contraction as previously described; these designations are shown within the brackets 142 and 172, for example.

To summarize, the encoding which is shown in chart 118 in FIG. 6 produces the matrix of image data 120 shown in FIGS. 7A and 7B. The encoding mentioned is handled by the amount finding processor 100 shown in FIG. 4. By this encoding, the ability to separate the objects 164, 122, and 128 or their associated records #1-#19 is facilitated. The image data shown in FIGS. 7A and 7B is then subjected to segmentation (where necessary) by the segmentation processor 114 (FIG. 4) as alluded to earlier herein. The processor 114 also includes a ROM 178, a processor (MP) 180, a row (R) counter 182, a column (C) counter 184, and interface and control logic 186 interconnecting the various elements shown.

The image data 120 shown in FIGS. 7A and 7B is divided up by objects so that each individual object 164, 122, and 128 is placed in a separate buffer 188 associated with the RAM 112. The image data for object 128, for example, is stored in the buffer 188 as pixels, and is present in binary form as previously described. At this point, the outer boundaries (row and column) of the monetary amount of a document are also known. The image data relating to the monetary amount is then forwarded to the segmentation processor 114 (FIG. 4) to begin the segmentation process which is designated generally as 190 in FIG. 8.

The segmentation process 190 is shown very generally in FIG. 8, and the first step therein includes the step 192 of receiving the image data like 120 (FIGS. 7A and 7B), for example. The data is received by the processor 114, and it is stored in the buffer 188. At this time each object or "character" of image data is separate from one another, and the image data is in the matrix form shown in FIGS. 7A and 7B. Note also at this time that an object or a "character" may be comprised of two joined digits like object 128 shown in FIG. 7A. The row counter 182 and the column counter 184 (FIG. 4) are used in the determination of certain calculations to be performed as will be described hereinafter.

A program listing for the segmentation process 190 is included as Appendix A at the end of the specification. The listed program is written in FORTRAN IV. These sheets are consecutively numbered #1-#65, with these numbers being enclosed in a circle to provide for easy reference to specific sheets when necessary.

The next step in the process 190 is step 194 (FIG. 8) in which the objects or characters are reconstructed and/or isolated. Reconstruction means that certain separate records or objects which probably should be grouped with an object are grouped with it. Isolation means that an object which probably contains two characters has been separated into two objects or characters.

The basic problem in reconstruction is to recognize all the individual records or objects which are associated with a broken character and to store them as one object or "character". FIGS. 9 and 10 show two situations which are typical and which are encountered in reconstruction. The blocks or objects 196 and 198, shown in FIG. 9, represent areas of all black pixels which are located within the perimeters of these objects; the same is true for objects 200 and 202 shown in FIG. 10. Some definitions are in order:

1. An object like 196 is comprised of a group of black pixels which are connected in any direction.

2. Two objects are parts of broken characters if they satisfy the following condition (a) or condition (b).

(a) The thinner object overlaps the other by v % or less in the vertical direction and by h % or more in the horizontal direction. The phrase "thinner object" means that it is smaller than the other object in width.

(b) Overlap in the vertical direction (with regard to FIG. 10) is less than "s" pixels; there is a gap of less than "g" pixels in the horizontal direction; and the object on the left side of the two is below the right one.

After the objects or characters are reconstructed as just described with regard to step 194 in FIG. 8, the object is examined to determine whether or not it is a single character as indicated by step 204. An object includes connected characters if it satisfies certain conditions; the evaluations are made by the segmentation processor 114 (FIG. 4). It should be recalled that the data associated with a character or object at this time is in the matrix form shown in FIG. 7A and 7B, and that the row counter 182 and the column counter 184 (FIG. 4) may be used to obtain the various parameters which are to be described hereinafter. The following terms are used in step 204 and apply to the object:

P=Perimeter (Number of black edge pixels),

W=Width,

H=Height,

A=Number of black pixels in the object,

TA=Width.times.height=total area,

W/H=Width to height ratio,

A/TA=Area to total area ratio,

P.sup.2 /A=Perimeter squared to area ratio, and

m=200 in the embodiment described.

Having defined the terms used, an "object" includes connected characters or is not a single character as evaluated in step 204 if any one of the following three equations is satisfied. The equations are:

For example, with regard to the first equation, if the perimeter (P) is greater than m (200 in the embodiment described) then it most likely means that the object is comprised of two characters, and the response at step 204 is a "no." In the embodiment described, there are 154 pixels per inch; the pixels are shown in exaggerated size in FIGS. 7A and 7B. A "no" from step 204 means that the "two character" object must be segmented at step 206 by techniques to be described later herein. After the object is segmented at step 206, it is subjected to step 208 at which the same tests already described in relation to step 204 are applied, and if a "two character" object is again suspected, it is subjected to step 206 again. After segmentation at step 206, if a single character results therefrom, the single character is placed in a discrete area of the buffer 188. When the segmentation process 190 shown in FIG. 8 is completed, the individual characters are transferred (step 209) from the buffer 188 to the recognition processor 124 (FIG. 4) where character recognition is performed as previously described.

As previously stated, when "joined characters" are found as an object in step 204 in FIG. 8, for example, an object like 128 in FIG. 7A is subjected to segmentation as shown by step 206 in FIG. 8. The purpose of segmentation is to locate the joint where the "joined characters" are connected and to remove it so that the joined characters can be isolated as single characters to facilitate character recognition.

The segmentation step 206 shown in FIG. 8 is comprised of three basic subroutines, namely:

1. JNTLOC, (See page 34 of Appendix A.)

2. REMJNT, (See page 38 of Appendix A.), and

3. ZEROUT. (See page 42 of Appendix A.)

In general, the function of routine JNTLOC is to scan an object like 128 that contains connected characters and to find the location of the joint between the two characters.

The general function of the routine REMJNT is to analyze joints along certain orientations. For example, the most common orientations of joints are 45.degree., 60.degree., 90.degree., 120.degree. and 135.degree. . The lengths of these joints are determined, and they are ranked according to length, with the shortest joint having the highest priority and the longest joint having the lowest priority. Segmenting joined characters along the shortest joint helps to preserve the original shapes of the joined characters better than segmenting characters along the longer joints.

The general function of the routine ZEROUT is to test the joint picked out by the routine REMJNT to determine whether or not the joint picked out is a true joint. A true joint is one which, after it is removed, causes the joined characters to become disconnected. If the joint tested is not a true joint, the joint with the second highest priority is then tested, etc. When a true joint is found, the two characters are segmented along the joint, and thereafter, the separated characters are each subjected to the tests (step 208 in FIG. 8) to determine whether or not a single character exists. This process is repeated to enable an object consisting of three characters to be segmented. If no true joint is found during the testing mentioned, then no segmentation of the joined characters is performed; these joined characters are simply routed to the character recognition processor 124 for processing. In all probability, the joined characters will not be read by the character recognition processor 124 (FIG. 4), and consequently, these joined characters will have to be read subsequently by an operator viewing the image of the document on one of the IDTs 14-1, 14-2, or 14-3 (FIG. 1) as previously explained.

The routine JNTLOC can be understood best by referring to the object 128 in FIG. 7A. It is apparent from viewing the binary ones and zeros shown therein that the object 128 represents the joined characters "6" and "8". The first step in routine JNTLOC is to scan the object (in a vertical direction as viewed in FIG. 7A) along lines where a joint joining the characters "6" and "8" may be found most likely. From a practical experience, such a joint is found between 1/4 to 3/4 of the width of the object 128. When the object 128 is to be scanned in this regard, its outer column and row parameters are known as each object is discrete in the buffer 188 (FIG. 4). The region in which the scanning is done is shown as R in FIG. 7A and is given by the equation:

in which "MP" is equal to the mid-point of the object 128. The scanning is done from left to right and from the bottom of the object towards the top as viewed in FIG. 7A. At this time in the processing, the left-most column of the object is referred to as column zero and increases to the right (FIG. 7A) and correspondingly, the bottom row of object 128 is referred to as row zero. The row and column counters 182 and 184 (FIG. 4) are utilized for counting and referencing in this regard.

Assume that the scanning mentioned starts at the column marked 210 in FIG. 7A and proceeds upwardly from the bottom of the object 128. To detect a joint between two characters, a 3.times.3 examining window is moved over the object. The 3.times.3 matrix for the examining window was selected because it can detect joints consisting of one black pixel. FIGS. 11, 12, and 13 show three different pixel arrangements which are indicative of a joint between two characters to be separated. With regard to FIGS. 11, 12, and 13, the blank spaces in each 3.times.3 matrix represent "don't care" bits; the binary "1"s and "0"s shown are under consideration, with "x" being a black pixel or a binary "1" and also being the primary pixel under consideration. Each of the windows 212, 214, and 216 represents a potential joint between two characters. In order to select these windows 212, 214, and 216, binary weights are assigned to each of the squares within the windows. By summing up the total value for each window, those windows having predetermined binary values (for binary "1"s present) can be selected as having the configurations shown.

With regard to window 212 in FIG. 11, if the central pixel X were removed, the segmentation line to be used would be vertical and would pass through the "0"s shown therein.

With regard to window 214 in FIG. 12, if the central pixel X were removed, the segmentation line to be used would pass through the binary "0"s and rise from left to right along a 45 degree line with respect to a vertical line.

With regard to window 216 in FIG. 13, if the central pixel X were removed, the segmentation line to be used would pass through the binary "0"s and would fall from left to right along a 45 degree line with respect to a vertical line.

Another pattern which is indicative of a possible joint is shown by window 218 in FIG. 14. Window 218 is slightly different from the window 212 shown in FIG. 11, for example, in that window 218 represents a 2.times.2 matrix. The pattern shown in FIG. 14 in which X is equal to a binary one is used to pick out possible joints between two characters because the pattern shown is characteristic of the great majority of joints which do exist between connected characters. When a possible joint exists in the position of the "X" pixel in FIGS. 11-14, the associated particular row and column coordinates are utilized by the routine REMJNT as will be described hereinafter. For each black pixel which is evaluated by the window technique mentioned, the three by three matrix window is used (like FIGS. 11-13), and thereafter, the two by two matrix is used (like FIG. 14).

Having discussed the various examining windows used, it now seems appropriate to discuss how the windows are moved relative to the image data associated with object 128 shown in FIG. 7A. As earlier stated, the scanning is done in an upward direction and is done from left to right.

Starting with the column 210 in FIG. 7A and proceeding upwardly, the first black pixel encountered is marked 220. Column 210 is the first column (in the example described) within the range R within which segmentation is anticipated to be performed as previously explained. When the first black pixel is encountered in column 210, the window movement relative to that black pixel is expressed by the following steps:

Step #1. Move the window "diagonally" to the lower right from the black pixel under consideration;

Step #2. Move the window to the right from the black pixel under consideration;

Step #3. Move the window "diagonally" to the upper right from the black pixel under consideration; and

Step #4. Move the window directly upwardly from the black pixel under consideration.

When a black pixel is found as a result of the Steps #1-#4 mentioned, that newly-found black pixel becomes the reference point for the window movement mentioned. As soon as a black pixel is found by any of the Steps #1-#3, the steps remaining in the sequence of Steps #1-#4 need not be performed. Basically, the technique being described is to search for the outer boundary of a record (which probably is one character of two or more characters within an object like 128) and to follow it generally upwardly and to the right in the expectation of finding a point at which segmentation can be made. The segmentation is made along the lines expressed by situations shown in windows 212, 214, and 216 (FIGS. 11, 12 and 13) for example. An example of window movement will be explained with regard to FIG. 7A.

As seen from FIG. 7A, the first column within the region R, where segmentation is anticipated to take place is column 210. When proceeding upwardly along column 210, the first black pixel encountered is black pixel 220. From black pixel 220, the adjacent pixels are examined via Steps #1-#4 as previously described. In this regard, a zero or white pixel exists diagonally down and to the right; a zero exists to the right of pixel 220; a zero exists diagonally up and to the right of black pixel 220; and finally, by Step #4, a black pixel 222 is found above black pixel 220. Black pixel 222 is now used as the reference pixel and Steps #1-#4 are repeated resulting in black pixel 224 being used as the next reference pixel. In the next examination sequence, black pixel 226 is found as a result of Step #2. Steps #1-#4 are repeated until the examination process proceeds to black pixel 228. Using black pixel 228 as a reference pixel, Steps #1-#4 reveal that there is no "adjacent" black pixel as examined by these Steps #1-#4. When such a situation is encountered, the process proceeds upwardly (in the column in which the current reference pixel or black pixel 228 is located) until a black pixel is encountered. In this regard, black pixel 230 is located above black pixel 228, and the examination continues with black pixel 230 being the reference pixel. The next black pixels 232 and 234 are found as a result of Step #2, and subsequently, black pixel 236 is found as a result of Step #1. Notice that black pixels 230, 232, and 234 are associated with record #4 and black pixel 236 is associated with record #8. It should be recalled that the image data shown in FIGS. 7A and 7B is found in buffer 188 (FIG. 4) at the time that it is being examined by steps #1-#4 mentioned, and it is comprised of binary ones and zeros as shown. Also, while Steps #1-#4 look for the outer boundary of a record, the reference black pixel which is used in Steps #1-#4 is also used as the "x" or center pixel in the windows 212, 214, and 216 shown in FIGS. 11, 12 and 13, respectively, and is also used as the "x" pixel in window 218 shown in FIG. 14. Notice that with black pixel 234 as the reference or "x" pixel, window 218 (FIG. 14) indicates that black pixel 234 might represent a point along which segmentation might be made between records #4 and #8 of object 128 in FIG. 7A.

After having found a possible segmentation point as represented by black pixel 234 in FIG. 7A, another examination process is introduced to ascertain the direction along which the segmentation between records #4 and #8 should take place. From experience, it has been determined that if segmentation is to take place, the most likely vectors along which the segmentations take place are along the vectors #1-#5 shown in FIG. 15. These vectors #1-#5 are numbered in the order of priority. For example, when a possible joint is found as represented by the windows in FIGS. 11-14, the first vector direction along which pixels are examined is represented by segmentation vector #1 in FIG. 15. Vector #1 represents a direction which is in the same column or directly "up" from the reference black pixel "x" located within the examining windows shown in FIGS. 11-14. Vector #2 represents a direction which is up and to the right at a 45 degree angle, with "up" and "to the right" being referenced from the standpoint of the image data shown in FIG. 7A in the example being described. Vector #3 represents a direction which is up and to the left at a 45 degree angle. Finally, vectors #4 and #5 represent angles of about 30 degrees with regard to vector #1 and they are positioned as shown. These vectors #1-#5 are given customary, angular trigomometric designations as shown.

When the examination for black pixels occurs along the directions represented by vectors #1-#5 in FIG. 15, a count of the number of black pixels encountered is kept in the buffer memory 188 (FIG. 4) for each of these vectors. The number of black pixels encountered along the vectors #1-#5 thus provides a first test or a measure of the length of the segmentation cut required along each of these vectors to separate the records associated with an object. Generally, that vector that is the shortest among the vectors #1-#5 is generally the direction selected for making the cut or segmentation; however, that is not always true and certain other tests are made prior to segmentation.

A second test to determine which of the vectors #1-#5 (FIG. 15) provides the best line along which to separate the records of an object is to examine the column in which a certain first white pixel is located. This first white pixel is the one which is encountered on the vectors #1-#5 in determining the length of these vectors which are comprised of black pixels. When this first white pixel is encountered, the column in which it is located is noted, and an examination of the pixels in that column is made beginning with the first white pixel and extending upwardly (as viewed in FIG. 7A) towards the top of the object. If no black pixels are encountered in the column in which the "first white pixel" is located at the end of a vector #1-#5, it means that the segmentation line may be an appropriate one, providing other criteria are met. If some black pixels are encountered in the column in which the "first white pixel" is located, the perimeter of the record associated with the first-found black pixels is examined by moving the examining window upwardly and to the right as previously explained. If the top of the image data (FIG. 7A) can be reached by this process without encountering a joint between two records, the second test is satisfied.

The third and final test is that the intended segmentation line must be within the range "R" previously mentioned. The range R represents the most-likely place where two characters forming as an object might be joined.

To summarize, the segmentation line to be selected is selected for the shortest vector of vectors #1-#5 whose associated "first white pixel" lies in a column with no black pixels in this column when proceeding towards the top of the associated image (FIG. 7A), and for that shortest vector which also lies within the R limit. Some examples will clarify these tests.

For example, with regard to FIG. 7A, black pixel 234 represents the x pixel located in window 218 shown in FIG. 14. When viewing the column in which black pixel 234 is located, there are three black pixels for a segmentation vector #1 (straight up) and only two black pixels (counting black pixel 234 and black pixel 238) for a segmentation vector #2. Segmentation vector #2 provides the shortest length for a segmentation line and it satisfies test #1. The first white pixel encountered to end the vector #2 is white pixel 240. White pixels exist in the column containing and starting with white pixel 240 and continuing to the top of the image data shown in FIG. 7A; therefore, test #2 is satisfied. The proposed segmentation line passing through black pixels 234 and 238 lies within the R limit shown at the bottom of FIG. 7A; therefore, test #3 is satisfied. Because tests #1-#3 are satisfied, the cut line 126 would be made along the line 126 which passes through black pixels 234 and 238.

FIG. 16 shows another example of image data for an object 242 which appears to be the numbers "1" and "5" which are joined. As previously described, each object, like 242, has outer column markers 244 and 246 and outer row markers 248 and 250 to define the perimeter of the object 242. The binary zeros or white pixels are not shown in FIG. 16 to simplify the Figure; only the binary ones or black pixels are shown.

In examining the object 242 (FIG. 16) to look for a joint between two records, the technique of moving the windows shown in FIGS. 11-14 through Steps #1-#4 is employed as previously described. In this regard, black pixel 252 represents the "x" pixel shown in window 218 in FIG. 14. After examining the possible cuts along segmentation vectors #1-#5 shown in FIG. 15, segmentation vector #2 is selected as previously described, and it passes through black pixel 252 to produce a segmentation line 254 (FIG. 17) which divides the object 242 (FIG. 16) into the two objects 242-1 and 242-5 shown in FIG. 17. The two objects 242-1 and 242-5 are again examined to determine whether or not these two objects represent single characters as previously discussed in relation to step 208 shown in FIG. 8. In this example, the two objects 242-1 and 242-5 would be interpreted as single characters, and consequently, they would be routed to the character recognition processor 124 to effect character recognition. When objects or characters are separated they are maintained in the same order as they appear on the document 26 (FIG. 3) so that the courtesy amount 82 can be read properly.

Some miscellaneous comments relative to the detailed program listing shown on pages 1-65 of Appendix A appear in order.

As previously stated, the program listing is written in FORTRAN IV. Pages 1-65 of the listing have various descriptions of the operations interspersed throughout to facilitate an understanding of the entire process.

Pages 1-9 of the listing relate to various initialization procedures for getting data from the various files utilized. Page 9 refers to a subroutine for preparing a name for the next file for the next document 26 being transported along the document track 30.

Pages 11 and 12 of the listing show the various steps included in a routine for segmenting machine printed characters. This particular routine is conventional, and basically, it just divides the joined, printed characters at their midpoint.

Page 14 of the listing contains the high-level, control portion for controlling various subroutine mentioned in the listing. SEGMEN is the name of the routine which will call the ENCODE, DECODE, PASTE, and SIFT routines also mentioned in the listing. The ENCODE routine is that one which was explained in developing the chart shown in FIG. 6, and the DECODE routine refers to reconstructing the figures from the chart shown in FIG. 6. The PASTE routine is mentioned on page 15 of the listing. The SIFT routine is mentioned on page 16 of the listing.

Page 15 of the listing refers to the process described in relation to FIGS. 9 and 10 which determines whether or not two elements or pieces are part of a broken character or are parts of two distance characters.

Page 15 also mentions the PASTE routine, with the associated details being listed on pages 41 and 42. The PASTE routine is a routine which essentially reconstructs broken characters. In other words, it is a routine which attempts to put together in one discrete buffer those elements which should properly be together. For example, FIG. 18 shows a portion 256 of the numeral "5" which is in its buffer 258. FIG. 19 shows a second portion 260 of a character which is located in its buffer 262. The original coordinates for each of the buffers 258 and 262 are saved to enable the segmentation processor 114 to decide whether the portions 256 and 260 are separate characters or whether these portions should properly be included in one buffer 264 (Fi9. 20) to represent a single character.

Page 16 of the listing refers to the SIFT routine which tests for the presence of connected characters. This routine is associated with the discussion of steps 204 as described earlier herein. If the SIFT routine indicates that there is just one character after an evaluation of the associated height, width, etc. paramenters, then there is no need for segmentation, and therefore, the character is sent to the recognition processor 124 for conventional character recognition.

Pages 18-30 of the listing relate to the detailed steps associated with the encoding process discussed in relation to the chart 118 shown in FIG. 6.

Pages 32 and 33 of the listing relate to the detailed steps for decoding the chart 118 shown in FIG. 6 to obtain the binary representation of the characters as shown in FIGS. 7A and 7B, for example.

Pages 35 and 36 of the listing relate to data manipulations which are made necessary because the program is written in FORTRAN which deals with words or bytes of data and the data for the particular embodiment discussed herein is stored in single bits or pixels.

Pages 37, 38 and 39 of the listing include detailed steps which relate to data manipulations associated with FORTRAN.

Pages 41 and 42 of the listing relate to the detailed steps associated with the PASTE routine mentioned on page 15 of the listing.

Pages 44 and 45 of the listing relate to the detailed steps associated with the SIFT routine mentioned on page 16 of the listing.

Page 47 of the listing relates to a HTRANS routine which is used to determine whether or not a character image contains a single character or connected characters. It is useful for joined characters like those shown in FIG. 21 which shows the numbers "57" being joined. The HTRANS routine performs a histogram analysis for those objects (FIG. 21) which do not have detectable corners. For this type of object 268, the number of pixel transitions which occur when scanning in a vertical direction from the left side of the object to the right side of the object are recorded. For this type of object 268, one can see that the center portion of the object has very few transitions in the horizontal line joining the "5" and "7". Generally, the width of this horizontal line is about one black pixel wide in the embodiment described. So, the joint at which segmentation would be made would be at that portion of the object which has the fewest number of transitions, and once that portion is found, that portion which has the fewest number of black pixels would indicate the narrowest portion of the joined characters. Segmentation is then made along this narrowest portion; in FIG. 21 this narrowest portion lies on the horizontal segment between the numbers "57".

Pages 50 and 51 of the listing refer to the routine JNTLOC discussed earlier herein with regard to step 206 shown in FIG. 8.

Pages 52-56 of the listing contain additional details of various portions of the process already described. For example, the routine REMJNT (for removing the joint between connected characters begins on page 54 of the listing.

Pages 59-65 of the listing contain additional details of various portions of the process described earlier herein. For example, the routine ZEROUT is found on page 59 of the listing.

Pages like 8, 10, 13, 31, 34, 43, 46, 48, 49, 57 and 58 of the program listing which were not specifically referred to in the description of the program listing contain certain lines which are not directly related to the processes described earlier herein. ##SPC1##