Fast spatial segmenter for handwritten characters

• US 5,001,765 A
• Filed: 09/06/1990
• Issued: 03/19/1991
• Est. Priority Date: 01/05/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jeanty, Henry H.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US07/579,102
• Time in Patent Office: 194 Days
• US Class Current: 382/179
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/15 Cutting or merging image elements, e.g. region growing, watershed or clustering-based techniques
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction
• CPC Class Codes: G06V 30/36 Matching; Classification

Abstract

A character recognition system 10 includes a segmentation processor 12 which is coupled between an electronic tablet 14 and a character recognizer 18. The tablet 14 has an associated stylus or pen 15 with which a user forms symbols, such as block printing or script characters, on a surface of the tablet 14. The tablet 14 has x-axis and y-axis output signals expressive of the position of the pen 15 within an x-y tablet coordinate system. A stroke capture device 16 intercepts the x-y outputs from the tablet to generate x-y position pair data for the segmentation processor 12. An output of the segmentation processor 12 is data expressive of connected strokes and unconnected strokes which is input to the character recognizer 18. The segmentation method and apparatus segments real-time handwriting outputs from the electronic tablet by a recursive method which rapidly locates a general area in which two strokes might intersect by successively finding intersections of maximal areas or boxes associated with the strokes until an exit condition is determined.

Claims

1. A segmentation processor for handwritten symbols, the processor being coupled to output signals of a writing stylus, tablet and data generation means which provide data indicating x-axis and y-axis displacements of points associated with a stroke of the stylus relative to a surface of the tablet;

the processor comprising;

means for identifying maximum and minimum x-axis and y-axis coordinates of a set of points associated with the stroke of the stylus;

means for determining the x-axis and y-axis coordinates of an area within which the identified maximum and minimum x-axis and y-axis coordinates associated with an individual stroke are contained, the area having a length along the y-axis and a width along the x-axis; and

means for processing a first area associated with a first stroke and a second area associated with a second stroke to determine if the first stroke and the second stroke are physically or logically connected one to another and form all of or a portion of a discrete handwritten character or symbol.

2. A segmentation processor as set forth in claim 1 wherein the means for processing comprises means for determining the x-axis and the y-axis coordinates of a region of intersection of the first and the second areas.

3. A segmentation processor for handwritten symbols, the processor being coupled to output signals of a writing stylus, tablet and data generation means which provide data indicating x-axis and y-axis displacements of points associated with a stroke of the stylus relative to a surface of the tablet;

the processor comprising;

means for identifying maximum and minimum x-axis and y-axis coordinates of a set of points associated with the stroke of the stylus;

means for determining the x-axis and y-axis coordinates of an area within which the identified maximum and minimum x-axis and y-axis coordinates associated with an individual stroke are contained, the area having a length along the y-axis and a width along the x-axis; and

means for processing a first area associated with a first stroke and a second area associated with a second stroke to determine if the first stroke and the second stroke are physically or logically connected on to another;

wherein

the means for processing comprises means for determining the x-axis and the y-axis coordinates of a region of intersection of the first and the second area; and

wherein the means for processing further comprises means for determining if the first area and the second area mutually and totally cross one another along the x-axis and along the y-axis.

4. A segmentation processor as set forth in claim 3 wherein the means for processing further comprises means for extending both the first and the second areas by at least a first predetermined amount along the y-axis and by at least a second predetermined amount along the x-axis.

5. A segmentation processor as set forth in claim 4 wherein the first predetermined amount is substantially equal to the second predetermined amount.

6. A segmentation processor as set forth in claim 4 wherein the first predetermined amount is substantially equal to approximately 50% of the length of the area along the y-axis and wherein the second predetermined amount is substantially equal to approximately 15% to approximately 20% of the width of the area along the x-axis.

7. A segmentation processor as set forth in claim 4 wherein the means for processing further comprises means for determining if an area of a region of intersection between the first and the second areas is substantially coincident to each of the first and the second areas.

8. A segmentation processor as set forth in claim 7 wherein the means for processing further comprises means for determining a substroke of the stroke associated with the first area and a substroke of the stroke associated with the second area, each of the substrokes having at least one point having x-axis and y-axis coordinates which are contained within the area of the region of intersection.

9. In a recognition system for recognizing handwritten symbols, the system including a writing stylus, a tablet and data generation means for providing data indicating x-axis and y-axis displacements of points associated with a stroke of the stylus relative to a surface of the tablet, a method of segmenting strokes into symbols such as characters comprising the steps of:

identifying maximum and minimum x-axis and y-axis coordinates of individual ones of a set of points associated with the stroke of the stylus;

determining the x-axis and y-axis coordinates of a block area within which the identified maximum and minimum x-axis and y-axis coordinates associated with the stroke are contained; and

processing a first block area associated with a first stroke and a second block area associated with a second stroke to determine if the first and the second strokes are physically or logically connected one to another, wherein the step of processing includes a step of determining if the first block area intersects at least a portion of the second block area, and wherein the step of processing further includes a step of;

