Three-dimensional model construction using unstructured pattern

• US 7,660,458 B1
• Filed: 12/14/2004
• Issued: 02/09/2010
• 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): Kim; Charles
• Assistant Examiner(s): Park; Edward
• Application Number:
  US11/011,727
• Time in Patent Office: 1,883 Days
• Field of Search: 382/154, 345/419, 345/427, 356/12
• 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, comprising:

projecting an unstructured pattern onto a target object using a projector, wherein the target object is a pair of pages of a multi-page document;

capturing a pair of stereoscopic images of the unstructured pattern projected onto the target object, wherein one or more stereoscopic cameras capture the pair of stereoscopic images;

generating respective lines in each of the stereoscopic images;

vertically rectifying the pair of stereoscopic images relative to each other to align the respective lines;

performing signal processing on the pair of stereoscopic images to horizontally cross-correlate portions of the pair of stereoscopic images in order to identify corresponding portions in the pair of stereoscopic images, wherein the signal processing is performed utilizing the image data from the stereoscopic images without specification of the pattern;

capturing a pair of readable images each conveying the content of one of the pair of pages, wherein one or more cameras that are different from the one or more stereoscopic cameras capture the pair of readable images; and

compensating for distortion in the pair of readable images by transforming the pair of readable images with an output of the signal processing,

wherein performing signal processing includes dividing a first of the two stereoscopic images into regions, a plurality of regions forming each line, each region having a width that is greater than its height and wherein the performing signal processing is performed for each region of the first stereoscopic image.

2. The method of claim 1, wherein the projecting is performed by an infrared projector to project the unstructured pattern in infrared light onto the target object.

3. The method of claim 1, further comprising:

constructing a three-dimensional model of the target object.

4. The method of claim 3, further comprising rectifying a digital image of the target object utilizing the three-dimensional model of the target object.

5. The method of claim 1, wherein the unstructured pattern includes at least one feature in each region, the feature being locally unique along at least a portion of the line on which the region is located.

6. The method of claim 1, wherein the unstructured pattern includes at least one feature in each region, at least a portion of which extends along the height of the region.

7. The method of claim 1, wherein the performing signal processing further includes:

comparing each region in the first stereoscopic image to areas at a plurality of positions along a corresponding line in a second of the two stereoscopic images, each area being of generally a same size as each region, each comparison generates a similarity score between the region in the first stereoscopic image and the area in the second stereoscopic image; and

designating the area in the second stereoscopic image with the highest similarity score as the area that matches the region in the first stereoscopic image.

8. The method of claim 7, wherein the comparing is performed on areas in the second stereoscopic image within a predetermined distance from an area corresponding to the region being compared in the first stereoscopic image.

9. The method of claim 1, wherein an epipolar line of the pair of stereoscopic cameras is generally perpendicular to a spine of the bound document.

10. The method of claim 1, wherein the one or more cameras comprise two cameras, and wherein the pair of stereoscopic cameras are located between the two cameras.

11. The method of claim 1, comprising forming a text document from transformed pair of readable images by optically recognizing characters in the transformed pair of readable images.

12. A 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:

receiving a pair of stereoscopic images of an unstructured pattern projected onto a target object, wherein the pair of stereoscopic images are captured from a first pair of perspectives, respectively, and wherein the target object is a curved surface of a document;

generating respective lines in each of the stereoscopic images;

vertically rectifying the pair of stereoscopic images relative to each other to align the respective lines;

performing signal processing on the pair of stereoscopic images to horizontally cross-correlate portions of the pair of stereoscopic images in order to identify corresponding portions in the pair of stereoscopic images, wherein the signal processing is performed utilizing the image data from the stereoscopic images without specification of the unstructured pattern;

receiving an image of the curved surface of the document from a third perspective that is different from either of the first pair of perspectives, wherein the image of the curved surface of the document conveys the content of the document; and

transforming the image of the curved surface of the document into an image of the document at it would appear were it not curved based on a result of the signal processing,

wherein performing signal processing includes dividing a first of the two stereoscopic images into regions, a plurality of regions forming each line, each region having a width that is greater than its height and wherein the performing signal processing is performed for each region of the first stereoscopic image.

13. The computer readable storage medium of claim 12, wherein the pair of stereoscopic images are of the unstructured pattern projected onto a target object in infrared light.

14. The computer readable storage medium of claim 12, further including instructions that, when executed by a processor, cause the processor to perform actions comprising:

constructing a three-dimensional model of the target object.

15. The computer readable storage medium of claim 14, further including instructions that, when executed by a processor, cause the processor to perform actions comprising:

rectifying a digital image of the target object utilizing the three-dimensional model of the target object.

16. The computer readable storage medium of claim 12, in which the unstructured pattern includes at least one feature in each region, the feature being locally unique along at least a portion of the line on which the region is located.

17. The computer readable storage medium of claim 12, in which the unstructured pattern includes at least one feature in each region, at least a portion of which extends along the height of the region.

18. The computer readable storage medium of claim 12, in which the performing signal processing further includes:

comparing each region in the first stereoscopic image to areas at a plurality of positions along a corresponding line in a second of the two stereoscopic images, each area being of generally a same size as each region, each comparison generates a similarity score between the region in the first stereoscopic image and the area in the second stereoscopic image; and

designating the area in the second stereoscopic image with the highest similarity score as the area that matches the region in the first stereoscopic image.

19. The computer readable storage medium of claim 18, in which the comparing is performed on areas in the second stereoscopic image within a predetermined distance from an area corresponding to the region being compared in the first stereoscopic image.

20. A system, comprising:

an infrared projector configured to project an infrared pattern onto a target object, wherein the target object is a multi-page document;

a support configured to position the target object in front of the infrared projector;

a pair of stereoscopic infrared cameras configured to capture stereoscopic images of the infrared pattern projected onto the target object;

a signal processor configured to vertically rectify a pair of stereoscopic images relative to each other to align respective lines of the stereoscopic images, and further configured to perform signal processing on the pair of stereoscopic images to horizontally cross-correlate portions of the pair of stereoscopic images in order to identify corresponding portions in the pair of stereoscopic images and to construct a three-dimensional model of the target object; and

another camera configured to capture an image of the semantic content of a page of the target object, wherein the signal processor is further configured to transform the image of the semantic content of the page based on the three-dimensional models

wherein the signal processor is further configured to divide a first of the two stereoscopic images into regions, a plurality of regions forming each line, each region having a width that is greater than its height, the signal processor is further configured to perform the signal processing for each region of the first stereoscopic image.

21. The system of claim 20, wherein the infrared pattern includes at least one feature in each region, the feature being locally unique along at least a portion of the line on which the region is located.

22. The system of claim 21, wherein the infrared pattern includes at least one feature in each region, at least a portion of which extends along the height of the region.

23. The system of claim 21, wherein the signal processing performed by the signal processor includes:

comparing each region in the first stereoscopic image to areas at a plurality of positions along a corresponding line in a second of the two stereoscopic images, each area being of generally a same size as each region, each comparison generates a similarity score between the region in the first stereoscopic image and the area in the second stereoscopic image; and

designating the area in the second stereoscopic image with the highest similarity score as the area that matches the region in the first stereoscopic image; and

constructing the three-dimensional model of a target object based on the image data of the pairs of matching region and area.

24. The system of claim 21, wherein the signal processor performs the comparing on areas in the second stereoscopic image within a predetermined distance from an area corresponding to the region being compared in the first stereoscopic image.

25. The system of claim 20, wherein the pair of stereoscopic infrared cameras comprise an optical band-pass filter configured to pass infrared light while obstructing at least part of the visible spectrum.