from Hacker News

Page Dewarping

by pietrofmaggi on 8/18/16, 1:45 PM with 70 comments

• by kazinator on 8/18/16, 9:38 PM

  This strikes close to home for me, because I've done this "by hand" quite a number of times, using some interactive Gimp filters, with very good results. I've been able to take a perspective photo of a curved page lying on a desk, get it almost perfectly straight, and threshold it to clean black and white or sharp gray scale.

  Here is my very quick and dirty manual job of the same example page:

  http://www.kylheku.com/~kaz/dewarp.png

  Literally less than five minutes.

  First I cropped the image. Then duplicated the layer. Blurred the top layer (Gaussian, 50 radius). Then flipped to Divide mode and merged the visible layers. This leveled the lightness quite well, almost completely eliminating the shadow over he right side of the page and all other lighting differences. There is a hint of the edge of the shadow still present because it is such a sharp contrast; but that can be eliminated in an adjustment of the intensity curves. In such cases it may be helpful to experiment with smaller blur radii, too.

  I then did a perspective transform in the lateral direction, squeezing the left side top-bottom and expanding the right, resulting in the warp now being approximately horizontal. (The perspective transform is not just for adding a perspective effect; it is also useful reversing perspective!)

  Finally, I used the Curve Bend (with its horrible interactive interface and awful preview) to warp in a compensating way. Basically, the idea is to draw an upper and lower curve which is the opposite of the curve on the page. I made two attempts, keeping the results of the second.

  If the preview of this tool wasn't a ridiculous, inscrutable thumbnail, it would be possible to do an excellent job in one attempt, probably close to perfect.

  Because the page is evenly light thanks to the divide-by-blurred layer trick, it will nicely threshold to black and white, or a narrow grayscale range.

• by cooper12 on 8/18/16, 5:29 PM

  I love well-illustrated writeups. Even a reader without mathematics or programming knowledge can understand what steps the author took. His model actually seems to better represent the warped paper than a cylinder would. (though I don't know the actual specifics of the CTM model)

  I wish he went into more details on the steps taken after dewarping. You can tweak the image levels to get good contrast, but surprisingly there aren't any shadows from underleveling or loss of detail from overleveling. I wonder if the author ran OCR on the scans after, and speaking of OCR, IIRC Leptonica is one of the dependencies of Tesseract so it must do some similar pre-processing.

  Edit: reading more carefully, he mentions that he used adaptive thresholding from OpenCV.

• by niftich on 8/18/16, 5:27 PM

  Recently, Dropbox wrote about dewarping prior to OCR in their app: https://news.ycombinator.com/item?id=12297944

  This code had the same idea, and is open-source!

• by troymc on 8/18/16, 7:55 PM

  I use Microsoft's "Office Lens" app on my Android phone all the time, like a "smart camera" which automatically squares off and white-balances each photo of a page (usually mail or forms filled in by hand). It can't handle warped pages though, so I hope they add something like this!

• by peterjmag on 8/18/16, 10:00 PM

  it came in handy whenever a student emailed me their homework as a pile of JPEGs.

  Gotta admire this guy's resourcefulness—and patience. If I were a professor, I'd probably just reject the assignment outright if a student sent me a bunch of photos from their smartphone in lieu of a PDF or a "proper" scan. :)

• by mzucker on 8/18/16, 7:35 PM

  Thanks for the feedback, everyone -- happy to answer questions here or in the Disqus comments on my blog.

• by anilgulecha on 8/19/16, 5:58 AM

  Here's something that I think has not been done, but could be quite lucrative, building a high resolution scanner using the phone camera, multiple pictures and interpolation/noise removal.

  Most phone cameras these days have good resolutions, and you could technically take a 6x4 photo, divvy it to 3x3 grid and take close up photos, and have smart algorithms interpolate the pixels to form a single image with high res. I'd even bet you'd results equal to or better than a flat bed scanner.

  For better us, just open the camera preview and slowly pan over the image.

  Has someone tried something like this? With FOSS apps like mosaic, hdr tools and imagemagick, it should be possible. I'm guessing opencv would be needed for interpolation and noise removal..

• by Syzygies on 8/18/16, 5:00 PM

  This problem is fundamentally different with stereo images; there is a hope of reconstructing the exact 3D geometry of the page before flattening, rather than inferring from content. An iPhone app that did this would do well.

• by Ciantic on 8/18/16, 7:14 PM

  I wonder if someone has tried to dewarp whole book from a video when flipping through it. I imagine that could be handy way to copy the whole book.

• by jgable on 8/18/16, 7:18 PM

  This is great! My wife is a music teacher and often scans sheet music so that it's more portable. She has been asking me for a while for something exactly like this. I'll have to tweak it to work on sheet music, since I imagine his methods to identify lines of text won't work for the music staff out of the box.

• by amelius on 8/19/16, 8:35 AM

  The next step would be to "depixelate" the resulting image. How could this be done? I guess OCR would not work because of the variation of the fonts (you don't want the document to end up in a single font; you want to keep the fonts). Could a deep learning approach work here, even if it has not been trained on all the specific fonts?

• by renlo on 8/19/16, 1:12 AM

  How much of an effect does the camera lens make in page warping? Correct me if I'm wrong, but for shorter focal length lenses I would think it would warp the page more. If a person accounted for that, could they get a near perfect result? Or does his algorithm account for that? It seems that one would need to know where the center of the image would be.

• by petters on 8/19/16, 8:33 AM

  "You can see these are not exactly small optimization problems. The smallest one has 89 parameters in the model, and the largest has 600."

  Those are small optmization problems. These types of problems are solved in computer vision for hundreds of thousands of variables. His problem can be solved in real-time, not tens of seconds.

• by paul_milovanov on 8/19/16, 6:04 AM

  Consider mentioning Dan Bloomberg as the author of the original work as well as Leptonica. :)

• by voltagex_ on 8/19/16, 3:17 AM

  Thank you for the gif near the start - it really helped me to understand what was going on.

• by saynsedit on 8/18/16, 8:00 PM

  Is using a curve whose end points are fixed to zero to model the warping accurate? I can't see a rationale for why the end points should both be 0.

• by artursapek on 8/18/16, 7:30 PM

  I've always been interested in getting into graphics programming, and stuff like this only makes me more interested. Really well written post.

• by nullcipher on 8/18/16, 10:57 PM

  Wrap this in a service and you have a startup!

• by anowell on 8/18/16, 10:53 PM

  This is solid. I'm an engineer at Algorithmia, and this caught our attention as the sort of project we love to host as a service on our algorithm marketplace. We've already made note of it for our team to consider adding (thanks to the generous MIT license), but I wanted to reach out in case you'd rather add, own, and optionally monetize it on our platform yourself. Either way, this was a great read with impressive results.