Compensating for distortion in digital images

• US 7,974,463 B2
• Filed: 01/21/2010
• Issued: 07/05/2011
• Est. Priority Date: 12/14/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Saric, Marin
• Primary Examiner(s): Le; Brian Q
• Assistant Examiner(s): Park; Edward
• Application Number:
  US12/691,406
• Publication Number:
  US 20100177169A1
• Time in Patent Office: 530 Days
• Field of Search: 382/154, 382/173, 382/180, 382/190, 382/223
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/10048 Infrared image
• CPC Class Codes: G06T 2207/30204 Marker
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: H04N 1/047 Detection, control or error compensation of scanning velocity or position H04N1/0402 and H04N1/17 take precedence
• CPC Class Codes: H04N 1/195 the array comprising a two-dimensional array or a combination of two-dimensional arrays
• CPC Class Codes: H04N 1/19594 using a television camera or a still video camera
• CPC Class Codes: H04N 13/10 Processing, recording or transmission of stereoscopic or multi-view image signals
• CPC Class Codes: H04N 2201/0434 specially adapted for scanning pages of a book
• CPC Class Codes: H04N 2201/04712 using unbroken arrays of detectors, i.e. detectors mounted on the same substrate
• CPC Class Codes: H04N 2201/04713 Details of the detector arrangement, e.g. non-standard position, optical details H04N2201/04712 takes precedence
• CPC Class Codes: H04N 2201/04717 on the scanned sheet, e.g. a reference sheet
• CPC Class Codes: H04N 2201/04734 Detecting at frequent intervals, e.g. once per line for sub-scan control
• CPC Class Codes: H04N 2201/04787 by changing or controlling the addresses or values of pixels, e.g. in an array, in a memory, by interpolation

Abstract

Systems and methods using an unstructured pattern for three-dimensional model construction, such as may be used for processing images of documents are disclosed. The method generally includes projecting an unstructured infrared pattern onto a target object, capturing a pair of stereoscopic images of the pattern projected onto the target object, such as with infrared cameras, performing signal processing on the pair of stereoscopic images to cross-correlate portions of the stereoscopic images in order to identify corresponding portions in the stereoscopic images, and constructing a three-dimensional model of the target object. The three-dimensional model can be utilized to rectify, e.g., de-warp, an image of the target object, e.g., a page or both facing pages of a bound document.

Claims

1. A method of compensating for distortion in a digital image, comprising:

projecting an unstructured pattern onto a document using a projector;

capturing a pair of stereoscopic images of the unstructured pattern projected onto the document using one or more stereoscopic cameras;

generating a plurality of lines in each of the stereoscopic images, each line comprising a plurality of non-overlapping regions of the stereoscopic images, the plurality of non-overlapping regions having a first height equal to a second height of each line, and rectifying the pair of stereoscopic images relative to each other such that each line in a first stereoscopic image of the pair of stereoscopic images corresponds to a line in a second stereoscopic image of the pair of stereoscopic images;

cross-correlating portions of the pair of stereoscopic images to identify corresponding portions in the pair of stereoscopic images, the cross-correlating being achieved based on image data from the stereoscopic images without specification of the unstructured pattern;

capturing a digital image of the document using an imaging camera;

constructing a three-dimensional model of a surface of the document; and

compensating for distortion in the digital image by rectifying the digital image based on spatial data provided by the three-dimensional model.

2. The method of claim 1, wherein cross-correlating portions of the pair of stereoscopic images comprises:

comparing a selected region of a line in the first stereoscopic image to regions of a corresponding line in the second image;

generating a plurality of similarity scores based on the comparing; and

identifying a match between the selected region and a region of the corresponding line in the second image based on a highest similarity score of the plurality of similarity scores.

3. The method of claim 2, wherein the comparing, generating and identifying are performed for all regions of the lines in the first stereoscopic image, and the three-dimensional model is generated based thereon.

4. The method of claim 1, wherein the digital image includes a pair of digital images each conveying content of the document, the document including a multi-page document, and compensating for distortion in the digital image is achieved by transforming the pair of digital images based on the three-dimensional model.

5. The method of claim 1, wherein the cross-correlating comprises dividing a first image of the pair of stereoscopic images into regions, and cross-correlating each region of the first stereoscopic image with a region of a second image of the pair of stereoscopic images.

6. The method of claim 1, wherein the projector is an infrared projector that projects the unstructured pattern in infrared light onto the document.

7. The method of claim 1, wherein the unstructured pattern is feature-rich and includes at least one feature in each region of a plurality of regions of the stereoscopic images, the feature being locally unique along at least a portion of the line on which the region is located.

8. The method of claim 1, wherein without specification of the unstructured pattern indicates that dimensions and relative positions of features the unstructured pattern are unspecified.

9. The method of claim 1, wherein the cross-correlating further includes:

selecting a region of the plurality of non-overlapping regions in a particular line of the plurality of lines of the first stereoscopic image; and

comparing the selected region of the particular line to regions of a corresponding line of the second stereoscopic image, the regions of the corresponding line within a predetermined distance from an area corresponding to the selected region.

