US 4,700,401 AGrant
Method and Apparatus for Character Recognition Employing a Dead-Band Correlator
Issue Date:1987-10-13
•48 Claims
•24 Drawing Sheets
Abstract
A character recognition system is disclosed utilizing a dead-band correlator for providing recognition of printed typestyles having horizontal and vertical stroke width variations without impairing the resolution required for character feature analysis. The system provides fewer character-to-mask registration errors, simultaneous computation of correlation scores of registration positions of masks with respect to the unknown character to compensate for additional registration errors, improved reject and substitution rates by utilizing unique threshold and separation requirements for masks, lower error rates by using small and large noise filtering and combining dual level acceptance criteria used in conjunction with re-try methods, stroke width normalization to aid in recognition of characters with badly degraded stroke widths, and selection of specific mask sets during multiple typestyle recognition processing than has previously been possible.
Metadata
Assignee
- Dest Corporation
Inventors
- Cary H. Masatsugu
- Bruce S. Denning
- Martin N. Nelson
Application Information
Application Number:US 9020713
Filing Date:1986-08-27
Priority Date:1983-02-28
Art Unit:266
Classifications
IPC:
G06K 964
Field of Search:
38236469;54;27;30;34;42728
Patent Drawings (24 sheets)
Description
Background of the Invention
A simple bit-level correlation scheme for use in a character recognition apparatus entails a one-to-one comparison between each character pixel and its associated mask pixel. For purposes of this specification, a pixel is defined as an individual picture element. Every pixel is given a weight of one or zero, for a mismatch or match respectively. FIGS. 1a and 1b illustrate an example of this scheme. The resulting mismatch count, hereby referred to as the character score for the specific mask, ranges from 0 for a character which is completely identical to a mask, to 768 (i.e., 24.times.32) for a character which is the negative of a mask. This correlation scheme can be represented by the following equation: ##EQU1## where c.sub.xy is the character pixel value (either 0 or 1) at row x and column y, and m.sub.xy is the associated mask pixel value (either 0 or 1) and .sym. is the "exclusive-OR" logical operation. This technique produces the highest degree of resolution available in a bit matching system. In FIGS. 1a and 1b, pixels labeled x.sup.a in the character to be identified have no counterparts in corresponding locations in the mask, and pixels labeled x.sup.b in the mask have no counterparts in corresponding locations in the character. If the pixels are each weighted by a score of "1", the resulting mismatched score is the sum of x.sup.a +x.sup.b, which in the example equals 24.
Maximum resolution is not necessarily desirable for purposes of character recognition. The resulting scores are representative of absolute pixel variations and are not necessarily responsive to character feature variations. An example of such high resolution creating improper identification is shown in FIGS. 2a-2c. Assuming that FIGS. 2a and 2b represent the mask fields for a lower case `l` and upper case `I`, respectively, an unknown character as diagrammed in FIG. 2c produces scores of 9 for the I mask and 18 for the l mask, as summarized below:
The unknown character, a slightly degraded lower case `l`, is identified as the wrong symbol. Cases such as this occur frequently when a large spectrum of characters are processed. The correlation scheme favors the wrong mask, due to the fact that each pixel mismatch carries the same weight, regardless of the location of that pixel with respect to the main strokes of the characters. Note that in this example the mismatching pixels of the upper case `I` mask are farther away from the nearest matching pixel, whereas the mismatching pixels of the lower case `l` mask are only one pixel distance away from the nearest matching pixel.
To counteract this shortcoming, a correlator can be developed that weighs each pixel mismatch as a function of that pixel's distance to the nearest matching pixel. A large weight would be attached to a mismatched pixel that is located a great distance from the nearest matching pixel, and a small weight would be attached to a mismatched pixel that is adjacent to a matching pixel. An example of this grading scheme is shown in FIGS. 3a and 3b for the examples in FIGS. 1a and 1b. A mismatch one pixel away from a matching pixel is given the weight of 0.5; a mismatch two pixels away from the matching pixel is given a weight of 2; and, mismatches n pixels away from the matching pixel are given the weight n.sup.2. Thus, pixels `a` are one pixel distance from the nearest matching pixel, and a weight of 0.5 is given for `a` pixels. Pixels labeled `b` are two pixels away, and are weighted 2. Pixels labeled `c` are three pixels away, and are weighted 9.
The resulting mismatched score is:
The example of FIG. 2 with a distance-weighted correlation scheme is illustrated in FIG. 4, with the resulting mismatched score as given below:
Hence, the unknown character is properly identified as a lower case "l". Unfortunately, a distance-weighted correlation implementation is both costly and time-consuming, requiring a conversion from bit-level weighting having only two states to multiply level weighting having many states.
Summary of the Invention
A simple approximation of the distance scheme with binary states can be accomplished by weighting mismatches within a specific distance around and matching pixel with a weight of zero. Each character pixel is compared with the associated mask pixel and a logically OR'ed combination of adjacent mask pixels, hereafter referred to as the dead-band region. The single mask pixel is similarly compared with the associated character pixel and a combination of adjacent character pixels. The specific pixels used in the dead-band region are chosen to be the pixels immediately above and below, and to the right and left of pixel in question.
Since most character strokes are vertically and horizontally oriented, variations between characters and ideal masks tend to appear in those directions. Typical copiers tend to round character corners and blur strokes in directions perpendicular to the page edge, and different sources of type faces commonly have different stroke widths. The dead-band region of the present invention is selected to accommodate stroke width variations and degradations in the horizontal and vertical directions. The result is that the resolution of the correlator is decreased, but this reduction in resolution does not affect the ability to differentiate character features that extend a known number of pixels from the main stroke. The character scores, calculated with such a dead band region, therefore tend to accentuate character feature differences and deemphasize stroke width variations.
With any correlation technique, proper character-to-mask registration is essential. The dead-band correlator of the present invention is more immune to slight registration errors than the single bit level correlator, due to its wider tolerance level. Nonetheless, misregistration in any direction can result in scores. In order to improve the correlation output, nine different character-to-mask registrations are correlated simultaneously. These registrations form a grid about a central registration. This process, together with the use of a dead-band region incorporating a preselected range (in pixels) in vertical and horizontal directions, results in a correlation scheme which is both registration tolerant and informative.
Description of Drawings
FIGS. 1a and b illustrate operation of a bit-to-bit character correlator typical in the prior art.
FIGS. 2a, b and c show an example of improper character identification employing the correlation scheme of FIGS. 1a and 1b.
FIGS. 3a and b illustrate operation of a distance-weighted character correlator commonly found in the prior art.
FIGS. 4a, b and c show an example of character identification employing the correlation scheme of FIGS. 3a and 3b.
FIGS. 5a and b illustrate operation of a dead-band correlator according to the principles of the present invention.
FIGS. 6a, b and c show an example of character identification employing the correlation scheme of FIGS. 5a and 5b.
FIG. 7 is a block diagram of a character recognition system according to the principles of the present invention.
FIG. 8 is a flowchart for initializing the system of FIG. 7.
FIG. 9 is a table of character mask threshold values employed in the system of FIG. 7.
FIGS. 10a and 10b are a block diagram of the correlator employed in the system of FIG. 7.
FIG. 11 is a flowchart of the interrupt service routine algorithm employed in the system of FIG. 7.
FIG. 12 is a vector diagram of a character mapped into a mask set according to the principles of the present invention.
FIG. 13 is a set of vector diagrams for a plurality of recognizable masks for which the threshold values are given in FIG. 9.
FIGS. 14a, b and c illustrate the resolution of intersecting masks according to the principles of the present invention.
FIG. 15 illustrates the effect of lowering threshold values for masks in the system of the present invention.
FIGS. 16a, b and c illustrate the effect of a minimum score separation requirement on the resolution of intersecting masks according to the principles of the present invention.
FIG. 17 is a flowchart of the algorithm for reiterative processing of character data employed in the system of FIG. 7.
FIG. 18 illustrates the process of removing small amounts of noise from the character field of a character to be identified according to the principles of the present invention.
FIGS. 19a, b and c illustrate character burn according to the principles of the present invention.
FIGS. 10a, b and c illustrate character regrow according to the principles of the present invention.
FIG. 21 illustrates the block diagram of the correlator hardware.
FIG. 22 illustrates the detailed implementation of the correlator hardware.
FIG. 23 illustrates the registration shifting in the corelator.
Description of the Preferred Embodiment
Referring to FIGS. 5a and b, the distance-weighted dead-band correlator of the present invention weights pixel mismatches within a pre-selected distance around a matching pixel at zero weight. Each mask pixel is compared with a corresponding combination of character pixels, and each character pixel is compared with a corresponding combination of mask pixels. The pixels within the dead-band are those immediately above and below, typically 2 each, and to the right and left, also typically 2 each, of the pixel of interest.
The resulting correlation is expressed mathematically below: ##EQU2## where c.sub.xy is the character pixel value represented by a digital 0 or 1 at row x and column y, and m.sub.xy is the mask pixel value represented by a digital 0 or 1 at row x and column y. The dead-band region and the new correlation scheme is shown in FIGS. 5a and 5b. The lightly shaded area 50 illustrates a typical dead-band area defined for each pixel to be examined. Pixels labeled `a` are one pixel away, either horizontally or vertically, from the nearest matching pixel (dark shaded area 51) and are weighted as zero. Pixels labeled `b` are more than one pixel distance from the nearest matching pixel and are weighted with 1. The resulting mismatched score is:
The total character score can range from 0 to 768.
FIG. 6 shows the results as tabulated below of the example in FIGS. 2a-2c with the dead-band correlation scheme:
The recognition process is initiated by loading digital data representing an unknown character field into a correlator RAM buffer 71 as shown in FIG. 7. The software as shown in FIG. 8 then directs the selection of a mask set to be used in a table look-up procedure. The mask set is controlled by a mask header table as shown in FIG. 9. The header table contains information needed to properly utilize the mask set. The hardware of FIG. 7 is initialized by loading the breakpoint counter register 83 with the number of masks to be used. For the preferred embodiment, nine masks are used. A score threshold register 82 is loaded with the maximum score that should be reported. This limits the correlator outputs to scores that are significantly low. Finally, the starting address of the mask space is loaded into mask address registers 75. Accessing the low order address byte enables the hardware processing function.
The unknown character is converted from byte format in the RAM buffer 71 to a serial bit stream with the parallel to serial converter 79. The first mask is likewise serialized in parallel to serial converter 78, and both serial bit streams 77a and 77b are sent into a correlator logic network 77. This network 77, whose block diagram is shown in FIG. 10a, is a combination of sequential and combinatorial circuits. The output of the network 77 is loaded into score counters 101.
In general, nine score counters 101 are required. However, only eight score counters 101 can also be used. As shown in FIGS. 10a and 10b, the L1D1 registration zone (i.e., the left one and down one group of pixels) can be omitted, thereby reducing the amount of recognition hardware.
At the end of each mask period, the score counters 101 are shifted via bus 77c into a magnitude comparator 80. The lowest of the eight or nine scores is then loaded into an output score register 81. If the lowest score is less than the score threshold register 82, an interrupt is generated on the microprocessor interrupt line 84 to microprocessor 85. The microprocessor 85 is thus informed that a potentially satisfactory correlation has been performed. The lowest score, its associated registration zone, and the mask address are read by the software in the microprocessor 85 and stored for evaluation.
The character is then recirculated and processed with the next mask. Since the masks are continuous in mask memory in the Mask Rom 74, the next mask address need not be loaded. After each mask period, the breakpoint counter 83 is decremented. When the breakpoint counter 83 reaches zero, the hardware ceases processing and another interrupt is generated. This signals the end of the mask set.
Referring again to FIGS. 10a and 10b, an unknown character is shown digitized into 768 bits, 24 bits wide by 32 bits high with each bit representing one pixel. Each font or typestyle is represented by approximately 100 masks, including those for numbers, capitals and the like. The sequence within correlator 77 is given below:
Correlator Sequence
1. Reset: Clears all score counters 101.
2. Count errors in score counters 101 during mask and character clocking.
3. Load: transfers values from counters 101 to holding registers 102.
4. Shift: causes all holding registers 102 to be cascaded so that each score is moved to the next register 102 on each shift clock. The score in the last register 102 is sent to the magnitude comparitor 80 on each shift clock.
5. Error counting can start again for the next mask after the load pulse since all scores are saved in the holding registers 102.
Description of the Correlator Hardware
The unknown characters are isolated from the page of text by an Isolation Process and are passed to a Recognition Process. The character is stored in a matrix 24 wide by 32 high. Each mask is also stored in this format in a font read-only-memory (ROM). The process of character identification is called "mask-matching". The unknown character is tested again all masks in the font.
The method for character identification is to correlate both the character and mask matrices and find the mask with the lowest error score. This correlation method compensates for irregularities in the text, the digitizing system, and the isolation system.
As shown in FIGS. 21, 22, and 23, the correlator system consists of a shift register section 120, a region (window) generating section 122, and nine simultaneously operating correlators 125. A central correlator assumes perfect registration between the mask and character matrices. Four more correlators account for a 1 bit registration error in one dimension only. The last four correlators account for a 1 bit registration error in both dimensions.
As shown in FIGS. 21 and 22, each correlator is designed in two parts. The first part compares one bit of the character matrix to a corresponding 5-bit region in the mask matrix. The region is defined as the corresponding bit and all four adjacent bits: up, down, right and left. The second part of the correlator compares one bit of the mask matrix to the corresponding 5-bit region of the character matrix. If there is a match in both parts of the comparitor, then no error count is recorded.
The correlator hardware performs the matrix matching by a serial mechanism one bit position at a time. The matrices are 24.times.32 bits, so there are 768 bit positions made during the sequence. The matrices are presented to the correlator board in synchronous serial form. The correlator converts a small portion consisting of five 24-bit lines, back into parallel form so that the surrounding regions are available for each bit position.
As shown in FIGS. 21 and 22, the character bits are observed through a mask window made up of a 3.times.5 matrix. The mask bits are observed through a character window made up of a 5.times.3 matrix. As the mask and character signals are synchronously shifted through these windows, measurements are made in each position. The regions are created by OR-ing 5 bits of the shift register together.
The central correlator is implemented as shown in FIG. 22. The central character bit C13 is compared to the mask region made up of M03, M13, M23, M12, M14. The comparison is made to detect a mismatch so that only errors are tabulated. This comparison implements the rule that if C13 is a black bit and either M03, M13, M23, M12, or M14 is a black bit, then there is a match. If none of the bits in the region is black, then there is a mismatch. This function is accomplished by AND-ing the bit and region signals together.
The C13 bit is simultaneously compared with two other regions of the mask which represent an up-shift or a down-shift in relative registration. The mask regions are: Up (M15, M24, M14, M04, M13) and down (M13, M22, M12, M02, M11). In addition, bits C12 and C14 are simultaneously compared to all three mask regions. The result is that nine separate measurements are made.
An additional nine measurements are made with mask bits M12, M13, M14, against three regions of the character: center (C23, C14, C13, C12, C03), left (C24, C15, C14, C13, C04) and right (C22, C13, C12, C11, C02). There are actually a total of eighteen measurements made at each bit position (768 total positions), but in the electronics, matching pairs are OR-ed together so that nine terms remain. The nine results are used to enable the clock to an error score counter.
At the end of the correlation, each of the nine counters can have a different error score in the range of 0 to 768. As a practical matter, the score counters are designed to count to a maximum of 128 since error counts above 128 are not significant.
The interrupt service rountine used by microprocessor 85 is shown in FIG. 11. Since both the low score interrupt and the breakpoint interrupt are on the same interrupt level, the software must check for both on every interrupt. At each interrupt, the mask address is converted to an ASCII code by indexing into an ASCII translation table which is referenced in the mask header table. The new score is then compared to the current low score and next lowest score. Only the lowest score for each ASCII code is retained. The current mask address is then compared to the expected breakpoint address. If the mask address is not equal to the breakpoint address, a simple return from the interrupt service routine is executed. When the breakpoint address is reached, the processing of the accumulated data is enabled. The character is then represented in the mask set by the lowest score and its ASCII code, and the next lowest score and its ASCII code. The former is referred to as the best guess mask, and the latter is its nearest neighbor.
The scores for a given character can be viewed as vectors in an n-dimensional mask space. In order to simplify the following description, it has been assumed that the vectors can be transformed into a two dimensional space. FIG. 12 is a representation of a character mapped into a mask set by its best guess and nearest neighbor. The vector magnitudes are equivalent to the associated scores, and the vector directions are functions of the ASCII code. Using this concept, all possible character fields (there are 2.sup.768 possible input fields) can be mapped into the mask set. Obviously, not all inputs are legal characters. A method for resolving legitimate characters from unrecognizable characters, noise, and characters from a different mask space is required.
The first approximation for determining a legitimate character is the use of a low score threshold requirement. If the lowest score meets some minimum level, the character is identified by the associated mask's ASCII code. The threshold requirement creates two basic categories of inputs. All input fields that are mapped into any mask's threshold space are identified with that ASCII code. All input fields that do not fall into any mask's threshold space are deemed unidentifiable, and are labeled as rejects. By adjusting the score threshold requirement, the reject rate can be tailored to any level.
The threshold values need not be equal for all masks. Since different masks vary in terms of pixel count, stroke orientation, and surface area, theresholds should be different for each mask. For example, it is reasonable to expect the scores for n samples of a specific punctuation mark will vary much less than the scores for n samples of a capital M. Different thresholds create different recognizable masks spaced as shown in FIG. 13. The threshold criteria are mask set dependent and a threshold table is given in FIG. 9. Characters which fall within circles as defined by mask thresholds are indentified by that mask's ASCII code. Characters that fall outside all circles are rejected.
When two similar masks have intersecting spaces, the intersection must be resolved. An example of this occurs with a Prestige Elite lower case `a` and lower case `s`, as shown in FIGS. 14a and b. The blocked pixels represent matching pixels within dead-band regions. The theoretically ideal mismatch as shown in FIG. 14c is only 22. In order to accommodate most of the characters, the thresholds for each mask will tend to intersect. The shaded area 150 represents possible substitutions. The identity of a character that maps into the intersecting region 150 is uncertain. An incorrectly identified character is called a substitution.
There are a number of ways to control the substitution rate. One method is to lower the threshold requirements to a point where no intersections 150 of mask space occur. Characters that may have been substituted before are now rejected properly. Reducing the threshold, however, increases the reject rate of acceptable characters for any given mask. Characters with a magnitude equivalent to that of the potential substitution, but in a different direction, will also be rejected. Thus, as shown in FIG. 15, shaded regions 160 and 162 represent fields of characters that should be identified correctly, but are rejected due to lower thresholds. Dark area 165 represents substitutions which are thereby avoided.
To accomodate acceptable characters while still rejecting potential substitutions, a second requirement should be placed on the recognition of an input field. The next lowest score (nearest neighbor) contains some directional information. By using the difference between the next score and the lowest score (called score separation), the characters which fall in an intersecting field can be isolated. Therefore, a minimum score separation requirement is added to the criteria. Using this second requirement, possible substitutions can be rejected properly while still allowing a broader threshold to accommodate legitimate characters. By adjusting the required thresholds and separations for each mask, the overall reject and separation rates for a mask set can be controlled.
In certain instances, different sources of a generic typestyle produce slightly different characters with the same ASCII code designation. An example is shown in FIGS. 16a and 16b. A typical Prestige Elite lower case `a` from one manufacturer's typeball (source A) is different from the lower case `a` from another manufacturer's printwheel (source B), even though they belong to the same generic typestyle. For character pairs such as this, the scoring threshold values that would be required to recognize both types of characters with a single mask would be too large for practical purposes, allowing many possible substitutions and non-recognizable characters into the mask space. Therefore, a duplicate mask with an equivalent ASCII code designation is added to the mask set. This creates a further subdivision for the mask set. Since the ASCII codes for the best guess and nearest neighbor are not allowed to be equal, the threshold and separation criteria can still be applied to all masks of each ASCII code. Thus, referring to FIG. 16c, the shaded region 170 is rejected.
Processing
Referring to FIG. 17, software control permits the recognition of characters to be an iterative process. Confidence in recognition is based on the threshold and separation requirement. A dual level of thresholds and separation is established in order to improve confidence in identification, while still allowing the recognition of a broad spectrum of character inputs.
The original character is assumed to be registered properly. Its data is passed through the correlator 77, and the resulting scores logged. The results are then evaluated using tight threshold and separation criteria. If the results are acceptable with tight requirements, the character is considered recognized with a high confidence factor. If the results fail to meet the tight requirements, the charcter data undergoes "retry processing".
Retry processing is a series of functions designed to eliminate noise and degradations from data representing the character. After each function is performed, the data is processed through the correlator 77. If the results meet the tight requirements, character recognition processing is complete. If not, the new results are compared to the old results to determine if the function has improved recognition of the character (i.e., a lower score). If recognition was improved, the current character is passed on to the next phase of retry. If recognition was degraded, the previous character (before the last retry) is restored and passed on to the next phase of retry.
The level of improvement is dependent on the specific function utilized. This continues until the results have been accepted with the tight thresholds, or all retries are attempted. If all the retries fail to produce a tight acceptance, the results are evaluated with a somewhat looser criteria. If the results are acceptable under the looser criteria, the character is identified with a lower confidence factor. If the results fail under the looser criteria, the character is labeled a reject.
The first retry function attempts to center the character. If the character was previously mis-centered, the character is centered and data representing it is passed to the correlator 77. If the character was previously centered properly, the original character data is passed to the next level of retry.
The second level of retry processing attempts to filter small isolated noise which exists in the character field. This is accomplished by compressing the character field into vertical and horizontal composites to form silhouettes 171 and 172 as shown in FIG. 18. These silhouettes are inspected for isolated black shadows up to two pixels by two pixels in area. If none are found, the character data is passed to the next level of retry. If noise is found, the black bits are erased, using the horizontal and vertical positions of the shadow silhouette as indicies. Referring again to FIG. 18, noise pixel 173 does not affect recognition, while noise pixel 174 may affect recognition of the character. If the character field is now blank, the field is assumed to be noise, and recognition is halted. Any remaining character is re-centered and sent to the correlator 77. No improvement of recognition is required in this phase, since black areas as small as two by two are not considered to be significant features for recognition.
The third level of retry processing is similar to the previous function in that it involves further noise filtering. The character data, along with the correlation results, are copied into a holding buffer. The original character data then undergoes a further noise filtering process which erases any isolated black area smaller than five pixels by seven pixels. If no such areas are found, the character data is passed on to the next level of retry. If the character data field after filtering is blank, the character data is restored from the holding buffer and passed on to the next level of retry. Any remaining character data is re-centered and passed to the correlator 77. If the new results meet the tight requirements for threshold and separation, the filtered character data is considered to represent the final character. If not, the new results are compared to the old results. If the new low score is lower than the old low score, and the new separation is greater than the old separation, the filtering process is considered legitimate, and the filtered character data is passed to the next level of retry. If the old score or separation is better, the original, unfiltered character data is passed to the next level of retry.
The distinction between small and large noise levels and the improvement in recognition are implemented to prevent incorrect filtering. Dots on certain lower case i's, as well as some types of punctuation, can appear smaller than the large noise size requirement since certain character features can be as small as four pixels by six pixels. Improvements in the scores and separations are required to prevent permanent distortions to such characters.
After noise has been erased from the character data field and a tight criteria has not been achieved, the data undergoes a status check. Included in the character field buffer is an indication as to whether or not the character data is located in a region of text that is underscored. If the underscore flag is not set, the character data is passed along to the next level of retry. If the underscore flag is set, the character data enters underline erasure processing. First, the character data and its results are copied into a holding buffer. The bottom row of black is then erased from the character data field, and the new character data is sent to the correlator 77. If the resulting character data meet the tight requirement, the character is deemed identified. If not, the new results are compared to the old results. The original character data is sent to the next level of retry if recognition did not improve. Again, "improvement" means the mismatch score is lower than the previous retry. If the new score and separation are better, another iteration of underscore removal is attempted. This continues until the results satisfy the tight requirements, or three iterations of underscore removal are completed. After three iterations, the character data is sent to the next level of retry.
If the character data reaches the fifth level of retry without being identified by the tight criteria, the data goes through a series of stroke width normalizers. These normalizers attempt to improve correlator resolution by varying character stroke width. One form of noramlizer, referred to as a software "burn", attempts to reduce very dark characters to reasonable proportions by removing pixels from the perimeter of character strokes. One phase of "burn" removes one pixel from the top and left of each stroke. The second phase of "burn" removes one pixel from the bottom and right of each stroke. This is accomplished by a series of shifts and logical AND functions performed on the character data. FIGS. 19a-c illustrate an example of a character before (FIG. 19a) and after a first (FIG. 19b) and second (FIG. 19c) burn iteration. Before each phase of burn is performed, the character data and results are copied to the holding buffer. After two burns are performed, the character data is sent to the correlator 77. If the results meet the tight requirements, the character is accepted. If not, a check is made for an improvement in recognition (i.e., a lower mismatch score). If recognition has been improved, the character data undergoes another phase of "burn". This form of retry continues, alternating between the two phases of "burn", until the results meet the tight criteria or recognition fails to improve between the previous results and the current results.
In order to prevent the burn retry algorithm from reducing the character data to a blank, or from changing all characters to punctuation marks, a secondary requirement is attached to the requirement of improved recognition. The ASCII code for the best guess is not allowed to change after a specified level of burn. This inhibits a burn from creating overly forced character data distortions.
Another normalizer, known as a software "regrow", is very similar to burn, except that it attempts to darken an overly light character. The two phases of regrow consist of adding a pixel to the top and left of each stroke, and adding a pixel to the bottom and right of each stroke. This is accomplished by applying a series of shifts and logical OR functions to the data. FIGS. 20a-c show an example of a character before (FIG. 20a) and after first (FIG. 20b) and second regrows (FIG. 20c). Regrow proceeds in a fashion similar to that of burn, continuing until the character data is accepted under tight requirements, or recognition fails to improve.
The burn and regrow processing is controlled by a normalizer routine, which keeps statistical page information as to whether burn or regrow is more likely to be needed. The routine initializes its counters at the start of each page, and updates them for each recognized character. The counters reflect the number of burns and regrows used before characters are recognized. The state of the counters aids in determining if the characters on the page tend to be darker or lighter than a normalized standard. The normalizing routine activates the burn retry for pages that tend to be darker. If the first burn iteration fails to improve recognition, the regrow retry is attempted. If the character is improved by at least one burn, regrow is disabled. Similarly, if the counters indicate that the page is lighter than normal, regrow is attempted first. If the first phase of regrow fails to improve recognition, the burn retry is attempted. If the character data is improved by at least one regrow phase, burn is inhibited. This normalizer thus assists in adapting the retry mechanism to different qualities of text.
Typestyle Recognition
A machine that is designed to recognize characters from multiple typestyles can compare each character with every mask in the system. This method is usually tedious, decreasing recognition speed for each additional typestyle added. Usually, however, pages are typed with one particular typestyle. Even in cases where multiple typestyles appear on the same page, the characters from a specific region of the page are usually members of the same typestyle. This information can aid in the recognition of a specific page region. If the particular typestyle can be determined, that typestyle mask set can be implemented by collecting data over a range of characters from a particular page area.
Typestyle recognition is initiated at the beginning of each page. A score counter for data representing each typestyle mask in the system is reset to zero. While in typestyle recognition mode, the characters are evaluated using all typestyle mask sets. The correlation results for each typestyle are stored in a typestyle data table. After the character data has been correlated with all possible typestyles, the correlation results are processed. Character data that is rejected in all typestyles is simply rejected, and data that is accepted in at least one typestyle is passed on to further processing. The best typestyle is determined by comparing the level of acceptances for each typestyle. If more than one typestyle recognizes the character data at the best level of acceptance, the ASCII codes from those typestyles are compared. If all of these typestyles do not agree on the ASCII code designation, the character data and all the typestyle results are placed in a holding buffer to await a typestyle determination. If the ASCII codes are all equal, the character data is accepted, and the low scores of all the typestyles are added to their respective score counters. Any typestyle that rejects the character data has its score counter disabled. All typestyle counters that reach a predetermined level are also disabled. A typestyle is recognized when one counter is left enabled, or the holding buffer of character data awaiting typestyle determination is full. If this occurs before all but one counter is disabled, the typestyle whose counter is lowest is selected. The holding buffer is then emptied, using the selected typestyle's results to accept or reject the character.
The selected typestyle is then used exclusively until character data cannot be resolved with the current typestyle set. If the character data fails the separation requirement but passes the tight threshold requirement, the character is rejected. If the character data fails the tight threshold requirement, the character data is processed through all typestyles. If no typestyle accepts the data with a high degree of confidence (i.e. tight acceptance levels), the character is rejected. If one of the typestyles does accept the character data with its tight requirements, typestyle recognition is re-entered, starting with the current character.
The selection of a typestyle mask set thus improves the efficiency and accuracy of the recognition system. The time required to correlate a character is directly proportional to the number of masks it must be compared against. By limiting the number of masks utilized, recognition speed can be increased. Typestyle selection also improves recognition accuracy. Characters within a specific typestyle are designed to be recognizable within that typestyle space. Different ASCII characters from different typestyles may contain similar features. By segregating the mask space by typestyle, near neighbors from different typestyles do not impede recognition capability.
Listings of Instructions of Routines and Subroutines
A listing of instructions of routines and subroutines for algorithms for controlling operation of the system according to the principles of the present invention are shown in Appendix A. ##SPC1##
Claims
What is claimed is:
1. An apparatus for recognition of printed characters having typestyles with horizontal and vertical stroke width variations, said apparatus comprising a microprocessor for producing processing instructions, character storage means coupled to the microprocessor for storing digital data representing the character to be recognized (character data hereafter), mask means coupled to the microprocessor and the character storage means for automatically providing digital data representing a plurality of typestyle masks (mask data hereafter) for comparison with the character data, processor means coupled to the microprocessor, character storage means and mask means for processing and reprocessing digital data representing mask data and character data in response to instructions received from the microprocessor, and correlation means coupled to the character storage means, the mask means and the processing means for correlating the character data and mask data, said correlation means including means for analyzing digital data representing a selectable dead-band region including a plurality of registration zones on and around a selected pixel within the printed characters which can comprise as many as nine registration zones including a central correlation zone centered on the selected central pixel, center-left, center-right, up-center and down-center correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters left, right, up and down respectively, from the selected central pixel, and up-left, up-right, down-left and down-right correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters, up and left, up and right, down and left, and down and right, respectively, from the selected central pixel, means for comparing each character pixel of character data to a corresponding combination of stored mask data representing a plurality of mask pixels within a dead-band region of plus and minus one pixel above, below, to the left and to the right, of a selected character pixel, means for comparing each mask pixel with the corresponding combination of character pixels within a dead-band region of plus and minus one pixel above, below, to the left and to the right, of a selected mask pixel, and means for storing digital data representing the correlation of mask data with character data.
2. In a character recognition system, a correlator comprising: first means for comparing individual bits of digital data representing the character to be recognized (character data bits hereafter) with corresponding individual bits of digital data representing a plurality of typestyle masks (mask data bits hereafter) and with the logical combination of mask data bits immediately adjacent to said corresponding mask data bits, and computing a first comparison score; second means for comparing mask data bits with the corresponding character data bits and with the logical combinations of character data bits immediately adjacent the corresponding character data bits, and computing a second comparison score; score register coupled to the first and second means for storing the first and second comparison scores and producing a first signal in response thereto; and third means, coupled to the score register for producing a second signal if the first signal is above a preselectable value, and for producing a third signal if the first signal is below a preselected value.
3. An apparatus as in claim 1 wherein the means for analyzing digital data representing the selectable region surrounding each bit of character data comprises: first and second delay means coupled to the character and mask data, respectively, for time delaying the character and mask data; logic gate means coupled to the first and second delay means for digitally measuring the amount of intersection of the character and mask data and for producing a digital score representative of the amount of intersection; and a plurality of digital counters coupled to the output of the logic gate means.
4. An apparatus as in claim 3 wherein the means for storing digital data representing the correlation of mask and character data comprises a plurality of digital registers coupled to the plurality of digital counters.
5. An apparatus as in claim 3 wherein the first and second delay means comprise a first and second plurality of serially connected delay lines.
6. An apparatus as in claim 5 wherein the serially connected delay lines each have one or more time delay taps.
7. An apparatus as in claim 3 wherein the logic gate means comprises a plurality of digital gates interconnected to produce digital scores in a plurality of registration zones on and around a selected central pixel within the printed characters.
8. An apparatus as in claim 7 wherein the number of registration zones is nine.
9. An apparatus as in claim 8 wherein the registration zones comprise: a central correlation zone centered on the selected central pixel; center-left, center-right, up-center and down-center correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters left, right, up, and down, respectively, from the selected central pixel; and up-left, up-right, down-left, and down-right correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters, up and left, up and right, down and left, and down and right, respectively, from the selected central pixel.
10. An apparatus as in claim 7 wherein the number of registration zones is eight.
11. An apparatus as in claim 10 wherein the registration zones comprise: a central correlation zone centered on the selected central pixel; center-left, center-right, up-center and down-center correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters, left, right, up, and down, respectively, from the selected central pixel; and up-left, up-right, and down-right correlation zones each shifted one pixel with respect to the horizontal and vertical strokes of the printed characters, up and left, up and right, and down and right, respectively, from the selected central pixel.
12. An apparatus as in claim 3 wherein the character data is measured through a mask window centered about a selected pixel made up of a first matrix three horizontal by five vertical pixels in size, and the mask data is measured through a character window centered about the selected pixel made up of a second matrix five horizontal by three vertical pixels in size.
13. In an optical character recognition system, a method for recognizing characters printed on a page, said characters having typestyles with horizontal and vertical stroke width variations, said method comprising: (a) digitizing a character into a sequence of character data corresponding to the presence or absence of character information in a character field composed of a plurality of character pixels; (b) comparing each character pixel of character data to a corresponding combination of stored mask data representing a plurality of mask pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected character pixel; (c) comparing each mask pixel with the corresponding combination of character pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected mask pixel, and (d) weighting pixels within one pixel of the nearest matching pixel with a weight of zero.
14. A method as in claim 13 further comprising: (e) weighting pixels more than one pixel distant from the nearest matching pixel with a weight of one.
15. A method as in claim 14 further comprising: (f) correlating the comparison results of a plurality of different character to mask registration zones for each character and mask pixel.
16. A method as in claim 14 further comprising correlating the comparison results of nine different character to mask registration zones for each character and mask pixel.
17. A method as in claim 14 further comprising correlating the comparison results of eight different character to mask registration zones for each character and mask pixel.
18. A method as in claim 15 further comprising: (g) registering the lowest correlation score if the registered correlation is less than a preselected threshold score; and (h) signaling that a potentially satisfactory recognition has occurred.
19. A method as in claim 18 further comprising resolving the intersection of two similar but different character masks.
20. A method as in claim 19 wherein the step of resolving the intersection of two similar but different character masks comprises: (i) measuring the threshold score between the mask and character data for a character which is considered recognized to obtain the lowest correlation score; (j) measuring the next lowest correlation score between the recognized character and the next nearest mask neighbor; (k) subtracting the next lowest correlation score from the lowest correlation score to form a separation score.
21. A method as in claim 20 further comprising: compressing the character data into vertical and horizontal silhouette composites; erasing from the data representing the original character field silhouette bits which are isolated by a selected number of pixels greater than the smallest expected character feature size from the main silhouette; repeating the steps (b) through (k) to produce a second correlation score and a second separation score; and signaling a satisfactory recognition if the character data field is not blank, the second correlation score is less than the original correlation score, and the second separation score is greater than the original separation score.
22. A method as in claim 19 further comprising dividing the set of mask data into separate sets of mask data for different versions of the same generic typestyle.
23. A method as in claim 18 further comprising: centering the character data relative to the mask data field; repeating the steps (b) through (h) to produce a third correlation score; comparing the original and the third correlation scores; and accepting the lower of the original and the third correlation scores.
24. A method as in claim 18 further comprising: (l) erasing from the character data data representing darkened areas in the bottom row of the character field; and repeating steps (b) through (h) and (l) up to a specified number of times if in each repetition the correlation score is less than the previous repetition.
25. A method as in claim 18 further comprising: (m) removing from the character data data representing at least one pixel from the perimeter of each character stroke; and (n) repeating steps (b) through (h) and (m) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
26. A method as in claim 25 in which the steps (m) and (n) are used continuously within each page of printed characters.
27. A method as in claim 18 further comprising: (o) removing from the character data data representing one pixel from the top and left of each character stroke; (p) removing from the character data data representing one pixel from the bottom and right of each character stroke; and repeating steps (b) through (h), (o), and (p) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
28. A method as in claim 18 further comprising: (q) adding to the character data data representing one pixel to the top, bottom, left, and right of each character stroke; and (r) repeating steps (b) through (h) and (q) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
29. A method as in claim 28 in which the steps (q) and (r) are used continuously within each page of printed characters.
30. A method as in claim 18 further comprising applying a single character mask set within one typestyle to each successive character until no satisfactory recognition has occurred for one of the successive characters.
31. In an optical character recognition system, apparatus for recognizing characters printed on a page, said characters having typestyles with horizontal and vertical stroke width variations, said apparatus comprising: (a) means for digitizing a character into a sequence of character data corresponding to the presence or absence of character information in a character field composed of a plurality of character pixels; (b) means for comparing each character pixel of character data to a corresponding combination of stored mask data representing a plurality of mask pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected character pixel; (c) means for comparing each mask pixel with the corresponding combination of character pixels within a deadband region of plus and minus one pixel above, below, to the left, and to the right of a selected mask pixel; and (d) means for weighting pixels within one pixel of the nearest matching pixel with a weight of zero.
32. The apparatus as in claim 31 further comprising: (e) means for weighting pixels more than one pixel distant from the nearest matching pixel with a weight of one.
33. The apparatus as in claim 32 further comprising: (f) means for correlating the comparison results of a plurality of different character to mask registration zones for each character and mask pixel.
34. The apparatus as in claim 32 further comprising means for correlating the comparison results of nine different characters to mask registration zones for each character and mask pixel.
35. The apparatus as in claim 32 further comprising means for correlating the comparison results of eight different character to mask registration zones for each character and mask pixel.
36. The apparatus as in claim 33 further comprising: (g) means for registering the lowest correlation score if the registered correlation is less than a preselected threshold score; and (h) means for signaling that a potentially satisfactory recognition has occurred.
37. The apparatus as in claim 36 further comprising means for resolving the intersection of two similar but different character masks.
38. The apparatus as in claim 37 wherein said means for resolving the intersection of two similar but different character masks comprises: (i) means for measuring the threshold score between the mask and character data for a character which is considered recognized to obtain the lowest correlation score; (j) means for measuring the next lowest correlation score between the recognized character and the next nearest mask neighbor; (k) means for subtracting the next lowest correlation score from the lowest correlation score to form a separation score.
39. The apparatus as in claim 38 further comprising: means for compressing the character data into vertical and horizontal silhouette composites; means for erasing from the data representing the original character field silhouette bits which are isolated by a selected number of pixels greater than the smallest expected character feature size from the main silhouette; means for repeating the steps (b) through (k) to produce a second correlation score and a second separation score; and means for signaling a satisfactory recognition if the character data field is not blank, the second correlation score is less than the original correlation score, and the second separation score is greater than the original separation score.
40. The apparatus as in claim 37 further comprising means for dividing the set of mask data into separate sets of mask data for different versions of the same generic typestyle.
41. The apparatus as in claim 36 further comprising: means for centering the character data relative to the mask data field; means for repeating the steps (b) through (h) to produce a third correlation score; means for comparing the original and the third correlation scores; and means for accepting the lower of the original and the third correlation scores.
42. The apparatus as in claim 36 further comprising: (l) means erasing from the character data data representing darkened areas in the bottom row of the character field; and means for repeating steps (b) through (h) and (l) up to a specified number of times if in each repetition the correlation score is less than the previous repetition.
43. The apparatus as in claim 36 further comprising: (m) means for removing from the character data data representing at least one pixel from the perimeter of each character stroke; and (n) means for repeating elements (b) through (h) and (m) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
44. The apparatus as in claim 40 in which the elements (m) and (n) are used continuously within each page of printed characters.
45. The apparatus as in claim 36 further comprising: (o) means for removing from the character data data representing one pixel from the top and left of each character stroke; (p) means for removing from the character data data representing one pixel from the bottom and right of each character stroke; and means for repeating elements (b) through (h), (o), and (p) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
46. The apparatus as in claim 36 comprising: (q) means for adding up to the character data data representing one pixel to the top, bottom, left, and right of each character stroke; and (r) means for repeating elements (b) through (h) and (q) up to a specified number of times if in each repetition the correlation score is less than in the previous repetition.
47. The apparatus as in claim 46 in which the elements (q) and (r) are used continuously within each page of printed characters.
48. The apparatus as in claim 36 further comprising means for applying a single character mask set within one typestyle to each successive character until no satisfactory recognition has occurred for one of the successive characters.
Patent Citations (20)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3167746 | 1965-01-01 | Reines et al. | |
| US3219974 | 1965-11-01 | Rabinow | |
| US3274550 | 1966-09-01 | Klein | |
| US3295105 | 1966-12-01 | Gray et al. | |
| US3303466 | 1967-02-01 | Holt | |
| US3496543 | 1970-02-01 | Greenly | |
| US3618016 | 1971-11-01 | Van Steenis | |
| US3629826 | 1971-12-01 | Cutala et al. | |
| US3634822 | 1972-01-01 | Chow | |
| US3760356 | 1973-09-01 | Srivastava | |
| US3805237 | 1974-04-01 | Cobb et al. | |
| US3818445 | 1974-06-01 | Neville | |
| US3820067 | 1974-06-01 | Shepard | |
| US3846754 | 1974-11-01 | Oka et al. | |
| US3878509 | 1975-04-01 | Kikuchi et al. | |
| US3905018 | 1975-09-01 | Gray | |
| US3934225 | 1976-01-01 | De Possel | |
| US4153897 | 1979-05-01 | Yasuda et al. | |
| US4288782 | 1981-09-01 | Bader et al. | |
| US4308523 | 1981-12-01 | Schapira |
Non-Patent Literature (2)
- IBM Technical Disclosure Bulletin, vol. 15, No. 5 (Oct. 1972), "Amount Line Finding Logic", K. Kerchmar.
- IBM Technical Disclosure Bulletin, vol. 14, No. 9, Feb. 1972, "Iterative Segmentation", R. J. Baumgartner.