Method and apparatus for determination of text orientation

• US 7,286,718 B2
• Filed: 01/26/2004
• Issued: 10/23/2007
• 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): Wu, Jingge
• Assistant Examiner(s): BLOOM, NATHAN J
• Application Number:
  US10/764,655
• Publication Number:
  US 20050163399A1
• Time in Patent Office: 1,366 Days
• Field of Search: 382203-204, 382289-290, 382/276, 382/181
• 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. Method for determining orientation of an image, said method comprising the steps of:

obtaining a plurality of text characters from at least a portion of said image;

determining a direction in which each of said text characters opens; and

determining the orientation of said image based on said directions in which said plurality of text characters open.

2. The method of claim 1, wherein said obtaining step comprises:

segmenting each of said plurality of text characters out of an image background to define a respective character region having a plurality of rows and columns of pixels.

3. The method of claim 2, wherein said segmenting step is performed using a connected component analysis.

4. The method of claim 2, wherein said segmenting step further comprises cropping a bottom row of pixels and a top row of pixels from each character region.

5. The method of claim 2, wherein said step of determining a direction in which each of said text characters opens comprises:

analyzing at least a portion of said character region to determine a degree to which the respective text character opens toward a first direction;

analyzing at least a portion of said character region to determine a degree to which the respective text character opens toward a second direction; and

comparing said degrees to which the respective text character opens toward said first and second directions to determine a single direction toward which the respective text character opens.

6. The method of claim 5, wherein the step of determining the degree to which the respective text character opens toward said first direction comprises the steps of:

counting a total quantity of background pixels recursively connected with background pixels of a column located furthest to the first direction to obtain a first numerical value indicative of the degree to which said respective text character opens toward said first direction.

7. The method of claim 6, wherein the step of determining the degree to which the respective text character opens toward said second direction comprises the steps of:

counting a total quantity of background pixels recursively connected with background pixels of a column located furthest to the second direction to obtain a second numerical value indicative of the degree to which said respective text character opens toward said second direction.

8. The method of claim 7, further comprising the steps of:

calculating, for each of said text characters, a ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction;

calculating, for each of said text characters, a ratio of the degree to which said text character opens toward said first direction over the degree to which said text character opens toward said second direction;

calculating, for each of said text characters, a difference between the degree to which said text character opens toward said second direction and the degree to which said text character opens toward said first direction; and

calculating, for each of said text characters, a difference between the degree to which said text character opens toward said first direction and the degree to which said text character opens toward said second direction.

9. The method of claim 8, further comprising:

concluding that a text character opens toward said second direction if a first set of conditions is met, said first set of conditions comprising;

said ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction is greater than a first predefined threshold; and

said difference between the degree to which said text character opens toward said second direction and the degree to which said text character opens toward said first direction is greater than a predefined fraction of said text character'"'"'s respective character region;

concluding that said text character opens toward said first direction if a second set of conditions is met, said second set of conditions comprising;

said ratio of the degree to which said text character opens toward said first direction over the degree to which said text character opens to toward said second direction is greater than said first predefined threshold; and

said difference between the degree to which said text character opens toward said first direction and the degree to which said text character opens toward said second direction is greater than said predefined fraction of said text character'"'"'s respective character region; and

concluding that said text character is weakly directional if neither the first nor second set of conditions is met.

10. The method of claim 9, wherein said first predefined threshold is 2.5.

11. The method of claim 9, wherein said predefined fraction is 1/10.

12. The method of claim 5, wherein said step of determining an orientation of said image further comprises:

calculating a quantity of text characters in said at least a portion of said image that opens toward said second direction;

calculating a quantity of text characters in said at least a portion of said image that opens toward said first direction;

concluding that said image is orientated upside down if a ratio of said quantity of text characters in said at least a portion of said image that open toward said second direction over said quantity of text characters in said at least a portion of said image that open toward said first direction is greater than a second predefined threshold; and

concluding that said image is orientated right side up if a ratio of said quantity of text characters in said at least a portion of said image that open toward said first direction over said quantity of text characters in said at least a portion of said image that open toward said second direction is greater than said second predefined threshold.

13. The method of claim 12, wherein said second predefined threshold is 2.

14. The method of claim 1, wherein said step of determining a direction in which each of the text characters opens comprises the steps of:

providing a set of training images;

orientating said set of training images right side up; and

determining a direction in which said training images exhibit a dominant directional property.

