What is a good algorithm or library for cropping images to avoid whitespace or empty areas?

Question

I have a whole bunch of images of illustrations that I would like to crop to a smaller preview size.

The problem is that I want to crop them to show an "interesting" part of the illustration (ie avoid areas of whitespace).

The images typically have a flat color or a subtle gradient for the background. They are mostly vector style artwork with fairly distinct shapes.

Here are some examples: link ;-)

I've been thinking about using some sort of image feature detection algorithm with a sliding window to find the area with the greatest number of features.

I'm implementing this in PHP, but I don't mind implementing it myself if there isn't a library or extension available.

Ideas?

Answer 1

Well, you might want to consider just using an edge detection algorithm. Pick the area with the largest number of edges. Give higher weight to edges that are not blurry (as they may be from the background).

Answer 2

ImageMagick for PHP has automated generation of thumbnails. This SO question has a link to an ImageMagick auto-crop operator, and I'm not sure, but I think this is the PHP interface to it.

From the link:

bool Imagick::trimImage ( float $fuzz )
Remove edges that are the background color from the image.

For more general "interestingness", maybe try an inverse of seam carving (to find the highest energy, rather than lowest energy areas).

Answer 3

ImageMagick has a trim operation. It's available as a library but I don't know how hard it is to use from PHP. There are some PHP interfaces.

Answer 4

OK, so here's what I would've done, after looking at the examples:

Sum all rows and all columns of each image. You'll get two arrays, both looking like this:

      /-----\  /--\
    _/       --    |
___-                \_________

By looking at these arrays for a few images, find a suitable threshold (probably something just above zero). Then the leftmost and the rightmost crossing of this threshold is where you have to crop. I hope I've managed to make it clear enough, if not -- ask!

Answer 5

A CLI program using http://pecl.php.net/package/imagick:

<?php
   dl('imagick.so');

   $img = new Imagick();
   $img->readImage($argv[1]);

   # (* 0.0: exact match; * 1.0: crop entire image)
   $fuzz = current($img->getQuantumRange()) * 0.25; 

   $img->trimImage($fuzz);

   $img->writeImage($argv[2]);
?>

It should work good enough, as long as the image doesn't have a frame around its border.

Answer 6

Here's a fairly simple approach using an edge-detection filter, and then cropping around the center-of-edginess of the image to generate a thumbnail. It works pretty well on most images, but not if there are more than one subject. I'm open to suggestions on other ways of identifying the "interesting" points in a source image.