9 ms·
Page Dewarping
- Syzygies 10y agoThis 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.
- radarsat1 10y agoI've always thought it should be possible using a short video of the camera orbiting the page from different angles. (Assuming a static scene of course.)
- manmal 10y agoOr now, some frames of a live photo.
- mzucker 10y agoThat sounds like a good idea and pretty straightforward to implement -- now I almost wanna try it...
- niftich 10y agoRecently, Dropbox wrote about dewarping prior to OCR in their app: https://news.ycombinator.com/item?id=12297944 https://news.ycombinator.com/item?id=12297944 This code had the same idea, and is open-source!
- marcusjt 10y agoNo, what this code does is much more sophisticated - Dropbox do not dewarp (i.e. remove non-linear distortions) they only transform the image to make the document rectilinear (leaving the distortions/deformations intact), which is much simpler.
- vidarh 10y agoDewarping images for OCR isn't a new idea at all - while older systems used to do simple de-skew (tilting the image) for speed reasons, the need for warping the image to improve results has been known for a very long time, and most production quality OCR engines has done something like it for a long time. (this isn't to slight the article - it's a great, well written presentation on how to implement it)
- cooper12 10y agoI 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.
- Ciantic 10y agoI 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.
- mortenjorck 10y agoPage warp becomes but a tiny part of the problem with a page-flip video – now you have motion blur, varying exposure, resolution, noise, and depth of field to worry about. Maybe if you had a camera capable of recording extremely high frame rates at high resolution (probably north of 120fps @ 1440p), a high-intensity, diffuse light source, and a lens with a tight aperture / narrow focal length, you’d at least have something to work with.
- voxic11 10y agoDoesn't that describe most modern cell phone cameras?
- Jarwain 10y agoI haven't heard of a phone camera that can do video at 120fps, they're usually 30, maybe 60 fps. The S7 has some high framerate slow-mo option, but it's limited to a 720p resolution.
- chrisfosterelli 10y agoThe iPhone 6S records 1080p at 120 fps and 720p at 240 fps for their Slow-Mo feature [0]. [0]: http://www.apple.com/ca/iphone-6s/specs/ http://www.apple.com/ca/iphone-6s/specs/
- loeg 10y agoThe iphone 6S can do 120 fps for a short period of time.
- gamman 10y agoMaybe close enough: http://spectrum.ieee.org/automaton/robotics/robotics-software/book-flipping-scanning http://spectrum.ieee.org/automaton/robotics/robotics-softwar...
- jgable 10y agoThis 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.
- kazinator 10y agoIf she literally scans it with a scanner, why would it need dewarping? This is for when you use a digital camera on pages not lying flat. If you have the option go for scanning. Scans still benefit from cleanup, such as rotation and adjusting the levels (making everything near white perfectly white) and possibly manual cleanup (removal of specks of dust or the odd hair that was on the scanner).
- jgable 10y agoShe scans it in a scanner, but the music is often in large books that don't lay completely flat, so you still see the warping near the binding.
- kazinator 10y agoAh that; it's a major difficulty. A problem is that not only does the shape warp, but any part of the image that is lifted away from the scanner glass, even slightly, gets blurred quite a bit.
- mcshicks 10y agoI built one of these, it's really simple and quick to make. http://www.instructables.com/id/Bargain-Price-Book-Scanner-From-A-Cardboard-Box/ http://www.instructables.com/id/Bargain-Price-Book-Scanner-F... They still warp, but less than laying flat on the table and it's quicker if you do all the even pages, then all the odd pages. Actually the hardest part is making the camera stable so it doesn't move when you press the button. Lots of info on different hardware setups and scanning software here that can batch translate into pdf and different formats. http://www.diybookscanner.org/forum/index.php http://www.diybookscanner.org/forum/index.php
- artursapek 10y agoI've always been interested in getting into graphics programming, and stuff like this only makes me more interested. Really well written post.
- mzucker 10y agoThanks for the feedback, everyone -- happy to answer questions here or in the Disqus comments on my blog.
- tomn 10y agoThis is really interesting, thanks! If you decide to try to make this faster, check out ceres[0] a non-linear least squares optimisation framework that does automatic differentiation using a clever C++ template hack. I've used it a few times to solve these kind of problems and found it to be very good! [0] http://ceres-solver.org/ http://ceres-solver.org/
- mzucker 10y agoYep, I'm still waiting to use ceres for something - I didn't end up using it on my image approximation project https://mzucker.github.io/2016/08/01/gabor-2.html https://mzucker.github.io/2016/08/01/gabor-2.html because it doesn't work well with inequality constraints.
- tomn 10y agoAh yes, only supporting constraints on the parameters can be annoying if your problem requires that.
- owernonvl 10y agoI really enjoyed the article! By the way, you mentioned using word boundaries in regexes to replace variable names. GNU Emacs regexes can actually include "symbol boundaries" (which are a little better for variable names than word boundaries), represented as "\_<symbol\_>". Personally, I like using the "highlight-symbol" package, which provides the "highlight-symbol-query-replace" command to basically execute M-% for the symbol at point.
- mzucker 10y agoCool - will check it out!
- troymc 10y agoI 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!
- claar 10y agoYes, Office Lens is great for that. I recently switched to CamScanner, which has an even better algorithm for deskewing pages (take a pic of a receipt at an odd angle, it automatically transforms it to flat and rectangular). Pro version was on sale -- I'm not affiliated, just a happy customer and highly related to this article.
- reitanqild 10y agoI have it as well, but use Office Lens or Google Drive (create a shortcut to a folder on home screen of android device and use it to scan into it). The reason is CamScanner tried to upsell me to some monthly plan. For all good advice on HN that you should build recurring revenue: It seriously annoys me when people tries to do that by demanding monthly payments for static features. (Totally OK with selling license keys for new features etc.)
- reitanqild 10y agoUpdate: CamScanner is now less annoying than what I used to remember. I might actually be switching back.
- saynsedit 10y agoIs 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.
- mzucker 10y agoThe main rationale is removing redundant degrees of freedom -- since the page is allowed to rotate freely, the edges of the page can still move around plenty.
- saynsedit 10y agoI see, so basically assume the two end points are at zero and there is some rotation accounting for the endpoint offset in real space. It still doesn't seem fully accurate as I can imagine a non-rotated cubic curve with endpoints at an offset, but I assume your simplification works well enough.
- kazinator 10y agoThis 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 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.
- kctess5 10y agoDivide by blur is very crafty. Will have to give that a shot next time I have a similar need in Photoshop.
- drcode 10y agoAs a comic artist working with scanned images, the "divide by blur" trick is going to save me significant effort in the future. THIS is exactly the sort of insight I wish I would get when I click one of those "one weird trick" links!
- peterjmag 10y agoit 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. :)
- Freak_NL 10y agoOr compromise; write up an awesome blog post about how you wrote software to turn their photos into proper scans, and reject their homework (with a link to the blog post).
- vidarh 10y agoReject it, in the form of a picture of a handwritten note on a print-out of his jpegs.
- Asooka 10y agoFor full effect, put the jpeg print outs on a wooden table, stick the note to it, take a photo, put it in word and take a photo of the screen.
- anowell 10y agoThis 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.
- deleted 10y ago[deleted]
- nullcipher 10y agoWrap this in a service and you have a startup!
- renlo 10y agoHow 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.
- mzucker 10y agoPretty sure focal length would affect things as you say, but also physical dimensions matter too. My program assumes fixed focal length and then picks the page dimensions that work with the assumed focal length -- almost certainly not the correct ones.
- voltagex_ 10y agoThank you for the gif near the start - it really helped me to understand what was going on.
- anilgulecha 10y agoHere'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..
- brownbat 10y agoI've used some free apps that turn phones into document scanners. Almost all banks I use have something like that embedded for check deposits. Maybe they're just doing deskew rather than dewarping though... loose documents aren't usually warped like book pages. The next hard problem would be help with DIY book scanning. Like the camera could sit over my shoulder and detect when I've turned a page, then automatically take a picture of the new page. Then OCR kicks in, and conversion to EPUB, preserving graphics when pages have non-text elements. Mostly just feel like we can probably do better than the massive contraptions over at www.diybookscanner.org
- paul_milovanov 10y agoConsider mentioning Dan Bloomberg as the author of the original work as well as Leptonica. :)
- petters 10y ago"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.
- mnw21cam 10y agoCompared to weather prediction, which is an optimisation problem involving hundreds of millions of variables, and occupies a hefty supercomputing cluster for a few hours.
- amelius 10y agoThe 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?
- vidarh 10y agoPlenty of engines will do OCR and use the shapes recognised with high certainty to affect how they detect the rest. There are many ways of doing this, and you can achieve some results even without knowing if your image is text, but just has lots of self-similarity by virtually sliding a "grid" over the image, slicing it up into n-by-n squares, running any of a number of nearest-neighbour variants over it, and then for each cluster replace all instances of the squares in the cluster by the one which minimise the overall error rate vs the others. This will work reasonably well for very structured images such as text, as long as enough characters are near correct, and will retain custom fonts etc. but clean them up quite a bit as long as they either are different enough, or occur often enough on a page to not get "corrected". I'm sure there are better ways of doing this too - it's been a decade since I kept up with OCR research.