Method and apparatus for resolving perspective distortion in a document image and for calculating line sums in images

• US 6,873,732 B2
• Filed: 07/09/2001
• Issued: 03/29/2005
• Est. Priority Date: 07/09/2001
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Dance, Christopher R.
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US09/901,508
• Publication Number:
  US 20030026482A1
• Time in Patent Office: 1,359 Days
• Field of Search: 382/199, 382/275, 382/293, 382/281, 382/202
• US Class Current: 382/199
• CPC Class Codes: G06T 5/80 Geometric correction
• CPC Class Codes: G06V 20/62 Text, e.g. of license plates, overlay texts or captions on TV images
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines
• CPC Class Codes: G06V 30/166 Normalisation of pattern dimensions

Abstract

Perspective distortion is estimated in a digital document image by detecting perspective pencils in two directions, one being parallel to text lines, and the other being parallel to the boundaries of formatted text columns. The pencils are detected by analyzing directional statistical characteristics of the image. To detect a pencil, a first statistical line transform is applied to transform the image into line space, and a second statistical score transform is applied to transform the image into pencil space. A dominant peak in pencil space identifies the perspective pencil. In addition, a computationally efficient line summing technique is used for effecting sums of pixels along inclined target lines (or curves) through an image. The technique includes pre-generating partial sums, and summing along step segments of a target line using the partial sums.

Claims

1. A method for estimating perspective in an image, comprising:

(a) applying at least one transform to the image to transform the image into a coordinate space representative of directional statistical characteristics in the image; and

(b) processing the transformed image to determine at least one pencil which aligns with said directional statistical characteristics present in the image,

wherein the transform includes differencing adjacent values.

2. A method according to claim 1, wherein the transform includes differencing adjacent values in a direction generally perpendicular to the direction of the line along which the sum is taken.

3. A method according to claim 1, wherein the transform is applied to detect statistical characteristics generally parallel to lines of text.

4. A method according to claim 1, wherein (a) and (b) are performed a first time to detect a first pencil aligned in a first direction, and wherein (a) and (b) are performed a second time to detect a second pencil aligned in a second direction different from the first direction.

5. A method according to claim 1, wherein said statistical characteristics are representative of text characteristics.

6. A method according to claim 5, wherein said statistical characteristics are representative of a direction of a text line in the image.

7. A method according to claim 5, wherein said statistical characteristics are representative of a direction of a boundary of a block of text.

8. A method according to claim 1, wherein (a) comprises:

applying a transform to the image to transform the image into line space, in which a line in the original image is transformed into a point value in line space.

9. A method according to claim 8, wherein (b) comprises applying a second transform to further transform the transformed image from line space to a pencil space coordinate system, the pencil space coordinate system being such that a curve in line space is transformed into a point value in pencil space, indicative of a pencil aligned with characteristics in the image.

10. A method according to claim 9, wherein the pencil space coordinate system is parameterized by the rate of change of line slope, and a first slope.

11. A method according to claim 9, wherein the pencil space coordinate system is defined by polar coordinates based on a Gaussian sphere.

12. A method according to claim 9, wherein the second transform includes summing values taken along lines through values of the transformed image.

13. A method according to claim 12, wherein the second transform includes a non-linear function of values from the first transformed image.

14. A method according to claim 12, wherein the second transform includes a minimum threshold function, such that points below a minimum threshold value are ignored.

15. A method according to claim 1, wherein the line space is slope-intercept space, said transform being parameterized by slope and intercept coordinates.

16. A method according to claim 1, wherein the line space is uniform angle space, said transform being parameterized by angle and distance to an origin of the image plane.

17. A method according to claim 1, wherein the transform includes summing values taken along lines through pixels of the image.

18. A method according to claim 17, wherein the sum includes points selected as a variable scale, said scale being defined by an amount of background space detected around the point.

19. A method according to claim 18, further comprising detecting said scale of a point, by detecting the size of an area of predetermined shape adjacent to the point, said area including only background space.

20. A method according to claim 19, wherein said predetermined shape is a triangle.

21. A method according to claim 19, wherein a gray level of background space is detected with reference to a contrast value applied to the point.

22. A method according to claim 21, further comprising selecting a point only if a predetermined second area on an opposite side of said point to the first area includes a gray level indicative of foreground space in said second area.

23. A method according to claim 22, wherein said second area has a rectangular shape.

24. Apparatus for estimating perspective in an image, comprising:

a first image transformer for applying at least one transform to the image to transform the image into a coordinate space representative of directional statistical characteristics in the image; and

a first pencil detector for processing the transformed image to determine at least one pencil which aligns with said directional statistical characteristics present in the image,

wherein the at least one transform includes differencing adjacent values.

25. Apparatus according to claim 24, further comprising:

a second image transformer for applying a second transform to the image to transform the image into a coordinate space representative of directional statistical characteristics in the image in a second direction different from the first transformer; and

a second pencil detector for processing the transformed image to determine a second pencil which aligns with said directional statistical characteristics present in the image in said second direction.

26. A method for calculating a sum of discrete pixel values along at least part of a target curve defined by a first direction and a set of stepping-values in said first direction at which a discretization of said target curve steps perpendicularly to said first direction, the method comprising:

(a) calculating a plurality of partial line sums of pixels along partial lines in a first direction parallel to a coordinate axis, each partial sum being parameterized by an intercept and a variable position away from the intercept,

(b) calculating the sum of pixel values by combining respective partial line sums representative of segments of the target curve at at least two of the said stepping values,

wherein the sum O_m(y) alone the target curve is defined as;

$Q_m<br><br>\left(y\right)=\mathrm{PS}<br><br>\left(W-1,y+n\right)+\underset{k=1}{\overset{n}{\sum <br><br>}}<br><br>\mathrm{PS}<br><br>\left(x_k,y+k-1\right)-\mathrm{PS}<br><br>\left(x_k,y+k\right),$

where

W=width of an image in pixels;

n=number of values X_m={x₁, x₂, . . . , x_n} at which the target curve crosses adjacent intercept values; and

PS(x, y)=partial sum $\mathrm{PS}<br><br>\left(x,y\right)=\underset{u=0}{\overset{x}{\sum <br><br>}}<br><br>I<br><br>\left(u,y\right).$

27. A method according to claim 26, wherein the target curve is a line.

28. A method according to claim 27, further comprising repeating (b) to calculate sums at different values of slope-intercept (m,y).