Processing means for use in an optical character recognition system

• US 4,918,740 A
• Filed: 07/21/1989
• Issued: 04/17/1990
• Est. Priority Date: 10/01/1985
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: The Palantir Corp. (Microsoft Corporation)
• Inventors: Ross, David J.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Covso, Jose L.
• Application Number:
  US07/384,053
• Time in Patent Office: 270 Days
• Field of Search: 382/9, 382/13, 382/22, 382/25, 382/40, 382/45, 382/47, 382/48, 382/61, 382/69, 390/730, 390/731, 364/521, 364/523
• US Class Current: 382/177
• CPC Class Codes: G06V 30/242 Division of the character sequences into groups prior to recognition; Selection of dictionaries

Abstract

Means is provided for use in an optical character recognition system to narrow the possible characters associated with a given unknown input character, primarily based upon subline information. This means also serves to add to the possibility set additional possible characters, and to determine point sizes for each character. In the event that the subline information provided is erroneous, the subline information is corrected.

Claims

1. The method of analyzing character information consisting of pixel data and subline information of unknown characters to determine the character type of each of said unknown characters, said method comprising the steps of:

fetching a plurality of character information segments, each representing a character and including subline information consisting of the location of that character'"'"'s ascender line, lowercase line, base line, and descender line with respect to the pixels forming that character;

for a selected one of said character information segments, determining if said subline information is accurate based upon comparison with the subline information of a selected one of said character information segments;

providing accurate subline information by resetting said subline information of said selected one of said character information segments, with respect to the pixels forming that character, if inaccurate, without altering the subline information of character information segments corresponding to adjacent characters; and

using said accurate subline information to determine the character type of said selected one of said character information segments.

2. The method as in claim 1 wherein the step of resetting said subline information is performed by utilizing the height of the character and information regarding the character'"'"'s type.

3. The method of claim 2 wherein the character'"'"'s type is selected from the group of character types consisting of:

"A" type characters, wherein the topmost pixel of the character corresponds to the ascender subline and the bottommost pixel of the character corresponds to the base subline;

"a" type characters, wherein the topmost pixel of the character corresponds to the lowercase subline and the bottommost pixel of the character corresponds to the base subline; and

"q" type characters, wherein the topmost pixel of the character corresponds to the lowercase subline and the bottommost pixel of the character corresponds to the descender subline.

4. The method of claim 1 wherein said selected one of said character information segments has known accurate subline information.

5. The method of claim 1 wherein said selected one of said character information segments and said selected one of said character information segments which is being reset are located within said plurality of character information segments on the same side of the largest gap located between two adjcent character information segments which in turn are located between two character information segments having accurate subline information.

6. The method of claim analyzing character information consisting of pixel data and subline information of unknown characters to determine the character type of each of said unknown characters, said method comprising the steps of:

fetching a plurality of character information segments, each representing a character and including subline information consisting of the location of that character'"'"'s ascender line, lowercase line, base line, and descender line with respect to the pixels forming that character;

for a selected one of said character information segments, determining if said subline information is accurate based upon comparison with the subline information of a selected one of said character information segments;

providing accurate subline information by resetting said subline information of said selected one of said character information segments, with respect to the pixels formming that character, if inaccurate; and

using said accurate subline information to determine the character type of said selected one of said character information segments,

wherein the subline spacings of the characters are used to access a histogram of subline spacings defined, at least in part, by the subline spacings of said plurality of character information segments in order to locate a relative maximum for use in resetting the subline information.

7. The method of claim 6 wherein said histogram is an "a" character type histogram maintained for the occurrences of values of distance between the base subline and lowercase subline for each "a" type character wherein the topmost pixel of the character corresponds to the lowercase subline and the bottommost pixel of the character corresponds to the base subline.

8. The method of claim 7 wherein the "a" character type histogram is scanned over a range of approximately 0.6 h to 0.7 h, where h is an "A" type character'"'"'s height, to locate a relative maximum for use as the distance between the lowercase subline and the base subline on the "A" type character wherein the topmost pixel of the character corresponds to the ascender subline and the bottommost pixel of the character corresponds to the base subline.

9. The method of claim 8 wherein, if a relative maximum is not located, the "a" character type height histogram is scanned over a range of approximately 0.5 h to 0.85 h to locate a relative maximum.

10. The method of claim 9 wherein 0.67 h is used as a maximum if a relative maximum is not found.

11. The method of claim 6 wherein said histogram is an "A" character type histogram maintained for the occurrence of values of distance between the ascender subline and base sublines for each "A" type character wherein the topmost pixel of the character corresponds to the ascender subline and the bottommost pixel of the character corresponds to the base subline.

12. The method of claim 11 wherein the "A" character type height histogram is scanned over a range of approximately d/0.6 to d/0.7, where d is an "a" type character'"'"'s height, to locate a relative maximum for use as the distance between the ascender subline and the base subline on the "a" type character.

13. The method of claim 12 wherein, if a relative maximum is not located, the "A" character type height histogram is scanned over a range of approximately d/0.5 to d/0.85 to locate a relative maximum.

14. The method of claim 13 wherein d/0.67 is used as a maximum if a relative maximum is not found.

15. The method as in claim 6 wherein said step of providing accurate subline information is performed without altering the subline information of character information segments corresponding to adjacent characters.

16. The method of determining point size of an optically read character based upon detected pixel location within said character, comprising the steps of:

obtaining a data set defining the pixel locations of said optically read character;

using said pixel locations to determine subline information for said optically read character, said subline information comprising ascender line, lowercase line, base line, and descender line;

using said subline information to find a relative maximum in a character height histogram defining the heights of a plurality of characters; and

using said relative maximum to define point size.

17. The method of claim 16 wherein said relative maximum is divided by a constant to define point size.

18. The method of claim 17 wherein said constant is 2.9 when one pixel is equal to 1/300 inch.

19. The method of claim 17 wherein said relative maximum is used to perform a table look-up operation to define point size.

20. The method of claim 16 wherein point size variations between adjacent characters must be greater than a selected amount to be considered a valid variation in point size.

21. The method of claim 20 wherein said selected amount is one point size.

22. The method of claim 20 wherein said selected amount is a selected fraction of the point size calculated for the previous character.

23. The method of claim 22 wherein said selected fraction is one fourth.