Techniques in optical character recognition

• US 8,189,961 B2
• Filed: 06/09/2010
• Issued: 05/29/2012
• Est. Priority Date: 06/09/2010
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nijemcevic, Djordje, Galic, Sasa
• Primary Examiner(s): Koziol, Stephen R
• Application Number:
  US12/797,219
• Publication Number:
  US 20110305393A1
• Time in Patent Office: 720 Days
• Field of Search: 382/100, 382/182, 382/198, 382/199, 382/266, 382/289, 382/292
• US Class Current: 382/292
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines

Abstract

An image deskew system and techniques are used in the context of optical character recognition. An image is obtained of an original set of characters in an original linear (horizontal) orientation. An acquired set of characters, which is skewed relative to the original linear orientation by a rotation angle, is represented by pixels of the image. The rotation angle is estimated, and a confidence value may be associated with the estimation, to determine whether to deskew the image. In connection with rotation angle estimation, an edge detection filter is applied to the acquired set of characters to produce an edge map, which is input to a linear hough transform filter to produce a set of output lines in parametric form. The output lines are assigned scores, and based on the scores, at least one output line is determined to be a dominant line with a slope approximating the rotation angle.

Claims

1. A computer-readable storage medium, not comprising a propagated data signal, encoded with computer-executable instructions which, when executed by a processor, perform a method for recognizing characters of an original set of characters displayed on a surface in an original linear orientation, the method comprising:

within an image of the original set of characters, identifying an acquired set of characters represented by pixels of the image, the acquired set of characters having an acquired linear orientation skewed relative to the original linear orientation by a rotation angle;

applying an edge detection filter to the acquired set of characters to produce an edge map, the edge map identifying edge pixels comprising pixels of the image lying along a plurality of lines associated with the acquired set of characters;

inputting the edge map to a linear hough transform filter to produce a set of output lines in (r, Θ

) parametric form, where for each output line, r is a length of a normal line drawn perpendicular to the output line between a point of origin and a particular edge pixel through which the output line passes, and Θ

is an angle the normal line forms to a horizontal axis;

forming a matrix having rows and columns, each of the edge pixels passed through by a particular output line (r, Θ

) being represented by an element of the matrix located at a particular row corresponding to Θ

of the particular output line and a particular column corresponding to r of the particular output line;

assigning a score to each output line, the score based on a dispersion of edge pixels within the particular row corresponding to Θ

of the particular output line;

based on the scores, within the set of output lines, identifying at least two dominant output lines, (rdom1, Θ

dom1) and (rdom2, Θ

dom2);

calculating a first confidence value corresponding to a likelihood that Θ

dom1 estimates the rotation angle;

calculating a second confidence value corresponding to a likelihood that Θ

dom2 estimates the rotation angle; and

based on the first and second confidence values, determining whether Θ

dom1 or Θ

dom2 estimates the rotation angle.

2. The computer-readable storage medium according to claim 1,

wherein calculating the first confidence value comprises determining a first dispersion of scores by dividing a sum of all scores by the score of the particular row corresponding to Θ

dom1,

wherein calculating the second confidence value comprises determining a second dispersion of scores by dividing the sum of all scores by the score of the particular row corresponding to Θ

dom2,

wherein when the first dispersion of scores is lower than the second dispersion of scores, deeming it likely that Θ

dom1 estimates the rotation angle, and

wherein when the second dispersion of scores is lower than the first dispersion of scores, deeming it likely that Θ

dom2 estimates the rotation angle.

3. The computer-readable storage medium according to claim 1, further comprising:

after determining whether Θ

dom1 or Θ

dom2 estimates the rotation angle, based on either the first confidence value or the second confidence value or both, determining whether to deskew the acquired set of characters by rotating the image back by the estimated rotation angle,

when either the first confidence value or the second confidence value or both are over a predetermined threshold, deskewing the acquired set of characters, and when either the first confidence value or the second confidence value or both are under the predetermined threshold, not deskewing the acquired set of characters.

