Русский English Tags View Sergey Zolotaryov's profile on LinkedIn Sign-in
Automatic image deskew in Java
Permanent link 27-10-2010 anydoby java graphics

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.

Add a comment

elemer.flat
21-11-2013

it does not work

babouin.billou
28-05-2014

It's works well.



package com.img.tools.process;

import com.openbee.easycapture.core.business.document.io.DocInput;
import com.openbee.easycapture.core.model.document.RDocument;
import com.openbee.easycapture.core.model.document.RPage;
import com.openbee.easycapture.core.model.physical.Rectangle;
import com.openbee.img.tools.process.Deskew;
import org.apache.commons.imaging.Imaging;
import org.apache.commons.io.FilenameUtils;

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.net.URL;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created on 03/05/2014.
 */
public class DeskewApp {
    public static void main(String[] args) {
        String[] args2 = {
"file:///tmp/skew/06deg.png"};
        mainFct(args2);

    }

    public static void mainFct(String[] args) {
        try {
            if(args.length < 1 || args[0] == "--help" || args[0] == "-h") {
                System.out.print(
                        "Usage: java HocrToPdf INPUTURL.tiff INPUTURL.html OUTPUTURL.pdf\n" +
                                "\n" +
                                "Converts hOCR files into PDF\n" +
                                "\n" +
                                "Example: java com.acoveo.hocrtopdf.HocrToPdf file:///home/username/hocr.html ./output.pdf\n");
                if(args.length < 1)
                    System.exit(-1);
                else
                    System.exit(0);
            }
            URL inputImgFile = null;
            File imgFile = null;
            try {
                inputImgFile = new URL(args[0]);
                imgFile = new File(inputImgFile.toURI());
            } catch (Exception e) {
                System.out.println("First and second parameters have to be a valid URL");
                e.printStackTrace();
                System.exit(-1);
            }
            BufferedImage img = Imaging.getBufferedImage(imgFile);
            if(img == null) {
                System.exit(-1);
            }
            System.out.println("Image name : " + imgFile);

            System.out.println(" - page " + " width x height = " + img.getWidth() + " x " + img.getHeight());
            double res = Deskew.doIt(img);
            System.out.println(" -- skew " + " :" + res);

        } catch (IOException e) {
            e.printStackTrace();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}


package com.openbee.img.tools.process;

import java.awt.*;
import java.awt.image.BufferedImage;
import java.awt.image.DataBuffer;

public class Deskew {

    public static double doIt(BufferedImage image) {
       ...
    }
    // code of the post
    // Be sure to put doIt in static

}

And import in maven common.imaging


        <dependency>
            <groupId>org.apache.commons</groupId>
            <artifactId>commons-imaging</artifactId>
        </dependency>