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.'"
More importantly (Score:2, Funny)
Does it run on Linux? Does it work for scanning porn?
Re: (Score:2)
Re: (Score:2)
IMPORTANT QUESTIONS (Score:2, Funny)
Re:IMPORTANT QUESTIONS (Score:4, Funny)
The same way as your face.
Re: (Score:2)
note to self: (Score:2, Funny)
do NOT sit on the copier machine with pants down at google hq
Patent!!??!! (Score:5, Funny)
Re:Patent!!??!! (Score:4, Funny)
So why didnt you do or patent it before?
Re: (Score:2, 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:Patent!!??!! (Score:4, Informative)
Re: (Score:2)
they patented this new 3D barcode system.
Really, I've never seen a 3D barcode on anything. maybe 2D, but definitely no 3D barcodes on my packages.
Re: (Score:2)
Re: (Score:2, Interesting)
I hate patents as much as anyone else, but:
1) This isn't so obvious, and requires some fairly complex math
2) It is pretty complex (in the way it functions), enough that i would actually consider this patent-worthy.
But, there is some "prior art" of such functions in the visible range for scanning bodies IIRC.
I believe this was meant to be funny, and i shall accept incoming whooshes of air with joy.
Have at you.
note: i still hate patents though.
I can't see why they would benefit from patenting this method...
I
Re: (Score:2)
I hate patents as much as anyone else, but: 1) This isn't so obvious, and requires some fairly complex math 2) It is pretty complex (in the way it functions), enough that i would actually consider this patent-worthy.
I would add that at least this patent is not solely a software patent; it has a hardware component.
Re: (Score:2)
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: (Score:3, Funny)
Whoa, "radon transform"? Hold on a second, wiz-kid. Does that use poisonous gas or something? It's certainly not mathematics, because that means stuff like "three times four".
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: (Score:3, Insightful)
I almost feel bad. I know what a radon transform is and I've taken a class on inverse problems.
My point was just that the common view of what is mathematics is rather anemic and quick to give engineering credit to relatively simple ideas. I suspect that the patent office has similar fallacious thinking.
Re: (Score:2)
So... (Score:5, Interesting)
They've been making "anti-copy paper" designed to defeat optical scanning for years now, surely something similar in the IR band could be effected...
Re: (Score:3, Insightful)
Maybe those books are less important to commit to a digital scan ;-)
Re:So... (Score:5, Insightful)
Failing that there are alternative methods that might work as well.
Re: (Score:2)
Why? Just as you said, they already have anti-copy paper. If you don't want someone to be able to copy your book, simply print using that (of course, that will cause your costs to skyrocket). It's not as if the IR block would prevent the copy, it'd just mean the copy looks like crap (thus potentially impacting your image as a publisher).
Re: (Score:2)
Re: (Score:2)
Two things, first off, they just use something else to accomplish the same thing. If you can read it, something else can as well. It may not be as fast, it may take some time and money to develop and optimize but that amount of time and money is probably pretty trivial to Google.
Second, Google doesn't care about any book that can do that at this time, they are going after old works currently, that aren't being produced by anyone anyway, so nothing they are going after right now is going to be affected by
Shhh! Don't Give Them Ideas! (Score:2)
If the publishers see this article, the next book I want to read is going to be written in capchas!
The really hard ones without an audio guide!
Re: (Score:2)
Would it matter with the 100s of millions of books that are already there they have go to thru first?
Wish i had that at home, would love to scan a lot of my stuff but refuse to cut it.
Re: (Score:2)
Before one does it? Not long. Before any significant amount of product is produced using it? Probably forever, on cost and particularly cost/benefit issues. Besides, if the protected product produced was particularly interesting to those wanting to scan it, they could almost certainly modify the scan system to accomodate
Re:So... (Score:4, Interesting)
With respect to the foolishness over "copy protection" it is interesting to consider the possible application of the old line "the worse, the better." [wikipedia.org] The idea is that, in order for a bad situation to change, it must get worse, so that the cost of tolerating it becomes unbearably high. As long as DRM and anti-copy paper, and macrovision and all the others cause relatively limited customer displeasure and support calls, there will be little incentive to change, and things will remain as they are. If you can drive the content guys to ever more intrusive measures, things might actually get bad enough to spur a blowback.
Patent? Prior Art? (Score:3, Insightful)
Wasn't this a Sci-Fi movie staple back in the 80s? They used it for body and object scanning, not books...but still.
Re: (Score:2)
Why did they run an OCR on a body scan? :D
Re: (Score:3, Funny)
The New Bell Labs? (Score:5, Interesting)
I've read many comments over the years about the old Bell Labs and how a huge amount of pioneering research came out of them over the course of their existance, i.e. before they got axed.
It would seem that Google Labs is performing somewhat the same function, albeit more oriented towards software rather than physical research.
Re: (Score:3, Interesting)
Doesn't Google have something called the 20% policy or something like that? Where Google engineers devote 20% of their time to non-Google projects?
Not exactly basic research, but not necessarily commercial applications.
The closure of Bell Labs is
Re: (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.wikip [wikipedia.org]
Mostest importanly... (Score:4, Interesting)
...who's flipping the pages?
Re: (Score:3, Funny)
I heard from some guy, somewhere, that on weekends the Oompa Loompas do it.
Re: (Score:2, Informative)
Obvious question... (Score:2)
That's cool and all that, but who (or what) flips the pages?
--riney
Re:Obvious question... (Score:4, Funny)
That's cool and all that, but who (or what) flips the pages?
Interns.
You laugh, but look at this (Score:5, Interesting)
That's modded funny, but take a look at this. [google.com]
Maybe they use automated page turning machines for normal books, and turn pages by hand for older/more fragile works?
Re:You laugh, but look at this (Score:5, Funny)
Now THAT'S a page turner.
Ba dum dum. Thanks, I'll be here all week! Try the veal, and don't forget to tip your waitress!
Re: (Score:2)
Dear god, what sort of hideous Lovecraftian monstrosity is pictured turning pages there??? O_O I can't tell if those are fingers or flippers. Burn it with fire!
Re: (Score:2)
I think the strange appearance of the hands is due to the hand moving while being scanned. I remember, in high school, moving my hand inside a scanner while it was being scanned, causing all sorts of fun distortions: wavy fingers, extremely long fingers, etc.
Re: (Score:3, Informative)
Re: (Score:3, Interesting)
This is another one.
http://www.treventus.com/index_en.html [treventus.com]
http://www.youtube.com/watch?v=hlOQuuLYavY [youtube.com]
Unnecessary? (Score:2)
Can't you just calculate the 3D model of the page based on a known stuff?
Make a generic flattener filter that takes in page height and length, as well as page number.
Manually tweak the output a bit for the first and last pages, and then intermediary pages can all be calculated with much more accuracy than you need.
Hell, with this method any book "scanned" (using a camera from overhead) could be processed. Let those college kids who love Google so much run their books through your filters (and do the manual
Re:Unnecessary? (Score:4, Interesting)
Pages lie different from the front to the back of the book, and books are bound differently. So you can't use a generic model and expect it to be accurate in most cases.
I actually think this is really cool because it seems to account for any scenario, including folded pages, I would assume. Although, I suppose that in extreme bends it might not be perfect, but certainly they just need to ensure that pages are adequately flat. It automates the entire process.
I wonder if they've built an automated page-turning mechanism; I would assume they have. Just drop in a book and let the machine go to town on it.
Re: (Score:2)
Re: (Score:2)
I know they do - that's why you take a pic of the first and last pages first, and adjust those.
The 3D model for all pages is the same - a sheet of paper of a certain length and width.
The lay of the paper will be between the two extremes of the first and last pages.
Effectively, you can define the lay of the paper as a simple curve in the x/y plane.
The last page will be a flat line, the first page will be the most eccentrically curved.
Page 3(4) lays almost identical to page 1(2).
The curve is just a little fla
Isn't that all known? (Score:2, Insightful)
Re: (Score:2)
Cite needed.
You really don't understand what a patent is, do you?
Hint: you don't patent ideas.
Re:Isn't that all known? (Score:4, Interesting)
Building 3d computer models by stereoscopic analysis of project light patterns is at least twenty years old. In fact it mentions in the summary that it they use an established technique.
As for your second comment... that's kind of my point. Since the technique is not new, the equipment is not new, what did google do that was new? Perhaps there is some actual invention in the process somewhere; but I don't have enough faith in the patent process to unquestioningly ASSUME that there is.
What are the chances... (Score:4, Interesting)
...that Google licenses this to scanner manufacturers and we see this at a consumer level at some point in the future? I know I'd pay good money for a book scanner that doesn't need to have a 'book edge' (which you already have to pay through the nose for)...
Re: (Score:2)
Re: (Score:2)
This type of image processing requires obscene amounts of memory and CPU time to do.
That's OK; have you heard of Winmodems? Just imagine a cheap scanner that does all the correction in software on your PC.
Butt what about... (Score:2, Funny)
Re:Butt what about... (Score:4, Funny)
Is this what the graphics department is talking about bump mapping?
Karma burn.
Re: (Score:3, Funny)
Why is this a big deal? (Score:5, Insightful)
I don't see why this is such a showstopper for other book scanning projects. Right off the top of my head I can think of three methods of dewarping book scans that have nothing do to with Google's methods. While Google's method is definitely quite interesting and seems like a great solution, it is by no means whatsoever the only way of accomplishing this.
Re: (Score:3, Insightful)
No one said its a big deal, its simply a 'neat' way to accomplish the goal. As geeks we are generally interested in these neat ideas.
No one said Google was evil for patenting it.
No one said Google now has a monopoly on book scanning.
No one really said anything other than 'this is how they do it' and we all said 'neat'.
cool, but not patent-worthy (Score:4, Insightful)
This is useful and interesting, but doesn't seem particularly novel.
Projecting a known pattern onto a surface or using multiple cameras to determine the shape of a surface have been around for quite a while, so adding it to an OCR system doesn't seem like a big deal.
Re: (Score:2)
Yes it is you clueless N00b.
It's the mechanism and how they do it thats patented, not the idea.
If you patent something that turns widgetrs over, I can still patent something else that turns widgets over, as long as is does it DIFFERENTLY.
Seriously people, it's pretty simple.
Yes the Patent office needs to be tuned, but there is nothing wrong with the patent. In fact, what you seem to suggested would make the system completly unusable.
Idiot.
But can they remove finger-scans and hand-scans? (Score:3, Interesting)
De-warping sounds useful, but there are problems that it probably won't solve --
Like the operator who scans a book page with his/her fingers or hand stuck between the page and the scanner-glass. For example, the dreaded 'New York Hand' or its fingers can be seen occupying the place of part of the text or figures on many pages of books scanned for Google-Books from the New York Public Library. On some pages, the impression of the fingers is clear enough to show the rings worn by the Hand that was doing the scanning. :(
It will take more than a de-warping patent to solve that one .....
-wb-
Re: (Score:2)
On that note has anyone tried the option on google books to report unreadable pages and if so do they do anything about it?
Seems like overkill (Score:2)
A typical book page has text on in in parallel lines which can be used to correct for curvature, straight-edge formatted into rectangles which can be used to correct for skew. Who needs another grid?
If a page doesn't have suitable text on it (e.g. a graphic), then just assume it's warped the same as the previous page (the one it's lying on top of).
Wood chipper? (Score:3, Funny)
This is way better than my idea, which was to throw the book into a wood chipper, scan the results, and then algorithmically reassemble them...
OCR (Score:3, Interesting)
Google should return to the open source community a decent OCR app+engine. Tesserac+ocropus are just too little, and it's already too late.
Windows already has decent ocr habilities, any hp scanner comes with decent image to page-document sofware. It's a shame that google, that has been build upon open source and has maybe the best ocr technology in the world, hasn't returned a competitive and free ocr solution for Linux.
Playing Catch-up (Score:2)
... 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.
Especially with that shiny new patent.
Re:Playing Catch-up (Score:5, Insightful)
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: (Score:3, Insightful)
This may be a projector thing, but they are doing something of physical manipulation. It would be pretty much appropriate to be patented. The whole thing is physically transformative. Meanwhile, if someone made their own version using something different, it too, would be patentable/improvement patent, which is how the patent system is supposed to work.
To be clear, I'm saying the system as a whole should be patentable (infrared), but not the software used to decode it.
That reminds me (off topic) (Score:3)
Totally off topic here but I'll risk it.
It really bothers me that neither Rock Band nor Guitar Hero can auto-calibrate the audio lag using the microphone. There's absolutely no reason I can see that they can't "listen" for the calibration beeps with the mic to get a perfect reading.
Re: (Score:2, Informative)
Uhhh doesn't Rock Band 2 do that with a miniature microphone (and light sensor) built into the revised guitar?
Re: (Score:2)
Woah! I own the damn thing and I had no idea. In my defense I play drums 99% of the time. :) Thanks!
Re: (Score:2)
Just when I thought you were going to make an interesting point on the worthiness of patents "in the broader sense" as you put it, it turns out you were just rooting for someone else.
Your comment didn't turn out to be all that "worthy".
In the broader sense, that is.
Re:Playing Catch-up (Score:5, Funny)
This is actually what I envisioned for a book scanner, years ago.
But unlike Google, I...
1) Never built it.
2) Am not facing lawsuits from overzealous sue-happy publishers.
Seems like a good defensive patent to have.
Re:Playing Catch-up (Score:5, Interesting)
This trick has been used for 20 years in astronomy. You shine a really powerful laser of known metrics into the sky and measure the atmospheric distortion suffered by the beam.
Then you take those numbers and calculate what it would take to even out the beam, and you feed THAT set of numbers to a telescope with adaptive optics which will then correct for the atmospheric distortion. Bingo, suddenly your telescope is able to take sharp images without having the air screw it up.
The technique is very effective and results in ground-based telescopes that rival anything the Hubble can do. Plus they are easier to fix.
I want to say this is called Guidestar but I am not sure.
Anyway the similarity to Google's process is simply that you shine a light or image of known value on something unknown and look at how the image now deviates from what you expect. A little math and suddenly you know exactly the shape of the unknown object. Brilliant.
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.
Re:Playing Catch-up (Score:5, Interesting)
Word.
I was involved in evaluating rare books back around the turn of the century.
I can personally attest that representatives of online book search companies were attempting to buy up one of a kind pieces for destructive scanning.
There was one dealer in possession of a somewhat flawed, but well examined Shakespeare folio that had to put the kabosh on a reputation making deal because he found out the buyer was going to slice the piece out of its binding for scanning.
I turned down a much smaller offer on a much less significant, but still very cool, two hundred year old angler's guide (with hand colored plates and original binding) for the same reason.
Quality scans without destruction can only help raise the profile of rare books and the value they offer society - not simply for their content, but as tangible examples of the evolution of the art of communication.
Re: (Score:3, Funny)
If you were a rare book expert during the turn of the century, why isn't your slashdot ID smaller?
;
Re: (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.
Well said. (Score:2)
I'd also much rather hear how they managed the page flipping. Even with a lot of these machines they'd still have to achieve an impressive flipping rate without damaging the page being scanned.
Re: (Score:2)
Especially with that shiny new patent.
Couldn't they just build and operate the scanner somewhere outside the patents coverage area?
Re: (Score:2)
I kind of doubt the patent will stop any competitors. It should be trivial to achieve the same result with dozens of different methods.
I'm kind of surprised they used that method in fact. There should of been several that allowed them to scan the books without even requiring them to fully flip open and lay flat each page. With so many books to scan speed must of been important.
I guess this method worked because the device was so cheap that they could just make a lot of scanners.
Re:Why? (Score:4, Insightful)
Ok, is it just me, but wouldn't it be easier to just cut the spine off the book instead of developing a whole new way of scanning it?
With 7 million books, the manpower and time saved for them to cut the spine off would be worth it.
Also, they can resell the books if needed or give them charity after they are done.
Kind of would be a waste of a paper to tear that many books apart.
Re: (Score:2)
Kind of would be a waste of a paper to tear that many books apart.
Yep, and it would take a lot of spine.
Oh man, I'm like a card catalog of puns today!
Re: (Score:2)
Re: (Score:2)
Keep in mind, the majority of the books they are scanning are old, out-of-print and copyright expired texts. They aren't something you can pop over to Amazon and order another one of. So the bulk ARE old and/or valuable.
Re: (Score:2)
Re: (Score:2)
Read "Rainbow's End" by Vernor Vinge
Re: (Score:3, Insightful)
Re:Why? (Score:5, Informative)
Re: (Score:3, Interesting)
Only if Google refused to license it. Google isn't Microsoft or Intel; I doubt they'd go that route.
In fact, since Google has paid for the innovation of this tech, including the R&D for it, patenting it and then allowing companies to license it reduces the barrier since companies that couldn't have paid for the research now have the technique available to them.
Re:As a writer, I did not give my permission to co (Score:4, Interesting)
Cough, you don't ahve to. I can copy your book all gad damn day long and have not violated your rights or the copyright code.
The moment I try to distribute them, then it's a copyright violation.
It's called copyright, because the only reason one would copy it was to distribute it.
Backup really wasn't an issue then like it is now.
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: (Score:2)