AU726852B2

AU726852B2 - Method and device for handwritten character recognition

Info

Publication number: AU726852B2
Application number: AU22168/97A
Authority: AU
Inventors: Farzad Ehsani; Liyang Zhou
Original assignee: Motorola Inc
Current assignee: Motorola Solutions Inc
Priority date: 1996-03-08
Filing date: 1997-03-06
Publication date: 2000-11-23
Anticipated expiration: 2017-03-06
Also published as: IL125648A0; WO1997033249A1; AU2216897A; EP0896704A1; CN1181827A; CA2247359A1

Description

WO 97/33249 PCT/US97/04349 METHOD AND DEVICE FOR HANDWRITTEN CHARACTER RECOGNITION Field of the Invention This invention relates generally to handwriting recognition by a character recognizer, and more particularly to improving recognition of handwritten characters using a postprocessing method and device.

Background of the Invention Several contemporary hand-held devices have attempted to permit users to enter text characters or alphanumeric information via a stylus and a digitizing tablet. For example, the NewtonTM personal digital assistant, by Apple Computer, and the MarcoTM wireless personal communicator by Motorola, accepts handwritten characters (as opposed to cursive handwriting) on a display screen. The device attempts to convert the handwritten characters into a typewritten representation of the handwritten characters. The concept of converting handwritten entries into typewritten representations is expanding to recognition of characters written in Chinese and other languages.

Part of the known process of converting handwritten characters into typewritten representations includes comparing the elements of the handwritten characters with a predetermined set of template characters. This is generally performed by a character recognizer that determines which of a set of template characters in a template character library most closely resembles a given handwritten character. The determination is generally based upon probabilities that the chosen template characters will be the same as the handwritten character.

-2- Conventional character recognizers have approximately a to 80 percent accuracy rate when attempting to correc'ly recognize handwritten characters from a digitizing tablet or other input device, yielding a 15 to 30 percent error rate. This accuracy rate is not good enough for the average user to feel confident in the ability of the recognizer.

There are several areas where character recognizers can be useful and valuable. For instance, character recognizers can be useful in conferences or seminars where a user does not bring in a keyboard but desires to electronically take notes. A character recognizer would then be used. If the character recognizer does not have a fairly high rate of accuracy, the notes taken during the seminar may become misleading.

Use of character recognizers may be valuable in hospitals if the character recognizer has a high rate of accuracy. Handheld character recognizers would allow hospital personnel to checks patients and enter by hand reports which may be life saving. Without a high recognition rate, lives may be endangered.

One very useful application for character recognizers is inputting Chinese characters for electronic processing and storage. Chinese characters do not lend themselves well to keyboard entry making word processing in the Chinese language difficult. Chinese characters are complex and changing a small portion of the character may entirely change the meaning of the character or word. A high rate of accuracy is necessary for Chinese character recognition. Unfortunately, conventional character recognizers and recognition processes have not achieved the high accuracy necessary for these 3 0 varying application.

-3- Summary of the Invention According to one aspect of the present invention there is provided a method of handwritten character recognition including the steps of: receiving a first input representative of a handwritten character and a second input representation of an adjacent character; comparing the first input with each template of a template character set; selecting from the template character set a plurality of template characters which are likely to resemble the handwritten character to provide a subset of candidate characters, each of the candidate characters having a value representing a degree of similarity with the handwritten character; and processing the candidate characters according to a language model by comparing each candidate character with the adjacent character to determine a predetermined probability in a given language that the candidate character could be in combination with the adjacent character, thereby to determine which of the candidate characters is most likely to be the handwritten character.

The step of processing the possible characters according to a language model preferably includes: combining each of the candidate characters with a surrounding character to form combined characters; assigned a combined value to each of the combined characters where the combined value represents a probability that the surrounding character would be in combination with a respective one of the candidate characters; and resorting the candidate characters. Additionally or in the alternative it includes comparing each of the candidate characters with a surrounding character to determine a probability that the surrounding character would be in combination with a respective one of the candidate characters; and determining from the probability for each of the candidate characters which of the candidate characters most resembles other handwritten character.

