Optical object recognition method and system

[0002] The invention relates to optical object recognition (OOR), particularly to optical character recognition (OCR), and post-processing techniques therefor. The invention particularly concerns optical character recognition (OCR) systems that receive an image of a document, separate the image into blobs that contain characters, and analyze the blobs to recognize and extract characters from the blobs.

[0003] Current OCR systems use a variety of approaches including template matching, statistical correlation, and font mapping. They typically perform an initial OCR in which the systems break a document image into blobs containing images of characters, try to recognize and extract the characters, and present the recognized characters in their original order. Unfortunately, the initial OCR leaves many unrecognized blobs that each contain more than one character or that contain fragments of characters.

[0004] We consider OCR systems a subset of a more general category we call “optical object recognition (OOR)” systems, where document images are arrays of data to be analyzed, characters are the particular objects recognized, and the blobs are “elements” of the arrays of data to be analyzed. For simplicity, we discuss our invention and practice and describe the exemplary embodiment of our invention in terms of OCR systems. Our preferred initial OCR method also leaves such unrecognized blobs after a first pass. As applied to text recognition, the initial OCR routine assumes that each blob is an individual character in a known font set, a set that the routine has been taught in one manner or another before it is run. This assumption fails in two situations: when the OCR routine cannot distinguish two or more characters by their spatial characteristics and thus merge the characters into one blob; and when the OCR routine misinterprets a character's spatial characteristics and splits it among two or more blobs. The first situation typically arises when there is inadequate spacing between characters, as illustrated in FIGS. 1 and 3-6. In FIGS. 4 and 5, Blobs 1, 2, 3, and 5 contain single characters that the OCR will handle with no problem. However, in FIGS. 4 and 6, Blob 4 includes “345”, Blob 6 includes “78”, and Blob 7 includes “90”, none of which will be recognized because of the merger of multiple characters therein into single blobs. The second situation typically arises when there is unusual formatting (italics, perhaps), an unusual font (such as MICR as shown in the bottom row of FIGS. 2 and 7 with conventional font equivalents above), or light printing. In the case of the MICR characters of FIG. 2, the OCR routine will likely split each character into three blobs, none of which will be recognized. Thus, as shown in FIG. 7, the OCR routine will place the more conventional characters of the top row into individual Blobs 8, 12, 16, and 20, but will split their MICR equivalents in the bottom row into multiple Blobs 9-11, 13-15, 17-19, and 21-23. Our initial OCR routine locates and determines the sizes of blobs in a region of interest (ROI) in an image of a document that are to be recognized by the OCR routine.

[0005] To reduce the number of unrecognized blobs, many current OCR systems include post-processing routines that take another look at blobs left by the initial OCR. These post-processing systems reduce the number of unrecognized blobs, but still have lower than desired success rates and suffer from a lack of robustness. Thus, a need exists for a more robust OCR system and method that can separate and recognize characters that are not distinguishable by their spatial characteristics with a higher success rate than current OCR systems and methods. Another need exists for a more robust OCR system and method that can recognize characters that would ordinarily be left unrecognized because of unusual spatial characteristics leading prior art OCR systems and method to break the characters into multiple blobs.

[0006] Our invention satisfies this need using an improvement on existing OCR methods; the invention applies OCR to a document iteratively to simplify, strengthen, improve, and accelerate analysis as compared to prior art methods. Our improvement lies in the application of a post-processing routine that analyzes the blobs left unrecognized after the initial OCR routine is done. First, the post-processing routine breaks the ROI into unknown regions. Next, the routine analyzes each unknown region separately by attempting a correlation of the unknown region with a character from the known font set, starting at the upper left corner of the unknown region. In other words, the system has a set of character templates from the known font set and it uses a correlation coefficient between a current unknown character and each of the set of character templates to see how well it matches the templates. If there is a good match, the unknown region size is reduced by the width of the recognized character and the correlation is attempted again on the reduced unknown region. This is repeated until the entire unknown region is recognized or until every character in the font set has been tried. A variation of the correlation sequence moves the template around in the unknown region rather than only trying the upper left corner. When this method is applied to merged characters, the post-OCR analysis recognizes the individual characters contained in the blobs not recognized by the initial OCR. Once this is complete, the recognized characters are reordered to reflect their arrangement in the original image.

[0007] Our method then regroups unrecognized blobs left by the merged character analysis into new unknown regions for another pass of the OCR routine. Leftover blobs that meet predetermined criteria, such as having particular spatial relationships, and which meet the conditions of an unknown region as defined in the merged character recognition routine are placed into the unknown regions. Once the routine defines the unknown regions, it applies OCR to recognize characters that have been split among two or more blobs.

[0008] We prefer to use an adaptive learning routine for sequencing the order in which characters are correlated in our new routine. This causes the system to correlate a character according to the probability that a character is merged into another character. This probability is based on the frequency of observed mergings of each character in the observed font set. The character with the highest probability value is tried first in the correlation sequence of the new routine.

[0009] OCR with our improved method enjoys accuracies at least as high as prior art methods and is more robust to boot.

