Grouping lines in freeform handwritten text

A computer system for processing handwriting input by organizing freeform handwriting received as strokes of electronic ink into lines of handwritten text, the computer system comprising:

• a processing unit that executes computer-readable instructions read from a computer-readable storage medium;
• a user input device that accepts data as electronic ink, wherein the user input device is connected to the processing unit through a system bus;
• and
• one or more computer-readable media readable by the processing unit and having computer-readable instructions stored thereon, the computer-readable instructions comprising:
• a stroke grouping generation module that receives electronic ink from the input device, organizes the electronic ink into an initial grouping of strokes into lines, and generates a plurality of alternate groupings of strokes into lines, wherein each of the plurality of alternate groupings is a variation of the initial grouping;
• and
• a grouping cost determination module that determines a cost of the initial grouping and of each of the plurality of alternative groupings using a global cost function, wherein:
• if the cost of the initial grouping is not greater than the cost of any of the alternative groupings, the grouping cost determination module outputs the initial grouping as lines of handwritten text to an application;
• and
• if the cost of the initial grouping is greater than at least one of the alternative groupings, the grouping cost determination module selects an alternative grouping having a lower cost than each of the other alternative groupings and provides the selected grouping to the stroke grouping generation module, which processes the selected grouping as a new initial grouping.

One or more computer storage media having computer-readable instructions embodied thereon for performing a method of partitioning freeform handwriting input into lines of handwritten text, the method comprising:

• (a) receiving freeform handwriting input, the handwriting input comprising a plurality of electronic ink strokes;
• (b) partitioning the plurality of electronic ink strokes into an initial stroke grouping, the initial stroke grouping comprising an arrangement of a plurality of initial line groups of strokes, each of the plurality of initial line groups of strokes comprising a line of handwritten text;
• (c) generating a plurality of alternate stroke groupings, each of the plurality of alternate stroke groupings comprising an alternate arrangement of one or more alternate line groups of strokes, each of the one or more alternate line groups of strokes comprising a line of handwritten text, wherein each of the plurality of alternate stroke groupings is a variation of the initial stroke grouping;
• (d) calculating a cost associated with the initial stroke grouping using a global cost function comprising at least one likelihood term, the likelihood term comprising a characteristic of the initial stroke grouping that reflects a likelihood that the initial stroke grouping is an accurate partitioning of the plurality of strokes into lines of handwritten text;
• (e) calculating a cost associated with the alternate stroke grouping using the global cost function, the likelihood term comprising a characteristic of the alternate stroke grouping that reflects a likelihood that the alternate stroke grouping is an accurate partitioning of the plurality of strokes into lines of handwritten text;
• and
• (f) determining whether the cost associated with the alternate stroke grouping is less than the cost associated with the initial stroke grouping wherein:
• (1) if the cost associated with the alternate stroke grouping is not less than the cost associated with the initial stroke grouping, the method further comprises outputting the initial stroke grouping to an application;
• and
• (2) if the cost associated with the alternate stroke grouping is less than the cost associated with the initial stroke grouping, the method further comprises repeating the steps of (c)-(f) wherein the alternate stroke grouping is substituted for the initial stroke grouping.