15. The method of claim 14, wherein said step of determining a direction in which said set of training images exhibit a dominant directional property 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.

16. The method of claim 8, further comprising the steps of:

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

calculating, for each of said text characters, the absolute difference between the degree to which said text character opens toward said second direction and the degree to which said text character opens toward said first direction; and

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

17. The method of claim 16, further comprising the 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 is 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 (the ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction) equals zero.

18. The method of claim 17, further comprising the steps of:

concluding that a character directionality as indicated by the ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction will not yield an accurate determination of character orientation in a respective 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 image based on a character directionality as indicated by the ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction, if an extent to which said first and second histograms overlap does not exceed the third predefined threshold.

19. The method of claim 18, wherein the third predefined threshold is 0.3.

20. The method of claim 18, wherein the step of determining the orientation of said image comprises:

concluding that a text character opens toward said second direction if a first set of conditions is met, said first set of conditions comprising;

said ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction is greater than a first predefined threshold; and

said difference between the degree to which said text character opens toward said second direction and the degree to which said text character opens toward said first direction is greater than a predefined fraction of said text character'"'"'s respective character region;

concluding that said text character opens toward said first direction if a second set of conditions is met, said second set of conditions comprising;

said ratio of the degree to which said text character opens toward said first direction over the degree to which said text character opens to toward said second direction is greater than said first predefined threshold; and

said difference between the degree to which said text character opens toward said first direction and the degree to which said text character opens toward said second direction is greater than said predefined fraction of said text character'"'"'s respective character region; and

concluding that said text character is weakly directional if neither the first nor second set of conditions is met.

21. The method of claim 20, wherein said step of determining an orientation of said image further comprises:

calculating a quantity of text characters in said at least a portion of said image that open toward said second direction;

calculating a quantity of text characters in said at least a portion of said image that open toward said first direction;

concluding that said image is orientated upside down if a ratio of said quantity of text characters in said at least a portion of said image that open toward said second direction over said quantity of text characters in said at least a portion of said image that open toward said first direction is greater than a second predefined threshold; and

concluding that said image is orientated right side up if a ratio of said quantity of text characters in said at least a portion of said image that open toward said first direction over said quantity of text characters in said at least a portion of said image that open toward said second direction is greater than said second predefined threshold.

22. A computer readable medium containing an executable program for determining the orientation of an image, where the program performs the steps of:

obtaining a plurality of text characters from at least a portion of said image;

determining a direction in which each of said text characters opens; and

determining the orientation of said image based on said directions in which said plurality of text characters open.

23. The computer readable medium of claim 22, wherein said obtaining step comprises:

segmenting each of said plurality of text characters out of an image background to define a respective character region having a plurality of rows and columns of pixels.

24. The computer readable medium of claim 23, wherein said segmenting step is performed using a connected component analysis.

25. The computer readable medium of claim 23, wherein said segmenting step further comprises cropping a bottom row of pixels and a top row of pixels from each character region.

26. The computer readable medium of claim 22, wherein said step of determining a direction in which each of said text characters opens comprises:

analyzing at least a portion of said character region to determine a degree to which the respective text characters open toward a first direction;

analyzing at least a portion of said character region to determine a degree to which the respective text character open toward a second direction; and

comparing said degrees to which the respective text character opens toward said first and second directions to determine a single direction toward which the respective text character opens.

27. The computer readable medium of claim 26, wherein the step of determining the degree to which the respective text character opens toward said first direction comprises the steps of:

counting a total quantity of background pixels recursively connected with a column located furthest to the first direction to obtain a first numerical value indicative of the degree to which said respective text character opens toward said first direction.

28. The computer readable medium of claim 27, wherein the step of determining the degree to which the respective text character opens toward said second direction further comprises the steps of:

counting a total quantity of background pixels recursively connected with a column located furthest to the second direction to obtain a second numerical value indicative of the degree to which said respective text character opens toward said second direction.

29. The computer readable medium of claim 28, further comprising the steps of:

calculating, for each of said text characters, a ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction;

calculating, for each of said text characters, a ratio of the degree to which said text character opens toward said first direction over the degree to which said text character opens toward said second direction;

calculating, for each of said text characters, a difference between the degree to which said text character opens toward said second direction and the degree to which said text character opens toward said first direction; and

calculating, for each of said text characters, a difference between the degree to which said text character opens toward said first direction and the degree to which said text character opens toward said second direction.