[0010] FIG. 1 shows a sample portion of a scanned document including a region of interest under analysis by the invention.

[0011] FIG. 2 shows in the bottom row a type of font (MICR) that will almost certainly yield split characters. The top row shows the conventional equivalent of the MICR symbols in the bottom row.

[0012] FIG. 3 shows how the initial pass of the OCR routine places what it believes to be characters in the region of interest of FIG. 1 into blobs.

[0013] FIG. 4 shows the bottom portion of the region of interest of FIG. 1 divided into seven blobs, some of which contain merged characters.

[0014] FIG. 5 shows single character containing blobs from FIGS. 1, 3, and 4.

[0015] FIG. 6 shows merged character containing blobs from FIGS. 1, 3, and 4.

[0016] FIG. 7 shows the characters of FIG. 2 and of the top portions of FIGS. 1 and 3 after they have been placed into blobs.

[0017] FIG. 8 shows blobs left behind in the region of interest of FIG. 3 after the initial pass of the OCR routine.

[0018] FIG. 9 shows how the blobs in the region of interest of FIG. 8 are grouped into unknown regions by the invention before the second application of the OCR method.

[0019] FIG. 10 shows blobs in the region of interest of FIG. 9 left behind by the second application of the OCR routine and regrouped into new unknown regions.

[0020] FIG. 11 shows a starting point of an analysis window of the invention in a particular unknown region of FIG. 9.

[0021] FIG. 12 shows the unknown region of FIG. 11 after a character has been recognized, its image has been removed from the unknown region, and the analysis window has been moved to a new location within the unknown region.

[0022] FIG. 13 shows the unknown region of FIG. 12 after another character has been recognized, its image has been removed from the unknown region, and the analysis window has been moved to a new location within the unknown region.

[0023] FIG. 14 is a schematic representation of the operation of the invention.

[0024] FIG. 15 is a schematic representation in flowchart format of the unknown region defining routine of the invention.

[0025] While we describe our invention in terms of OCR of text from scanned documents, we envision other uses for our invention. In its broadest terms, our invention is an optical object recognition system that uses an optical object recognition (OOR) method and routine iteratively on an array of data to more accurately and more robustly recognize objects appearing in the array of data. The OOR routine parses the array of data into elements before or as part of the first pass at recognition, the elements being blobs in the case of OCR. In our exemplary embodiment, the array of data is an image of a document and the objects recognized are characters in the document image so that the OOR is an OCR. The types of objects that could be recognized in OOR are diverse and could even include three-dimensional objects. Our invention is preferably implemented in a system that has a computer including a processor and a memory; an output device, such as a printer, display, or mass storage device to which the system can send a data file; and some means to require the array of data to be analyzed, such as a mass storage device from which the system can retrieve or receive a data file including the array of data or an input device, such as a scanner, from which the system can receive the array of data.

[0026] Our invention preferably begins by acquiring or otherwise receiving an image of a document, such as that shown in FIG. 1, and identifying blobs in a region of interest 1 of the image as shown in FIG. 3. Identification of the blobs can be achieved by, for example, parsing the image to identify the blobs according to quantities of “white space” between “dark” areas of the image as is known in the art. The criteria used for blob identification yield single characters in the bulk of the blobs, but leave some characters in groups within individual blobs and split other characters among two or more blobs as discussed above and as can be seen in FIGS. 1-7. The particular criteria applied in the initial pass preferably include spatial characteristics of the blobs, such as spacing between substantially contiguous “dark” areas of the image or positional relationships between blobs. The criteria could also include spectral, gray level, intensity, luminance, or other criteria depending on the particular type of objects the invention is to recognize.

[0027] After blob identification, our invention performs an initial pass with an OCR method, such as that described in U.S. Pat. Nos. 5,150,425; 5,159,644; and 5,204,914, the disclosures of which are hereby incorporated by reference. The initial pass finds and recognizes substantially all single characters in respective blobs, but leaves unrecognized blobs containing merged and/or split characters, as shown in FIGS. 6 and 8. As reflected in the schematic representations of FIGS. 14 and 15, our invention divides the remnants of the initial pass into unknown regions, the effects of which are shown in FIG. 9. Preferably, the unknown region defining routine analyzes the region of interest 1 from left to right and line by line, applies the OCR method to the unknown regions to recognize merged characters, and then repeats these steps to recognize split characters.

[0028] An unknown region extends from a beginning of an unrecognized blob to a point at which unrecognized data stops and includes substantially contiguous data between these points along a first dimension of the unknown region. A second dimension of the unknown region is determined by a value of the contents of the unknown region along the second dimension. In a document image to which the exemplary embodiment of the invention is applied, this first dimension is the width of the unknown region; the second dimension is the height of the unknown region and is preferably substantially equal to the height of the tallest blob of the unknown region. Thus, beginning on the first line of the image that includes unrecognized blobs and with particular reference to FIG. 15, the preferred embodiment of our invention effectively starts at the left of the line and moves right until it encounters the start of an unrecognized blob, at which point an unknown region also begins. The invention then proceeds to the right until unrecognized data ends, the line ends, or both, at which point the unknown region ends. If the end of the unknown region does not coincide with the end of the line, the invention proceeds to the right, looking for the beginning of another unrecognized blob that defines the beginning of another unknown region. When the routine encounters the end of a line, it advances to the left of the next line, unless the end of the line is also the end of the unknown region, in which case the routine ends. As mentioned above, the heights of the unknown regions are the heights of the tallest of their contents. The unknown regions are preferably rectangular.

