Forgot your password?
typodupeerror
Books Businesses Google Media The Internet Hardware

How Google's High Speed Book Scanner De-Warps Pages 209

Posted by ScuttleMonkey
from the onto-dewarping-brains-next dept.
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.'"
This discussion has been archived. No new comments can be posted.

How Google's High Speed Book Scanner De-Warps Pages

Comments Filter:
  • by Anonymous Coward

    Does it run on Linux? Does it work for scanning porn?

    • Yes and yes, although only scanning in porn magazines instead of actually using it in the porn itself would be a very unimaginative way to use this technology...
  • I wonder how ass curvature comes out with that scanner.
  • do NOT sit on the copier machine with pants down at google hq

  • by aashenfe (558026) on Friday May 15, 2009 @04:27PM (#27972131) Journal
    When is the patent office going to quit giving patents for obvious techniques? :)
    • by sopssa (1498795) <sopssa@email.com> on Friday May 15, 2009 @04:35PM (#27972253) Journal

      So why didnt you do or patent it before?

      • Re: (Score:2, Informative)

        by aashenfe (558026)
        Simple, I was trying to be funny. Notice the smiley :)
    • Re: (Score:2, Interesting)

      by Anonymous Coward

      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

      • by javaxjb (931766)

        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:Patent!!??!! (Score:5, Informative)

      by Timmmm (636430) on Friday May 15, 2009 @05:51PM (#27973099)

      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)

        by retchdog (1319261)

        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)

          by petermgreen (876956) <plugwashNO@SPAMp10link.net> on Friday May 15, 2009 @07:25PM (#27974043) Homepage

          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)

            by retchdog (1319261)

            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.

    • by AHuxley (892839)
      The Russians (iirhad a cute trick too. A tiny spy cam with two lights pointing down on the page. When the two dots where joined the camera was it the right distance and the spy got a quality image of a page.
  • So... (Score:5, Interesting)

    by fuzzyfuzzyfungus (1223518) on Friday May 15, 2009 @04:28PM (#27972143) Journal
    How long before some particularly vengeful luddite publisher starts printing on treated paper stock that has an IR visible pattern, calculated to confuse these scanners, printed on it?

    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)

      by Anonymous Coward

      Maybe those books are less important to commit to a digital scan ;-)

    • Re:So... (Score:5, Insightful)

      by twistedsymphony (956982) on Friday May 15, 2009 @04:43PM (#27972335) Homepage
      they could probably do it in the visible spectrum as well, it would just take twice as long because they can't map and scan at the same time.

      Failing that there are alternative methods that might work as well.
    • by Chyeld (713439)

      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).

    • by bmwm3nut (556681)
      Then you just do phased-lock detection. In the IR with current cheap detectors you can modulate in the kHz without any problem. I wouldn't be surprised if they do that now. In my lab we look for changes in an IR signal that are about 10^8 times smaller than the background IR radiation. It's not a hard problem to solve.
    • by BitZtream (692029)

      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

    • 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!

    • by nurb432 (527695)

      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.

    • by russotto (537200)

      How long before some particularly vengeful luddite publisher starts printing on treated paper stock that has an IR visible pattern, calculated to confuse these scanners, printed on it?

      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

  • Patent? Prior Art? (Score:3, Insightful)

    by mveloso (325617) on Friday May 15, 2009 @04:29PM (#27972163)

    Wasn't this a Sci-Fi movie staple back in the 80s? They used it for body and object scanning, not books...but still.

  • The New Bell Labs? (Score:5, Interesting)

    by ObsessiveMathsFreak (773371) <obsessivemathsfreak.eircom@net> on Friday May 15, 2009 @04:30PM (#27972177) Homepage Journal

    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.

  • by Anonymous Coward on Friday May 15, 2009 @04:32PM (#27972207)

    ...who's flipping the pages?

    • Re: (Score:3, Funny)

      by Anonymous Coward

      I heard from some guy, somewhere, that on weekends the Oompa Loompas do it.

    • Re: (Score:2, Informative)

      There are automatic page turning machines that use puffs of air and a stylus to move through a book.
  • That's cool and all that, but who (or what) flips the pages?

    --riney

  • 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)

      by MaWeiTao (908546) on Friday May 15, 2009 @04:44PM (#27972349)

      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.

      • by againjj (1132651)
        Another poster [slashdot.org] shows that at least one book has been imaged with hand page turning [google.com]. Two pages of fingers.
      • 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

  • by Toonol (1057698)
    The technique is old, many years old. What is google's patent for? The use of a decades-old technique ON BOOKS?
    • by geekoid (135745)

      Cite needed.

      You really don't understand what a patent is, do you?
      Hint: you don't patent ideas.

      • by Toonol (1057698) on Friday May 15, 2009 @06:49PM (#27973693)
        "Looker."

        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.
  • by Shaterri (253660) on Friday May 15, 2009 @04:41PM (#27972305)

    ...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)...

    • by againjj (1132651)
      This is not about the imager per se. It is about the way to take images and post process them afterwords. Basically, they take three pictures, one in visible light and two in infrared, and then use the two in infrared to create a stereoscopic image and correct the image in visible light so it is not warped. From the patent, it does look like the imager is a camera, and not a scanner, since the description talks about a book resting on a platform with cameras above it. I do notice the patent makes no men
  • Imagine what this technology could do for coworkers who like to photocopy their butts!
  • by MBoffin (259181) on Friday May 15, 2009 @04:48PM (#27972403) Homepage

    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)

      by BitZtream (692029)

      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'.

  • by Chirs (87576) on Friday May 15, 2009 @04:56PM (#27972495)

    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.

    • by geekoid (135745)

      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.

  • by waterbear (190559) on Friday May 15, 2009 @05:49PM (#27973077)

    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-

    • On that note has anyone tried the option on google books to report unreadable pages and if so do they do anything about it?

  • 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).

  • by mkcmkc (197982) on Friday May 15, 2009 @06:30PM (#27973511)

    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)

    by 12357bd (686909) on Saturday May 16, 2009 @04:10AM (#27977119)

    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.

You know, the difference between this company and the Titanic is that the Titanic had paying customers.

Working...