30. The computer readable medium of claim 29, further comprising:

concluding that a text character opens toward said second direction if a first set of conditions is met, said first set of conditions comprising;

said ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction is greater than a first predefined threshold; and

said difference between the degree to which said text character opens toward said second direction and the degree to which said text character opens toward said first direction is greater than a predefined fraction of said text character'"'"'s respective character region;

concluding that said text character opens toward said first direction if a second set of conditions is met, said second set of conditions comprising;

said ratio of the degree to which said text character opens toward said first direction over the degree to which said text character opens to toward said second direction is greater than said first predefined threshold; and

said difference between the degree to which said text character opens toward said first direction and the degree to which said text character opens toward said second direction is greater than said predefined fraction of said text character'"'"'s respective character region; and

concluding that said text character is weakly directional if neither the first nor second set of conditions is met.

31. The computer readable medium of claim 30, wherein said first predefined threshold is 2.5.

32. The computer readable medium of claim 30, wherein said predefined fraction is 1/10.

33. The computer readable medium of claim 26, wherein said step of determining an orientation of said image further comprises:

calculating a quantity of text characters in said at least a portion of said image that opens toward said second direction;

calculating a quantity of text characters in said at least a portion of said image that opens toward said first direction;

concluding that said image is orientated upside down if a ratio of said quantity of text characters in said at least a portion of said image that open toward said second direction over said quantity of text characters in said at least a portion of said image that open toward said first direction is greater than a second predefined threshold; and

concluding that said image is orientated right side up if a ratio of said quantity of text characters in said at least a portion of said image that open toward said first direction over said quantity of text characters in said at least a portion of said image that open toward said second direction is greater than said second predefined threshold.

34. The computer readable medium of claim 33, wherein said second predefined threshold is 2.

35. The computer readable medium of claim 22, wherein said step of determining a direction in which each of said text characters opens comprises the steps of:

providing a set of training images;

orientating said set of training images right side up; and

determining a direction in which said training images exhibit a dominant directional property.

36. The computer readable medium of claim 35, wherein said step of determining a direction in which said training images exhibit a dominant directional property 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.

37. The computer readable medium of claim 29, further comprising the steps of:

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

calculating, for each of said text characters, the absolute difference between the degree to which said text character opens toward said second direction and the degree to which said text character opens toward said first direction; and

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

38. The computer readable medium of claim 37, further comprising the 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 is 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 (the ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction) equals zero.

39. The computer readable medium of claim 38, further comprising the steps of:

concluding that a character directionality as indicated by the ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction will not yield an accurate determination of character orientation in a respective 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 image based on a character directionality as indicated by the ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction, if an extent to which said first and second histograms overlap does not exceed the third predefined threshold.

40. The computer readable medium of claim 39, wherein the third predefined threshold is 0.3.

41. The computer readable medium of claim 39, wherein the step of determining the orientation of said image further comprises:

concluding that a text character opens toward said second direction if a first set of conditions is met, said first set of conditions comprising;

said ratio of the degree to which said text character opens toward said second direction over the degree to which said text character opens toward said first direction is greater than a first predefined threshold; and

said difference between the degree to which said text character opens toward said second direction and the degree to which said text character opens toward said first direction is greater than a predefined fraction of said text character'"'"'s respective character region;

concluding that said text character opens toward said first direction if a second set of conditions is met, said second set of conditions comprising;

said ratio of the degree to which said text character opens toward said first direction over the degree to which said text character opens to toward said second direction is greater than said first predefined threshold; and

said difference between the degree to which said text character opens toward said first direction and the degree to which said text character opens toward said second direction is greater than said predefined fraction of said text character'"'"'s respective character region; and

concluding that said text character is weakly directional if neither the first nor second set of conditions is met.

42. The computer readable medium of claim 41 wherein said step of determining an orientation of said image further comprises:

calculating a quantity of text characters in said at least a portion of said image that opens toward said second direction;

calculating a quantity of text characters in said at least a portion of said image that opens toward said first direction;

concluding that said image is orientated upside down if a ratio of said quantity of text characters in said at least a portion of said image that open toward said second direction over said quantity of text characters in said at least a portion of said image that open toward said first direction is greater than a second predefined threshold; and

concluding that said image is orientated right side up if a ratio of said quantity of text characters in said at least a portion of said image that open toward said first direction over said quantity of text characters in said at least a portion of said image that open toward said second direction is greater than said second predefined threshold.