Detection of grooves in scanned images

• US 7,508,978 B1
• Filed: 09/13/2004
• Issued: 03/24/2009
• Est. Priority Date: 09/13/2004
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lefevere, Francois-Marie, Saric, Marin
• Primary Examiner(s): Chawan; Sheela C
• Application Number:
  US10/938,727
• Time in Patent Office: 1,653 Days
• Field of Search: 382/100, 382/131, 382/294, 382/215, 382/285, 382/154, 382/293, 382/276, 382/128, 358/474, 358/497, 358/488, 358/471, 358/493, 358/530, 358/400, 358/466, 715/209, 715/274, 600/407, 600/426, 345/427, 345/419, 345/421, 345/422, 345/418, 250/208.1, 250/226, 356/402, 355/25, 355/23, 399/361, 399/362, 348/E13.025, 348/E13.003, 348/E13.002, 348/E13.001, 707/E17.11, 378/23
• US Class Current: 382/154
• CPC Class Codes: G01B 11/2545 with one projection direction and several detection directions, e.g. stereo
• CPC Class Codes: G03B 35/00 Stereoscopic photography
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 30/184 by analysing segments intersecting the pattern
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition

Abstract

A system and method locate a central groove in a document such as a book, magazine, or catalog. In one implementation, scores are generated for points in a three-dimensional image that defines a surface of the document. The scores quantify a likelihood that a particular point is in the groove. The groove is then detected based on the scores. For example, lines may be fitted through the points and a value calculated for the lines based on the scores. The line corresponding to the highest calculated value may be selected as the line that defines the groove.

Claims

1. A system comprising:

an infrared projector;

a pattern mask located in an output path of the infrared projector;

a stereoscopic camera to generate images of opposing pages of a document from which a three-dimensional image of a surface of the opposing pages of the document is generated; and

control logic to process the three-dimensional image to locate a groove that is defined by the spine of the document and located between the opposing pages of the document.

2. The system of claim 1, wherein the document is a book.

3. The system of claim 1, wherein the document is a magazine or catalog.

4. The system of claim 1, further comprising:

a second camera to take two-dimensional images of the surface of the opposing pages of the document.

5. The system of claim 4, wherein the second camera includes:

two cameras.

6. The system of claim 4, wherein the second camera is a high definition camera.

7. The system of claim 1, wherein the stereoscopic camera includes two lenses configured to take stereoscopic images.

8. The system of claim 7, wherein the stereoscopic camera includes an infrared camera.

9. A system comprising:

a stereoscopic camera to generate images of opposing pages of a document from which a three-dimensional image of a surface of the opposing pages of the document is generated; and

control logic to;

calculate a score for each point in on a surface of the three-dimensional image, the score quantifying a likelihood that a particular one of the points is located in a groove defined by a spine of the document;

locate a plurality of lines through the points; and

identify, as the groove, one of the lines that maximizes a total score of the points that comprise the line.

10. The system of claim 9, wherein the score for a first of the points is calculated as:

(z₁−

z₀)+(z<sub>−

1</sub>−

z₀),

where z₀ is the Z coordinate value of the first point, z₁ is the Z coordinate value of a point immediately to the right of z₀ along the X axis, and z<sub>−

1</sub> is the Z coordinate value of a point immediately to the left of z₀ along the X axis.

11. The system of claim 9, wherein the control logic is configured to iteratively calculate the score for each of the points and locate the plurality of lines using progressively finer levels of resolution of the three-dimensional image.

12. The system of claim 9, wherein the control logic is configured to

bias the scores of the points that are located closer to a middle of the three-dimensional image more than the scores of the points that are located further from the middle of the three-dimensional image.

13. A computer-implemented method for detecting a groove defined by a spine of a document, the method comprising:

generating a score for each point on a surface of a three-dimensional image, the score quantifying a likelihood that a particular one of the points is located in the groove;

biasing the scores of the points that are located closer to a middle of the three-dimensional image more than the scores of the points that are located further from the middle of the three-dimensional image; and

detecting a location of the groove based on the biased generated scores.

14. The method of claim 13, further comprising:

fitting a plurality of lines through the points;

calculating a value for each of the plurality of lines based on the scores of the points that comprise the line; and

selecting one of the plurality of lines as a line that defines the location of the groove based on the calculated values.

15. The method of claim 14, further comprising:

calculating the value for each of the plurality of lines as a sum of the scores of the points corresponding to the line.

16. The method of claim 14, further comprising:

selecting one of the plurality of lines as the line having a maximum value.

17. The method of claim 14, further comprising:

repeating the generating the score for each of the points, the fitting the plurality of lines, and the calculating the value for each of the lines, using progressively finer resolutions of the points on the surface of the three-dimensional image.

18. The method of claim 17, wherein the progressively finer resolutions of the points on the surface of the three-dimensional image includes points located in a vicinity of a previous line that has a maximum value defines the groove.

19. The method of claim 13, wherein the document is a book.

20. The method of claim 13, wherein the document is a magazine or catalog.

21. A computer-implemented method for locating a groove defined by a spine of a document, the method comprising:

generating a score for each point on a surface of a three-dimensional image, the score quantifying a likelihood that a particular one of the points is located in the groove,

wherein the score for a first of the points is calculated as;

(z₁−

z₀)+(z<sub>−

1</sub>−

z₀),

where z₀ is the Z coordinate value of the first point, z₁ is the Z coordinate value of a point immediately to the right of z₀ along an axis, and z<sub>−

1</sub> is the Z coordinate value of a point immediately to the left of z₀ along the axis; and

detecting a location of the groove based on the scores.

22. The method of claim 21, further comprising:

identifying, using an infrared projector, the points on the surface of the three-dimensional image.

30. The method of claim 21, further comprising:

identifying, using an infrared stereoscopic camera, the points on the surface of the three-dimensional image.

23. A device for detecting a groove defined by a spine of a document, the device comprising:

means for generating a score for each point on a surface of a three-dimensional image, the score quantifying a likelihood that a particular one of the points is located in the groove;

means for fitting a plurality of lines through the points;

means for calculating a value for each of the plurality of lines based on the scores of the points that comprise the line; and

means for selecting one of the plurality of lines as a line that defines a location of the groove based on the calculated values.

24. The device of claim 23, wherein the device further comprises:

means for biasing the scores of the points that are located closer to a middle of the three-dimensional image more than the scores of the points that are located further from the middle of the three-dimensional image.

25. The device of claim 23, wherein the means for calculating comprises:

means for calculating the value for each of the plurality of lines as a sum of the scores of the points corresponding to the line.

26. A computer-readable medium containing instructions that when executed by a processor cause the processor to:

generate a score for each point on a surface of a three-dimensional image, the score quantifying a likelihood that a particular one of the points is located in a groove defined by a spine of the document;

fit a plurality of lines through the points;

calculate a value for each of the plurality of lines based on the scores of the points that comprise the line; and

select one of the plurality of lines as a line that defines a location of the groove based on the calculated values.

27. The computer-readable medium of claim 26, wherein the points on the surface of the three-dimensional image are generated using an infrared projector.

28. The computer-readable medium of claim 26, wherein the points on the surface of the three-dimensional image are generated using a stereoscopic infrared camera.

29. A method for detecting a groove defined by a spine of a document, the method comprising:

generating a score for each point on a surface of a three-dimensional image, the score quantifying a likelihood that a particular one of the points is located in the groove;

biasing the scores of the points that are located closer to a middle of the three-dimensional image more than the scores of the points that are located further from the middle of the three-dimensional image;

fitting a plurality of lines through the points;

calculating a value for each of the plurality of lines based on the scores of the points that comprise the line; and

selecting one of the plurality of lines as a line that defines a location of the groove based on the calculated values.

31. The method of claim 29, where the calculating a value for each of the plurality of lines includes:

calculating the value for each of the plurality of lines as a sum of the scores of the points corresponding to the line.

32. The method of claim 31, wherein the selecting one of the plurality of lines as a line that defines the location of the groove further comprises:

selecting a line with a highest calculated value as the line that defines the location of the groove.

33. A computer-readable medium containing instructions that when executed by a processor cause the processor to:

generate a score for each point on a surface of a three-dimensional image, the score quantifying a likelihood that a particular one of the points is located in a groove defined by a spine of a document;

bias the scores of the points that are located closer to a middle of the three-dimensional image more than the scores of the points that are located further from the middle of the three-dimensional image; and

detect a location of the groove based on the biased scores.

34. The computer-readable medium of claim 33, further comprising instructions that when executed by the processor cause the processor to:

fit a plurality of lines through the points;

calculate a value for each of the plurality of lines based on the scores of the points that comprise the line; and

select one of the plurality of lines as a line that defines the location of the groove based on the calculated values.

35. The computer-readable medium of claim 34, further comprising instructions that when executed by the processor cause the processor to:

calculate the value for each of the plurality of lines as a sum of the scores of the points corresponding to the line.

36. The computer-readable medium of claim 34, further comprising instructions that when executed by the processor cause the processor to:

select one of the plurality of lines as the line having a maximum value.

37. The computer-readable medium of claim 33, wherein the document is a book.

38. The computer-readable medium of claim 33, wherein the document is a magazine or catalog.

39. The computer-readable medium containing instructions that when executed by a processor cause the processor to:

generate a score for each point on a surface of a three-dimensional image, the score quantifying a likelihood that a particular one of the points is located in a groove defined by a spine of a document;

bias the scores of the points that are located closer to a middle of the three-dimensional image more than the scores of the points that are located farther from the middle of the three-dimensional image;

fit a plurality of lines through the points;

calculate a value for each of the plurality of lines based on the scores of the points that comprise the line; and

select one of the plurality of lines as a line that defines a location of the groove based on the calculated values.

40. The computer-readable medium of claim 39, further comprising instructions that when executed by the processor cause the processor to:

calculate the value for each of the plurality of lines as a sum of the scores of the points corresponding to the line.

41. The computer-readable medium of claim 40, where, when selecting one of the plurality of lines as a line that defines the location of the groove, the instructions cause the processor to:

select a line with a highest calculated value as the line that defines the location of the groove.