Method and system of deskewing an image using monochrome conversion to separate foreground from background

• US 7,668,404 B2
• Filed: 06/30/2004
• Issued: 02/23/2010
• Est. Priority Date: 06/30/2004
• Status: Expired due to Fees

• Current Assignee: Lexmark International Incorporated (Ninestar Corporation)
• Original Assignee: Lexmark International Incorporated (Ninestar Corporation)
• Inventors: Whitlock, Michael L., Ellingsworth, Joshua E., Dicken, Larry J., Chaudhuri, Saikat, Adams, Stephen P.
• Primary Examiner(s): Ahmed; Samir A.
• Assistant Examiner(s): TSAI, TSUNG YIN
• Application Number:
  US10/880,873
• Publication Number:
  US 20060002629A1
• Time in Patent Office: 2,064 Days
• Field of Search: 382/289, 382/296
• US Class Current: 382/289
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image

Abstract

A method and system of deskewing an image. The method and system includes capturing a first image, forming a number of regions within the first image, generating a bounding rectangles for each region, calculating an area for each bounding rectangle, rotating each region by an angle within a predefined range, finding the angle that minimizes the area of each bounding rectangle, and rotating each region by the angle found.

Claims

1. A method of deskewing an image, comprising the steps of:

capturing a first image;

forming a plurality of regions within the first image;

generating a plurality of bounding rectangles for the plurality of regions;

calculating a plurality of areas for the plurality of bounding rectangles;

rotating the plurality of regions by a plurality of angles within a predefined range;

following rotating the plurality of regions, finding a plurality of angles that substantially minimize the plurality of calculated areas of the plurality of bounding rectangles, each found angle for a region being deskew angle therefor; and

rotating the plurality of regions by the plurality of angles found,

wherein the above steps are performed by a processor.

2. A method as claimed in claim 1, further comprising receiving a plurality of parameters from a user.

3. A method as claimed in claim 1, further comprising converting the first image to a monochrome image.

4. A method as claimed in claim 3, wherein converting the first image to a monochrome image is based on a threshold value, where all color values below the threshold are considered a first color and all colors above the threshold are considered a second color different from the first.

5. A method as claimed in claim 1, wherein forming a plurality of regions within the first image further comprises:

converting the first image to a monochrome image; and

forming a plurality of regions of adjacent pixels with the same color values.

6. A method as claimed in claim 1, wherein forming a plurality of regions within the first image further comprises:

displaying the first image to a user;

sensing selections made to the first image by the user; and

forming the plurality of regions based on selections by the user.

7. A method as claimed in claim 1, further comprising applying a filter to remove noise from the first image.

8. A method as claimed in claim 1, further comprising analyzing the plurality of regions.

9. A method as claimed in claim 8, wherein analyzing the plurality of regions comprises displaying the regions to a user.

10. A method as claimed in claim 1, further comprising adjusting the plurality of regions.

11. A method as claimed in claim 10, wherein adjusting the plurality of regions comprises deleting unwanted regions automatically based on a parameter input by a user.

12. A method as claimed in claim 10, wherein adjusting the plurality of regions comprises deleting unwanted regions manually based on selections indicated by a user.

13. A method as claimed in claim 10, wherein adjusting the plurality of regions comprises joining subsets of the plurality of regions automatically based on a parameter input by a user.

14. A method as claimed in claim 10, wherein adjusting the plurality of regions comprises joining subsets of the plurality of regions manually based on selections indicated by a user.

15. A method as claimed in claim 1, wherein the predefined range for rotating the region extends from about −

45 degrees to about 45 degrees.

16. A method as claimed in claim 1, wherein rotating the region by an angle within a predefined range is accomplished by stepping through the predefined range by a preset amount.

17. A method as claimed in claim 16, wherein the preset amount is 1 degree per rotation.

18. A method as claimed in claim 1, wherein rotating the region by an angle within a predefined range is accomplished by testing two rotation angles.

19. A method as claimed in claim 1, wherein forming a plurality of regions comprises:

reading a first color value of a first pixel;

determining if the first color value matches a region color value;

if the first color value matches the region color value, creating a first region containing the first pixel;

if the first color value matches the region color value, reading a second color value of a second adjacent pixel to the first region;

determining if the second color value matches the region color value;

if the second color value matches the region color value, adding the second pixel to the first region;

reading a third color value of a third, non-adjacent pixel;

determining if the third color value matches the region color value; and

if the third color value matches the region color, creating a second region containing the third, non-adjacent pixel.

20. A system of deskewing an image, the system comprising:

an image capturing device configured to capture a first image; and

a processor configured to form a plurality of regions within the first image,

generate a plurality of bounding rectangles for the plurality of regions, calculate a plurality of areas for the plurality of bounding rectangles, rotate each of the plurality of regions separately, following rotating the plurality of regions, finding a plurality of angles that substantially minimize the plurality of calculated areas of the plurality of bounding rectangles, each found angle for a region being deskew angle therefor, and record a plurality of minimum areas and corresponding angles for the plurality of bounding rectangles, the corresponding angles being independent from each other, and rotate each of the plurality of regions by the corresponding angle therefor.

21. A system as claimed in claim 20, wherein the processor is further configured to find a plurality of portrait or landscape orientated rectangles that completely enclose the plurality of regions.

22. A system as claimed in claim 20, wherein the processor is further configured to output the plurality of regions rotated at the recorded plurality of angles.

23. A system as claimed in claim 20, wherein the processor is further configured to analyze the content of the plurality of regions.

24. A system as claimed in claim 20, wherein the processor is further configured to interact with a user to receive instructions.

25. A system as claimed in claim 24, wherein the processor is further configured to adjust the plurality of regions formed by applying the set of instructions supplied by the user.

26. A system as claimed in claim 20, wherein the processor is further configured to form the plurality of regions within the first image by converting the first image to a monochrome image and finding groups of adjacent pixels that share one color of the two-color monochrome image.

27. A processor configured to:

receive a first image from an image capturing device;

form a plurality of regions within the first image;

generate a plurality of bounding rectangles for the plurality of regions;

calculate a plurality of areas for the plurality of bounding rectangles;

rotate each of the plurality of regions;

following rotating the plurality of regions, finding a plurality of angles that substantially minimize the plurality of calculated areas of the plurality of bounding rectangles, each found angle for a region being deskew angle therefor;

record a plurality of minimum areas for the plurality of bounding rectangles; and

rotate each region by an angle corresponding to a minimum area of the bounding rectangle for the region.

28. A system as claimed in claim 27, wherein the processor is further configured to find a plurality of portrait or landscape orientated rectangles that completely enclose the plurality of regions.

29. A system as claimed in claim 27, wherein the processor is further configured to output the plurality of regions rotated at the recorded plurality of angles.

30. A system as claimed in claim 27, wherein the processor is further configured to analyze the content of the plurality of regions.

31. A system as claimed in claim 27, wherein the processor is further configured to interact with a user to receive input.

32. A system as claimed in claim 31, wherein the processor is further configured to adjust the plurality of regions formed by applying the input supplied by the user.

33. A system as claimed in claim 27, wherein the processor is further configured to form the plurality of regions within the first image by converting the first image to a two-color image and finding groups of adjacent pixels that share one color of the two-color image.