10. The method of claim 9, wherein the predetermined distance is a width of the selected region.

11. A non-transitory computer-readable storage medium embedded with a computer program product, the computer program product including instructions that, when executed by a processor, cause the processor to perform actions comprising:

projecting an unstructured pattern onto a document using a projector;

capturing a pair of stereoscopic images of the unstructured pattern projected onto the document using one or more stereoscopic cameras;

generating a plurality of lines in each of the stereoscopic images, each line comprising a plurality of non-overlapping regions of the stereoscopic images, the plurality of non-overlapping regions having a first height equal to a second height of each line and rectifying the pair of stereoscopic images relative to each other such that each line in a first stereoscopic image of the pair of stereoscopic images corresponds to a line in a second stereoscopic image of the pair of stereoscopic images;

cross-correlating portions of the pair of stereoscopic images to identify corresponding portions in the pair of stereoscopic images, the cross-correlating being achieved based on image data from the stereoscopic images without specification of the unstructured pattern;

capturing a digital image of the document using an imaging camera;

constructing a three-dimensional model of a surface of the document; and

compensating for distortion in the digital image by rectifying the digital image based on spatial data provided by the three-dimensional model.

12. The computer-readable storage medium of claim 11, wherein cross-correlating portions of the pair of stereoscopic images comprises:

comparing a selected region of a line in the first stereoscopic image to regions of a corresponding line in the second image;

generating a plurality of similarity scores based on the comparing; and

identifying a match between the selected region and a region of the corresponding line in the second image based on a highest similarity score of the plurality of similarity scores.

13. The computer-readable storage medium of claim 12, wherein the comparing, generating and identifying are performed for all regions of the lines in the first stereoscopic image, and the three-dimensional model is generated based thereon.

14. The computer-readable storage medium of claim 11, wherein the digital image includes a pair of digital images each conveying content of the document, the document including a multi-page document, and compensating for distortion in the digital image is achieved by transforming the pair of digital images based on the three-dimensional model.

15. The computer-readable storage medium of claim 11, wherein the cross-correlating comprises dividing a first image of the pair of stereoscopic images into regions, and cross-correlating each region of the first stereoscopic image with a region of a second image of the pair of stereoscopic images.

16. The computer-readable storage medium of claim 11, wherein the projector is an infrared projector that projects the unstructured pattern in infrared light onto the document.

17. The computer-readable storage medium of claim 11, wherein the unstructured pattern is feature-rich and includes at least one feature in each region of a plurality of regions of the stereoscopic images, the feature being locally unique along at least a portion of the line on which the region is located.

18. The computer-readable storage medium of claim 11, wherein without specification of the unstructured pattern indicates that dimensions and relative positions of features the unstructured pattern are unspecified.

19. A system, comprising:

a projector configured to project an unstructured pattern onto a document;

one or more stereoscopic cameras configured to capture a pair of stereoscopic images of the unstructured pattern projected onto the document;

one or more processors that generate a plurality of lines in each of the stereoscopic images, each line comprising a plurality of non-overlapping regions of the stereoscopic images, the plurality of non-overlapping regions having a first height equal to a second height of each line and rectify the pair of stereoscopic images relative to each other such that each line in a first stereoscopic image of the pair of stereoscopic images corresponds to a line in a second stereoscopic image of the pair of stereoscopic images, and that cross-correlate portions of the pair of stereoscopic images to identify corresponding portions in the pair of stereoscopic images, the cross-correlating being achieved based on image data from the stereoscopic images without specification of the unstructured pattern; and

an imaging camera that captures a digital image of the document, wherein the one or more processors construct a three-dimensional model of a surface of the document, and compensate for distortion in the digital image by rectifying the digital image based on spatial data provided by the three-dimensional model.

20. The system of claim 19, wherein the one or more processors cross-correlate portions of the pair of stereoscopic images by:

comparing a selected region of a line in the first stereoscopic image to regions of a corresponding line in the second image;

generating a plurality of similarity scores based on the comparing; and

identifying a match between the selected region and a region of the corresponding line in the second image based on a highest similarity score of the plurality of similarity scores.

21. The system of claim 20, wherein the comparing, generating and identifying are performed for all regions of the lines in the first stereoscopic image, and the three-dimensional model is generated based thereon.

22. The system of claim 19, wherein the digital image includes a pair of digital images each conveying content of the document, the document including a multi-page document, and compensating for distortion in the digital image is achieved by transforming the pair of digital images based on the three-dimensional model.

23. The system of claim 19, wherein the one or more processors cross-correlate by dividing a first image of the pair of stereoscopic images into regions, and cross-correlating each region of the first stereoscopic image with a region of a second image of the pair of stereoscopic images.

24. The system of claim 19, wherein the projector is an infrared projector that projects the unstructured pattern in infrared light onto the document.

25. The system of claim 19, wherein the unstructured pattern is feature-rich and includes at least one feature in each region of a plurality of regions of the stereoscopic images, the feature being locally unique along at least a portion of the line on which the region is located.

26. The system of claim 19, wherein without specification of the unstructured pattern indicates that dimensions and relative positions of features the unstructured pattern are unspecified.