4. A computer-readable storage medium, not comprising a propagated data signal, encoded with computer-executable instructions which, when executed by a processor, perform a method for recognizing characters of an original set of characters displayed on a surface in an original linear orientation, the method comprising:

identifying an image, acquired by an image capture device, of the original set of characters, the image having an acquired set of characters corresponding to the original set of characters, each character of the acquired set of characters represented by a group of pixels in the image, each pixel of the group having a grayscale value, the acquired set of characters having an acquired linear orientation skewed relative to the original linear orientation in an amount able to be expressed by a rotation angle;

within the image, identifying a portion of the acquired set of characters;

applying an edge detection filter to the portion of the acquired set of characters to produce an edge map, the edge map identifying, based on the grayscale values of pixels from groups of pixels representing characters within the portion, a set of edge pixels comprising pixels lying along a mean line or a base line of the characters within the portion;

inputting the edge map to a linear hough transform filter, the linear hough transform filter configured to produce a set of output lines in (r, Θ

) parametric form, where for each output line, r is a length of a normal line drawn perpendicular to the output line between a point of origin and a particular edge pixel through which the output line passes, and Θ

is an angle the normal line forms to a horizontal axis;

forming a matrix having a plurality of rows identified by row indices and a plurality of columns identified by column indices, each of the edge pixels passed through by a particular output line (r, Θ

) being represented by an element of the matrix located at a particular row index corresponding to Θ

of the particular output line and a particular column index corresponding to r of the particular output line;

based on a distribution of the elements within the matrix, assigning a score to at least some of the output lines;

based on the scores of the at least some of the output lines, identifying a dominant output line;

identifying the row index of the matrix associated with the dominant output line;

based on the identified row index, identifying the angle Θ

of the dominant output line; and

estimating the rotation angle based on the identified angle Θ

,

the original set of characters able to be decoded based at least in part on the estimated rotation angle.

5. The computer-readable storage medium according to claim 4, further comprising:

deskewing the acquired set of characters in an amount based on the estimated rotation angle in such a manner that the characters of the original set of characters are able to be recognized.

6. The computer-readable storage medium according to claim 4, further comprising:

calculating a confidence value, the confidence value a representation of a reliability of the estimated rotation angle, and

based on the confidence value, deciding whether to deskew the acquired set of characters.

7. The computer-readable storage medium according to claim 6, wherein assigning a score to at least some of the output lines comprises

assigning a score to at least some of the output lines based on a quantity of elements located on each of the at least some of the output lines,

the dominant output line having the most elements located thereon.

8. The computer-readable storage medium according to claim 7, wherein calculating the confidence value comprises

either normalizing the quantity of elements located on the dominant output line over an area of the image, or normalizing a number of edge pixels covered by the dominant output line over a width of the image, and

calculating the confidence value based on the normalizing.

9. The computer-readable storage medium according to claim 6, wherein the original set of characters and the acquired set of characters comprise a number of lines of text, the number of lines of text corresponding to multiple dominant output lines sharing the same row index, wherein the number of lines of text is approximated by counting local element maximas in the same row index, and wherein locations of the number of lines of text are determined by identifying, for each of the number of lines of text in the same row index, a column index and the corresponding normal line r.

10. The computer-readable storage medium according to claim 9, wherein deciding whether to deskew the acquired set of characters comprises

calculating the confidence value based on multiplying the number of lines of text by an inverse dispersion of the scores of the at least some of the output lines;

and

deciding whether to deskew based on both the estimated rotation angle and the confidence value.

11. The computer-readable storage medium according to claim 4, wherein assigning a score to at least some of the output lines comprises

assigning a score to at least some of the output lines based on a quantity of elements located on each of the at least some of the output lines,

the dominant output line having the most elements located thereon.

12. The computer-readable storage medium according to claim 4, wherein assigning a score to at least some of the output lines comprises

