Dekeystoning with a checkerboard

[rob]

I've only tried this on a single image so far, but I got excited, so I thought I would share.

To make things easy on Scan Tailor, I figured that I could correct for keystoning by throwing a checkerboard onto the platen every N pages, and once all the scanning was done, have a preprocessor program run through the images, find the checkerboard calibration images, and dekeystone all following page images from there (until the next checkerboard image was encountered). If you have to change the location, orientation, or zoom of the camera, you would have to throw the checkerboard back up to add a new calibration image.

The goal here is to correct for distortion caused by camera location and orientation with respect to the platen. NOT with respect to the book, which is what Scan Tailor is for.

So I wrote a program (in C, and I cried while doing it) which takes one checkerboard image, computes a dekeystoning correction, and applies it to a second image. I used OpenCV, which is a free image processing library that has checkerboard detection routines.

Here are the results. Discussion follows after each image.

p001 checkerboard.jpg (56.91 KiB) Viewed 7865 times

Here are small versions of the checkerboard image (left) and the same image after automatic correction (right). Since the checkerboard is supposed to be square, it is easy to take the four detected corners, figure out where they were supposed to be if the checkerboard image were truly square, and compute a transform which corrects the image.

Here is what was hiding behind the checkerboard. I added a thin rectangle around the text block so you can see that there is keystoning: at the bottom, the text breaks out of the box, even though the top and bottom margins appear pretty straight.

NOTE: Click on the image to see in full. For some reason, the scrollbars aren't appearing in my browser so I can't see the entire image. If that happens to you, just click on the image to see the whole thing.

I applied the checkerboard correction parameters that I found in the checkerboard calibration image to the page image. (The exposure looks different because I manually corrected it. Not well enough, obviously) At first I was puzzled because the image seemed rotated, but I realized that perhaps the book was rotated slightly with respect to the platen. So I unrotated the image (in Photoshop) and applied a thin rectangle. The results are much better. I believe that any distortion remaining is due to warping.

So in theory, ST should have an easier time with this image in terms of automatically rotating it, finding margins, and dewarping.

The next step is to alter the program to run through a list of images, and then release the program. Sadly, the program is C and relies on external libraries (namely, OpenCV), which means this isn't going to be as polished as Scan Tailor :/

The two-image program source code is attached, if anyone is interested. It requires OpenCV 2.2.

[ahmad]

Very impressive.

I am planning to use a similar technique in my single-camera scanner, except it will only be calibrated once per book, manually using Hugin, then corrected with Panotools. I'm far too stupid to code automatic calibration, particularly in C!

[Shaknum]

This is amazing, and just what we need. I can throw out lightroom, and stop wasting my time. I do have one modest suggestion. While you have a checkerboard pattern up there anyway, could you compute the dpi and add that to the image's metadata? Just a thought that might save even more time. I currently use a grid image on my first shot for each book, which helps me see things well enough to manually adjust keystone and then also compute DPI. Thanks again for putting this together, I'm off to try it out.

[rob]

Yes, can definitely calculate DPI, as long as you know how big the squares are. I haven't worked on that yet, since I don't know how to get OpenCV to save as a JPG with dpi information.

In the next post is the final program source code: you will need both OpenCV 2.2 and Qt. The program is not good enough for the end user, so for now it's strictly developers only. Or Tulon only

Here also is an 8x8 checkerboard for use with the program (which assumes an 8x8 checkerboard). Print it out (making it smaller if you need to), trim it so that there is about one square of whitespace around the checkerboard, and paste it onto something fairly flat (a pane of glass is ideal). Place the calibrator on top of the platen, not under the platen. Make sure the entire checkerboard is viewable in the camera AFTER you set the location, orientation, and zoom on a typical page in your book! Then take a picture of the checkerboard on the platen. You will probably want two checkerboards so that you can calibrate both sides at the same page.

After you take the checkerboard image, remove the checkerboards, not changing the location, orientation, or zoom of the camera, and continue taking page images. You can probably get away with many tens of pages before adding another checkerboard calibration image.

Usage: ./program <Directory of images>

The program will find all the .jpg/.jpeg images in the directory, sort them alphabetically, and go through them one by one. If it finds a checkerboard, it will use it for calibration. Note that images without checkerboards take a little while to search. If a checkerboard isn't found in an image, the previous calibration will be used, and the file will be output to "dekeyed <original filename>".

[rob]

Source code for program. This version does a fast check of the image first, to determine if there might be a checkerboard in it. Makes the whole program faster. Also puts the program under GPL v3 license.

To compile under MacOS. May be useful also under Linux. Windows, you're on your own.

Code: Select all

sudo port install qt4-mac
sudo port install opencv
g++    -c -g -I/opt/local/include -MMD -MP -MF main.o.d -o main.o main.cpp
g++     -o camera main.o -L/opt/local/lib -lopencv_calib3d -lopencv_core -lopencv_highgui -lopencv_imgproc -lQtCore


[Shaknum]

I added just a couple of lines so it will at least tell you the dpi if you tell it how many inches the width or height of the checkerboard pattern is, for example: ./camera <Directory of images> <Width of checkerboard in inches> (the second argument can be a decimal as well as an integer).

main-dpi.cpp

(8.04 KiB) Downloaded 179 times

[Shaknum]

I'm trying to figure out what I need to do to write the DPI info straight into the EXIF data, but haven't had much time yet. This is a fantastic little program and the really cool thing is that by adding DPI info we won't have to worry about changing the camera's zoom in the middle of a book scan. For instance, say you are scanning a book and you choked up on it pretty far to maximize the resolution and all of a sudden you hit a page that is bigger than the rest. You just stop taking pics, zoom out a bit, take a pic with the checkerboard and then continue until you want to zoom in again. Also this would be useful with cameras with auto-zoom when you want to stop mid book turn the cameras off, get a good night sleep, then come back in the morning. As long as this thing computes your DPI, which it now does, your pages will end up being the same size after you run them through ScanTailor, or whatever.

[matt]

To compile under MacOS. May be useful also under Linux. Windows, you're on your own.

I'm able to compile (under Mac OSX) the program but it seg faults immediately. Any ideas on how to troubleshoot?

Code: Select all

~$ g++    -c -g -I/opt/local/include -MMD -MP -MF main.o.d -o main.o main.cpp
~$ g++     -o camera main.o -L/opt/local/lib -lopencv_calib3d -lopencv_core -lopencv_highgui -lopencv_imgproc -lQtCore
~$ ./camera
Segmentation fault
~$


[rob]

Sadly, no, I don't know how to debug it. :_( Sorry, but C isn't my native language.

I'm thinking about a Java version using Q-codes...

[Shaknum]

Any ideas on how to troubleshoot?

No idea how to troubleshoot, but I know what your problems is. You need to put a path in following the command (e.g. ./camera ~/Documents/BookPages), or also add the inch measurement of the checkerboard if you are using my modified version (e.g. ./camera ~/Documents/BookPages 5). Apparently it seg faults if you don't give it a path with images to sift through. It's just an ungraceful shut down. On a side note, I just used this with a full book and only used the checkerboard on the first page then scanned through the rest of the 200+ pages. When I processed things it came out perfect. Also, at first it wouldn't detect the checkerboard from one of my cameras, so I opened that file in Photoshop and adjusted the levels so it was nearly bitonal, then it worked like a charm.

I had seen this checkerboard thing as an example tutorial for openCV in the past, but never realized the application for this. Great catch Rob. Also, calculating those DPI measurements with the checker board resulted in perfectly sized pages (my cameras had slightly different zoom settings) and nearly flawless content detection in ScanTailor.