Those who have to process scans should know how painful it is to manually deskew images. There are several approaches to do this deskewing automatically. The basis of all the methods is to identify lines following the same direction in a image and then by deviation from horizontal or vertical axis we can guess the skew angle. Then we choose the best lines and deskew the image.
I have used the Hough transform, which has a plenty of examples on the net and produces soso results. But only for the images without lineart that contains weird lines (it treats them as main lines :)). My task was exactly the opposite - to deskew images with lineart on them.
After thorough search I found an interesting abandoned Gimp autodeskew plugin - it uses GPL version of the Radon transform, a much more sophisticated technique used in x-ray analysis. This very transform finds scew so nicely that I decided to port it into Java and use in my project. The source code for C++ is here. It is so convoluted that translating it and making it work in Java took about 2 days. Here’s what I came up with:
public double doIt(BufferedImage image) {
final double skewRadians;
BufferedImage black = new BufferedImage(image.getWidth(), image.getHeight(), BufferedImage.TYPE_BYTE_BINARY);
final Graphics2D g = black.createGraphics();
g.drawImage(image, 0, 0, null);
g.dispose();
skewRadians = findSkew(black);
System.out.println(-57.295779513082320876798154814105 * skewRadians);
return skewRadians;
}
static int getByteWidth(final int width) {
return (width + 7) / 8;
}
static int next_pow2(final int n) {
int retval = 1;
while (retval < n) {
retval <<= 1;
}
return retval;
}
static class BitUtils {
static int[] bitcount_ = new int[256];
static int[] invbits_ = new int[256];
static {
for (int i = 0; i < 256; i++) {
int j = i, cnt = 0;
do {
cnt += j & 1;
} while ((j >>= 1) != 0);
int x = (i << 4) | (i >> 4);
x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
bitcount_[i] = cnt;
invbits_[i] = x;
}
}
}
static double findSkew(final BufferedImage img) {
final DataBuffer buffer = img.getRaster().getDataBuffer();
final int byteWidth = getByteWidth(img.getWidth());
final int padmask = 0xFF << ((img.getWidth() + 7) % 8);
int elementIndex = 0;
for (int row = 0; row < img.getHeight(); row++) {
for (int col = 0; col < byteWidth; col++) {
int elem = buffer.getElem(elementIndex);
elem ^= 0xff;// invert colors
elem = BitUtils.invbits_[elem]; // Change the bit order
buffer.setElem(elementIndex, elem);
elementIndex++;
}
final int lastElement = buffer.getElem(elementIndex - 1) & padmask;
buffer.setElem(elementIndex - 1, lastElement); // Zero trailing bits
}
final int w2 = next_pow2(byteWidth);
final int ssize = 2 * w2 - 1; // Size of sharpness table
final int sharpness[] = new int[ssize];
radon(img.getWidth(), img.getHeight(), buffer, 1, sharpness);
radon(img.getWidth(), img.getHeight(), buffer, -1, sharpness);
int i, imax = 0;
int vmax = 0;
double sum = 0.;
for (i = 0; i < ssize; i++) {
final int s = sharpness[i];
if (s > vmax) {
imax = i;
vmax = s;
}
sum += s;
}
final int h = img.getHeight();
if (vmax <= 3 * sum / h) { // Heuristics !!!
return 0;
}
final double iskew = imax - w2 + 1;
return Math.atan(iskew / (8 * w2));
}
static void radon(final int width, final int height, final DataBuffer buffer, final int sign,
final int sharpness[]) {
int[] p1_, p2_; // Stored columnwise
final int w2 = next_pow2(getByteWidth(width));
final int w = getByteWidth(width);
final int h = height;
final int s = h * w2;
p1_ = new int[s];
p2_ = new int[s];
// Fill in the first table
int row, column;
int scanlinePosition = 0;
for (row = 0; row < h; row++) {
scanlinePosition = row * w;
for (column = 0; column < w; column++) {
if (sign > 0) {
final int b = buffer.getElem(0, scanlinePosition + w - 1 - column);
p1_[h * column + row] = BitUtils.bitcount_[b];
} else {
final int b = buffer.getElem(0, scanlinePosition + column);
p1_[h * column + row] = BitUtils.bitcount_[b];
}
}
}
int[] x1 = p1_;
int[] x2 = p2_;
// Iterate
int step = 1;
for (;;) {
int i;
for (i = 0; i < w2; i += 2 * step) {
int j;
for (j = 0; j < step; j++) {
// Columns-sources:
final int s1 = h * (i + j);// x1 pointer
final int s2 = h * (i + j + step); // x1 pointer
// Columns-targets:
final int t1 = h * (i + 2 * j); // x2 pointer
final int t2 = h * (i + 2 * j + 1); // x2 pointer
int m;
for (m = 0; m < h; m++) {
x2[t1 + m] = x1[s1 + m];
x2[t2 + m] = x1[s1 + m];
if (m + j < h) {
x2[t1 + m] += x1[s2 + m + j];
}
if (m + j + 1 < h) {
x2[t2 + m] += x1[s2 + m + j + 1];
}
}
}
}
// Swap the tables:
final int[] aux = x1;
x1 = x2;
x2 = aux;
// Increase the step:
step *= 2;
if (step >= w2) {
break;
}
}
// Now, compute the sum of squared finite differences:
for (column = 0; column < w2; column++) {
int acc = 0;
final int col = h * column;
for (row = 0; row + 1 < h; row++) {
final int diff = x1[col + row] - x1[col + row + 1];
acc += diff * diff;
}
sharpness[w2 - 1 + sign * column] = acc;
}
}This algorythm is damn fast because it calculates 8 pixels at a time - operating on a byte bitmap with precalculated stuff for all pixel permutations in a byte. Don’t ask me how it does the job, it just does it :) Enjoy.
First published on the old anydoby.com blog on 2010-10-27.