for at least some consecutive elements located in consecutive columns at the at least some of the row indices, computing a sum of squared differences of grayscale values of edge pixels associated with the consecutive elements located in consecutive columns, the score of a particular output line proportional to the computed sum,

the dominant output line having the maximum score.

13. The computer-readable storage medium according to claim 4, wherein assigning a score to at least some of the output lines comprises

for consecutive elements located in consecutive columns at the at least some of the row indices, computing a sum of squared differences of the number of consecutive elements located in consecutive columns, the score of a particular output line proportional to the computed sum,

the dominant output line having the maximum score.

14. The computer-readable storage medium according to claim 4,

wherein the image comprises a page having a plurality of regions, an acquired set of characters located in each region, the portion of the acquired set of characters being identified within each region, and

wherein the steps of

applying the edge detection filter to the portion of the acquired set of characters,

inputting the edge map to the linear hough transform filter,

forming the matrix,

assigning the score,

identifying the dominant output line,

identifying the row index,

identifying the angle Θ

of the dominant output line, and

estimating the rotation angle

are performed based on the portion of the acquired set of characters located in each region.

15. The computer-readable storage medium according to claim 14, wherein the plurality of regions comprise rectangular regions, evenly sampled across the height of the page.

16. The computer-readable storage medium according to claim 14, further comprising:

deskewing the acquired set of characters in an amount based on the estimated rotation angles associated with each region.

17. The computer-readable storage medium according to claim 16, wherein deskewing comprises

calculating confidence values representing the reliability of the estimated rotation angles associated with different regions;

using the calculated confidence values as weighting factors to estimate a page rotation angle; and

deskewing the page in an amount based on the estimated page rotation angle.

18. The computer-readable storage medium according to claim 4, wherein the edge detection filter comprises a Sobel convolution kernel filter.

19. A system for recognizing characters of an original set of characters displayed on a surface in an original linear orientation, the system comprising:

a computer-readable storage medium, not comprising a propagated data signal; and

a processor responsive to the computer-readable storage medium and to one or more computer programs stored in the computer-readable storage medium, the one or more computer programs, when loaded into the processor and executed, operable to perform a method comprising;

identifying an image, acquired by an image capture device, of the original set of characters, the image having an acquired set of characters corresponding to the original set of characters, each character of the acquired set of characters represented by a group of pixels in the image, each pixel of the group having a grayscale value, the acquired set of characters having an acquired linear orientation skewed relative to the original linear orientation in an amount able to be expressed by a rotation angle,

within the image, identifying a portion of the acquired set of characters;

applying an edge detection filter to the portion of the acquired set of characters to produce an edge map, the edge map identifying, based on the grayscale values of pixels from groups of pixels representing characters within the portion, a set of edge pixels comprising pixels lying along a mean line or a base line of the characters within the portion,

inputting the edge map to a linear hough transform filter, the linear hough transform filter configured to produce a set of output lines in (r, Θ

) parametric form, where for each output line, r is a length of a normal line drawn perpendicular to the output line between a point of origin and a particular edge pixel through which the output line passes, and Θ

is an angle the normal line forms to a horizontal axis,

forming a matrix having a plurality of rows identified by row indices and a plurality of columns identified by column indices, each of the edge pixels passed through by a particular output line (r, Θ

) being represented by an element of the matrix located at a particular row index corresponding to Θ

of the particular output line and a particular column index corresponding to r of the particular output line,

based on a distribution of the elements within the matrix, assigning a score to at least some of the output lines,

based on the assigned scores, identifying a dominant output line;

identifying the row index of the matrix associated with the dominant output line,

based on the identified row index, identifying the angle Θ

of the dominant output line, and

estimating the rotation angle based on the identified angle Θ

,

the original set of characters able to be decoded based at least in part on the estimated rotation angle.

20. The system according to claim 19, wherein the processor is associated with an operating environment selected from the group comprising:

a network-side operating environment and a client-side operating environment.