Detecting skew angle in a scanned image

• US 20060039628A1
• Filed: 09/17/2004
• Published: 02/23/2006
• Est. Priority Date: 08/21/2004
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Li, Xing, Clingerman, Terri A.
• Granted Patent: US 7,200,285 B2
• Time in Patent Office: Days
• US Class Current: 382/289
• CPC Class Codes: H04N 1/3873 defined only by a limited number of coordinate points or parameters, e.g. corners, centre; for trimming
• CPC Class Codes: H04N 1/3878 Skew detection or correction

Abstract

Detecting skew and determining skew angle using the front of a document by determining background-to-document transitions. Incoming scanlines are interval sampled in the fast scan direction every nth pixel. The samples are collected and organized into a two dimension array comprised of scanline based rows and interval based columns. The collected and organized samples are analyzed by intervals to determine a scanline (row) where a specified sampling condition exceeds predetermined threshold. The corresponding row-interval point forms a background-to-medium transition point of the edge of a document. When two or more background-to-medium transition points are found from different intervals the skew angle can be determined using linear regression.

Claims

1. A method, comprising:

generating a plurality of scanlines of grayscale image data that represent an original document captured inside a scan area;

interval sampling said captured grayscale image data to provide intensity values for corresponding pixels in said plurality of scanlines;

creating a two-dimensional array of relative intensity values for said plurality of scanlines, with relative intensity values for pixels from a same scanline arranged in a same array row and relative intensity values for pixels from a same sampling interval arranged in a same array column;

from said relative intensity values, identifying a plurality of background-to-medium transition points for said grayscale image data; and

determining a skew angle of said original document based upon a location of a plurality of said background-to-medium transition points.

2. The method of claim 1, wherein said skew angle determination is obtained using a linear regression of a plurality of said two-dimensional array relative intensity values.

3. The method of claim 1, wherein said background-to-medium transition points are identified as a first pixel collected in a respective interval where an intensity value exceeds a threshold value.

4. The method of claim 1, wherein said background-to-medium transition points are identified in real time.

5. The method of claim 1, where determining the plurality of background-to-medium transition points is performed as each successive row is added to said two-dimensional array.

6. The method of claim 1, wherein interval sampling is performed by measuring said grayscale image data every n^th pixel, where n is an integer.

7. The method of claim 1, wherein the skew angle is determined relative to the fast scan direction.

8. A machine readable medium having instructions stored thereon that when executed by a processor cause a system to:

generate a plurality of scanlines of grayscale image data that represent an original document captured inside a scan area;

interval sample said captured grayscale image data to provide intensity values for corresponding pixels in said plurality of scanlines;

create a two-dimensional array of relative intensity values for said plurality of scanlines, with relative intensity values for pixels from a same scanline arranged in a same array row and relative intensity values for pixels from a same sampling interval arranged in a same array column;

from said relative intensity values, identify a plurality of background-to-medium transition points for said grayscale image data; and

determine a skew angle of said original document based upon a location of a plurality of said background-to-medium transition points.

9. A machine readable medium of claim 8, wherein said skew angle determination is performed using a least squares fit of the values in the two-dimensional array.

10. A machine readable medium of claim 8, wherein said background-to-medium transition points are identified as a first pixel in a respective interval where an intensity value exceeds a threshold value.

11. A machine readable medium of claim 8, wherein said skew angle determination is performed in real time.

12. A machine readable medium of claim 8, wherein determining the plurality of background-to-medium transition points is performed as each successive row is added to said two-dimensional array.

13. A machine readable medium of claim 8, wherein interval sampling is performed by measuring the input video signals at every nth pixel of a scan line, where n is an integer.

14. A system, comprising:

a document transport that moves an original document in a slow scan-direction to a scanning surface;

an image sensor that moves across said original document in a fast scan direction detecting the intensity of light reflected from said scanning surface and converts said reflected light into digital image data; and

a processor that interval samples said grayscale image data to provide intensity values for corresponding pixels in said plurality of scanlines, creates a two-dimensional array of relative intensity values for said plurality of scanlines identifies a plurality of background-to-medium transition points for said grayscale image data and determines a skew angle of said original document based upon a location of a plurality of said background-to-medium transition points.

15. The system of claim 14 wherein said two-dimensional array is arranged such that relative intensity values for pixels from a same scanline are located in a same array row and relative intensity values for pixels from a same sampling interval are located in a same column.

16. The system of claim 14, wherein said processor determines said skew angle using a standard linear regression of the two-dimensional array sample values.

17. The system of claim 14, wherein said processor determines said first background-to-medium transition point using a specified sampling condition to determine if sample values of a first interval cause said specified sampling condition to exceed a threshold value.

18. The system of claim 14, wherein said processor determines said skew angle in real time.

19. The system of claim 14, wherein interval sampling is performed by measuring said input video signals at every nth pixel, where n is an integer.

20. The system of claim 14, wherein said sampling interval is 64 pixels.