Method and apparatus for identifying the rotation angle and bounding rectangle of a digitized form

• US 20080018941A1
• Filed: 07/11/2006
• Published: 01/24/2008
• Est. Priority Date: 07/11/2006
• Status: Active Grant

• Current Assignee: Accusoft Corporation
• Original Assignee: Pegasus Imaging Corporation (Accusoft Corporation)
• Inventors: Taylor, Garland S.
• Granted Patent: US 7,817,854 B2
• Time in Patent Office: Days
• US Class Current: 358/3.27
• CPC Class Codes: H04N 1/3878 Skew detection or correction
• CPC Class Codes: H04N 1/409 Edge or detail enhancement; Noise or error suppression

Abstract

Methods and apparatus for determining the skew angle of a digitized form scanned at an angle to the original page are described. The method determines a rotation angle and a boundary rectangle of best fit. Sections of the digital image in the form of thin strips are examined for the boundary between the page and the region of the scanned image beyond the original page. The Hough transform is employed to determined candidate edge line segments for the page from the sets of perimeter points. These line segments are then combined to select the best rectangle enclosing the page, from which the skew angle is determined. The algorithm also determines a rotated bounding box enclosing the page. An innovation of the invention is the use of fuzzy logic, whereby several candidates for perimeter points, candidate edges, and bounding rectangles are determined in each step of the computation with associated confidence values and the final skew angle is selected by choosing the bounding rectangle with the highest confidence values.

Claims

1. A method of processing an image represented by a plurality of pixel values, each pixel value corresponding to a pixel element, the method comprising:

generating for each of a plurality of first bands of pixel values in said image, a first set of first histogram values, said first bands extending in a first direction, each first histogram value corresponding to a set of pixel values extending in a second direction perpendicular to said first direction; and

analyzing at least some of the first set of histogram values to determine for each analyzed first set of histogram values a location of a first image edge and a first confidence value corresponding to the determined first image edge location.

2. The method of processing an image of claim 1, wherein said analyzing to determine a location of a first image edge generates a first set of first image edge locations and corresponding edge location confidence values, the method further comprising:

determining from the first set of image edge locations and corresponding confidence values, a first possible image edge line.

3. The method of claim 2, wherein determining from the first set of image edge locations and corresponding confidence values, a first possible image edge line includes giving greater weight to determined first image edge locations corresponding to bands closer to the center of the image than to bands located further away from the center of the image when making said first possible image edge line determination.

4. The method of processing an image of claim 2, further comprising:

analyzing at least some of the first set of histogram values to determine for each analyzed first set of histogram values a location of a second image edge and a second confidence value corresponding to the determined second image edge location.

5. The method of claim 4,

wherein said analyzing to determine a location of a second image edge generates a second set of first image edge locations and corresponding edge location confidence values;

and

wherein the method further comprises;

determining from the second set of image edge locations and corresponding confidence values, a second possible image edge line.

6. The method of claim 5, wherein, said first and second image edge locations correspond to different sides of the analyzed first band.

7. The method of claim 5, wherein determining from the second set of image edge locations and corresponding confidence values, a second possible image edge line includes giving greater weight to determined second image edge locations corresponding to bands closer to the center of the image than to bands located further away from the center of the image when making said second possible image edge line determination.

8. The method of claim 5, further comprising:

generating for each of a plurality of second bands of pixel values in said image, a second set of histogram values, said second bands extending in a second direction which is perpendicular said first direction, each second histogram value corresponding to a set of pixel values extending in said first direction; and

analyzing at least some of the second set of histogram values to determine for each analyzed second set of histogram values a location of a third image edge and a third confidence value corresponding to the determined third image edge location.

9. The method of claim 8, wherein said analyzing at least some of the second set of histogram values generates a third set of image edge locations and third set of corresponding edge location confidence values, the method further comprising:

determining from the third set of image edge locations and corresponding confidence values, a third possible image edge line.

10. The method of claim 9, wherein determining from the second set of image edge locations and corresponding confidence values, a third possible image edge line includes giving greater weight to determined third image edge locations corresponding to bands closer to the center of the image than to bands located further away from the center of the image when making said third possible image edge line determination.

11. The method of claim 9, further comprising

determining from the third set of image edge locations and corresponding confidence values, a fourth possible image edge.

12. The method of claim 11, further comprising:

determining at least a fifth, a sixth, seventh and eighth possible image edge line, said fifth and sixth possible image edges extending primarily in said second direction and said seventh and eight possible image edges extending primarily in said first direction.

