How Google's High Speed Book Scanner De-Warps Pages 209
Hugh Pickens writes "Patent 7,508,978, awarded to Google, shows how the company has already managed to scan more than 7 million books. Google's system uses two cameras and infrared light to automatically correct for the curvature of pages in a book. By constructing a 3D model of each page and then 'de-warping' it afterward, Google can present flat-looking pages online without having to slice books up or mash them onto a flatbed scanner. Stephen Shankland writes that the 'sophistication of the technology illustrates that would-be competitors who want to feature their own digitized libraries won't have a trivial time catching up to Google.' First, a book is placed on a flat surface, while above it, an infrared projector displays a special mazelike pattern onto the pages. Next, two infrared cameras photograph the infrared pattern from different perspectives. 'The images can be stereoscopically combined, using known stereoscopic techniques, to obtain a three-dimensional mapping of the pattern,' according to the patent. 'The pattern falls on the surface of (the) book, causing the three-dimensional mapping of the pattern to correspond to the three-dimensional surface of the page of the book.'"
Re:Playing Catch-up (Score:5, Informative)
Notably, for instance, there has been a fair bit of interest, for some years, in using digital cameras in concert with projectors, either for automatic keystone/distortion correction, for projectors that aren't perfectly aligned with the projection surface, or for automatic coordination of multiple projectors illuminating the same surface, without laborious manual tiling adjustment. This is, in essence, an equivalent problem(inferring a surface's geometry based on pictures of a known image projected upon it).
The IEEE has held "Projector-Camera systems" workshops since 2003 [procams.org], and somebody was obviously working on it before that. I'm not saying that Google's patent falls into asshole troll territory or anything; but the notion of doing surface geometry inference based on known image projection isn't nearly as novel as it might seem.
Re:Patent!!??!! (Score:2, Informative)
Re:Obvious question... (Score:3, Informative)
Re:Patent!!??!! (Score:5, Informative)
I believe the pattern barcode scanners use is simply trying to look for the barcode in several different directions, but I could be wrong.
I also believe there's either rudimentary correction for common types of distortion (i.e. on cylindrical objects) or just wide enough tolerances to allow it to work anyways.
Re:Why? (Score:5, Informative)
Re:That reminds me (off topic) (Score:2, Informative)
Uhhh doesn't Rock Band 2 do that with a miniature microphone (and light sensor) built into the revised guitar?
Re:Patent!!??!! (Score:4, Informative)
Re:Patent!!??!! (Score:5, Informative)
You jest, but this technique *has* been around for years. I remember when digital cameras first became available there was a product that could perform a 3D scan by projecting a pattern onto the object and using an offset picture. I think the pattern came on a slide - that's how long ago it was! Here's a whole wikipedia page about the scanning technique: http://en.wikipedia.org/wiki/Structured_Light_3D_Scanner [wikipedia.org]
This picture is especially good: http://en.wikipedia.org/wiki/File:6-seat.jpg [wikipedia.org]
Anyway after reading the patent abstract, it isn't about the 3D scanning at all, it appears to be about an algorithm to find the fold once you've already got the point cloud. I would have thought that was fairly trivial. A possible approach would be to take the radon transform of the height map and find the smallest value that's roughly in the middle.
Re:Playing Catch-up (Score:3, Informative)
Really? Structured light to find 3D geometry is old hat ... the optical and signal processing part of book scanning seem pretty easy, making the mechanical part for page flipping robust seems a lot harder to me.
Re:As a writer, I did not give my permission to co (Score:4, Informative)
Be sure to check out the exclusive rights in copyrighted works [cornell.edu] before making blanket assertions on what is and is not legal under copyright law. The exclusive rights granted by copyright include both reproduction and distribution. There are lots of exceptions to these exclusive rights, but an interpretation that completely eviscerates the exclusive right to reproduce a work is not supported by the Copyright Act.
Re:Patent!!??!! (Score:4, Informative)
It certainly is mathematics and it's not that hard to understand either. basically it is the mathematical equivilent of what a hard field tomograph does.
Consider a function of two values and consider those values to be 2D coordinates. Consider also that the function is zero outside of a defined area.
Now consider that there are an infiniate number infinitely long number of straight lines passing through that area and each can be defined by two parameters, an angle and an offset from the orgin in the direction perpendicular to the line.
Along each of those lines an integral can be calculated. those integrals form the radon transform of the function (with each integral being identified by the two parameters).
Not really that complicated, the trickiest bit is probablly deciding how best to approximate the line integrals from your limited number of data points.
Re:Mostest importanly... (Score:2, Informative)
Re:The New Bell Labs? (Score:3, Informative)
I can't find proof in a quick search, but I do remember others posting responses here recently (possibly Anonymous Cowards) to people mentioning the 20% time with things like (paraphrase) "that will be useful for Google". In other words, the implication (or at least my inference) was that while they are technically "non-Google", the intent was that eventually they would be Google projects or the projects would be killed off.
I have no first hand knowledge of that, however.
The small paragraph http://en.wikipedia.org/wiki/Google#Innovation_Time_Off [wikipedia.org] is interesting, and says (with a citation)
Re:Playing Catch-up (Score:5, Informative)
It's simply called adaptive optics (AO). In AO, a guidestar is a natural isolated point-like star that is close to your science object (what you are trying to look at). If a laser is used to excite the sodium layer to create an artificial reference, it's called a "laser guidestar".
Anyway, this "trick" is completely different from adaptive optics in both the mathematics and implementation.