Spatial sorting and formatting for handwriting recognition

• US 6,603,881 B2
• Filed: 10/23/2001
• Issued: 08/05/2003
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ratzlaff, Eugene H., Perrone, Michael P.
• Primary Examiner(s): Mariam, Daniel G.
• Application Number:
  US10/047,152
• Publication Number:
  US 20020097909A1
• Time in Patent Office: 651 Days
• Field of Search: 382/179, 382/151, 382/181, 382/185-187, 382/189, 382/202, 382/224, 382/225, 382/287, 382/291, 382/310, 382/313, 345/661, 345/662, 345/700, 345/702
• US Class Current: 382/186
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

Systems and methods for reordering unconstrained handwriting data using both spatial and temporal interrelationships prior to recognition, and for spatially organizing and formatting machine recognized transcription results. The present invention allows a machine recognizer to generate and present a full and accurate transcription of unconstrained handwriting in its correct spatial context such that the transcription output can appear to “mirror” the corresponding handwriting.

Claims

1. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for spatially formatting recognition results of handwriting data, wherein the handwriting data comprises a set of strokes, each stroke comprising a set of x-y coordinates, the method steps comprising:

determining bounding region information for unconstrained handwriting data based on x-y coordinates associated with the unconstrained handwriting data;

generating recognition results for the unconstrained handwriting data, the recognition results comprising recognized text corresponding to the unconstrained handwriting data; and

spatially formatting the recognition results, wherein the step of spatially formatting the recognition results comprises positioning the recognized text on a display page in substantially a same proximate spatial location as the corresponding unconstrained handwriting data is located on an ink page using the bounding region information for the corresponding unconstrained handwriting data.

2. The program storage device of claim 1, further including instructions for performing the step of resolving collisions between recognized text on the display page.

3. The program storage device of claim 2, wherein the instructions for performing the step of resolving collisions between recognized text on the display page include instructions for:

receiving each line of the display page having recognized words positioned therein; and

iteratively processing each word starting at a beginning of the line and moving any current word which overlaps in text with any previously processed word in a desired direction until there is no text overlap.

4. The program storage device of claim 2, wherein the instructions for performing the step of resolving collisions between recognized text on the display page include instructions for:

selecting a font size of the recognized text such that the recognized text fits in the bounding region of the corresponding handwriting data; and

placing the recognized text on the display page based on the bounding region location.

5. The program storage device of claim 1, further including instructions for performing the step of adjusting white spaces on the display page.

6. The program storage device of claim 1, wherein the instructions for performing the positioning step include instruction for:

selecting a grid for the display page, the grid comprising grid coordinates; and

mapping the recognized text to the grid by placing the recognized text at a grid coordinate that corresponds to a reference coordinate of the bounding region of the corresponding handwriting-data.

7. The program storage device of claim 6, wherein the instructions for performing the step of selecting a grid includes instructions for one of automatically selecting a default grid and prompting a user to select a grid.

8. The program storage device of claim 6, further including instructions for performing the steps of:

detecting a percentage of text overlap on the grid after the mapping step;

comparing the detected percentage to a predefined threshold value; and

adjusting the resolution of the grid coordinates if the detected percentage falls below the predefined threshold value.

9. The program storage device of claim 1, wherein the instructions for performing the positioning step include instruction for:

sorting the recognition results in a desired order based on a first reference coordinate of the bounding regions of the corresponding handwriting data;

building a line for each group of spatially related recognition results in the sorted order based on the bounding region information; and

mapping the lines to a grid comprising grid coordinates.

10. The program storage device of claim 9, wherein the instructions for the mapping step include instructions for:

selecting a grid line having a coordinate which corresponds to an average of the first reference coordinates of the bounding regions associated with the built line; and

aligning the recognition results on the grid line based on a second reference coordinate of the bounding regions associated with the built line.

11. The program storage device of claim 9, wherein the instructions for performing the line building step include instructions for:

(a) selecting a group of unprocessed bounding regions such that each unprocessed bounding region in the group overlaps with at least one other bounding region in the group in the direction that corresponds to the sorting order;

(b) building a line from the recognition results corresponding to the selected group of bounding regions;

(c) marking each of the bounding regions in the group as processed; and

(d) repeating steps (a)-(c) until all bounding regions have been processed.

12. The program storage device of claim 9, wherein the instructions for performing the line building step include instructions for:

(a) selecting a desired unprocessed bounding region as a reference bounding region;

(b) selecting all unprocessed bounding regions which overlap with the reference bounding region in the direction that corresponds to the sorting order;

(c) building a line from the recognition results corresponding to the selected bounding regions;

(d) marking the selected bounding regions as processed; and

(e) repeating steps (a) through (d) until all bounding regions have been processed.

13. The program storage device of claim 1, further including instructions for:

tracking a recognition state comprising previous recognition results for each recorded page of handwriting data; and

merging current recognition results with a corresponding recognition state to produce the recognition results that are processed for display.

14. The program storage device of claim 13, wherein the instructions for performing the merging step include instructions for:

comparing the current recognition results with the corresponding recognition state; and

replacing any previous recognition results of the recognition state with the current recognition results which align to the same handwriting data.

15. A system for spatially formatting recognition results of handwriting data, wherein the handwriting data comprises a set of strokes, each stroke comprising a set of x-y coordinates, the system comprising:

means for determining bounding region information for unconstrained handwriting data based on x-y coordinates associated with the unconstrained handwriting data;

means for generating recognition results for the unconstrained handwriting data, the recognition results comprising recognized text corresponding to the unconstrained handwriting data; and

means for spatially formatting the recognition results, wherein the means for spatially formatting the recognition results comprises means for positioning the recognized text on a display page in substantially a same proximate spatial location as the corresponding unconstrained handwriting data is located on an ink page using the bounding region information for the corresponding unconstrained handwriting data.

16. The system of claim 15, further comprising means for resolving collisions between recognized text on the display page.

17. The system of claim 16, wherein the means for resolving collisions comprises:

means for selecting each line of the display page having recognized words positioned therein; and

means for iteratively processing each word of each line starting at a beginning of the line and moving any current word which overlaps in text with any previously processed word in a desired direction until there is no text overlap.

18. The system of claim 16, wherein the means for resolving collisions comprises:

means for selecting a font size of the recognized text such that the recognized text fits in the bounding region of the corresponding handwriting data; and

means for placing the recognized text on the display page based on the bounding region location.

19. The system of claim 15, further comprising means for adjusting white spaces on the display page.

20. The system of claim 15, wherein the means for positioning comprises:

means for selecting a grid for the display page, the grid comprising grid coordinates; and

means for mapping the recognized text to the grid by placing the recognized text at a grid coordinate that corresponds to a reference coordinate of the bounding region of the corresponding handwriting data.

21. The system of claim 20, further comprising:

means for detecting a percentage of text overlap on the grid after the mapping step;

means for comparing the detected percentage to a predefined threshold value; and

means for adjusting the resolution of the grid coordinates if the detected percentage falls below the predefined threshold value.

22. The system of claim 15, wherein the positioning means comprises:

means for sorting the recognition results in a desired order based on a first reference coordinate of the bounding regions of the corresponding handwriting data;

means for building a line for each group of spatially related recognition results in the sorted order based on the bounding region information; and

means for mapping the lines to a grid comprising grid coordinates.

23. The system of claim 22, wherein the mapping means comprises:

means for selecting a grid line having a coordinate which corresponds to an average of the first reference coordinates of the bounding regions associated with the built line; and

means for aligning the recognition results on the grid line based on a second reference coordinate of the bounding regions associated with the built line.

24. The system of claim 15, further comprising:

means for tracking a recognition state comprising previous recognition results for each recorded page of handwriting data; and

means for merging current recognition results with a corresponding recognition state to produce the recognition results that are processed for display.

25. The system of claim 24, wherein the merging means comprises:

means for comparing the current recognition results with the corresponding recognition state; and

means for replacing any previous recognition results of the recognition state with the current recognition results which align to the same handwriting data.

26. A method for spatially formatting recognition results of handwriting data, wherein the handwriting data comprises a set of strokes, each stroke comprising a set of x-y coordinates, the method comprising the steps of:

determining bounding region information for unconstrained handwriting data based on x-y coordinates associated with the unconstrained handwriting data;

generating recognition results for the unconstrained handwriting data, the recognition results comprising recognized text corresponding to the unconstrained handwriting data; and

spatially formatting the recognition results, wherein the step of spatially formatting the recognition results comprises positioning the recognized text on a display page in substantially a same proximate spatial location as the corresponding unconstrained handwriting data is located on an ink page using the bounding region information for the corresponding unconstrained handwriting data.