determining if the block areas associated with the first stroke and the second stroke mutually and totally cross one another along the x-axis and the y-axis; and

if the block areas are so determined to mutually and totally cross one another,

indicating that the first and the second stroke are connected one to another.

10. A method as set forth in claim 9 wherein the step of determining if the block area mutually and totally cross further includes the initial steps of extending one of the block areas at least along the y-axis by a first predetermined amount and extending the other one of the block area at least along the x-axis by a second predetermined amount.

11. A method as set forth in claim 10 wherein the first predetermined amount is substantially equal to the second predetermined amount.

12. A method as set forth in claim 10 wherein the first predetermined amount is substantially equal to approximately 50% of a length of the block area along the y-axis and wherein the second predetermined amount is substantially equal to approximately 15% to approximately 20% of a width of the block area along the x-axis.

13. A method as set forth in claim 10 wherein the step of processing further includes a step of determining if an area of the region of intersection is substantially coincident with each of the first and the second block areas and, if the area of the region of intersection is determined to be substantially coincident with the area of each of the first and the second block areas, indicating that the two strokes associated with the two block areas are connected.

14. A method as set forth in claim 13 wherein, if the area of the region of intersection is determined not to be substantially equal to the area of each of the first and the second block areas, the step of processing further includes a step of determining a substroke of the stroke associated with the first block area and a substroke of the stroke associated with the second block area, each of the substrokes being determined to have at least one point having x-axis and y-axis coordinates which are contained within the area of the region of intersection.

15. In a recognition system for recognizing handwritten symbols, the system including a writing stylus, a tablet and data generation means for providing data indicating x-axis and y-axis displacements of points associated with a stroke of the stylus relative to a surface of the tablet, a method of segmenting strokes into characters comprising the steps of:

(a) indicating maximum and minimum x-axis and y-axis coordinates of individual ones of a set of points associated with the stroke of the stylus;

(b) determining the x-axis and the y-axis coordinates of a block area within which the indicated maximum and minimum x-axis and y-axis coordinates are contained; and

(c) processing a first block area associated with a first stroke and a second block area associated with a second stroke to determine if the first and the second strokes are physically or logically connected one to another, wherein the step of processing includes the steps of;

(d) extending the first block area at least along the y-axis by a first predetermined amount and extending the second block area at least along the x-axis by a second predetermined amount;

(e) determining if the first and the second block areas mutually and totally cross one another along the x-axis and the y-axis; and

if the block areas are so determined to mutually and totally cross one another,

(f) indicating that the first stroke and the second stroke are connected one to another;

if the block areas are determined to not mutually and totally cross one another,

(g) extending the first block area at least along the x-axis by a first predetermined amount and extending the second block area at least along the y-axis by a second predetermined amount;

(h) determining if the first and the second block areas mutually and totally cross one another along the x-axis and the y-axis; and

if the block areas are so determined to mutually and totally cross one another,

(i) indicating that the first stroke and the second stroke are connected one to another;

if the block areas are determined to not mutually and totally cross one another,

(j) determining if the two extended block areas share an area of intersection; and

if the two extended block areas do not share an area of intersection,

(k) indicating that the two strokes are disconnected one from the other;

if the two extended block areas do share an area of intersection,

(l) determining a first substroke of the stroke associated with the first block area and a second substroke of the stroke associated with the second block area, each of the substrokes having at least one point having x-axis and y-axis coordinates which are contained within the area of intersection; and

if neither the first stroke and/or the second stroke have a substroke within the area of intersection,

(m) indicating that the two strokes are disconnected and terminating the steps of the method;

else

(n) determining the x-axis and the y-axis coordinates of a first block area associated with the first substroke and the x-axis and y-axis coordinates of a second block area associated with the second substroke; and

(o) repetitively executing steps (d) through (n) utilizing the block areas associated with the substrokes until the first and the second strokes are determined to be either connected to one another or unconnected from one another.

16. A method as set forth in claim 15 wherein, subsequent to the execution of step (j) and if the two extended block areas do share an area of intersection, further includes the steps of:

determining if the area of intersection is substantially coincident with the area of each of the first and the second extended block areas; and

if the area of intersection is determined to be substantially coincident to the area of each of the first and the second extended block areas, indicating that the first stroke and the second stroke are connected one to another.

17. A method as set forth in claim 15 wherein steps (1) through (n) are replaced by the steps of:

(1) determining a first substroke, if any, of the stroke associated with the first block area, the first substroke having at least one point having x-axis and y-axis coordinates which are contained within the area of intersection;

(m) determining the x-axis and the y-axis coordinates of a block area associated with the first substroke;

(n) determining a second substroke, if any, of the stroke associated with the second block area, the second substroke having at least one point having x-axis and y-axis coordinates which are contained within the block area associated with the first substroke;

if a second substroke is determined not to have at least one point within the block area of the first substroke

indicating that the two strokes are not connected, otherwise

(o) determining the x-axis and the y-axis coordinates of a block area associated with the second substroke, and;

(p) repetitively executing steps (d) through (o) until the first and the second strokes are determined to be either connected to one another or unconnected from one another.