Spatial sorting and formatting for handwriting recognition

• US 6,333,994 B1
• Filed: 03/31/1999
• Issued: 12/25/2001
• 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): Boudreau, Leo
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/282,818
• Time in Patent Office: 1,000 Days
• Field of Search: 382/179, 382/181, 382/185, 382/186, 382/187, 382/189, 382/225, 382/314, 382/202, 382/226, 345/161, 345/167
• 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 sorting handwriting data, the method steps comprising:

receiving unconstrained handwriting data comprising a set of strokes, each stroke comprising a set of x-y coordinates associated therewith;

determining a bounding region for each stroke;

clustering the strokes into groups of spatially-related strokes based on the bounding region information;

wherein the clustering step include instructions for clustering the strokes into single line (SL) groups; and

ordering the clustered groups.

2. The program storage device of claim 1, wherein the SL groups are ordered in accordance with recognition requirements.

3. The program storage device of claim 1, wherein the instructions for performing the step of clustering the strokes into SL groups include instructions for performing the steps of:

merging individual strokes into forward projection (FP) groups such that the strokes comprising each FP group have bounding regions which overlap in a desired direction by a predetermined threshold; and

iteratively merging the FP groups in accordance with a merging algorithm utilizing one of at least one merging variable and a plurality of merging variables to form the SL groups.

4. The program storage device of claim 3, wherein the step of merging the strokes into FP groups is further based on temporal relationships between the strokes.

5. The program storage device of claim 3, wherein the instructions for performing the step of merging individual strokes into FP groups includes instruction for:

projecting each stroke onto a desired axis;

combining strokes having overlapping projections which meet the predetermined threshold.

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

assigning descriptor evidence to each stroke, the descriptor evidence including one of x and y extrema of the stroke, stroke length, stroke width and height, estimate of a characteristic of the stroke, and a combination thereof;

estimating an overall full width at half height (FWHH) for the FP groups; and

estimating an inter-line spacing (ILS);

wherein the merging variables include one of an overlap of the bounding regions of the FP groups, nearness of a center-of-gravity of a desired axis of two FP groups with respect to the overall FWHH, the estimated ILS, temporal relationships of the strokes, spatial relationships of the strokes, an amount, size, and extent of all strokes in FP group, the descriptor evidence of the strokes, and a combination thereof.

7. The program storage device of claim 6, wherein the instructions for estimating the overall FWHH include instructions for:

projecting each FP group onto a desired axis;

generating a histogram for each projection;

estimating a peak center for each histogram;

estimating a FWHH for each histogram based on the corresponding estimated peak center; and

calculating a statistical mean of the estimated FWHH for the histograms to provide an estimate of the overall FWHH for the FP groups.

8. The program storage device of claim 1, further comprising instructions for performing the step of estimating an inter-line spacing (ILS) based on bounding region information.

9. The program storage device of claim 8, wherein the instructions for estimating the ILS include instructions for:

projecting the strokes onto a desired axis;

calculating an autocorrelation of the projection; and

evaluating the autocorrelation to determine the ILS.

10. The program storage device of claim 8, wherein the instructions for estimating the ILS include instructions for utilizing a fitting function to determine a best-fit inter-line estimate by calculating a distance to a set of hypothesized lines with varying inter-line distances, and selecting the set of hypothesized lines with the minimum distance.

11. The program storage device of claim 9, wherein the instructions for estimating the ILS further include instructions for utilizing a fitting function to determine a best-fit inter-line estimate by calculating a distance to a set of hypothesized lines with varying inter-line distances, and selecting the set of hypothesized lines with the minimum distance, wherein the fitting function estimate of the ILS is used to one of confirm and replace the ILS estimate based on the autocorrelation.

12. The program storage device of claim 1, wherein the instructions for the step of ordering the clustered groups further include instructions for reordering strokes within each clustered group based on the corresponding bounding region information.

13. The program storage device of claim 12, wherein the instructions for reordering strokes within each clustered group include instruction for:

projecting each stroke comprising a given clustered group onto a desired axis;

assigning strokes having projections that are one of overlapping and abutting into subgroups;

reordering the subgroups; and

reordering the strokes within each subgroup.

14. The program storage device of claim 13, wherein the subgroups are reordered within their corresponding clustered groups in a desired direction, and wherein the strokes within each subgroup are reordered in accordance with recognition requirements.

15. The program storage device of claim 12, further including instructions for performing the step of clustering the reordered clustered groups into phrases.

16. The program storage device of claim 15, wherein the instructions for performing the step of clustering the reordered clustered groups into phrases includes instructions for:

detecting spaces between the subgroups;

determining if the detected spaces are spaces between words;

subdividing the subgroups if the detected spaces are determined to be spaces between words.

