Character recognition system using the generalized hough transformation and method

• US 5,220,621 A
• Filed: 07/31/1991
• Issued: 06/15/1993
• Est. Priority Date: 08/01/1990
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Saitoh, Fumihiko
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/738,391
• Time in Patent Office: 685 Days
• Field of Search: 382/22, 382/41, 382/54, 382/1, 364/725
• US Class Current: 382/200
• CPC Class Codes: G06V 10/753 Transform-based matching, e.g. Hough transform

Abstract

A character recognition system and method using the generalized Hough transform are disclosed. A template table which stores edge point parameters to be used for the generalized Hough transform is compressed so as to include only predetermined parameters, and is then divided into a plurality of template tables which are respectively loaded in the memories of a plurality of subprocessors operating in parallel under the control of a main processor. In performing recognition processing, these subprocessors operate in parallel according to their related partial template tables. Character recognition using the generalized Hough transform provides a high rate of character recognition. Also, parallel processing using the compressed template tables and partial template tables helps shorten table search time and computation time, thereby increasing processing efficiency.

Claims

1. A character recognition system comprising:

means for storing a template table for each of a plurality of basic character patterns, which includes parameters extracted at edge points of an image of the basic character pattern used for the generalized Hough transform;

means for detecting an image of an object including a character to be recognized;

means for detecting edge points of the image of said object;

means for accessing, based upon data specifying a selected template table and said detected edge points, parameters from said selected template table, which are used for the generalized Hough transform of said detected edge points;

means for performing the generalized Hough transform based upon said accessed parameters and coordinates of said detected edge points;

means for recording cumulative values for the coordinates generated by said transform; and

means for judging from said recorded cumulative values whether or not the image of said object includes the character corresponding to said selected template table.

2. A character recognition system according to claim 1, wherein said parameters stored in each said template table define a gradient direction at each of the edge points of the image of the corresponding basic character pattern and a straight line connecting each of the edge points and a predetermined reference point and wherein said edge point detecting means includes means for detecting the coordinates of, and a gradient direction at, each of the edge points of the image of said object, and said accessing means includes means for accessing from said selected template table said straight line defining parameters for the edge points having gradient directions approximately equal to the gradient directions detected at the edge points of the image of said object.

3. A character recognition system according to claim 1, including means for compressing each said template table so as to include only the parameters for the edge points of curved edge portions of the image of the corresponding basic character pattern.

4. A character recognition system according to claim 1, wherein each said template table is divided into a plurality of partial template tables;

said storing means consisting of a plurality of memory units allocated to store said partial template tables individually;

said accessing means and said performing means being provided for each of said memory units;

a plurality of said accessing means and said performing means being operated in parallel.

5. A character recognition system according to claim 1, wherein said judging means includes means for comparing said stored cumulative values with a predetermined threshold value associated with said selected template table.

6. A character recognition system comprising:

means for generating a template table which includes parameters extracted at edge points of an image of a basic character pattern for character recognition used for the generalized Hough transform;

means for compressing said template table so as to include only said parameters for the edge points of curved edge portions of said image;

means for storing said compressed template table;

means for detecting an image of an object including a character to be recognized;

means for detecting edge points of the image of the object;

means for accessing, based upon said detected edge points, parameters to be used for the generalized Hough transform of said detected edge points from said compressed template table stored in said storing means;

means for performing the generalized Hough transform based upon said accessed parameters and the coordinates of said detected edge points;

means for recording cumulative values for the coordinates generated by said transform; and

means for judging from said recorded cumulative values whether or not the image of said object includes the character corresponding to said template table.

7. A character recognition system according to claim 6, wherein the parameters stored in said template table define a gradient direction at each of the edge points of the image of the basic character pattern and a straight line connecting each of the edge points and a predetermined reference point and wherein said edge point detecting means includes means for detecting the coordinates of, and a gradient direction at, each of the edge points of the image of said object;

said accessing means including means for accessing from said template &

able said straight line defining parameters for the edge points having gradient directions approximately equal to the gradient directions detected at the edge points of the image of said object.

8. A character recognition system comprising:

means for detecting an image of an object including a character to be recognized,

a main processor means having memory means and being connected to said detecting means, and

a plurality of subprocessor means connected to said main processor means through a common bus and each having memory means,

said memory means in each said subprocessor means storing partial template tables each of which is a different part of an overall template table, each of said partial template tables containing a gradient direction at each of a plurality of edge points of an image of a different one of basic character patterns to be used for character recognition and a straight line connecting each of the edge points and a predetermined reference point;

said main processor means including means for detecting the coordinates of, and a gradient direction at, each of edge points of the image of said object;

said main processor means including means for supplying a template table number and the coordinates and gradient direction for each of the detected edge points to a selected subprocessor means having stored therein a partial template table including the detected gradient direction;

said selected subprocessor means each including means for accessing the parameters for an edge point having a gradient direction approximately equal to said detected gradient direction;

said selected subprocessor means performing the generalized Hough transform based upon said accessed parameters and the coordinates of said detected edge point, and then transferring the resultant coordinates generated by the transform to said main processor means;

said main processor means recording cumulative values for the coordinates transferred from said subprocessor means, and determining from said stored cumulative values whether said image of said object includes the character corresponding to said selected template table.

9. A character recognition system according to claim 8, wherein said memory means of said main processor means includes means for storing an index table for each of said template tables which indicates the correspondence between said partial template tables and said subprocessor means.

10. A method for character recognition comprising the steps of:

storing in a memory a template table for each of a plurality of basic character patterns, which includes parameters extracted at edge points of an image of the basic character pattern used for the generalized Hough transform;

