Method and apparatus for determination of text orientation

• US 7,657,120 B2
• Filed: 08/24/2007
• Issued: 02/02/2010
• Est. Priority Date: 01/26/2004
• Status: Expired due to Fees

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Aradhye, Hrishikesh B.
• Primary Examiner(s): Mehta, Bhavesh M
• Assistant Examiner(s): BLOOM, NATHAN J
• Application Number:
  US11/844,555
• Publication Number:
  US 20080175516A1
• Time in Patent Office: 893 Days
• Field of Search: None
• US Class Current: 382/290
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1463 Orientation detection or correction, e.g. rotation of multiples of 90 degrees

Abstract

The present invention relates to a method for determining the orientation of text, so that the text can be correctly read. In one embodiment, the method analyzes the “open” portions of text characters to determine in which direction the open portions face. By determining the respective densities of characters opening in each direction (e.g., right or left), the method can establish in which direction the text as a whole is orientated. The present invention may be adapted for use in automated mail processing, to determine the orientation of checks in automated teller machine envelopes, or the orientation of scanned or copied documents, or documents sent via facsimile, or to determine the orientation of digital photographs that include text (e.g., road signs, business cards, driver'"'"'s licenses, etc.), among other applications. A fast, substantially automatic determination of text orientation according to the present invention will reduce the labor expense and processing delay required for manual orientation.

Claims

1. A method for determining a dominant character orientation for a given script, comprising steps of:

using a processor to perform steps comprising;

providing a set of training images of said script;

orientating said set of training images right side up;

calculating a first value representing a degree to which characters in said set of training images open toward a first direction;

calculating a second value representing a degree to which characters in said set of training images open toward a second direction orientated oppositely from said first direction;

determining, in accordance with said first value and said second value, a direction in which said training images exhibit a dominant directional property, wherein said determining comprises;

specifying a first direction of interest, wherein an axis of said first direction of interest forms a first angle with respect to a horizontal axis; and

rotating said set of training images by a second angle, said second angle being a negative of said first angle, to orientate said first direction of interest horizontally;

initializing a set of character directionality values to an empty set;

calculating, using the processor, for each individual text character in said set of training images, an absolute difference between the first value and the second value; and

appending said set of character directionality values by a value of log (ratio of the first value over the second value), if said absolute difference is greater than a predefined fraction of a respective character region of said individual text character; and

storing information associating said script and said dominant directional property in a device that performs an orientation correction on documents including text.

2. The method of claim 1, further comprising steps of:

specifying a second direction of interest to investigate if said set of character directionality values is still an empty set;

constructing a first histogram of elements in said set of character directionality values if said set of character directionality values is not empty; and

constructing a second histogram, said second histogram being a mirror of said first histogram at log (ratio of the first value over the second value) equals zero.

3. The method of claim 2, further comprising steps of:

concluding that a character directionality as indicated by the ratio of the first value over the second value will not yield an accurate determination of character orientation in said first direction of interest, if an extent to which said first and second histograms overlap exceeds a third predefined threshold; and

determining the orientation of said text based on a character directionality as indicated by the ratio of the first value over the second value, if an extent to which said first and second histograms overlap does not exceed the third predefined threshold.

4. The method of claim 3, wherein the third predefined threshold is 0.3.

5. The method of claim 3, further comprising step of:

specifying a third direction of interest to investigate if a character directionality as indicated by the ratio of the first value over the second value will not yield an accurate determination of character orientation in said first direction of interest.

6. A computer readable storage medium containing an executable program for determining a dominant character orientation for a given script, where the program performs steps of:

providing a set of training images of said script;

orientating said set of training images right side up;

calculating a first value representing a degree to which characters in said set of training images open toward a first direction;

calculating a second value representing a degree to which characters in said set of training images open toward a second direction orientated oppositely from said first direction;

determining, in accordance with said first value and said second value, a direction in which said training images exhibit a dominant directional property, wherein said determining comprises;

specifying a first direction of interest, wherein an axis of said first direction of interest forms a first angle with respect to a horizontal axis; and

rotating said set of training images by a second angle, said second angle being a negative of said first angle, to orientate said first direction of interest horizontally;

initializing a set of character directionality values to an empty set;

calculating, for each individual text character in said set of training images, an absolute difference between the first value and the second value; and

appending said set of character directionality values by a value of log (ratio of the first value over the second value), if said absolute difference is greater than a predefined fraction of a respective character region of said individual text character; and

storing information associating said script and said dominant directional property in a device that performs an orientation correction on documents including text.

7. The computer readable medium of claim 6, further comprising steps of:

specifying a second direction of interest to investigate if said set of character directionality values is still an empty set;

constructing a first histogram of elements in said set of character directionality values if said set of character directionality values is not empty; and

constructing a second histogram, said second histogram being a mirror of said first histogram at log (ratio of the first value over the second value) equals zero.

8. The computer readable medium of claim 7, further comprising steps of:

concluding that a character directionality as indicated by the ratio of the first value over the second value will not yield an accurate determination of character orientation in said first direction of interest, if an extent to which said first and second histograms overlap exceeds a third predefined threshold; and

determining the orientation of said text based on a character directionality as indicated by the ratio of the first value over the second value, if an extent to which said first and second histograms overlap does not exceed the third predefined threshold.

9. The computer readable medium of claim 8, further comprising step of:

specifying a third direction of interest to investigate if a character directionality as indicated by the ratio of the first value over the second value will not yield an accurate determination of character orientation in said first direction of interest.

10. A computer readable medium containing an executable program for determining a dominant character orientation for a given script, where the program performs steps of:

providing a set of training images of said script;

orientating said set of training images right side up;

determining a direction in which said set of training images exhibit a dominant directional property, wherein said determining step comprises;

specifying a first direction of interest, wherein an axis of said first direction of interest forms a first angle with respect to a horizontal axis; and

rotating said set of training images by a second angle, said second angle being a negative of said first angle, to orientate said first direction of interest horizontally;

initializing a set of character directionality values to an empty set;

calculating, for each individual text character in said set of training images, an absolute difference between a degree to which said individual text character opens toward a first direction and a degree to which said individual text character opens toward a second direction orientated oppositely from said first direction; and

appending said set of character directionality values by a value of log (ratio of the degree to which said individual text character opens toward said first direction over the degree to which said individual text character opens toward said second direction), if said absolute difference is greater than a predefined fraction of a respective character region of said individual text character.

11. The computer readable medium of claim 10, further comprising steps of:

specifying a second direction of interest to investigate if said set of character directionality values is still an empty set;

constructing a first histogram of elements in said set of character directionality values if said set of character directionality values is not empty; and

constructing a second histogram, said second histogram being a mirror of said first histogram at log (ratio of the degree to which said individual text character opens toward said first direction over the degree to which said individual text character opens toward said second direction) equals zero.

12. The computer readable medium of claim 11, further comprising steps of:

concluding that a character directionality as indicated by the ratio of the degree to which said individual text character opens toward said first direction over the degree to which said individual text character opens toward said second direction will not yield an accurate determination of character orientation in said first direction of interest, if an extent to which said first and second histograms overlap exceeds a third predefined threshold; and

determining the orientation of said text based on a character directionality as indicated by the ratio of the degree to which said individual text character opens toward said first direction over the degree to which said individual text character opens toward said second direction, if an extent to which said first and second histograms overlap does not exceed the third predefined threshold.

13. The computer readable medium of claim 12, further comprising step of:

specifying a second direction of interest to investigate if a character directionality as indicated by the ratio of the degree to which said individual text character opens toward said first direction over the degree to which said individual text character opens toward said second direction will not yield an accurate determination of character orientation in said first direction of interest.