See the QR barcodes? Ideally they would be perfectly aligned with the book, say by shoving the page deep into the spine.
Now use the ZXing ("Zebra Crossing") software by Google to find the barcodes and print out the locations of the "finders" for each one. Each QR-formatted barcode has four finders, three large and one small. They are squares within squares. The ZXing software finds the centers of each square.
Here's the quick and dirty code I used, in case anyone is interested (also uses the sixlegs PNG reader library):
Code: Select all
/*
* Copyright (C) 2010 robertbaruch
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package barcode;
import com.google.zxing.BinaryBitmap;
import com.google.zxing.DecodeHintType;
import com.google.zxing.ResultPoint;
import com.google.zxing.client.j2se.BufferedImageLuminanceSource;
import com.google.zxing.common.BitMatrix;
import com.google.zxing.common.DetectorResult;
import com.google.zxing.common.HybridBinarizer;
import com.google.zxing.multi.qrcode.detector.MultiDetector;
import com.google.zxing.qrcode.detector.Detector;
import com.sixlegs.png.PngImage;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.Hashtable;
public class Main
{
public static void main(String[] args) throws Exception
{
File file = new File(args[0]);
BufferedImage buffImage = new PngImage().read(file);
long t = System.currentTimeMillis();
BufferedImageLuminanceSource source = new BufferedImageLuminanceSource(buffImage);
HybridBinarizer binarizer = new HybridBinarizer(source);
BinaryBitmap bitmap = new BinaryBitmap(binarizer);
BitMatrix matrix = bitmap.getBlackMatrix();
System.out.println("Black matrix is " + matrix.width + "x" + matrix.height);
MultiDetector detector = new MultiDetector(bitmap.getBlackMatrix());
Hashtable hints = new Hashtable();
hints.put(DecodeHintType.TRY_HARDER, Boolean.TRUE);
DetectorResult[] results = detector.detectMulti(hints);
System.out.println("Results in " + (System.currentTimeMillis()-t) + " msec");
for (DetectorResult result : results)
{
System.out.println("Result:");
for (ResultPoint point : result.getPoints())
{
System.out.println(" Point " + point.getX() + "," + point.getY());
}
}
}
}
Code: Select all
Black matrix is 3264x2448
Results in 953 msec
Result:
Point 2190.0,298.5
Point 2347.5,303.5
Point 2342.0,461.0
Point 2206.5,434.5
Result:
Point 678.5,252.0
Point 833.5,255.5
Point 828.0,412.5
Point 695.5,387.5
Each result has four points. A correctly rotated barcode will have the small finder (the "alignment" finder) at the lower right, and the other finders (the "positioning" finders) at the other corners. You can see in the image that the alignment finder is actually on the lower left, which says something about rotation. But even better, the points in the result given by the ZXing library are in the same order: positioning finder at lower left, positioning finder at upper left, positioning finder at upper right, alignment finder (lower right).
Thus, the vector formed by the line from the first to the second positioning finder is supposed to point straight up. Call that -90 degrees (where 0 degrees is pointing to the right) In the example above, the vector points at 1.82 degrees, to the right and slightly down, which means the image would have to be rotated 91.82 degrees counterclockwise to get the barcodes facing the right way. Now, obviously if you do that to the above image, the page would be upside-down. And that's correct, because I turned the barcode page upside-down to get the barcodes on the right side. Obviously I should have printed the barcodes on the other side of the page. But let's just pretend I did it the right way
The other barcode shows a 1.29 degree vector, for a 91.29 degree CCW rotation. Why the difference? Parallax! Because the camera's focus is not at infinity, parallel rays are not parallel, which means parallax. So we've extracted another very important feature of the image.
How about the perpendicular vectors -- the vectors from positioning finders 2 to 3? They should be at zero degrees, but the first is at 92.0 degrees, and the second is also at 92.0 degrees. The angles between the two vectors are thus 90.18 degrees and 90.71 degrees. Why aren't these angles exactly 90 degrees? Keystoning! Perpendicular lines are not perpendicular, which means keystoning. Yet another important feature of the image extracted via the barcodes.
From this data, a little hand-waving should result in an appropriate transform to get the image rotated properly and dekeystoned. Since I have a degree in mathematics, I am allowed to say that the solution is obvious and is left up to the student.
Kidding! I haven't done the math at this point, because I was excited enough to post immediately, in case it inspires someone.
--Rob