detecting edge points of an image of an object including a character to be recognized;

accessing, based upon data specifying a selected template table and said detected edge points, parameters from said selected template table, which parameters are used for the generalized Hough transform of said detected edge points;

performing the generalized Hough transform based upon said accessed parameters and the coordinates of said detected edge points;

recording cumulative values for the coordinates generated by said transform; and

judging from said recorded cumulative values whether or not the image of said object includes the character corresponding to said selected template table.

11. A method for character recognition according to claim 10, wherein each of said parameters stored in each said template table defines a gradient direction at each of the edge points of the image of the corresponding basic character pattern and a straight line connecting each of the edge points and a predetermined reference point and wherein said edge point detecting step includes detecting the coordinates of, and a gradient direction at, each of the edge points;

and said parameter accessing step includes accessing from said selected template table said straight line defining parameters for the edge points having gradient directions approximately equal to said detected gradient directions.

12. A method for character recognition according to claim 10, wherein said judging step includes comparing said recorded cumulative values with a predetermined threshold value for said selected template table.

13. A method for character recognition according to claim 10, including compressing each said template table so as to include only said parameters for the edge points of curved edge portions of the image of the corresponding basic character pattern.

14. A method for character recognition according to claim 10, including dividing each said template table into a plurality of partial template tables, which are respectively stored in memories of a plurality of subprocessors capable of operating in parallel under the control of a main processor.

15. A method for character recognition comprising the steps of:

generating a template table which includes parameters extracted at edge points of an image of a basic character pattern for character recognition used for the generalized Hough transform;

compressing said template table so as to include only said parameters for the edge points of curved edge portions of said image;

detecting each of a plurality of edge points of an image of an object including a character to be recognized;

accessing parameters to be used for the generalized Hough transform of said detected edge points from said compressed template table;

performing the generalized Hough transform based upon said accessed parameters and the coordinates of said detected edge points;

p1 recording cumulative values for the coordinates generated by said transform; and

judging from said recorded cumulative values whether or not the image of said object includes the character corresponding to said template table.

16. A method for character recognition according to claim 15, wherein said parameters stored in said template table define a gradient direction at each of the edge points of the image of said basic character pattern and a straight line connecting each of the edge points and a predetermined reference point and,

wherein said edge point detecting step includes detecting the coordinates of, and a gradient direction at, each of the edge points, and said parameter accessing step includes accessing from said template table said straight line defining parameters for the edge points having gradient directions approximately equal to the detected gradient directions.

17. A method for character recognition comprising the steps of:

generating a template table which includes parameters used for the Hough transform and extracted at edge points of a basic character pattern for character recognition;

dividing said template table into a plurality of partial template tables;

storing said partial template tables respectively in memories of a plurality of subprocessors capable of operating in parallel under the control of a main processor;

detecting, by said main processor, edge points of an image of an object including a character to be recognized said main processor having an index table indicating the correspondence between said partial template tables and said subprocessors;

operating said subprocessors in parallel so as to access from said partial template tables said parameters to be used for the generalized Hough transform of the detected edge points;

performing the generalized Hough transform by said subprocessors based upon said accessed parameters and the coordinates of said detected edge points;

transferring the coordinates generated by said transform from said subprocessors to said main processor;

recording cumulative values for said transferred coordinates by said main processor; and

judging from said recorded cumulative values whether or not the image of said object includes the character corresponding to said template table.

18. A method for character recognition according to claim 17, including compressing said generated template table so as to include only the parameters for the edge points of curved edge portions of the image of said basic character pattern.

19. A method for character recognition comprising the steps of:

generating a template table for each of a plurality of basic character patterns, which includes parameters representing a gradient direction at each of a plurality of edge points of an image of the character pattern and a straight line connecting each of the edge points and a predetermined reference point;

dividing said template tables into a plurality of partial template tables;

storing said partial template tables respectively in a plurality of subprocessors connected in parallel to one main processor;

detecting by said main processor the coordinates of, and a gradient direction at, each of the plurality of edge points of an image of an object including a character to be recognized;

supplying a template table number and each of said detected gradient directions from said main processor to a selected subprocessor having a partial template table including the detected gradient direction;

accessing by said selected subprocessor the parameters for an edge point having a gradient direction approximately equal to said detected gradient direction from said partial template table of the template table specified by said template table number;

performing the generalized Hough transform by said selected subprocessor based upon said accessed parameters and the coordinates of said detected edge point;

transferring the coordinates determined by said transform from said selected subprocessor to said main processor;

recording by said main processor cumulative values for said coordinates transferred from said subprocessor;

comparing said cumulative values with a predetermined threshold value for said specified template table; and

judging from the result of said comparison, whether or not the image of said object includes the character corresponding to said specified template table.

20. A method for character recognition according to claim 19, wherein said parameters represent the length of a straight line connecting each of the edge points and a predetermined reference point and an angle formed by each of said straight lines with a predetermined reference line.

21. A method for character recognition according to claim 19, wherein the entries of said template table are arranged in ascending order of said gradient directions before said dividing step.

22. A method for character recognition according to claim 21, wherein said main processor has an index table for each of said template tables, which indicates the correspondence between said partial template tables and said subprocessors for each of said template tables.

23. A method for character recognition according to claim 19, including said selected subprocessor accessing the parameters for an edge point having a gradient direction falling within a predetermined range of approximation to said detected gradient direction.

24. A method for character recognition according to claim 19, including compressing each said template table before said dividing step so as to include only said parameters for the edge points for curved edge portions of the image of said basic character pattern.