13. The method of claim 12, further comprising:

selecting a set of four possible edges lines from a set of possible edge lines including at least said set of eight possible edge lines as a function of which combination of edge lines in said set of possible edge lines is determined to most probably correspond to the shape of a scanned image.

14. The method of claim 13, wherein said selecting of a set of four possible edge lines includes considering how parallel to one another pairs of edge lines extending in the same general direction are.

15. The method of claim 13, wherein selecting of a set of four possible edge lines includes considering how closely pairs of edge lines extending in different directions come to forming a perpendicular intersection.

16. The method of claim 13, further comprising:

determining an image skew angle from the selected set of four possible edge lines.

17. The method of claim 16, further comprising:

determining, from the determined image skew angle, a bounding box for a printed area included in said image.

18. The method of claim 17, wherein said determining of a bounding box is based on points at which pairs of selected possible edge lines in said selected set of four possible edge lines intersect.

19. The method of claim 1, wherein the first image edge corresponds to a detected image parameter point.

20. The method of processing an image of claim 1, wherein said analyzing to determine a location of a first image edge generates a first set of first image edge locations and corresponding edge location confidence values, the method further comprising:

determining from the first set of image edge locations and corresponding confidence values, a first possible image edge line and a first line confidence value corresponding to said first possible image edge line; and

determining from the first set of image edge locations and corresponding confidence values, a second possible image edge line and a second line confidence value corresponding to said second possible image edge line.

21. The method of claim 20,

wherein said steps of determining from the first set of image edge locations and corresponding confidence values a first possible edge line and a first line confidence value, and a second possible edge line and a second line confidence value, include:

giving lower line confidence values to determined edge lines having the same characteristics but located closer to the center of the image than to edge lines located further away from the center of the image.

22. The method of claim 20,

wherein said steps of determining from the first set of image edge locations and corresponding confidence values, a first possible edge line and a first line confidence value, and a second possible edge line and a second line confidence value, include:

applying a lower weight to line confidence values closer to the center of the image than determined edge lines further away from the center of the image.

23. The method of claim 22, wherein said first and second edge possible lines correspond to the same side of an image, the method further comprising:

determining from the first set of image edge locations and corresponding confidence values, a third and further possible edge lines and corresponding third and fourth edge line confidence values, respectively, the thirds and fourth edge lines being located on an image edge positioned opposite said first and second possible edge lines.

24. A method of processing image data, method comprising:

selecting, from a set of possible edge lines including at least said set of eight possible edge lines, a set of four possible edges lines as a function of which combination of edge lines in said set of possible edge lines is determined to most probably correspond to the shape of a scanned image; and

performing one of;

i) outputting information indicating the selected set of four edge lines, ii) storing information indicating the selected set of four edge lines and iii) using the selected set of four edge lines in an image processing operation..

25. The method of claim 24, wherein said selecting of a set of four possible edge lines includes considering how parallel to one another pairs of edge lines extending in the same general direction are.

26. The method of claim 24, wherein selecting of a set of four possible edge lines includes considering how closely pairs of edge lines extending in different directions come to forming a perpendicular intersection.

27. The method of claim 24, further comprising:

determining an image skew angle from the selected set of four possible edge lines.

28. The method of claim 27, further comprising:

determining, from the determined image skew angle, a bounding box for a printed area included in said image.

29. The method of claim 28, wherein said determining of a bounding box is based on points at which pairs of selected possible edge lines in said selected set of four possible edge lines intersect.

30. An apparatus for processing an image represented by a plurality of pixel values, each pixel value corresponding to a pixel element, the apparatus comprising:

means for generating for each of a plurality of first bands of pixel values in said image, a first set of first histogram values, said first bands extending in a first direction, each first histogram value corresponding to a set of pixel values extending in a second direction perpendicular to said first direction; and

means for analyzing at least some of the first set of histogram values to determine for each analyzed first set of histogram values a location of a first image edge and a first confidence value corresponding to the determined first image edge location.

31. A machine readable medium including machine executable instructions which, when executed control a processor to perform implement a method processing an image represented by a plurality of pixel values, each pixel value corresponding to a pixel element, the method comprising the steps of:

generating for each of a plurality of first bands of pixel values in said image, a first set of first histogram values, said first bands extending in a first direction, each first histogram value corresponding to a set of pixel values extending in a second direction perpendicular to said first direction; and

analyzing at least some of the first set of histogram values to determine for each analyzed first set of histogram values a location of a first image edge and a first confidence value corresponding to the determined first image edge location.