# US 2010/0166314 A1 · Segment Sequence-Based Handwritten Expression Recognition > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2010/0166314 A1 - Document ID: US20100166314A1 - Status: Published application - Kind: A1 - Application number: 12/346,376 - Filed: 2008-12-30 - Published: 2010-07-01 - Earliest claimed: 2008-12-30 - Assignees: Microsoft Corporation - Inventors: Yu Shi; Frank Kao-Ping Soong - Web page: https://patentgrep.com/patent/US20100166314A1 ## CPC - G06V 30/36: {Matching; Classification} - G06F 18/29: {Graphical models, e.g. Bayesian networks} - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods and apparatuses for generating, by a computing device configured to interpret a handwritten expression, a symbol graph to represent strokes associated with the handwritten expression, are described herein. The symbol graph may include nodes, each node corresponding to a combination of a stroke and a candidate symbol for that stroke. The computing device may also generate a segment graph based on the symbol graph by combining nodes associated with a same stroke if strokes of their preceding nodes are the same. Also the computing device may perform a structure analysis on at least a subset of segment sequences represented by the segment graph to determine hypotheses for the handwritten expression. In other embodiments, rather than generate a segment graph, the computing device may determine segment sequences by selecting a number of symbol sequences from the symbol graph and combining symbol sequences having the same segmentation. ## Claims ### Claim 1 A method comprising: generating, by a computing device configured to interpret a handwritten expression, a symbol graph to represent a plurality of strokes associated with the handwritten expression, the symbol graph including a plurality of nodes, each node corresponding to a combination of a stroke and a candidate symbol for that stroke; generating, by the computing device, a segment graph based on the symbol graph by combining nodes associated with a same stroke if strokes of their preceding nodes are the same; and performing, by the computing device, a structure analysis on at least a subset of a plurality of segment sequences represented by the segment graph to determine a set of hypotheses for the handwritten expression. ### Claim 2 (depends on 1) The method of claim 1 further comprising performing a tree search on the symbol graph to score symbol sequences comprised of the nodes. ### Claim 3 (depends on 2) The method of claim 2 further comprising generating a segment score by determining a max score of the nodes combined to create the segment. ### Claim 4 (depends on 1) The method of claim 1, wherein the combining further comprises adding a candidate symbol associated with one node as an attribute of another node with which the one node is being combined. ### Claim 5 (depends on 4) The method of claim 4 further comprising deleting the one node and its incoming and outgoing edges after the adding. ### Claim 6 (depends on 4) The method of claim 4, wherein the one node has a lower score than the other node. ### Claim 7 (depends on 1) The method of claim 1 further comprising performing trigram rescoring on symbol sequences of the symbol graph. ### Claim 8 (depends on 1) The method of claim 1, wherein the subset of the segment sequences are the sequences having the highest scores. ### Claim 9 (depends on 1) The method of claim 1, wherein each symbol node comprises a candidate symbol, a relation of the candidate symbol to a candidate symbol of a predecessor node, and an indication of which stroke of the plurality of strokes the candidate symbol is proposed for. ### Claim 10 (depends on 1) The method of claim 1, wherein each segment comprises a candidate symbol, a relation of the candidate symbol to a candidate symbol of a predecessor segment, an indication of which stroke of the plurality of strokes the candidate symbol is proposed for, and a list of one or more alternative candidate symbols. ### Claim 11 A computer-readable medium having computer-executable instructions that, when executed on one or more processors, perform operations comprising: generating a symbol graph to represent a plurality of strokes associated with a handwritten expression, the symbol graph including a plurality of nodes, each node corresponding to a combination of a stroke and a candidate symbol for that stroke; determining a plurality of segment sequences by selecting a number of symbol sequences from the symbol graph and combining symbol sequences having a same segmentation; and performing a structure analysis on at least a subset of the segment sequences to determine a set of hypotheses for the handwritten expression. ### Claim 12 (depends on 11) The computer-readable medium of claim 11, wherein the computer-executable instructions perform operations further comprising performing a tree search on the symbol graph to score symbol sequences comprised of the nodes. ### Claim 13 (depends on 12) The computer-readable medium of claim 12, wherein the selected symbol sequences are the symbol sequences having the highest scores. ### Claim 14 (depends on 12) The computer-readable medium of claim 12, wherein the computer-executable instructions perform operations further comprising deleting a number of symbol sequences having the lowest scores. ### Claim 15 (depends on 11) The computer-readable medium of claim 11, wherein the determining further comprises selecting a subset of the selected symbol sequences until a predetermined number of segmentations is reached. ### Claim 16 (depends on 11) The computer-readable medium of claim 11, wherein the combining further comprises adding candidate symbols of a first symbol sequence as attributes of nodes of a second symbol sequence, each candidate symbol added to a node associated with a same stroke as the candidate symbol. ### Claim 17 (depends on 11) The computer-readable medium of claim 11, wherein each segment comprises a candidate symbol, a relation of the candidate symbol to a candidate symbol of a predecessor segment, an indication of which stroke of the plurality of strokes the candidate symbol is proposed for, and a list of one or more alternative candidate symbols. ### Claim 18 A tablet personal computer comprising: a processor; an input mechanism configured to receive a handwritten expression; and a plurality of executable instructions configured to be operated by the processor and to program the computing device to: generate a symbol graph to represent a plurality of strokes associated with a handwritten expression, the symbol graph including a plurality of nodes, each node corresponding to a combination of a stroke and a candidate symbol for that stroke; perform a tree search on the symbol graph to score symbol sequences comprised of the nodes; generate a segment graph based on the symbol graph by combining nodes associated with a same stroke if strokes of their preceding nodes are the same, the combining including adding a candidate symbol associated with one node as an attribute of another node with which the one node is being combined and deleting the one node and its incoming and outgoing edges after the adding; and perform a structure analysis on at least a subset of a plurality of segment sequences represented by the segment graph to determine a set of hypotheses for the handwritten expression, wherein the subset of the segment sequences are the sequences having the highest scores. ### Claim 19 (depends on 18) The tablet personal computer of claim 18 wherein the plurality of executable instructions are further configured to program the computing device to generate a segment score by determining the max score of the nodes combined to create the segment. ### Claim 20 (depends on 18) The tablet personal computer of claim 18 wherein the plurality of executable instructions are further configured to program the computing device to perform trigram rescoring on symbol sequences of the symbol graph.