Stroke-number-free and stroke-order-free on-line Chinese character recognition method

• US 5,796,867 A
• Filed: 06/12/1996
• Issued: 08/18/1998
• Est. Priority Date: 06/12/1996
• Status: Expired due to Term

• Current Assignee: Transpacific IP Group Limited
• Original Assignee: Industrial Technology Research Institute
• Inventors: Chen, Ju-Wei, Lee, Suh-Yin
• Primary Examiner(s): CHANG, JON CARLTON
• Assistant Examiner(s): Nguyen, Ha Tran
• Application Number:
  US08/662,861
• Time in Patent Office: 797 Days
• Field of Search: 382/185, 382/186, 382/187, 382/201, 382/202, 382/203, 382/209, 382/217, 382/218, 382/286, 395/10, 395/11, 395/50, 395/54, 395/60, 704/8, 704/10, 707/104
• US Class Current: 382/187
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet

Abstract

A stroke-order-free and stroke-number-free method for the on-line recognition of Chinese characters comprising the steps of: (a) inputting a handwritten input script on an on-line basis, (b) preprocessing the input script to reduce a number of possible matching template characters; (c) performing basic stroke recognition using a database of basic strokes to identify all possible basic strokes contained in the handwritten input script; (d) performing stroke correspondence using a database of stroke correspondence rules to find matching strokes in template characters for the strokes contained in the handwritten input script; and (e) performing computation of discrimination functions using a database of character patterns and a database of spatial relationships between strokes of characters to find one or more template characters with minimum error. Some of the key features of the method include: (a) the strokes recognized during the stroke correspondence are expanded to include fore strokes, back strokes, and points, in which the fore strokes are strokes that actually appear in a character, the back strokes are fictitious strokes provided to allow for stroke connections that should not appear, and the points are provided to allow for truncated back strokes in the input script; and (b) each stroke correspondence rule contains a specific set of stroke information including (i) allowed stroke types, (ii) at least one geometric feature measure, and (iii) criterion for applying the geometric feature measure; the geometric feature measure is a geometrically related characteristic measure, which can be x or y coordinates, length, or distance, associated with a particular stroke, to facilitate stroke recognition. In a preferred embodiment, eight types of stroke correspondences are allowed:(a) fore→fore, (2) back→back, (3) back→fore, (4) back→point, (5) back→null, (6) null→back, (7) fore→null, and (8) null→fore.

Claims

1. A stroke-order-free and stroke-number-free method for the on-line recognition of Chinese characters comprising the steps of:

(a) obtaining a database of template characters, each template character being represented by a set of stroke correspondence rules for describing its constituent basic strokes;

(b) obtaining a database of spatial relationships between strokes of characters and a database of character patterns;

(c) inputting a handwritten input script on an on-line basis;

(d) preprocessing said input script to select candidate template characters for matching against said input script;

(e) performing a basic stroke recognition procedure to identify all basic strokes contained in said input script using a database of basic strokes;

(f) classifying said strokes into fore strokes, back strokes, and points, wherein said fore strokes are strokes that actually appear in the character, said back strokes are fictitious strokes to allow for stroke connections that do not appear in said database of template characters, and said points are provided to allow for truncated back strokes in said input script;

(g) for each candidate template character, performing a stroke correspondence for each stroke correspondence rule contained therein until all the stroke correspondence rules contained in said template character are exhausted, so as to identify all fore stroke→

fore stroke correspondence;

(h) performing stroke matchings in accordance with an input stroke order to find other strokes correspondences including;

back→

point, back→

fore, fore→

null, null→

fore, back→

null, and null→

back; and

(i) performing computation of discrimination functions to find a template character with a minimum distance.

2. A stroke-order-free and stroke-number-free method for the on-line recognition of Chinese characters according to claim 1 which further comprises the steps of recording the stroke order of said input script and rearranging the stroke order provided of said template character according to said stroke order of said input script.

3. A stroke-order-free and stroke-number-free method for the on-line recognition of Chinese characters according to claim 1 wherein each of said stroke correspondence rules comprises:

(a) basic stroke types that are allowed in said input script; and

(2) at least one geometric feature measure associated with said stroke.

4. A stroke-order-free and stroke-number-free method for the on-line recognition of Chinese characters according to claim 3 wherein said geometric feature measure is an x-coordinate y-coordinate, length, or distance, associated with said stroke.

5. A stroke-order-free and stroke-number-free method for the on-line recognition of Chinese characters according to claim 1 which allows stroke correspondences of:

(a) fore→

fore, (2) back→

back, (3) back→

fore, (4) back→

point, (5) back→

null, (6) null→

back, (7) fore→

null, and (8) null→

fore.

6. A stroke-order-free and stroke-number-free method for the on-line recognition of Chinese characters according to claim 1 wherein each of said spatial relationships between strokes of characters consists of four vectors of ss(i, i+1), se(i, i+1), es(i, i+1), and ee(i, i+1), for which s represents the starting point and e represents the end point of strokes i and i+1.

7. An apparatus for on-line recognition of Chinese characters which is constrained by neither the stroke order nor the stroke number of said Chinese character, said apparatus comprising:

(a) memory means for storing a database of template characters, each template character being represented by a set of stroke correspondence rules for describing its constituent basic strokes;

(b) memory means for storing a database of spatial relationships between strokes of characters and memory means for storing a database of character patterns;

(c) means for inputting a handwritten input script on an on-line basis;

(d) means for preprocessing said input script to select candidate template characters for matching against said input script;

(e) means for performing a basic stroke recognition procedure to identify all basic strokes contained in said input script using a database of basic strokes;

(f) means for classifying strokes into fore strokes, back strokes, and points, wherein said fore strokes are strokes that actually appear in the character, said back strokes are fictitious strokes to allow for stroke connections that do not appear in said database of template characters, and said points are provided to allow for truncated back strokes in said input script;

(g) means for performing a stroke correspondence for each and every stroke correspondence rule contained in each candidate template character until all the stroke correspondence rules contained in said template character are exhausted, so as to identify all fore stroke→

fore stroke correspondence;

(h) means for performing stroke matchings in accordance with an input stroke order to find other strokes correspondences including;

back→

point, back→

fore, fore→

null, null→

fore, back→

null, and null→

back; and

(i) means for performing computation of discrimination functions to find a template character with a minimum distance.

8. An apparatus for on-line recognition of Chinese characters according to claim 7 which further comprises means for recording the stroke order of said input script and means for rearranging the stroke order provided of said template character according to said stroke order of said input script.

9. An apparatus for on-line recognition of Chinese characters according to claim 7 wherein each of said stroke correspondence rules comprises:

(a) basic stroke types that are allowed in said input script; and

(2) at least one geometric feature measure associated with said stroke.

10. An apparatus for on-line recognition of Chinese characters according to claim 9 wherein said geometric feature measure is an x-coordinate y-coordinate, length, or distance, associated with said stroke.

11. An apparatus for on-line recognition of Chinese characters according to claim 7 which allows stroke correspondences of:

(a) fore→

fore, (2) back→

back, (3) back→

fore, (4) back→

point, (5) back→

null, (6) null→

back, (7) fore→

null, and (8) null→

fore.

12. An apparatus for on-line recognition of Chinese characters according to claim 7 wherein each of said spatial relationships between strokes of characters consists of four vectors of ss(i, i+1), se(i, i+1), es(i, i+1), and ee(i, i+1), for which s represents the starting point and e represents the end point of strokes i and i+1.

13. A computer readable medium having a program for on-line recognition of Chinese characters which is constrained by neither the stroke order nor the stroke number of said Chinese character, said computer program comprising:

(a) code means for storing and retrieving data from a database of template characters, each template character being represented by a set of stroke correspondence rules for describing its constituent basic strokes;

(b) code means for storing and retrieving data from a database of spatial relationships between strokes of characters and a database of character patterns;

(c) code means for inputting a handwritten input script on an on-line basis;

(d) code means for preprocessing said input script to select candidate template characters for matching against said input script;

(e) code means for performing a basic stroke recognition procedure to identify all basic strokes contained in said input script using a database of basic strokes;

(f) code means for classifying said strokes into fore strokes, back strokes, and points, wherein said fore strokes are strokes that actually appear in the character, said back strokes are fictitious strokes to allow for stroke connections that do not appear in said database of template characters, and said points are provided to allow for truncated back strokes in said input script;

(g) code means for performing a stroke correspondence for each and every stroke correspondence rule contained in each candidate template character until all the stroke correspondence rules contained in said template character are exhausted, so as to identify all fore stroke→

fore stroke correspondence;

(h) code means for performing stroke matchings in accordance with an input stroke order to find other strokes correspondences including;

back→

point, back→

fore, fore→

null, null→

fore, back→

null, and null→

back; and

(i) code means for performing computation of discrimination functions to find a template character with a minimum distance.

14. The computer readable medium having a program for on-line recognition of Chinese characters according to claim 13 which further comprises code means for recording the stroke order of said input script and code means for rearranging the stroke order provided of said template character according to said stroke order of said input script.

15. The computer readable medium having a program for on-line recognition of Chinese characters according to claim 13 wherein each of said stroke correspondence rules comprises:

(a) basic stroke types that are allowed in said input script; and

(b) at least one geometric feature measure associated with said stroke.

16. The computer readable medium having a program for on-line recognition of Chinese characters according to claim 15 wherein said geometric feature measure is an x-coordinate y-coordinate, length, or distance, associated with said stroke.

17. The computer readable medium having a program for on-line recognition of Chinese characters according to claim 13 which allows stroke correspondences of:

(a) fore→

fore, (2) back→

back, (3) back→

fore, (4) back→

point, (5) back→

null, (6) null→

back, (7) fore→

null, and (8) null→

fore.

18. The computer readable medium having a program for on-line recognition of Chinese characters according to claim 13 wherein each of said spatial relationships between strokes of characters consists of four vectors of ss(i, i+1), se(i, i+1), es(i, i+1), and ee(i, i+1), for which s represents the starting point and e represents the end point of strokes i and i+1.