The value for each of the candidate characters and the combined value of the combined characters may be weighted to determine a weighted value for each of the candidate characters; and these may be ordered for each of the candidate characters to determine a sequential order for resorting the candidate characters.

According to a further aspect of the present invention there is provided a handwriting recognizer including: W:\maryNODELETEX22168-97.doc -4a character recognizer coupled to a handwriting input device, to choose a number of template characters from a template character set which are likely to resemble a handwritten character to provide a subset of candidate characters, each of the candidate characters having a value representing a degree of similarity with the handwritten character; a post-processor coupled to the character recognizer to process the candidate characters according to a language model by comparing each candidate character with an adjacent character to determine a predetermined probability in a given language that the candidate character could be in combination with the adjacent chamber, thereby to determine which of the candidate characters is most likely to be the handwritten character; and a display device coupled to the post-processor to receive the one of the candidate characters which is most likely to be the handwritten character.

Brief Description of the Drawings A preferred embodiment of the present invention will now be described with reference to the accompanying drawings wherein: FIG. 1 is a block diagram illustrating a preferred embodiment of the present invention.

FIG. 2 is a flow chart illustrating a method of performing the present invention.

FIG. 3 is a flow chart illustrating the method of performing the present invention according to the preferred embodiment.

FIG. 4 shows an example of the operation of a language modeling postprocessor according to the present invention.

Detailed Description of the Preferred Embodiment FIG.1 illustrates, with reference also to FIG. 2, a device and method, according to the present invention, for improving the accuracy of handwritten character recognition. Handwritten character recognizing devices, such as character recognizing device 100, generally include some sort of handwritten input device, tablet or digitizing display 110 allowing a user to enter handwritten characters to character recognizing device 100. It will be noted at this point that character recognizing devices may also receive input through devices other W:\rary\NODELETE\22168-97.doc -4athan through tablets. For instance, handwritten characters may be input to character recognizing device 100 via facsimile or any other media in addition to digitizing display 110.

