Non-iterative method of calculating image skew

• US 7,142,727 B2
• Filed: 12/17/2002
• Issued: 11/28/2006
• Est. Priority Date: 12/17/2002
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Notovitz, William, Schweid, Stuart Alan
• Primary Examiner(s): Mehta, Bhavesh M
• Assistant Examiner(s): TUCKER, WESLEY J
• Application Number:
  US10/321,922
• Publication Number:
  US 20040114831A1
• Time in Patent Office: 1,442 Days
• Field of Search: 382/282, 382/284, 382/289, 382/296, 358/538, 358/540, 358/453
• US Class Current: 382/289
• CPC Class Codes: G06V 30/1478 of characters or characters lines

Abstract

A parallel, non-iterative, memory efficient method of determining image skew. A document skew angle is determined from a fast scan second order moment data set and a slow scan second order moment data set. A slow scan second order moment data set can be generated by receiving a current scanline of image data, updating columns sums for a set of rotation angles using scanlines within a buffer comprising a band having a predetermined number B of scanlines, and updating the buffer with the current scanline. A fast scan second order moment data set is generated by projecting a plurality of pixels within each scanline of image data received to a first rotation angle wherein the plurality pixels project onto M rows; updating M memory locations, wherein each one of the M memory locations corresponds to one of the M rows and wherein each memory location is updated using pixels projecting onto the corresponding row whereby one of the M memory locations contains a completed row; and adding the square of the completed row sum to a moment accumulator.

Claims

1. A method of processing scanned image data comprising:

receiving image data, the image data comprising a plurality of scanlines with each scanline comprising a plurality of pixels;

generating a fast scan second order moment data set;

generating a slow scan second order moment data set; and

determining a document skew angle from the fast scan and slow scan second order moment data sets;

wherein the step of generating the slow scan second order moment data set includes

receiving a current scanline of image data,

updating columns sums for a set of rotation angles using scanlines within a buffer comprising a band of scanlines, the band having a predetermined number B of scanlines, and

updating the buffer with the current scanline.

2. The method of claim 1, wherein the step of updating the buffer uses a first in, first out priority.

3. The method of claim 1, wherein the step of updating columns sums for a set of rotation angles is performed in parallel with the step of receiving a current scanline.

4. The method of claim 1, wherein the step of updating columns sums for a set of rotation angles comprises:

for each scanline within the buffer, projecting pixels from the scanline onto columns in accordance with at least a first document rotation angle; and

for each column within a first set of columns, adding the number of ON pixels projected onto the column resulting from of the projection to the first document rotation angle to a column sum for the column.

5. The method of claim 1, wherein the step of generating the slow scan second order moment data set further comprises:

receiving a subsequent scanline,

updating columns sums for a second set of rotation angles using scanlines within the buffer, and

updating the buffer with the subsequent scanline using a first in, first out basis.

6. The method of claim 1, wherein the slow scan second order moment data set includes a second order moment for each rotation angle in a set having X unique rotation angles and the step of updating columns sums for a set of rotation angles updates the column sums for each of the X unique rotation angles.

7. The method of claim 1, wherein the slow scan second order moment data set includes a second order moment for each rotation angle in a set having X unique rotation angles and the step of updating columns sums for a set of rotation angles updates the column sums for X/B rotation angles.

8. The method of claim 1, wherein the step of wherein the step of generating the fast scan second order moment data set comprises:

projecting a plurality of pixels within the current scanline to a first rotation angle;

adding a first subset of the plurality of projected pixels to a first memory location;

adding a second subset of the plurality of projected pixels to a second memory location;

adding a third subset of the plurality of projected pixels to a third memory location; and

adding the square of the pixel sum in the first memory location to a moment accumulator.

9. The method of claim 8, wherein the step of generating the fast scan second order moment data set further comprises:

projecting a plurality of pixels within a subsequent scanline to the first rotation angle;

adding a first subset of the plurality of projected pixels within the subsequent scanline to the second memory location;

adding a second subset of the plurality of projected pixels within the subsequent scanline to the third memory location;

adding a third subset of the plurality of projected pixels within the subsequent scanline to the first memory location, and

adding the square of the pixel sum in the second memory location to the moment accumulator.

10. A method of processing image data comprising:

scanning a document to produce scanned image data comprising a plurality of scanlines, each scanline having a plurality of pixels;

generating a first set of second order moments, the first set of second order moments being based on row sums;

generating a second set of second order moments, the second set of second order moments being based on column sums; and

determining a document skew angle from the first and second sets of second order moments;

wherein the step of generating the first set of second order moments includes receiving a first scanline,

projecting a plurality of pixels within the first scanline to at least a first rotation angle,

adding a first subset of the plurality of projected pixels to a first memory location,

adding a second subset of the plurality of projected pixels to a second memory location,

adding a third subset of the plurality of projected pixels to a third memory location, and

adding the square of the pixel sum in the first memory location to a moment accumulator.

11. The method of claim 10, wherein the step of generating the fast scan second order moment data set further comprises adding a fourth subset of the plurality of projected pixels to a fourth memory location.

12. The method of claim 10, wherein the step of generating the first set of second order moments further includes:

receiving a second scanline;

projecting a plurality of pixels within the second scanline to the first rotation angle;

adding a first subset of the plurality of projected pixels within the second scanline to the second memory location;

adding a second subset of the plurality of projected pixels within the second scanline to the third memory location;

adding a third subset of the plurality of projected pixels within the second scanline to the first memory location, and

adding the square of the pixel sum in the second memory location to the moment accumulator.

13. The method of claim 10, wherein the step of generating the second set of second order moments includes:

updating columns sums for a set of rotation angles using scanlines within a buffer comprising a band of scanlines, the band having a predetermined number B of scanlines, and

updating the buffer with the first scanline according to a first in, first out priority.

14. The method of claim 13, wherein the step of generating the second set of second order moments further comprises:

updating columns sums for a second set of rotation angles using scanlines within the buffer, and

updating the buffer with the second scanline.

15. A memory efficient method of processing image data to determine image skew, comprising:

receiving scanned image data, the scanned image data comprising a plurality of scanlines with each scanline comprising a plurality of pixels;

generating a fast scan second order moment data set;

generating a slow scan second order moment data set; and

determining a document skew angle from the fast scan and slow scan second order moment data sets;

wherein the step of generating the fast scan second order moment data set includes

projecting a plurality of pixels within a scanline to at least a first rotation angle wherein the plurality pixels project onto M rows;

updating M memory locations, wherein each one of the M memory locations corresponds to one of the M rows and wherein each memory location is updated using pixels projecting onto the corresponding row whereby one of the memory locations contains a completed row sum and M−

1 of the memory locations contain partial row sums;

adding the square of the completed row sum to a moment accumulator; and

repeating the projecting, updating and adding steps for each scanline within a plurality of scanlines whereby a memory location having a completed row sum is reused to accumulate subsequent row sum so that only M memory locations are required to accumulate row sums.

16. The method of processing image data to determine image skew according to claim 15, wherein:

the step of projecting a plurality of pixels within a scanline further comprises projecting a plurality of pixels within the scanline to each angle within a set of N rotation angles, wherein each rotation angle projects pixels onto M_i rows for i=1 to N, wherein each rotation angle has M_i memory locations associated therewith, and wherein each of the M_i memory locations for a given rotation angle corresponds to one of the M_i rows; and

the step of updating memory locations further comprises updating the M_i memory locations associated with each rotation angle.

17. The method of processing image data to determine image skew according to claim 16, wherein the step of updating memory locations, updates the M_i memory locations for a given rotation angle in parallel.