17. A system for spatially sorting handwriting data, the handwriting data comprising a set of strokes, each stroke comprising a set of x-y coordinates, the system comprising:

means for receiving unconstrained handwriting data comprising a set of strokes, each stroke comprising a set of x-y coordinates associated therewith;

means for determining bounding region information for each stroke;

means for clustering the strokes into groups of spatially-related strokes based on the bounding region information, wherein the clustering means comprises means for clustering the strokes into single line (SL) groups; and

means for ordering the clustered groups.

18. The system of claim 17, wherein the SL, groups are ordered in accordance with recognition requirements.

19. The system of claim 17, wherein the means for clustering the strokes into SL groups comprises:

means for merging individual strokes into forward projection (FP) groups such that the strokes comprising each FP group have bounding regions which overlap in a desired direction by a predetermined threshold; and

means for iteratively merging the FP groups in accordance with a merging algorithm utilizing one of at least one merging variable and a plurality of merging variables to form the SL groups.

20. The system of claim 19, wherein temporal relationships between the strokes is considered in merging the strokes into FP groups.

21. The system of claim 19, wherein the means for merging individual strokes into FP groups comprises:

means for projecting each stroke onto a desired axis; and

means for combining strokes having overlapping projections which meet the predetermined threshold.

22. The system of claim 19, further comprising:

means for assigning descriptor evidence to each stroke, the descriptor evidence including one of x and y extrema of the stroke, stroke length, stroke width and height, estimate of a characteristic of the stroke, and a combination thereof;

means for estimating an overall full width at half height (FWHH) for the FP groups; and

wherein the merging variables include one of an overlap of the bounding regions of the FP groups, nearness of a center-of-gravity of a desired axis of two FP groups with respect to the overall FWHH, the estimated ILS, temporal relationships of the strokes, spatial relationships of the strokes, an amount, size, and extent of all strokes in FP group, the descriptor evidence of the strokes, and a combination thereof.

23. The system of claim 22, wherein the means for estimating the overall FWHH comprises:

means for projecting each FP group onto a desired axis;

means for generating a histogram for each projection;

means for estimating a peak center for each histogram;

means for estimating a FWHH for each histogram based on the corresponding estimated peak center; and

means for calculating a statistical mean of the estimated FWHH for the histograms to provide an estimate of the overall FWHH for the FP groups.

24. The system of claim 17, wherein the means for ordering the clustered groups further comprises means for reordering strokes within each clustered group based on the corresponding bounding region information.

25. The system of claim 24, wherein the means for reordering strokes within each clustered group comprises:

means for projecting each stroke comprising a given clustered group onto a desired axis;

means for assigning strokes having projections that are one of overlapping and abutting into subgroups;

means for reordering subgroups; and

means for reordering the strokes within each subgroup.

26. The system of claim 25, wherein the subgroups are reordered within their corresponding clustered clustered groups in a desired direction, and wherein the strokes within each subgroup are reordered in accordance with recognition requirements.

27. The systems of claim 24, further comprising means for clustering the reordered clustered groups into phrases.

28. The system of claim 27, wherein the means for clustering the reordered clustered groups into phrases comprises:

means for detecting spaces between the subgroups;

means for determining if the detected spaces are spaces between words; and

means for subdividing the subgroups if the detected spaces are determined to be spaces between words.

29. The system of claim 17, further comprising means for estimating an inter-line spacing (ILS) based on bounding region information.

30. The system of claim 29, wherein the means for estimating the ILS comprises:

means for projecting the strokes onto a desired axis; and

means for calculating an autocorrelation of the projection and evaluating the autocorrelation to determine the ILS.

31. The system of claim 29, wherein the means for estimating the ILS comprises a fitting function determination means to determine a best-fit inter-line estimate by calculating a distance to a set of hypothesized lines with varying inter-line distances, and selecting the set of hypothesized lines with the minimum distance.

32. A handwriting recognition system, comprising:

means for storing handwriting data, the handwriting data comprising a set of strokes, each stroke comprising a set of x-y coordinates;

a recognition engine;

a system for spatially sorting handwriting data for recognition, the spatial sorting system comprising;

means for determining bounding region information for each stroke based on the x-y coordinates of the stroke;

means for clustering the strokes into groups of spatially-related strokes based on the bounding region information; and

means for ordering the ordered clustered groups to the recognition engine; and

a system for spatially formatting recognition results from the recognition engine, the spatial formatting system comprising means for position the recognized text on a display page in a proximate spatial location as the corresponding handwriting data is located on an ink page using the bounding region information for the corresponding handwriting data.

33. The handwriting recognition system of claim 32, further comprising:

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

means for merging current recognition results from the recognition engine with a corresponding recognition state to produced the recognition results that are processed by the spatial formatting system.