US 5,359,671 AGrant
Character-Recognition Systems and Methods With Means to Measure Endpoint Features in Character Bit-Maps
Issue Date:1994-10-25
•22 Claims
•5 Drawing Sheets
Abstract
Character recognition method and system that identifies an input character as being a unique member of a defined character set. Specifically, a character bit-map of an input character is first generated. Thereafter, a character recognition procedure processes the character bit-map to generate a set of confidence measures one for each of the members of the character set. The confidence measures represent the degree of confidence that the input character corresponds to the members of the character set. A test is then made to determine if the confidence measure with the highest degree of confidence is acceptable. If there is an acceptable confidence measure, the member of the character set with the acceptable confidence measure is reported as the output character. If there is no acceptable confidence measure, a number of characters with the highest confidence measures are identified as candidates. Also, the character bit-map is analyzed further to obtain stroke-endpoint information which is then compared to a learned endpoint database having a number of character string-signature pairs. If there is a match between a database string and a candidate character, the match is used to report an output character. Endpoint location and orientation are obtained by modeling the bit-map as a charge distribution. A potential profile is constructed and thresholded and the results clustered into regions to obtain endpoint location information- The gradient of the potential profile is used to obtain endpoint orientation information.
Metadata
Assignee
- Eastman Kodak Company
Inventor
- Arun Rao
Application Information
Application Number:US 8609330
Filing Date:1992-03-31
Priority Date:1992-03-31
Art Unit:266
Classifications
IPC:
G06K 962G06K 948G06K 968
Field of Search:
38222;14;15;16;21;23;30;37;38;39
Patent Drawings (5 sheets)
Description
Technical Field of the Invention
This invention relates to character recognition techniques and, more particularly, to systems and methods for efficiently improving a margin of error in a machine recognition of printed characters.
Background Art
Computer techniques for machine recognition of hand printed characters have advanced considerably in the recent past. As a margin between error rates of a particular character recognition procedure and those of humans continues to decrease, further reductions in the error rate have become progressively more difficult to attain. In the case of neural-network-based algorithms, for example, this difficulty translates to procuring ever larger sets of training data for progressively smaller gains in error rates.
In view of this phenomena, one technique for reducing this error rate for machine based recognition processes has been to simultaneously use multiple recognition procedures, that have uncorrelated errors (i.e. make different kinds of mistakes), so that overall performance is enhanced. This technique exacts a fairly severe computational penalty, since the different procedures often have completely different (and hence non-shareable) intermediate steps, all of which have to be performed for each character.
A more efficient technique has been to simultaneously use only one or a few independent procedures for most characters and use additional independent procedures only for characters having a low measure of confidence. Although this technique can improve recognition error rates, the associated computational penalty can still be considerable. Unfortunately, this technique can be used effectively only with procedures that can provide a reasonably accurate measure of confidence.
More specifically, conventional optical character recognition (OCR) systems generally have as many outputs as there are characters to be recognized. An input character is usually identified by examining the values of the outputs. One of the simplest methods is to choose a character for the input character being recognized as that which corresponds to a particular output that has a maximum (or minimum) value. The confidence measure is also a function of the output values. In its most basic form, the value of the maximum (or minimum) output may be a measure of the confidence. A slightly more sophisticated confidence measure can be determined as a ratio between the maximum and a next highest output. However, the accuracy of confidence measure varies widely between the methods of measurement and between different OCR procedures.
Thus, a need still exists in the art for increasingly efficient techniques of reducing the margin between the error rates of particular OCR procedures and those of humans.
Summary
It is, therefore, an object of my present invention to provide techniques for efficiently reducing the error rates of character recognition systems and methods.
Another object is to improve the performance of feature-based character recognition systems by measuring additional character-features only when the "best" confidence measure is low.
Still another object of the invention is to provide systems and methods that quickly and efficiently obtain stroke-endpoint location and orientation from a character bit-map.
These and other objects are achieved in accordance with my inventive teachings by: effectively constructing a simple signature from each input character to be recognized based on quickly computable features only in those cases in which the confidence measure generated by an optical character recognition (OCR) procedure is low and then to use this signature to make an improved choice for that character. The key to the success of my inventive approach, when used in conjunction with an OCR procedure, lies in the quality of the signature and the accuracy of the confidence measure of this procedure.
In particular, it is widely recognized that curvature discontinuities in objects are strong contributors to human perception. By extending this concept to handwritten characters, I have found that the location and orientation of stroke endpoints prove to be very valuable features for character identification. As such, my invention relies on incorporating this information into the recognition process.
More specifically, my invention employs a character-feature measuring technique that is based on a charge model for pixels. Character endpoints are located by computing a "potential" at each pixel and applying a threshold. A binary signature is constructed from this information. A database of signatures and associated characters is then constructed using a large training set of character bit-maps. During actual use, a low confidence measure from the OCR procedure triggers a signature generation process. The signature is used to retrieve a list of potential characters from a previously created database. The character list is used to decide between first and second choices generated by the OCR procedure.
Specifically, in a training phase, known bit-mapped characters are presented to an endpoint-locating procedure. Endpoint location and orientation information are found and processed to yield a binary string (string of 1's and 0's) which constitutes the signature for each character. A database is built in which each entry consists of a signature and an associated string of likely candidate characters.
One aspect of my invention is directed to character recognition systems and methods that identify an input character as being a unique member of a defined character set. In particular, a character input device generates a character bit-map of an input character. A character recognition procedure processes the character bit-map and generates a set of confidence measures: one for each of the members of the character set. The confidence measures represent the degree of confidence that the input character corresponds to the members of the character set. The confidence measures are tested to decide if the confidence measure with the highest degree of confidence is an acceptable confidence measure. A first output device reports the member of the character set with the acceptable confidence measure as an output character. If there is no acceptable confidence measure, an augmenter identifies (N) of the members with the (N) highest confidence measures as candidates and further processes the bit-map. The augmenter measures a character feature of the bit-map. A second output device reports one of the (N) members as an output character based on the measure of the character feature.
According to another aspect of my invention, the character bit-map is analyzed by the augmenter to obtain stroke-endpoint information which is compared to a learned endpoint database having a number of character string-signature pairs. If there is a match between a database string and a candidate character, the match is used to report an output character. Endpoint location and orientation are obtained by modeling the bit-map as a charge distribution. A potential profile is constructed and thresholded and the results clustered into regions to obtain the endpoint location. The gradient of the potential profile is used to obtain the endpoint orientation.
Brief Description of the Drawings
The teachings of the present invention may be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which:
FIG. 1 is a block diagram of a preferred embodiment of an OCR system constructed in accordance with my inventive teachings;
FIG. 2 is a flow diagram for the OCR system of FIG. 1;
FIG. 3 is a diagrammatic view of a two-dimensional character bit-map;
FIG. 4 is a computer flow diagram illustrating in detail the endpoint-augmenter portion of the flow diagram of FIG. 2;
FIG. 5 is a three-dimensional graph illustrating a computed potential profile for a character bit-map of the type shown in FIG. 3;
FIG. 6 is a diagrammatic view, similar to the view of FIG. 3, showing those regions of the character bit-map of FIG. 3 that have been identified as stroke endpoints; and
FIG. 7 is a three-dimensional diagram illustrating spatial and orientation bins useful in understanding the invention.
To facilitate understanding, identical reference numerals, where possible, identify identical elements that are common to various figures.
Modes of Carrying Out the Invention
Referring now to the drawings, FIG. 1 shows optical character recognition (OCR) system 15 having character input system 18, which may be a conventional optical scanning system, a digitizer/pen system, or other character input device. Input system 18 is connected to digital computer 17. Character recognition processor 20, constructed in accordance with my invention, is resident in computer 17. Appropriate output device 16 is connected to the output of computer 17. Output device 16 may be a printer, a disk storage, a display, a data transmitter, or similar device for presenting, storing or transmitting characters outputted by processor 20.
In general, the operation of OCR system 15 is as follows. This system first reads characters in a conventional manner via input system 18. The input characters may typically be gray-scale images of machine-printed or handwritten alphanumeric text. The input to computer 17 is typically a binary string that is obtained by thresholding gray-scale image data produced in input system 18. Processor 20 stores the binary string as a set of bit-maps, one for each of the scanned characters. This processor then processes the bit-maps to select an output character from an internally stored database of characters. The selected output character is then transmitted to output device 16.
In FIG. 2, processor 20, typically being implemented through software, is shown in the form of a detailed flow diagram. In construct-bit-maps step 19, processor 20 constructs bit-maps from the binary string inputted by system 18 (see FIG. 1). The bit-maps are stored in an appropriate storage location (e.g. a disk file) of computer 17.
FIG. 3 diagrammatically shows a bit-map 30 of the type that would be obtained as a result of scanning a printed or handwritten character "A" at a large number of pixel locations. Bit-map 30 is represented here as a rectangular array of pixel locations arranged in columns x and rows y, with each of the pixel locations occupied by either a black or white pixel. The pixels are shown in FIG. 3 as an array of dots and dashes.
More specifically, for the illustrative example shown in FIG. 3, bit-map 30 consists of a total of thirty-nine columns and sixty rows. As such, bit-map 30 has 2,340 pixel locations. White pixels are represented by dashes (unoccupied pixel locations); while black pixels are represented by dots (occupied pixel locations) that together form the character "A" in uppercase. The character "A" in bit-map 30 has a number of character features including stroke endpoints 32-35. Of course, character bit-map 30 may be stored in computer 17 as a binary string of 2,340 bits (string of "1's" and "0's").
As shown in FIG. 2, after constructing and storing the bit-maps, processor 20 retrieves a bit-mapped character from its storage location in read step 21. In format step 22, the retrieved bit-map data is prepared for processing by performing such conventional functions as de-skewing and normalizing the bit-map to a standard size. Processor 20 then processes the bit-map data in OCR step 23 in accordance with an OCR procedure. For purposes of this description, the OCR procedure is assumed to be a conventional neural network having 2,340 inputs corresponding to the 2,340 pixels of bit-map 30 and, for example, thirty-six outputs corresponding to the total number of possible characters to be read, i.e. twenty-six uppercase letters of the alphabet plus ten numeric digits from zero to nine.
In confidence-measure step 24, the thirty-six outputs generated by the OCR procedure in OCR step 23 are used to obtain a confidence measure for each of the possible thirty-six characters. As mentioned above, many conventional OCR systems use these thirty-six outputs themselves as the confidence measures. For example, upon processing a bit-map in OCR step 23, the OCR procedure assigns a number, typically between zero and one, to each of the possible thirty-six characters. The values of these assigned numbers usually indicate the degree to which the processed bit-map corresponds to each of the various characters based on the criteria used by the OCR procedure. As such, these thirty-six assigned numbers may be directly used as confidence measures. Other OCR procedures often generate more accurate confidence measures. For instance, confidence measures may also be generated by computing a complex function of the set of thirty-six assigned numbers. Ascertaining a reasonably accurate confidence measure assures that an improvement in the accuracy of the final choice of an output character is efficiently accomplished.
More specifically, at least one of the assigned numbers from OCR step 23 will have, in most situations, a relatively high value. As such, its corresponding character will normally be selected as the output character, especially if the assigned number is much greater than the next highest assigned number, i.e. the ratio of the two highest assigned numbers is not close to one. In other situations, however, it may happen that all of the thirty-six assigned numbers are very low, or two or more assigned numbers, though high, are very close in value such that their ratios are very close to one. In these cases, the choice of an output character will not be clear. In fact, here, the character with the highest assigned number may not be the correct choice. In these questionable instances, the accuracy of the final selection is improved through use of the present invention by processing the bit-map further to choose between a few of the best candidates identified in OCR step 23.
In decision step 25, processor 20 decides if the "best" confidence measure is acceptable, i.e. is "OK", according to a pre-determined criteria as described above. If the "best" confidence measure is acceptable, the character with the "best" confidence measure is reported as the output character in output step 26. 0n the other hand, if the "best" confidence measure is not "OK", then two or more of the characters with, for example, the highest assigned numbers are identified as candidates and the bit-map is processed further in augment step 27 using different criteria (e.g. endpoint location and orientation) to select the proper output character for the character currently being recognized. After an output character is chosen in either output step 26 or augment step 27, the process steps are repeated, via decision step 28, until all bit-maps have been processed.
As indicated above, many OCR procedures do not directly make use of stroke-endpoint information and often incorrectly identify characters which are distinguishable on the basis of these features alone. I have found that the location and orientation of stroke endpoints for most handwritten characters prove to be very valuable features for character identification.
FIG. 4 shows a flow diagram for endpoint augmenter 40 that is used in augment step 27 shown in FIG. 2. A specific implementation of the endpoint augmenter 40 appears in APPENDIX A which lists a computer program written in the computer language "C" for a Sun SPARCstation running the UNIX operating system ("SPARCstation" is a registered trademark of Sun Microsystems, Inc. and "UNIX" is a registered trademark of American Telephone and Telegraph Company). This description and FIG. 4 refer to sections of the APPENDIX A program via their program labels that are enclosed in square brackets.
Endpoint augmenter 40 is a feature-based procedure in which the location and orientation of the stroke-endpoints of a character bit-map are measured, e.g. see endpoints 32-35 in FIG. 3. When triggered by decision step 25 (see FIG. 2), endpoint augmenter 40, in read step 41 shown in FIG. 4, begins by reading the bit-map constructed in construct-bit-maps step 19 (again see FIG. 2). Read step 41 is performed in program section [get.sub.-- point.sub.-- list()] (see APPENDIX A).
Endpoint augmenter 40 then analyzes the bit-map for stroke-endpoint locations and orientations. To perform this function, endpoint augmenter 40 first treats the bit-map as a point distribution function and then finds its potential profile V(x,y), where x and y are the rectangular coordinates of the pixel locations in the bit-map. These functions are performed in potential-profile step 42 (see FIG. 4) which corresponds to program sections [setup.sub.-- delta.sub.-- v()] and [compute.sub.-- potentials()] (see APPENDIX A).
More specifically, the set of black pixels (dots) in character bit-map 30 (see FIG. 3) constitute a point distribution function that is related to a potential function V(x,y) by a Poisson differential equation. To simplify and facilitate the process, each black pixel (dot) of bit-map 30 is modeled as an electrostatic charge (e.g. a negative charge); the entire bit-map 30 is modeled as a charge distribution on a dielectric surface. Using this model, the potential function V(x,y) corresponds to the electric potential (volts) produced by the charge distribution. A potential profile of the electrostatic potential V for bit-map 30 is computed using a Poisson differential equation as set forth in equation (1) below: ##EQU1## where: V=V(x,y) (potential profile),
.rho. is charge density at any point, and
.epsilon. is the dielectric constant.
Since actual electrostatic charges are not involved, several simplifying assumptions are made for the model. First, the right-hand side of Equation (1) is replaced by a constant at black pixel locations and zero elsewhere (white pixels). Also, since an accurate solution for potential V(x,y) is not required, it is assumed that each charge (black pixels) influences only a small neighborhood around it. These assumptions significantly accelerate the process of obtaining the potential profile V(x,y) when using this charge-based model.
FIG. 5 graphically shows a typical potential profile V(x,y) that would be computed in potential-profile step 42 shown in FIG. 4. From FIG. 5, it is evident that those black pixels located towards the edges will have relatively low potentials V. Moreover, those edge-pixels that are also located at the extremities of the characters (e.g. at stroke endpoints 32-35) will have the lowest potentials V, and can be isolated from the bit-map by thresholding, a process that is performed in thresholding step 43 (see FIG. 4) and in program section [belongs.sub.-- to.sub.-- corner()]. FIG. 6 shows the thresholded pixels for the bit-map 30 of FIG. 3.
Since there are typically multiple endpoints, such as the four endpoints 32-35, and since each endpoint will include a number of pixels (see FIG. 6), it is not sufficient just to perform thresholding step 43 in endpoint augmenter 40 shown in FIG. 4; contiguous regions of thresholded pixels must be clustered together and cluster regions located. Cluster regions are located in region-building step 44 and program sections [build.sub.-- contiguous.sub.-- regions()] and [belongs.sub.-- to.sub.-- corner()]. The region-building function is performed by making a search of the x-y locations of the thresholded pixels to locate those pixels that are located adjacent to each other. The adjacent pixels are then grouped into regions. Four regions are illustratively shown in FIG. 6.
The locations of the regions are now determined in region-location step 45, shown in FIG. 4, which is performed in program section [get.sub.-- region.sub.-- info ()]. The region locations are determined by finding their average column-row coordinates x.sub.i and Y.sub.i as follows. If there are n regions, and k.sub.i points in the i.sup.th region, then using equations (2) and (3) below: ##EQU2## where: (x.sub.i,Y.sub.i) is the pixel location of the i.sup.th region.
The region orientations are next determined in region-orientation step 46 which corresponds to program sections [get.sub.-- region.sub.-- info()] and [gradient()]. Region orientations are determined by first finding the gradient F of the potential V, i.e. F(x,y)=grad V(x,y). Using the electrostatic charge model, F corresponds to the electric field at a point (x,y). Using the x-y components of F, the region orientations are given by equation (4) as follows: ##EQU3## where: F.sub.y.sup.x and F.sub.j.sup.y are the x and y components, respectively, of the gradient, and
.theta. is the angle measured counterclockwise from the x axis.
FIG. 6 graphically shows the spatial locations of the regions generated for the endpoints 32-35 of the hand printed letter "A" of FIG. 2, and the angles .theta..sub.i at which the endpoints 32-35 are oriented. Specifically and illustratively, endpoint 32 is directed downwardly at 269.degree.. Endpoint 33, which is almost parallel to endpoint 32, is directed at 271.degree.. Endpoint 35 is directed at 60.degree. and endpoint 34 is directed at 342.degree..
A binary signature of the endpoint locations and orientations for the bit-map being processed is now computed in signature step 47, shown in FIG. 4, which corresponds to program sections [hc.sub.-- packed.sub.-- bin.sub.-- filter()], [get.sub.-- packed.sub.-- binary.sub.-- features ()] and [get.sub.-- packed.sub.-- binary.sub.-- fv()]. The binary signature is constructed by dividing the spatial and orientation dimensions into a number of bins defined herein as x-bins, y-bins and .theta.-bins. (See the defined constants XBINS, YBINS and THETA.sub.-- BINS in the APPENDIX A program.) As seen in FIG. 6, the area of bit-map 30 is divided into nine areas corresponding to the x- and y-bins. The boundaries of the x- and y-bins are located at x=1, 13, 26, 39 and y=1, 20, 40, 60.
Each of the x-, y- and .theta.-bins represents a particular combination of endpoint location and orientation. FIG. 7 illustrates a situation in which there are three x-bins, three y-bins and four .theta.-bins. A bin is assigned a value of unity if at least one region falls within it, and zero otherwise. Based on this rule, bin 35' of FIG. 7 is assigned a one because: (1) the corresponding x- and y-bins in FIG. 6 include endpoint 35, and (2) endpoint 35 has a 60.degree. orientation. Likewise, bins 32', 33' and 34' are all assigned ones because they correspond to the locations and orientations of endpoints 32, 33 and 34, respectively. Each of the other bins are assigned a zero because no other endpoints have been located. Finally, these ones and zeros are folded out in a pre-specified order to construct the binary signature vector as illustrated in FIG. 7.
The signature vector is then compared, in compare step 48, shown in FIG. 4, to a stored database of signature vectors and their associated character strings to locate any character matches between the members of the character strings and the identified candidate characters with the "best" confidence measures. If there is only one match, the matching candidate character is reported as the output character in output step 49. If there are a number of matching candidate characters, the matching character with the highest confidence measure is reported as the output character in output step 49. If there are no character matches, the candidate character with the highest confidence measure is reported as the output character in output step 49.
The signature database is generated during a training phase. This database is stored as an array of structures in computer 17. In this regard, processor 20 is trained with a training set, i.e. a large number of known character bit-maps. Processor 20 presents the training set of known bit-maps to endpoint augmenter 40 for processing. After each signature vector is constructed in signature step 47, this vector and the associated character are stored in the signature database. The signature database consists of a list of signature-string pairs. Also included is a count of the number of times each signature was encountered while processing the training set. In each signature-string pair, the string contains all of the characters in the training set that generated the corresponding signature.
TABLE A below lists a section of a database that was created using a large training set (approximately 10,000 characters) collected from various sources (digitizer, scanner and others). For simplicity, this database section shows a 9-element (3.times.3.times.1) binary signature. Location information is not present in the signatures. The first entry in TABLE A shows that the training set contained bit-maps of the characters 0, 2, 4, C and G that generated the same signature twenty-one times. The second entry shows that a set of characters that included all elements of the character set (thirty-six characters) failed to produce an endpoint 2,384 times. In this regard, the absence of an endpoint could be the result of a number of reasons, such as the character often does not have an endpoint (e.g. "0") or the endpoint stroke was not of sufficient size to produce a reading.
A number of sections of the APPENDIX A program correspond to compare step 48 shown in FIG. 4. Program section [hc.sub.-- packed.sub.-- bin.sub.-- load()] loads the database from file. Sections [msearch()] and [mfind()] are used to look up a signature by performing a metric search in the database and then return a list of elements meeting the specified matching criterion. In this case, a relative Hamming distance metric is used (see program sections [subsethood()], [relative.sub.-- hamming.sub.-- distance()], [num.sub.-- ones()], [xor()], and [and()]). Output step 49 corresponds to program step [get.sub.-- index()].
A polynomial-based OCR procedure was used to test the performance of processor 20 on 3600 character bit-maps generated by a GTC digitizer/pen mounted on a DECstation 3100 type workstation ("DECstation" is a trademark of Digital Equipment Corporation which also manufactures the workstation). The polynomial algorithm achieved 92.42% accuracy when used stand-alone without the endpoint augmenter 40. In conjunction with the endpoint augmenter 40, the accuracy improved to 94.14%, an error reduction of 22.7%.
Obviously many modifications and variations of the present invention are possible in the light of the above teachings. It is therefore to be understood, that within the scope of the appended claims, the invention may be practiced otherwise than as specifically described.
Industrial Applicability and Advantages
The present invention is useful in conjunction with optical character recognition (OCR) systems. In particular, when used in conjunction with such a system, the invention advantageously increases the recognition accuracy of characters than that previously obtainable in the art.
Appendix A
This appendix consists of a computer program listing that is written in the computer language "C" for a Sun SPARCstation running the UNIX operating system ("SPARCstation" is a registered trademark of Sun Microsystems, Inc. and "UNIX" is a registered trademark of American Telephone and Telegraph Company).
The program listing is an implementation of endpoint segmenter 40. ##SPC1##
Claims
I claim:
1. A character recognition system that identifies an input character as being a unique member of a defined character set, said system comprising: a bit-map means for generating a character bit-map of an input character; a character recognition means for processing said character bit-map and generating a set of (M) finite confidence measures one for each of (M) members of said character set, said confidence measures representing the degree of confidence that said input character corresponds to each of said (M) members of said character set; a decision means for deciding if the confidence measure with the highest degree of confidence is an acceptable confidence measure; a first output means for reporting as an output character the member of said character set with said acceptable confidence measure; an augment means for identifying (N) of said (M) members with the (N) highest confidence measures, where (M) is greater than (N), and processing said bit-map if said decision means decides that there is no acceptable confidence measure, said augment means having a measuring means for measuring stroke endpoint locations and orientations of said bit-map and a second output means for reporting one of said (N) members as an output character based on said stroke endpoint locations and orientations; and wherein said augment means further comprises a database means having a database of character strings, each said character string including a subset of said character set and wherein the members of each said subset represent different characters in said character set which have common stroke endpoint locations and orientations.
2. The system of claim 1 wherein said database means comprises unique database signatures each associated with one of said character strings; said measuring means comprising means for generating a search signature related to said location and orientation of said stroke endpoints; and said augment means comprising search means for searching, in response to said search signature, said database signatures to identify an output character string and for locating matches between said output string and said (N) members with the (N) highest confidence measures.
3. The system of claim 2 wherein said second output means comprises means for reporting one of said (N) members as an output character according to the following rule: if there is a match for only one of said (N) members and said output character string, report the matching member as the output character; if there is a match for more than one of said (N) members and said output character string, report the matching member with the highest confidence measure as the output character; and if there are no matches for said (N) members and said output character string, report the member with the highest confidence measure as the output character.
4. The system of claim 3 wherein (N) is equal to two.
5. The system of claim 3 wherein said measuring means further comprises charge model means for constructing a potential profile based on a charge distribution model of said bit-map and location means for thresholding said potential profile and clustering said thresholded profile to determine said locations of said stroke endpoints.
6. The system of claim 5 wherein said measuring means further comprises gradient means for obtaining a gradient of said potential profile to determine said orientations of said stroke endpoints.
7. A stroke endpoint detector that identifies which of (N) candidate characters represents a unique member of a defined character set comprising: a bit-map means for reading an input bit-map; a database means having a database of character strings, each said character string comprises a subset of said character set and wherein the members of each said subset representing different characters in said character set which have common stroke endpoint features; measuring means for measuring the location and orientation of said stroke endpoints of said character bit-map, said measuring means including charge model means for constructing a potential profile based on a charge distribution model of said bit-map and location means for thresholding said potential profile and clustering said thresholded profile to determine the locations of regions of said stroke endpoints in said bit-map; search means, responsive to said measuring means, for searching said database to identify an output character string, and locate matches between said output string and said (N) candidate characters; and output means responsive to said search means for reporting a matching candidate character as an output character.
8. The detector of claim 7 wherein said database means comprises unique database signatures each associated with one of said character strings; said measuring means comprises means for generating a search signature related to said location and orientation of said stroke endpoints; and said search means comprises means for searching, in response to said search signature, said database signatures to identify said output character string and for locating matches between said output string and said (N) candidate characters.
9. The detector of claim 8 wherein said (N) candidate characters each have a weighting factor associated therewith; and said output means comprising means for reporting one of said (N) candidate characters as an output character according to the following rule: if there is a match for only one of said (N) candidate characters and said output character string, report the matching candidate character as the output character; if there is a match for more than one of said (N) candidate characters and said output character string, report the matching candidate character with the highest weighting factor as the output character; and if there are no matches for said (N) candidate characters and said output character string, report the candidate character with the highest weighting factor as the output character.
10. The detector of claim 9 wherein (N) is equal to two.
11. The detector of claim 10 wherein said measuring means further comprises gradient means for obtaining a gradient of said potential profile to determine the orientations of said stroke endpoints.
12. A character recognition method for identifying an input character as being a unique member of a defined character set comprising the steps of: generating a character bit-map of an input character; processing said character bit-map with a character recognition procedure to generate a set of (M) finite confidence measures one for each of (M) members of said character set, said confidence measures representing the degree of confidence that said input character corresponds to each of said (M) members of said character set; determining if the confidence measure with the highest degree of confidence is an acceptable confidence measure; if there is an acceptable confidence measure, reporting as an output character the member of said character set with said acceptable confidence measure; if there is no acceptable confidence measure, identifying (N) of said (M) members with the (N) highest confidence measures, where (M) is greater than (N), and analyzing said character bit-map to measure stroke endpoint locations and orientations of said bit-map; reporting one of said (N) members as an output character based on the measure of said stroke endpoint locations and orientations; and further comprising the step of: constructing a database of character strings, each said character string comprising a subset of said character set and wherein the members of said subset represent different characters in said character set which have common stroke endpoint locations and orientations; and wherein said analyzing step comprises the step of searching said database.
13. The method of claim 12 further comprising the steps of: constructing said database with unique signatures each associated with one of said character strings; generating a search signature in said analyzing step to determine the location and orientation of said stroke endpoints; and using said search signature in said searching step for searching said database signatures to identify an output character string, and locating matches between said output string and said (N) members with the (N) highest confidence measures.
14. The method of claim 13 further comprising the step of reporting one of said (N) members as an output character according to the following rule: if there is a match for only one of said (N) members and said output character string, report the matching member as the output character; if there is a match for more than one of said (N) members and said output character string, report the matching member with the highest confidence measure as the output character; and if there are no matches for said (N) members and said output character string, report the member with the highest confidence measure as the output character.
15. The method of claim 14 wherein (N) is equal to two.
16. The method of claim 14 wherein said analyzing step further comprises the steps of: constructing a potential profile based on a charge distribution model of said bit-map; thresholding said potential profile to form a thresholded profile; and clustering said thresholded profile to determine the locations of regions of said stroke-endpoints in said bit-map.
17. The method of claim 16 wherein said analyzing step further comprises the step of obtaining a gradient of said potential profile to determine the orientations of said stroke endpoints.
18. A stroke endpoint detection method that identifies which of (N) candidate characters represents a unique member of a defined character set comprising: reading an input bit-map; constructing a learned database of character strings, each said character string comprising a subset of said character set and wherein the members of each said subset representing different characters in said character set which have common stroke endpoint locations and orientations; measuring stroke-endpoint location and orientation of said character bit-map by using a charge model means for constructing a potential profile based on a charge distribution model of said bit-map and thresholding said potential profile and clustering said thresholded profile to determine the locations of regions of said stroke endpoints in said bit-map; searching said database to identify an output character string, and locate matches between said output string and said (N) candidate characters; and reporting one of said matches as an output character.
19. The method of claim 18 further comprising the steps of: constructing said learned database with unique signatures each associated with one of said character strings; generating a search signature in said analyzing step to determine the location and orientation of said stroke endpoints; and using said search signature in said searching step for searching said database signatures.
20. The method of claim 19 wherein said (N) candidate characters each have a weighting factor associated therewith; and wherein said reporting step comprises the step of reporting one of said (N) candidate characters as an output character according to the following rule: if there is a match for only one of said (N) candidate characters and said output character string, report the matching character as the output character; if there is a match for more than one of said (N) candidate characters and said output character string, report the matching member with the highest weighting factor as the output character; and if there are no matches for said (N) candidate characters and said output character string, report the candidate character with the highest weighting factor as the output character.
21. The method of claim 20 wherein (N) is equal to two.
22. The method of claim 21 wherein said measuring step further comprises the step of obtaining a gradient of said potential profile to determine the orientations of said stroke endpoints.
Patent Citations (9)
Non-Patent Literature (5)
- J. J. Koenderink et al., "Two-dimensional curvature operators," Journal of the Optical Society of America, vol. 5, No. 7, Jul. 1988, pp. 1137-1141.
- K. Prazdny, "Simulitude-Invariant Pattern Recognition Using Parallel Distributed Processing," Proceedings of the Sixth National Conference on Artificial Intelligence, Seattle, Wash., 1987, pp. 728-732.
- *Proc. of the Int. Joint Conf. on Pattern Recognition, 8 Nov. 1976, Coronado, Calif., pp. 113-118; Y. Fujimoto et al., "Recognition of handprinted characters by nonlinear elastic matching".
- *Pattern Recognition, vol. 24, No. 7, 1991, Elmsford, N.Y., US, pp. 617-632; S. W. Lu et al. "Hierarchical attributed graph representation nad recognition of handwritten Chinese characters".
- *Proc. Computer Vision and Pattern Recognition, 5 Jun. 1988, Ann Arbor, Mich., pp. 424-429; J. Ohya et al., "A relaxational extracting method for character recognition in scene images".