# US 8,542,927 B2 · Character auto-completion for online east asian handwriting input > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,542,927 B2 - Document ID: US8542927B2 - Status: Granted - Kind: B2 - Application number: 12/146,874 - Filed: 2008-06-26 - Published: 2009-12-31 - Granted: 2013-09-24 - Earliest claimed: 2008-06-26 - Assignees: Microsoft Corporation - Applicants: Peng Liu; Lei Ma; Frank Kao-Ping Soong - Inventors: Peng Liu; Lei Ma; Frank Kao-Ping Soong - Web page: https://patentgrep.com/patent/US8542927B2 ## CPC - G06F 3/018: {Input/output arrangements for oriental characters} - G06V 30/347: {Sampling; Contour coding; Stroke extraction} - G06V 30/373: {using a special pattern or subpattern alphabet} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract An exemplary method includes receiving stroke information for a partially written East Asian character, the East Asian character representable by one or more radicals; based on the stroke information, selecting a radical on a prefix tree wherein the prefix tree branches to East Asian characters as end states; identifying one or more East Asian characters as end states that correspond to the selected radical for the partially written East Asian character; and receiving user input to verify that one of the identified one or more East Asian characters is the end state for the partially written East Asian character. In such a method, the selection of a radical can occur using radical-based hidden Markov models. Various other exemplary methods, devices, systems, etc., are also disclosed. ## Claims ### Claim 1 A method, implemented by a computing device, comprising: receiving stroke information relating to a partially written East Asian character, the partially written East Asian character being composed of one or more radicals; identifying the one or more radicals contained in the partially written East Asian character via one or more trained hidden Markov models; selecting a radical in a prefix tree, wherein the prefix tree branches to East Asian characters as end states, the selecting comprising: calculating a best partial matching score between the one or more radicals contained in the partially written East Asian character and the radical in the prefix tree; and calculating a partial matching score for each character in the prefix tree based on the best partial matching score; identifying an East Asian character as an end state from the prefix tree based on the partial matching score; receiving user input to verify that the identified East Asian character is the end state for the partially written East Asian character; and replacing the received stroke information with the identified East Asian character verified by the user input. ### Claim 2 (depends on 1) The method of claim 1 further comprising displaying the identified East Asian character. ### Claim 3 (depends on 1) The method of claim 1 wherein the stroke information comprises imaginary and real stroke information and wherein the selecting comprises selecting based on the imaginary and real stroke information. ### Claim 4 (depends on 1) The method of claim 1 further comprising receiving audio information. ### Claim 5 (depends on 4) The method of claim 4 wherein the selecting a radical comprises selecting based at least in part on the received audio information. ### Claim 6 (depends on 4) The method of claim 4 wherein the identifying the East Asian character comprises identifying based at least in part on the received audio information. ### Claim 7 (depends on 1) The method of claim 1 wherein the receiving user input comprises receiving audio information. ### Claim 8 (depends on 1) The method of claim 1 wherein the selecting comprises selecting based at least in part on slope and curvature of a pen trajectory. ### Claim 9 (depends on 1) The method of claim 1 wherein the receiving stroke information and the receiving user input occurs online. ### Claim 10 (depends on 1) The method of claim 1 wherein the selecting comprises selecting based at least in part on one or more trained hidden Markov models. ### Claim 11 (depends on 1) The method of claim 1 wherein the received stroke information corresponds to a stroke order path and wherein the selecting comprises selecting based on a multi-path model. ### Claim 12 (depends on 1) The method of claim 1 wherein the identifying the East Asian character as the end state from the prefix tree comprises identifying less than all possible end states. ### Claim 13 (depends on 1) One or more tangible computer storage media encoded with computer-executable instructions that, when executed, configure a computer system to perform the method of claim 1. ### Claim 14 A computing device comprising: an input mechanism for inputting stroke information relating to a partially written East Asian character, the partially written East Asian character being composed of one or more radicals; a trained hidden Markov model for identifying the one or more radicals contained in the partially written East Asian character; a prefix tree for identifying an East Asian character based at least in part on the one or more radicals identified by the trained hidden Markov model, the prefix tree branches to East Asian characters as end states, the East Asian character being identified by: calculating a best partial matching score between the one or more radicals contained in the partially written East Asian character and a radical in the prefix tree; calculating a partial matching score for each character in the prefix tree based on the best partial matching score; and identifying the East Asian character as an end state from the prefix tree based on one or more of the partial matching scores; and a character-auto completing mechanism for replacing the stroke information with the identified East Asian character based at least in part on user input that verifies that the identified East Asian character is the end state for the partially written East Asian character. ### Claim 15 (depends on 14) The computing device of claim 14 further comprising a speech input mechanism. ### Claim 16 (depends on 1) A cell phone comprising one or more tangible computer storage media including instructions that, when executed, cause one or more processors to perform the method of claim 1. ### Claim 17 (depends on 1) The method of claim 1, the selecting further comprising initiating a depth first search (DFS). ### Claim 18 (depends on 1) The method of claim 1, the identifying the one or more radicals contained in the partially written East Asian character via one or more trained hidden Markov models further including employing a Multi-Space Probability Distribution (MSD). ### Claim 19 One or more tangible computer-readable storage media storing computer-readable instructions that, when executed, instruct one or more processors to perform operations comprising: receiving stroke information relating to a partially written East Asian character, the partially written East Asian character being composed of one or more radicals; identifying the one or more radicals contained in the partially written East Asian character via one or more trained hidden Markov models; selecting a radical in a prefix tree, wherein the prefix tree branches to East Asian characters as end states, the selecting comprising: calculating a best partial matching score between the one or more radicals contained in the partially written East Asian character and the radical in the prefix tree; and calculating a partial matching score for each character in the prefix tree based on the best partial matching score; identifying an East Asian character as an end state from the prefix tree based on one or more of the partial matching scores; receiving user input to verify that the identified East Asian character is the end state for the partially written East Asian character; and replacing the received stroke information with the identified East Asian character verified by the user input. ### Claim 20 (depends on 19) The one or more computer-readable storage media of claim 19, wherein the operations further comprise displaying the identified East Asian character.