deskew

[phpfelipe]

Is there a easy way do deskew an scanned text image? Im using a command line tool (https://github.com/galfar/deskew) by executing in php.

[jcupitt]

Hello @fsimchen,

I've done deskew with FFTs:

http://libvips.blogspot.com/2015/11/fancy-transforms.html

See the bottom half of the post. Is that the kind of thing you need?

I've never tried to process a QR code. What algorithm are you implementing?

[phpfelipe]

I cant achieve any good results with, is slow too.

With imagick is very simple:

` $imagick = new \Imagick(realpath("images/NYTimes-Page1-11-11-1918.jpg")); $deskewImagick = clone $imagick;

//This is the only thing required for deskewing.
$deskewImagick->deskewImage($threshold);`

[jcupitt]

Do you have a test image?

[jcupitt]

I think (from memory) the imagemagick deskew is based on the Radon Transform. That's not in libvips and perhaps should be. You should be able to get a good result with FFTs, but it might be less stable and perhaps slower.

We'd need a test image and to do some investigation.

[phpfelipe]

[jcupitt]

I tried your image in that nip2 workspace and I got:

So it does work, I think, though I agree it's slow.

It does an FFT of the entire image, which will be very slow for large images like this. You could make it much faster by downsampling to eg. 128x128 pixels before taking the FFT.

[phpfelipe]

Will give it a try, thanks!

[jcupitt]

Oh hang on, my eye was tricked by the black edges, that's not a good result. I'll try again.

[phpfelipe]

Im trying with the nip2, but I cant manage to figure how to get that into a code, or to translate to php...

[jcupitt]

It seems the FFT method is not very accurate for large rotations. I got quite a good result by estimating, rotating, estimating again, then summing the two estimates and applying to the original. I shrank the image to 256x366 for the FFT to make processing fast.

It's still not quite perfect. You'd need to process a higher-res image for a more accurate result.

Probably the way to go is to implement the Radon transform.

Here's the nip2 workspace that I made: http://www.rollthepotato.net/~john/autorotate/rotate2.ws

[jcupitt]

Yes, sorry, nip2 -> php is not straightforward. I think adding the radon transform to libvips would be a better solution.

[phpfelipe]

Is there a way to get that nip2 workspace in some sort of code, could be any language? so i can make into php

[jcupitt]

You can run nip2 from the CLI, if that's any help. You do something like:

nip2 --batch --set A1=some-input-file --set main=output-cell -o x.png

And it'll run headless on a server. You could just system() out to it.

Alternatively, it'd take 30 minutes (guess) to rewrite as PHP.

[phpfelipe]

If you could please, Im trying with no success.

[jcupitt]

This mostly works for me:

#!/usr/bin/env php
<?php

require __DIR__ . '/vendor/autoload.php';

use Jcupitt\Vips;

// transform to polar coordinate space
function to_polar(Vips\Image $image): Vips\Image
{
  $xy = Vips\Image::xyz($image->width, $image->height);
  $xy = $xy->subtract([$image->width / 2.0, $image->height / 2.0]);
  $scale = min($image->width, $image->height) / $image->width;
  $xy = $xy->multiply(2.0 / $scale);
  $index = $xy->polar();
  $index = $index->multiply([1, $image->height / 360.0]);

  return $image->mapim($index);
}

// transform to rectangular coordinate space
function to_rectangular(Vips\Image $image): Vips\Image
{
  $xy = Vips\Image::xyz($image->width, $image->height);
  $xy = $xy->multiply([1.0, 360.0 / $image->height]);
  $index = $xy->rect();
  $scale = min($image->width, $image->height) / $image->width;
  $index = $index->multiply($scale / 2.0);
  $index = $index->add([$image->width / 2.0, $image->height / 2.0]);

  return $image->mapim($index);
}

// find the angle to correct the skew with
function find_skew(Vips\Image $image): float
{
  $fft = $image->fwfft()->wrap()->abs();
  $fft = to_rectangular($fft);
  $rows = $fft->project()["rows"];
  $peaks = $rows->subtract($rows->gaussblur(20, ["precision" => "integer"]));
  $result = $peaks->maxpos();
  $y = $result[2];
  $angle = 270 - 360 * $y / $rows->height;

  return $angle;
}

// rotate, keeping the size the same
function rotate_trim(Vips\Image $image, int $angle): Vips\Image
{
  $rotated = $image->rotate($angle, ["background" => 255]);
  $x_margin = ($rotated->width - $image->width) / 2;
  $y_margin = ($rotated->height - $image->height) / 2;

  return $rotated->crop($x_margin, $y_margin, $image->width, $image->height);
}

$image = Vips\Image::newFromFile($argv[1]);

// low-res one band mono version for skew estimation
$mono = $image->colourspace("b-w")[0]->resize(256.0 / $image->width);

// first estimate of skew
$first = find_skew($mono);

echo "first estimate = " . $first . "\n";

$mono = rotate_trim($mono, $first);

// estimate skew again ... the image should be close to the correct angle now,
// so we ought to get a better estimate
$second = find_skew($mono);

echo "second estimate = " . $second . "\n";

// and rotate the original by the combined estimate
$image = rotate_trim($image, $first + $second);

$image->writeToFile($argv[2]);

I see:

$ time ./deskew.php ~/Desktop/autorotate/form.png x.png
first estimate = -5.1044776119403
second estimate = -1.8805970149254

real    0m0.605s
user    0m0.920s
sys 0m0.081s

Producing:

It could maybe be tuned a bit more.

[phpfelipe]

I cant thank you enough! Really good library! I'm going to do more tests, and I think I have other questions.

Thanks!

[phpfelipe]

I got some good results with your code! I process 100 images im 12.88s.

Sometimes i got a result upside down.

[jcupitt]

Oh, nice!

Yes, you typically get four spikes in the FFT for the four directions, and it simply picks the largest. If that's not the one near the top, you'll get a flip. It probably ought to pick the largest, then find the rotation relative to the nearest orientation.

[phpfelipe]

I think now is very usable, working good for me! Thank you very much for this!

<?php

namespace Fsimchen\LaravelPackageOmr;

use Jcupitt\Vips;

class VipsDeskew
{
    function deskew(Vips\Image $image): Vips\Image
    {
        // low-res one band mono version for skew estimation
        $mono = $image->colourspace("b-w")[0]->resize(400 / $image->width);

        // filters do help skew estimation
        $mask = Vips\Image::newFromArray([[255, 128, 128], [255, 255, 255], [255, 128, 255]], 8);
        $mono = $mono->erode($mask)->more([230])->gaussblur('1');

        // first estimate of skew
        $first = $this->estimateDeskew($mono);
        $angleFinal = $first['angle'];
        //echo "first estimate = " . $first['angle'] . "<br>";

        if ($first['angle'] <> 0) {
            // second estimate of skew
            $second = $this->estimateDeskew($first['image']);
            if (($second['angle'] == $first['angle'])) $second['angle'] = 0;
            $angleFinal += $second['angle'];
            //echo "second estimate = " . $second['angle'] . "<br>";

            if ($second['angle'] <> 0) {
                // third estimate of skew
                $third = $this->estimateDeskew($second['image']);
                if ((($third['angle'] * -1) == $second['angle']) || ($second['angle'] == 0) || ($third['angle'] == $second['angle'])) $third['angle'] = 0;
                $angleFinal += $third['angle'];
                //echo "third estimate = " . $third['angle'] . "<br>";

                if ($third['angle'] <> 0) {
                    // fourth estimate of skew
                    $fourth = $this->estimateDeskew($third['image']);
                    if ((($fourth['angle'] * -1) == $third['angle']) || ($third['angle'] == 0) || ($fourth['angle'] == $third['angle'])) $fourth['angle'] = 0;
                    $angleFinal += $fourth['angle'];
                    //echo "fourth estimate = " . $fourth['angle'] . "<br>";
                }
            }
        }

        // and rotate the original by the combined estimate
        //echo "final estimate = " . $angleFinal . "<br>";
        return $this->rotate_trim($image, $angleFinal);
    }

    function estimateDeskew(Vips\Image $image): array
    {
        $angle = $this->find_skew($image); //->hist_norm()
        return [
            'image' => $this->rotate_trim($image, $angle),
            'angle' => $angle
        ];
    }

    // transform to polar coordinate space
    function to_polar(Vips\Image $image): Vips\Image
    {
        $xy = Vips\Image::xyz($image->width, $image->height);
        $xy = $xy->subtract([$image->width / 2.0, $image->height / 2.0]);
        $scale = min($image->width, $image->height) / $image->width;
        $xy = $xy->multiply(2.0 / $scale);
        $index = $xy->polar();
        $index = $index->multiply([1, $image->height / 360.0]);

        return $image->mapim($index);
    }

    // transform to rectangular coordinate space
    function to_rectangular(Vips\Image $image): Vips\Image
    {
        $xy = Vips\Image::xyz($image->width, $image->height);
        $xy = $xy->multiply([1.0, 360.0 / $image->height]);
        $index = $xy->rect();
        $scale = min($image->width, $image->height) / $image->width;
        $index = $index->multiply($scale / 2.0);
        $index = $index->add([$image->width / 2.0, $image->height / 2.0]);

        return $image->mapim($index);
    }

    // find the angle to correct the skew with
    function find_skew(Vips\Image $image)
    {
        $fft = $image->fwfft()->wrap()->abs();
        $fft = $this->to_rectangular($fft);
        $rows = $fft->project()["rows"];
        $peaks = $rows->subtract($rows->gaussblur(20, ["precision" => "integer"]));
        $result = $peaks->maxpos();
        $y = $result[2];
        $angle = round((270 - 360 * $y / $rows->height), 5);

        return $this->fixAngle($angle);
    }

    // fix the angle to rotate
    function fixAngle($angle, $limit = 20)
    {
        if ($angle > 0) {
            while ($angle > 0) $angle -= 45;
            $angle += 45;
            if ($angle > $limit) $angle = ($angle - 45) * -1;
        }

        if ($angle < 0) {
            while ($angle < 0) $angle += 45;
            $angle -= 45;
            if ($angle < ($limit * -1)) $angle = ($angle + 45) * -1;
        }

        return round($angle, 5);
    }

    // rotate, keeping the size the same
    function rotate_trim(Vips\Image $image, $angle): Vips\Image
    {
        $rotated = $image->rotate($angle, ["background" => 255]);
        $x_margin = ($rotated->width - $image->width) / 2;
        $y_margin = ($rotated->height - $image->height) / 2;

        return $rotated->crop($x_margin, $y_margin, $image->width, $image->height);
    }
}