Abstract:
A method provides for extracting features from a handwritten character which is input to an on-line input device. The on-line input device successively outputs stroke information indicating points on strokes of the handwritten character. The method includes a first step of detecting strokes of the handwritten character based on the stroke information. Thereafter, singular points are detected, based on the stroke information. Each of the singular points is defined as a pair of points on the strokes of the handwritten character which are written at different times but have substantially the same coordinates. Then, primitive sequences forming each of the strokes are obtained, and a connective relationship between each two formative sequences of each of the strokes is determined. Finally, the structure of each of the singular points is determined.

Description:
BACKGROUND OF THE INVENTION 
     (1) Field of the invention 
     The present invention generally relates to a method for extracting features from characters which is applied to a character recognition system, and more particularly to a method for extracting features from an on-line handwritten character. 
     (2) Description of related art 
     In an on-line handwriting recognition system, when an operator writes a character on a digitizing tablet, the character (an on-line handwritten character) is recognized based on coordinate data output from the digitizing tablet. The on-line handwriting recognition system has been studied for a long time. However, since the on-line handwritten character can have various shapes, it is difficult to accurately recognize the on-line handwritten character. 
     A conventional on-line handwriting recognition method is disclosed, for example, in Yoko Suminaga, &#34;On-line handwriting recognition for Kanji characters easing restrictions of writing, such as a restriction regarding simplified characters&#34; (NIKKEI ELECTRONICS, 331, pp. 115-133, Dec. 5, 1983). In this conventional on-line handwriting recognition method, the on-line handwritten character which can have various shapes is recognized by use of many features describing shapes of characters. However, as these features are adhoc determined, there is a disadvantage in that it requires a great deal of labor to make a dictionary regarding character shapes. Further, although the on-line handwriting recognition method requires an effective and high speed matching process, in the conventional on-line handwriting recognition method, a dynamic programming in which complex calculations are carried out is used to distinguish many different shapes of a character from each other. In addition, in a case where characters are recognized by use of a structural technique, as the structural technique greatly depends on a writing stroke order of each character, there is a disadvantage in that it requires a large-scale dictionary to recognize characters which can have various shapes, such as Kanji characters. 
     SUMMARY OF THE INVENTION 
     Accordingly, a general object of the present invention is to provide a novel and useful method for extracting features from an on-line handwritten character in which the disadvantages of the aforementioned prior art are eliminated. 
     A more specific object of the present invention is to provide a method for extracting features from an on-line handwritten character capable of extracting features which can be used to effectively easily recognize an on-line handwritten character which can have various shapes and be written in various writing stroke orders. 
     The above objects of the present invention are achieved by a method for extracting features from a character which is input to an on-line input means by writing the character by hand, the on-line input means successively outputting stroke information indicating points on strokes of the handwritten character, and the method comprising the steps of: (a) detecting strokes of the handwritten character based on the stroke information output from the on-line input means; (b) detecting singular points from the points on the strokes of the handwritten character based on the stroke information output from the on-line input means, each of the singular points being defined as a pair of points on the strokes of the handwritten character, which points are written at different times and have substantially the same coordinates as each other; (c) obtaining primitive sequences forming each of the strokes detected by the step (a), each of the primitive sequences being formed of primitives and each of the primitives being a monotone curve, the monotone curve being a curve which is either non-increasing or non-decreasing; (d) determining a connective relationship between each two primitive sequences of each of the strokes; and (e) determining a structure of each of the singular points detected by the step (b) based on primitive sequences including each of the singular points and a coupling of the primitive sequences including each of the singular points, whereby the connective relationship determined by step (d) and the structure of each of the singular points determined by step (e) are obtained as feature data. 
     According to the present invention, as the structure of the on-line input character is described by use of connective relationships between the primitive sequences and the structure of each of the singular points, it is possible to extract features which can be used to effectively easily recognize an on-line handwritten character which can have various shapes and be written in various writing stroke orders. 
     Additional objects, features and advantages of the present invention will become apparent from the following detailed description when read in conjunction with the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram illustrating an on-line handwriting recognition system. 
     FIG. 2 is a block diagram illustrating fundamental functions of the on-line handwriting recognition system provided in the character recognition system shown in FIG. 1. 
     FIG. 3 is a flow chart illustrating a process for recognizing an on-line input character. 
     FIG. 4 is a diagram illustrating an example of the on-line input character. 
     FIGS. 5a-5d are diagrams illustrating cases in which a singular point can be detected. 
     FIGS. 6a-6d are diagrams illustrating four types of primitives. 
     FIG. 7 is a diagram illustrating primitives on strokes forming the on-line input character shown in FIG. 4. 
     FIG. 8 is a diagram illustrating a concatenation of the primitives. 
     FIG. 9a-9d, 10a-10d, 11a-11d and 12a-12d are diagrams illustrating types of concatenation of the primitives. 
     FIG. 13 is diagram illustrating primitive sequences forming a first stroke of the on-line input character shown in FIG. 4. 
     FIGS. 14a-14d are diagrams illustrating types of singular points. 
     FIG. 15 is a diagram illustrating another example of the on-line input character. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     A description will now be given of an embodiment of the present invention. 
     Referring to FIG. 1, which shows a basic configuration of an on-line handwriting recognition system, the on-line handwriting recognition system has a CPU 1 (Central Processing Unit), a ROM 2 (Read Only Memory), a RAM 3 (Random Access Memory), an interface 4 to which an input unit 5 such as a digitizing tablet is connected, and an interface 6 to which an output unit 7 including a display unit, a printer and so on are connected. The CPU 1, the ROM 2, the RAM 3, and the interfaces 4 and 6 are respectively connected to each other by a system bus 8. The CPU 1 processes data in accordance with programs which are stored in the ROM 2. Data generated by the processing of the CPU 1 is stored in the RAM 3. An area used for an on-line handwriting recognition process is formed in the RAM 3. While an operator is writing a character on the digitizing tablet (the input unit 4), the digitizing tablet successively outputs coordinate data of sampled points on strokes of the character written thereon. The coordinate data output from the digitizing tablet is supplied via the interface 4 and the system bus 8 to the CPU 1. The CPU 1 carries out a first process for extracting features from the character based on the coordinate data and a second process for recognizing the character based on the features obtained by the first process. The recognition results obtained by the second process are supplied from the CPU 1 via the system bus 8 and the interface 6 to the output unit 7, so that the recognition results are, for example, displayed on the display unit (the output unit 7). 
     FIG. 2 shows fundamental functions of the on-line handwriting recognition system provided in the character recognition system shown in FIG. 1. Referring to FIG. 2, an on-line input block 11 is formed in the digitizing tablet (the input unit 5) shown in FIG. 1. The on-line input block 11 outputs stroke information, such as the coordinate data of the sampled points on strokes of the character which is written by the operator, in time series. A character input to the on-line input block 11 is referred to as an on-line input character. A line pattern structure analysis block 12 and a matching block 13 are respectively formed in the CPU 1 shown in FIG. 1. A character shape model block 14 is formed in the ROM 2 or the RAM 3. The line pattern structure analysis block 12 analyzes a line pattern structure of the on-line input character based on the stroke information supplied from the on-line input block 11. The line pattern structure analysis block 12 extracts features describing a general structure of the on-line input character which do not depend on the writing stroke order of the on-line input character. A standard model (a dictionary) of each character shape is previously recorded in the character shape model block 14. The matching block 13 carries out a matching of the features obtained by the line pattern structure analysis block 12 and the standard model of each character shape recorded in the character shape model block 14. The matching block 13 outputs recognition results of the on-line characters obtained in accordance with the matching process. 
     A detailed description will now be given of the line pattern structure analysis block 12, the matching block 13 and the character shape model block 14. 
     The Line Pattern Structure Analysis Block 12 
     While an operator is writing a character on the on-line input block 11 (the digitizing tablet), the on-line input block 11 samples points on lines of the character at a predetermined time rate. That is, the stroke information output from the on-line input block 11 is formed of coordinate data of sampled points P on strokes of the on-line input character. Each stroke is described by a curve formed of one or a plurality of line segments, each segment connecting adjacent sampled points to each other, as shown in FIG. 4. The sampled points P are sequentially output from the on-line input block 11. While an operator is inputting (writing), for example, a numerical character &#34;5&#34; to the on-line input block 11, as shown in FIG. 4, the on-line input block 11 successively outputs stroke information of sampled points P(0) through P(12) in this order. 
     The line pattern structure analysis block 12, to which the stroke information of the above sampled points P(0) through P(12) shown in FIG. 4 is supplied, carries out a process in accordance with a flow chart shown in FIG. 3. 
     (i) DETECTING STROKES (step 120a) 
     Step 120a detects strokes of the on-line input character input to the on-line input block 11 based on the sampled points P(0) through P(12) shown in FIG. 4. In this case, a pen for writing characters is separated from the digitizing tablet between sampled points P(9) and P(10), so that step 120a determines that a line pattern of the on-line input character is divided into two strokes, a first stroke connecting sampled points P(0) through P(9) and a second stroke connecting sampled points P(10) through P(12). That is, the first and second strokes are detected in step 120a. 
     (ii) DETECTING SINGULAR POINTS (step 120b) 
     Step 120b detects one or a plurality of singular points based on the sampled points P(0) through P(12) supplied from the on-line input block 11. 
     A singular point is defined as a pair of points on each stroke of the on-line input character, which points are written at different times and have substantially the same coordinates as each other. The singular point is detected in the following four cases. 
     A first case is indicated in FIG. 5(a). In FIG. 5(a), a line segment connecting sampled points p 1  and p 2  and another line segment connecting sampling points q 1  and q 2  are crossed in a state where the coordinates of the sampled points p 1  and q 1  are equal to each other. In this case, a pair of sampled points p 1  and q 1  is detected as the singular point. The above sampled points p 1 , p 2 , q 1  and q 2  can be an end point of each stroke and an inner point thereof. 
     A second case is indicated in FIG. 5(b). In FIG. 5(b), a line segment correcting sampled points p 1  and p 2  and another line segment connecting sampled points q 1  and q 2  are crossed in a state where the coordinates of an inner point of the line segment connecting the sampled points p 1  and p 2  and the coordinates of the sampled point q 1  are equal to each other. In this case, a pair of points comprising a point p 0  and the sampled point q 1  is detected as the singular point. The point p 0  is the closest point to the sampled point q 1  between the sampled points p 1  and p 2 . The sampled point q 1  can be an end point of the stroke and an inner point thereof. 
     A third case is indicated in FIG. 5(c). In points p 1  and p 2  and another line segment connecting the sampled points q 1  and q 2  are crossed in a state where the coordinates of an inner point of the line segment connecting the sampled points p 1  and p 2  and the coordinates of an inner point of the line segment connecting the sampled points q 1  and q 2  are equal to each other. In this case, four pairs of sampled points (p 1 , q 1  ), (p 1 , q 2 ), (p 2 , q 1 ) and (p 2 , q 2 ) are formed, and then a distance between the sampled points in each pair is calculated. A pair of sampled points having a distance therebetween which is the smallest distance is detected as the singular point. 
     A fourth case is indicated in FIG. 5(d). In FIG. 5(d), the sampled point q 1  is positioned in a detection area A which is formed based on the dimension of a line segment connecting the sampled points p 1  and p 2 . The detection area A is defined, for example, as a rectangular area having a width of 2d and a height equal to the length of the line segment connecting p 1  and p 2  where d is a predetermined threshold distance. The line segment connecting p 1  and p 2  is positioned at the center of the detection area A in a width direction thereof. In this case, a pair of points comprising a point p 0  and the sampled point q 1  is detected as the singular point. The point p 0  is the closest point to the sampled point q 1  between the sampled points p 1  and p 2 . In addition, as another sampled point q 3  is also positioned in the detection area, a pair of a point p 0 , which is the closest point to the sampled point q 3  between the sampled points p 1  and p 2 , and the sampled point q 3  is detected as the singular point. 
     In a case shown in FIG. 4, the sampled points P(1) and P(10) are written at different time and have the same coordinates. Thus, a pair of sampled points (P(1) and P(10)) is detected as the singular point in accordance with the above first case shown in FIG. 5(a). 
     (iii) DECOMPOSING STROKE INTO PRIMITIVES (step 121) 
     Each stroke detected in step 120a is decomposed into primitives. 
     An xy-monotone curve is a curve whose x coordinate and y coordinate values are always either non-increasing or non-decreasing when the curve is being traced. Coordinates of both end points of an xy-monotone curve are defined as P(x 0 ,y 0 ) and Q(x 1 ,y 1 ), where x 0  &lt;x 1  and y 0  &lt;y 1  if x 0  =x 1 . In this case, the point P is referred to as a &#34;head&#34; of the curve and the point Q is referred to as a &#34;tail&#34; of the curve. The xy-monotone curve is classified into the following four types of curves. 
     (1) First type 
     The first type of xy-monotone curve is a horizontal line (y 0  =y 1 ) which is symbolized by &#34;--&#34;. The first type of xy-monotone curve is indicated in FIG. 6(a). 
     (2) Second type 
     The second type of xy-monotone curve is a curve which increases in a right direction and decreases in a left direction [(x 0  -x 1 )×(y 0  -y 1 )&gt;0]. The second type of xy-monotone curve is indicated in FIG. 6(b) and symbolized by &#34;/&#34;. 
     (3) Third type 
     The third type of xy-monotone curve is a vertical line (x 0  =x 1 ) which is symbolized by &#34;|&#34;. The third type of xy-monotone curve is indicated in FIG. 6(c). 
     (4) Fourth type 
     The fourth type of xy-monotone curve is a curve which decreases in a right direction and increases in a left direction [(x 0  -x 1 )×(y 0  -y 1 )&lt;0]. The fourth type of xy-monotone curve is indicated in FIG. 6(d) and symbolized by &#34; &#34;. 
     Each of the above types of xy-monotone curves is referred to as a primitive. That is, the primitive is a simple curve element. 
     In the case shown in FIG. 4, the first stroke (P(0), P(1), . . . , and P(9)) and the second stroke (P(10), P(11) and P(12)) are respectively decomposed into primitives A 0  through A 6 , each of which belongs to one of the above types of xy-monotone curves, as shown in FIG. 7. That is, the first stroke is decomposed into the following primitives A 0  through A 5 . 
     A 0  (/):(P(0), P(1), P(2) and P(3)) 
     A 1  ():(P(3) and P(4)) 
     A 2  (/):(P(4) and P(5)) 
     A 3  ():(P(5), P(6) and P(7)) 
     A 4  (/):(P(7) and P(8)) 
     A 5  ():(P(8) and P(9)) 
     The second stroke is decomposed into a primitive A 6 . 
     A 6  (/):(P(10), P(11) and P(12)) 
     (iv) CONCATENATING PRIMITIVES (step 122) 
     The primitives obtained in step 121 are concatenated in accordance with predetermined concatenating rules. 
     It is assumed that two xy-monotone curve (primitives) a and b which belong to different types of xy-monotone curves form a curve which is not an xy-monotone curve and the xy-monotone curves a and b are not included in each other. A point P is positioned on both of the xy-monotone curves a and b, and points Q and R are positioned adjacent to the point P. The point Q is included in the xy-monotone curve a only and the point R is included in the xy-monotone curve b only. In this case, it is assumed that a vector product of a vector (x q  -x p , y q  -y p ) and a vector (x r  -x p ,y r  -y p ) is greater than zero, (x q  -x p )×(y r  --y p )-(x r  -x p )×(y q  --y p )&gt;0, where coordinate data o the point P is coor(P)=(x p ,y p ), coordinate data of the point Q is coor(Q)=(x q ,y q ), and coordinate data of the point R is coor(R)=(x r ,y.sub. r). 
     In the assumption described above, when the concatenations of two primitives a and b are indicated by ##EQU1## the concatenations of the primitives a and b are defined as follows. 
     In a case where A and B are one of the types of &#34;/&#34;, &#34; &#34;, &#34;|&#34; and &#34;--&#34; and α and β are either the &#34;head&#34; or the &#34;tail&#34;, a symbol [A,α, B, β] represents that the primitive a of a type A and the primitive b of a type B are concatenated with each other at α of the primitive a and β of the primitive b. 
     (Rule 1) 
     The concatenations represented by [ , head, /, tail], [ , head, --, tail], [-, head, /, head], and [ , head,  , head] are respectively defined as ##EQU2## 
     (Rule 2) 
     The concatenations represented by [ , head, /, head], [ , head, --, head], [--, head, /, head], and [ , head,  , head] are respectively defined as ##EQU3## 
     (Rule 3) 
     The concatenations represented by [/, tail,  , head], [/, tail, |, tail], [|, tail,  , head], and [/, tail, /, tail] are respectively defined as ##EQU4## 
     (Rule 4) 
     The concatenations represented by [ , tail, /, tail], [ , tail, --, tail], [-, tail, /, tail], and [ , tail,  , tail] are respectively defined as ##EQU5## 
     FIG. 8 shows the concatenation of two primitives. Referring to FIG. 8, two primitives a and b are concatenated so that a pair of vectors (PP a , PP b ) is in a right-handed system, where P is a point in an intersection of the primitives a and b, and P a  and P b  are respectively points on the primitives a and b. P a  corresponds to Q described above and P b  corresponds to R described above. In this case, the concatenation of primitives a and b is denoted by the above symbol ##EQU6## FIGS. 9(a), (b), (c) and (d) show the primitives a and b which are concatenated in accordance with the Rule 1 ##EQU7## FIGS. 10(a), (b), (c) and (d) show the primitives a and b which are concatenated in accordance with the Rule 2 ##EQU8## FIGS. 11 (a), (b), (c) and (d) show the primitives a and b which are concatenated in accordance with the Rule 3 ##EQU9## FIGS. 12 (a), (b), (c) and (d) show the primitives a and b which are concatenated in accordance with the Rule 4 ##EQU10## In a case where each stoke of the on-line input character is decomposed into the primitives as shown in FIG. 7, the following concatenations of primitives are obtained in step 122. ##EQU11## 
     (v) FORMING PRIMITIVE SEQUENCES (step 123) 
     A plurality of concatenations of primitives which are obtained in step 122 are linked together, so that the following primitive sequence can be generated. ##EQU12## 
     In a case shown in FIG. 7, when the concatenations primitives forming the first stroke (P(0), P(1), . . . , and P(9)) are linked together, the following two primitive sequences E 0  and E 1  are obtained. ##EQU13## The second stroke (P(10), P(11), and P(12)) is formed of only one primitive A 6 , so that the primitive sequence E 2  including only the primitive A 6  is obtained. 
     E 2  :A 6   
     A label &lt;ps,id&gt; is given to each primitive sequence indicated by the above formula (1). A first factor ps and a second factor id of the label are respectively defined as follows. ##EQU14## where corner ##EQU15## is a function which has a value of &#34;1&#34; when the primitives a and b are the same type and has a value of &#34;0&#34; when the primitives a and b are different types. 
     The second factor id of the label &lt;ps,id&gt; indicates an initial direction in which a concave curve defined by the primitive sequence is extended. In the first factor ps of the label &lt;ps,id&gt;, a first term, ##EQU16## corresponds to a difference between directions in the concave curve, so that the first term represents a number of rotations of the concave curve. A second term of the first factor ps, ##EQU17## is a correction term which is effectively used in a case where a concatenation of primitives shown in FIG.9(d), FIG. 10(d), FIG. 11(d) or FIG. 12(d) is provided at an end of a primitive sequence. For example, if a downward concavity and a leftward concavity are superposed on each other, the concatenation of primitives shown in FIG. 9(d) is obtained. 
     Hence, the primitive sequences E 0  and E 1  forming the first stroke of the above on-line &lt;3,0&gt; and &lt;4,2&gt;. 
     (vi) CONNECTING PRIMITIVE SEQUENCES (step 124) 
     The primitive sequences E 0  and E 1  shown in FIG. 13 have a common primitive A 2  which is positioned at an end of each primitive sequence. There are two types of connections between two primitive sequences. In the first type of connection, the primitive sequences are connected to each other in a state where the same primitive is positioned at a leading end of each primitive sequence, as shown the above example in FIG. 13. In the second type of connection, the primitive sequences are connected to each other in a state where the same primitive is positioned at a tail end of each primitive sequence. The first type of connection is referred to as an h-connection, and the second type of connection is referred to as a t-connection. For example, the primitives E 0  and E 1  are connected to each other in the form of the h-connection. This condition is represented by 
     E 1  -E 1 . 
     In the case of the t-connection, t is substituted for h in the above representation. 
     (vii) DETERMINING STRUCTURE OF SINGULAR POINT (step 125) 
     A structure of each singular point obtained in step 120b is determined. Each singular point is classified as being one of four singular point types shown in FIG. 14(a), (b), (c) and (d). A first type shown in FIG. 14(a) is referred to as a T-type. In the T-type, two line segments are coupled to each other at a singular point Q 1  to form a T-shape. A second type shown in FIG. 14(b) is referred to as an X-type. In the X-type, two line segments are crossed at a singular point Q 2  to form a X-shape. A third type shown in FIG. 14(c) is referred to as a K-type. In the K-type, three line segments are coupled to each other at a singular point Q 3  to form a K-shape. A fourth type shown in FIG. 12(d) is referred to as an L-type. In the L-type, two line segments are coupled to each other at a singular point Q 4  which is positioned at an end of each line segment to form an L-shape. The structure of each singular point is described by two primitive sequences, each of which includes a singular point and the type of singular point it is. 
     In the case of the on-line character shown in FIG. 7, the singular point (P(1) and P(10)) belongs to the T-type and is positioned on the primitives A 0  and A 6  which are respectively in the primitive sequences E 0  and E 1 . Thus, the structure of the singular point (P(1) and P(10)) is described by the following symbol; 
     
         (E.sub.0 T E.sub.1). 
    
     According to the process described above, the structure of the on-line input character shown in FIG. 4 can be described as follows. That is, the following structural description of a character shape is obtained 
     First stroke (P(0), P(1), . . . , and P(9)):E 0  &lt;3,0&gt; E 1  &lt;4,2&gt; 
     Second stroke (P(10), P(11), and P(12)):E 2  &#34;/&#34; 
     Singular point (P(1) and P(10)):(E p  T E 2 ) 
     The Matching Block 13 and the Character Shape Model Block 14 
     The standard model recorded in the character shape model block 14 is formed of the structural description of standard character shapes which are previously obtained in the same manner as that described above. The matching block 13 carries out the matching between the structural description of the on-line input character which is output from the line pattern structure analysis block 12 and the structural description of standard character shapes from the character shape model block 14, so that the matching block 13 outputs a recognition result regarding the on-line input character which is input to the on-line input block 11. 
     A result in the matching process only depends on the primitive sequences forming the strokes, the connection of primitive sequences and the structure of the singular point which has been described above. The result in the matching process does not depend on the writing stroke order, a direction in which each stroke extends, such as a direction from left to right and a direction from up to down. 
     A curve shown in FIG. 15 has a label &lt;5,2&gt;. This curve can be matched to the character &#34;0&#34; and &#34;6&#34; in accordance the shape of the curve. In a case like this, a detailed recognition of the curve can be performed by applying a statistical analyzing technique to parameter vectors describing the shape of the curve. For example, in the curve shown in FIG. 15, it can be recognized whether the curve is either a character &#34;0&#34; or &#34;6&#34; by applying a linear discrimination analysis to a vector (d 1  /d, d 2  /d, . . . , d 5 ) where d is defined as the following formula. ##EQU18## 
     The present invention is not limited to the aforementioned embodiments, and variations and modifications may be made without departing from the scope of the claimed invention.