Referring to the preferred embodiment of FIG. 1, with reference to the flow chart of FIG. 2, handwritten characters are input from digitizing display 110 to a character recognizer 120 (Step 200 of FIG. The character recognizer 120, in this preferred embodiment, chooses characters from a predetermined template character set 125 (step 210) for comparison with the handwritten character. The predetermined template characters of template character set 125 are the characters used in the.

language for which character recognizing device 100 is designed. For instance, if English handwritten characters are being input to character recognizing device 100, template character set 125 will contain information representing English characters in some form, such as longhand, print, or a combination of styles. If, for instance, recognizer 100 is designed for Chinese character input, template character set 125 will contain information representing Chinese characters in such styles (cursive or printed) as character recognizing device 100 is designed for.

Character recognizer 120 compares each input handwritten character to the characters stored in template character set 125 and chooses a number of the characters, or possible characters, which most closely resemble the input character. In a preferred embodiment, character recognizer 120 chooses 10 characters from the template character set 125.

To each of these number of possible characters (10 in the preferred embodiment), character recognizer 120 assigns a score (or value) that represents the degree of similarity between the respective possible character and the input character (step 220 of FIG. Character recognizer 120 then prioritizes the number of possible characters according to their respective scores (step 240). Character recognizer 120 prioritizes the number of possible characters according to their respective scores ordered into a chronological order with the W:AmaryWODELETE22168-97.doc WO 97/33249 PCT/US97/04349 possible character having the score indicative of the nearest similarity ordered at the top of the list.

As mentioned previously, handwritten characters which are processed simply by a character recognizer have approximately a 15 to 30 percent error rate when choosing the top prioritized possible character. Put another way, the probability that the top prioritized possible character chosen by character recognizer 120 is actually the same as the handwritten input character is about 80 to 85 percent. There is 1 0 a 92 to 96 percent probability that the actual handwritten input character is one of the number of possible characters chosen by character recognizer 120 when the total number of possible characters is 10 pursuant to the preferred embodiment. This accuracy is nearly the same as the degree of 1 5 accuracy most people have when reading handwritten characters, which accuracy is about 95 to 97 percent.

According to the teachings of the present invention, the accuracy of the 10 chosen possible characters is capitalized upon through the method described below to increase the probability that the character chosen as the top prioritized possible character is the same as the handwritten character.

The present invention contemplates further analyzing and processing the number of possible characters generated by character recognizer 120 to improve recognition accuracy. The additional analysis and processing (post-processing) focuses on the 10 possible characters.

Referring again to Figures 1 and 2, according to the preferred embodiment of the invention, character recognizer 120 outputs the list of 10 possible characters to a postprocessor 130 (step 250). Post-processor 130 processes the possible characters according to a language model to select which of the 10 possible characters is a best-fit character (step 260). In other words, the language model post-processing chooses one of the 10 possible characters for output. This 3 5 yields approximately a 90 to 92 percent probability that the WO 97/33249 PCT/US97/04349 character which is output, or best-fit character, is the same as the input handwritten character.

Language modeling is a process where each possible character processed is compared with a surrounding character to determine the probability that the possible character could be properly used in combination with such surrounding characters in the language being used. This process will be described in detail later.

After post-processor 130 has chosen a best-fit character 1 0 from the 10 possible characters, post-processor 130 outputs the best-fit character (step 270). In the preferred embodiment shown in FIG. 1, the best-fit character is output to digitiizing display 110 and displayed to the user.

The flow chart of FIG. 3 shows a preferred embodiment of 1 5 the post-processing method and is described in conjunction with the preferred embodiment of FIG. 1. After character recognizer 120 has performed the character recognition process to generate the list of number of possible characters (steps 300 and 310 of FIG. 3) (as taught earlier, the preferred embodiment uses 10 possible characters), a user must determine if the character recognition output is to be further processed (step 320). The choice made by the user is represented in FIG. 1 as switch 160.

There may be circumstances where the added accuracy of the post-processor 130 is not needed. Under these circumstances, a user may choose to use only the character recognizer 120 output.

If the user chooses not to further process the output of character recognizer 120, the top prioritized possible character 3 0 is chosen as the best-fit character (step 325) and output to the digitizing display 110 of the preferred embodiment (step 380).

Choosing the top prioritized possible character as the best-fit character simply means that no further processing is chosen and character recognizer 120 operates in a conventional -8manner with the output (top priotized possible character) sent directly to the digitizing display 110.

If the user determines that additional processing, and additional accuracy of post-processor 130, is needed, the number of possible characters are passed to language model processor 140 which includes combiner 142, scoring device 144, and language model library 145. Language model processor 140 compares each of the possible characters from character recognizer 120 with surrounding characters to determine the probability that the possible character could be in combination with the surrounding characters. The surrounding characters are usually previous characters which have been already been recognized which are stored by the computing device (Surrounding Characters 141), but may also be numbers, indications of the beginning of a sentence or word, words from a different language (such as English company names used while writing Chinese characters), etc. The surrounding characters may also be characters which have not been recognized, such as a character subsequent in sequence to the handwritten character currently being recognized. The present invention looks to any information surrounding the handwritten character which is stored in surrounding characters 141, since the surrounding information will always have some information that assists in the language model process of language model processor 140. Generally, the previous adjacent recognized character which has been correctly recognized will be the surrounding character compared with the possible characters in language model processor 140.

FIG. 4, illustrates the language model post-processing method using an example of two letters. In the example, two letters are assumed to have been input as handwritten characters. The first character in slot b will be assumed to have been processed previously and correctly by character recognizer 100 and confirmed as the letter The second character in slot a is the character to be recognized. As W:\mary\NODELETEI22168-97.doc WO 97/33249 PCTIUS97/04349 explained above, character recognizer 120 generates a number of possible characters, which for the preferred embodiment is possible characters, listed in FIG. 4 as al to an where n is (column 400). These template characters are then combined in combiner 142 (step 330 of FIG. 3) with, in the preferred embodiment, the previous correctly recognized adjacent handwritten character of slot b, or the letter The result is the combination of the letter in slot b, or in this example with each of the possible characters al through an (column 410).

The combinations of slot b with al through an are received in scoring device 144 of FIG. 1. Scoring device 144 obtains from language model library 145, for each of the combinations, a predetermined probability (combined score) that the adjacent character in slot b, will be combined with the number of possible characters al through an. Next, each of the combinations are assigned their respective combined score (step 340 and column 420). For instance, if character recognizer 120 determined al to be and the letter in slot b was already determined to be the probability that these two letters would be combined in sequence would be very high since and are combined in sequence in many different words. The combined score representing this probability found in language model library 145 would be high and an appropriate combined score would be assigned to "ha" If the letters were, for instance, an and b the probability that the two letters are combined, based upon common English words, is very low. In another language the probability may be higher. Language model library 145 is designed for specific uses and languages. The low combined score reflecting this unusual combination might be close to zero, or even zero if the probability is so low that the combination is not included in the language model library 145. This combined score would be then assigned to the combination "mz".

10 In the above example, each of the number of possible characters are combined with the previous adjacent charavter.

In fact, any combination of surrounding characters are contemplated in the present invention. The above example using the previous adjacent character in the language model process is a preferred embodiment.

Referring again to figures 1, 3, and 4, resorter 150 obtains the combined scores from scoring device 144, generates an order from the combined scores, and resorts the number of possible characters based upon that order. Specifically, a weighting element 152 of resorter 150 weights each of the combined scores from the scoring device 144 with the score of its corresponding number of possible characters to determine a weighted score for each of the number of possible characters (step 350). The weighting is calculated for each of the number of possible characters by: multiplying the score (see previous discussion with respect to step 220 of FIG. 2) from the character recognizer 120 with a first weighting factor XCR to obtain a weighted possible character score, (ii) multiplying the corresponding combined score with a second weighting factor XLM to obtain a weighted combined character score, and (iii) combining the two scores to obtain a weighted score for each of the number of possible characters (column 430 of FIG. The equation is: STOTan XCR SCRan XLM SLMan.

In the preferred embodiment, XCR and XLM combined equal 1. Further, at optimum values for the weighting factors, -CR is greater than LM, and XLM is equal to 0.33. A user may choose a value for -LM which is greater than or less than the optimum value, depending upon the desired output, and the choice may be input manually into weighting element 152.

Reorderer 154 of resorter 150 receives the weighted scores from weighting element 152 and orders the weighted scores. In the preferred embodiment, the weighted scores are ordered from highest to lowest. This WO 97/33249 PCT/US97/04349 determined order is used to resort the number of possible characters. Reorderer 154 then resorts the number of possible characters according to the order it just determined, and chooses the best-fit character from the reordered number of possible characters (steps 360 and 370). The best-fit character is then output (step 380).

Post-processing of the output of character recognizers is necessary in order to improve the rate of accuracy of selecting a single possible character representing an input handwritten character. Without the additional accuracy of post-processing, character recognizers will probably not become commercially viable. By using the language modeling process of the present invention, the probability of selecting a single possible character which is the same as a handwritten character increases from roughly 84% to approximately 90 to 92 percent.

This recognition accuracy brings handwriting recognition into an acceptable range for consumer use.

Claims

1. A method of handwritten character recognition including the steps of: receiving a first input representative of a handwritten character and a second input representation of an adjacent character; comparing the first input with each template of a template character set; selecting from the template character set a plurality of template characters which are likely to resemble the handwritten character to provide a subset of candidate characters, each of the candidate characters having a value representing a degree of similarity with the handwritten character; and processing the candidate characters according to a language model by comparing each candidate character with the adjacent character to determine a predetermined probability in a given language that the candidate character could be in combination with the adjacent character, thereby to determine which of the candidate characters is most likely to be the handwritten character.

2. A method according to claim 1 wherein the step of processing the candidate characters according to a language model includes: combining each of the candidate characters with a surrounding character to form combined characters; assigning a combined value to each of the combined characters where the combined value represents a probability that the surrounding character would be in combination with a respective one of the candidate characters; and sorting the candidate characters.

3. A method according to claim 2 where the step of sorting the candidate characters includes: weighting the values for the candidate characters taking into account the combined values; and ordering the candidate characters in a sequential order according to their weighted values. S4. A method according to claim 3 where the step of weighting the value for each of the candidate characters against a corresponding of the combined rl- W:\mary\NODE LETE\22168-97.doc -13- value of the combined characters to determine a weighted value for each of the candidate characters includes: multiplying the score for each of the candidate characters by a first weighting factor to obtain weighted candidate character values; multiplying the combined value for each of the combined characters with a second weighting factor to obtain weighted combined character values; and combining each of the weighted candidate character values with the weighted combined character values to obtain the weighted value for each of the candidate characters. A method according to any one of claims 2 to 4 wherein the step of assigning a combined value to each of the combined characters includes obtaining from a language model library the combined value.

6. A method according to any one of the preceding claims wherein the step of processing the candidate characters comprises: comparing each of the candidate characters with a surrounding character to determine a probability that the surrounding character would be in combination with a respective one of the candidate characters; and determining from the probability for each of the candidate characters which of the candidate characters is most likely to be the handwritten character.

7. A method according to claim 6 wherein the step of comparing each of the number of template characters with a surrounding character includes: combining each of the candidate characters with a surrounding character to form combined characters; and assigning a combined value to each of the combined characters where the combined value represents the probability that the surrounding character would be in combination with the respective one of the candidate characters.

8. A method according to claim 6 or 7 where the step of comparing each of the number of template characters with a surrounding character to determine a probability includes obtaining the probability from a language model look-up ,A ble. -14-

9. A handwriting recognizer including: a character recognizer coupled to a handwriting input device, to choose a number of template characters from a template character set which are likely to resemble a handwritten character to provide a subset of candidate characters, each of the candidate characters having a value representing a degree of similarity with the handwritten character; a post-processor coupled to the character recognizer to process the candidate characters according to a language model by comparing each candidate character with an adjacent character to determine a predetermined probability in a given language that the candidate character could be in combination with the adjacent chamber, thereby to determine which of the candidate characters is most likely to be the handwritten character; and a display device coupled to the post-processor to receive the one of the candidate characters which is most likely to be the handwritten character. A handwriting recognizer according to claim 9 wherein the character recognizer is coupled to a template character set to receive from the template character set the candidate characters and to assign the value to each of the candidate characters.

11. A handwriting recognizer according to claim 10 wherein the post- processor includes: a combiner coupled to the character recognizer to combine each of the candidate characters with a surrounding pre-recognized character to form combined characters; a scoring device coupled to the combiner to assign a combined value to each of the combined characters where the combined value represents a probability that the surrounding pre-recognized character would be in combination with a respective one of the candidate characters; and a sorter coupled to the scoring device to sort the candidate characters according to a sequential order determined by the combined values for the combined characters. CL W:\mary\NODELETE\22168-97.doC T u

12. A handwriting recognizer according to claim 11 wherein the sorter includes: a weighting element coupled to the scoring device to weight the values for the candidate characters taking into account the combined values; and a reorderer coupled to the weighting element to reorder the candidate characters according to a sequential order of the weighted values of the candidate characters; wherein the reorderer is coupled to the display device to output the candidate character most likely to resemble the handwritten character.

13. A handwriting recognizer according to claim 11 or 12 wherein the scoring device is coupled to a language model library to obtain the combined value.

14. A handwriting recognizer according to any one of claims 9 to 13 wherein the handwriting input device and the display device are a single digitizing tablet. A method of handwritten character recognition substantially as herein described with reference to the accompanying drawings.

16. A handwriting recognizer substantially as herein described with reference to the accompanying drawings. DATED: 22 September, 2000 PHILLIPS ORMONDE FITZPATRICK Patent Attorneys for: MOTOROLA, INC. .Q2a4w W:\maryIODELETE22168-97.doc