[0029] The manner in which our invention defines unknown regions remains essentially the same for recognizing merged characters and recognizing split characters. However, after merged character recognition, the blobs are grouped into new unknown regions according to relationships between the blobs if the relationships meet predetermined criteria. As with the parsing of the image into blobs, the particular relationships considered between the blobs can include spatial, spectral, intensity, gray level, and other relationships. Preferably, the relationship used in the regrouping of the blobs into new unknown regions is spatial and the predetermined criteria include a limitation that no blobs can have existed between two or more unrecognized blobs for them to be placed into one unknown region. This preferred spatial relationship and limitation of the predetermined criteria assume that, since no blobs appeared between the unrecognized blobs, each blob probably contains part of a single character. Grouping can be done for horizontally adjacent blobs and for vertically adjacent blobs to further improve recognition of split characters. Thus, as seen in the case of MICR characters in FIGS. 2 and 7-10, if the initial OCR splits a character into lower and upper parts and places the parts in respective blobs, neither of which are recognized in the first two passes of the OCR method, then the two parts can be rejoined at this point and the character can potentially be recognized. Once the unrecognized blobs are regrouped into new unknown regions, the OCR method is applied.

[0030] The application of the OCR method to each unknown region includes placing an analysis window at a start point in the unknown region, preferably so that an upper left corner of the analysis window coincides with the upper left corner of the unknown region. FIGS. 11-13 show an analysis window being used by the invention to recognize merged characters in Unknown Region 5, which includes Blob 4 of FIGS. 4 and 6. If the invention recognizes a character in the analysis window, then it records the recognized character, preferably in a memory; removes the portion of the unknown region encompassed by the analysis window; and tries again with the remaining portion of the unknown region as long as enough of the unknown region remains as shown in FIG. 12 after the “3” has been recognized, and again in FIG. 13 after the “4” has been recognized. We prefer to include a routine that will move the analysis window around the unknown region if placement in the upper left corner does not result in character recognition. Thus, if the “3” were not recognized in the initial application of the analysis window to the unknown region, the routine would iteratively increment the position of the analysis window to the right and/or down until a character was recognized or until substantially the entire unknown region had been analyzed. The analysis window size preferably depends on the sizes of the blobs identified at the beginning of the OCR process.

[0031] If unrecognized blobs remain, then the system preferably terminates the iterative OCR application and records or displays the remaining unrecognized blobs. Alternatively, the system could perform additional iterations, regrouping the blobs into unknown regions and applying OCR to the unknown regions. At some point, however, the system reaches a point of diminishing returns beyond which it makes little sense to continue.

[0032] While any suitable OCR routine can be used in our invention, we prefer to use the statistical correlation method of U.S. Pat. No. 5,150,425. The method of U.S. Pat. No. 5,150,425 first acquires a two-dimensional array of pixels, which we prefer to call an analysis window, from the region of interest. Then the method locates an unknown character in the analysis window and computes a correlation value R_xybetween the unknown character and each character of a trained set of characters (i.e., a font) using the formula $R_{\mathrm{xy}}^2=\frac{{\left[x_c^T{y}_c\right]}^2}{\left[x_c^T{x}_c\right]\left[y_c^T{y}_c\right]},$

[0033] where the mean corrected character vectors, x_c, y_c, are given by $x_c=x-{\mu }_x,y_c=y-{\mu }_y,\mathrm{and}$ $x_c^T=\left[x_{c_1},x_{c_2},\dots ,x_{c_N}\right],y_c^T=\left[y_{c_1},y_{c_2},\dots ,y_{c_N}\right].$

[0034] The trained set of characters can be derived in various ways so long as the trained set of characters is a set of characters the OCR routine can use as a reference. For example, they can be trained from the document image; they can be retrieved from a storage device; they can be described by a set of mathematical functions, equations, or formulae; or they can be predefined by other suitable means. In the broader context of OOR, a trained set of objects is used as a reference and can be trained in much the same way as the trained set of characters for OCR. The OCR routine then recognizes the unknown character as the trained character with the highest correlation value above a threshold value. The correlation values can be weighted or non-weighted, depending upon the particular application and the particular anticipated needs of the user. If the correlation values are weighted, the method adjusts the weights in the correlation calculations to place more emphasis on those areas of a character that exhibit less noise, less emphasis on those areas of the character that exhibit more noise, and more emphasis on those areas of a trained character that distinguish it from all other trained characters in the training set. U.S. Pat. Nos. 5,159,644 and 5,204,914 describe methods for optimally and statistically adjusting these weights.