[NOTE Aug 5, 2014] I wrote this in 2010 and took it offline between 2012 and 2014, but it is now back up. Since then, similar ideas have cropped up elsewhere and are worth consulting. Promising options include entropy-based methods (reddit, google search) and a commercial service (cropp.me).
Opticrop is a PHP script I wrote to crop a thumbnail of a specific width and height from a full-sized image.
Unlike most cropping routines out there, Opticrop uses edge-detection to find the most "interesting" part of the image to crop, so you won't get a useless thumbnail just because the top-left corner of your image happened to be a big patch of featureless sky. This post is a big-picture discussion of my method. If you just want the script, see the post on Opticrop's usage and implementation.
The Thumbnail-Cropping Problem
You've probably dealt with the thumbnail problem if you run a blog or website that publishes images with articles. When you link to that article (say, on your front page), it's nice to have a thumbnail of that article's "feature" image for your readers to click on.
The simplest way to make a thumbnail is to proportionally resize the original image to fit a width or height. However, if both dimensions are constrained, you usually have to crop the image before resizing.
For example, say your home page design uses square thumbnails, but your source images come in an odd assortment of width/height combinations. You'll need to open the source image up in Photoshop/GIMP, take your crop, and save the thumbnail for your website. If you're doing this dozens of times a day (like our photo editor does), it would be much nicer if you could somehow use a script--you open up the URL to a script, give it the path to an image, and it serves back a cropped/resized thumbnail. Unfortunately, a good script to do this is hard to come by, which is why I wrote Opticrop.
Figure 1. The usefulness of cropping. Suppose you need a 120px-wide thumbnail from a 600x400 source image. You can resize it proportionally to fit the width (left), but the height will be 80px in the thumbnail. If thumbnail height also needs to be 120px, then the original image should first be cropped to the 1:1 aspect ratio of the thumbnail (red box), and then resized (right).
A Google search will turn up simple explanations on how to resize/or crop images in PHP--see "examples" at the bottom of this page, or these tutorials. Many CMS's also come bundled with thumbnail-generation utilities. For instance, Movable Type 5 (the CMS used by my employer) has template tags for on-the-fly generation of resized or square-cropped thumbnails.
These solutions have their limitations. MT5 can make square thumbnails, but won't make them in arbitrary dimensions. What if you want a 200x50 thumbnail for a "related articles" widget for your sidebar? More generally, I want a script that will take an image, a width, and a height, and give me a thumbnail back that is exactly what a photo editor would have made in Photoshop.
With this goal in mind, I tracked down a few "smart" image resizer/croppers out there to find a starting point. A script by Gijs van Tulder ingeniously delegates all its work to the command-line ImageMagick utility, so you can run a bewildering array of commands through a simple URL string--he even wrote a custom command,
part, to do a simple crop-and-resize. Another script by Joe Lencioni isn't as powerful, but it does its own work using only functionality that comes with PHP--so you don't have to have ImageMagick installed or set up additional modules.
part command and MT5's square-thumbnail-generator crop as large of a region from the source image as possible without changing the aspect ratio, and center the crop along the dimension that needs cropping. This "largest centered crop" is generally a safe and simple strategy. However, if the source and target images have very different aspect ratios (i.e. you need to crop out more stuff), then a smarter strategy might be needed. Also, if the image contains a single small subject on an otherwise blank background, then you don't want to take the biggest crop you can get, but rather just enough to capture the subject. Otherwise you run the risk of scaling that spot down into obscurity.
Figure 2. Pitfalls of the "largest centered crop". It's easiest to take the largest centered crop before scaling to the target dimensions (such as a small square thumbnail), but the strategy yields less-than-ideal results when the aspect ratio of the original or target image are severely elongated, or when there is a small single subject on an otherwise uniform background.
In other words, the script needs to understand the content of an image. There are all sorts of fancy ways to do this, but I set out to write something that will be quick, simple, and require a minimum of external code. A key first step would be running the image to crop through an edge-detection filter. Like the name suggests, an edge-detection filter transforms an image based on changes in color and lightness--"interesting" areas with lots of detail get mapped to bright pixels, and uniform, boring areas like sky get mapped to dark pixels.
Figure 3. Several potential crops around the center of edginess (red dot). Images are shown after edge detection. At the bottom you can see the "best" crop in full color and after rescaling to target dimensions.
Armed with the edge-detection filter, a script can do all sorts of things to infer where to crop an image. For example, I decided to crop the image around a spot I calculate by averaging all the pixels' locations, weighted by the intensity of each pixel in the edge-detected image. This tell you the location of the "center-of-edginess" of the image , sort of like the center-of-gravity of a physical object. Just as the COG is a good place to put your finger if you want to balance something, the COE of an image a good point to use as the center of a crop (with important exceptions, noted below).
Once you know where to crop you still need to pick a crop size, since for any set of target dimensions you can make many crops with that aspect ratio from the source image. If you choose the crop by adding up the edginess of all the pixels in each possible crop and choosing the one with highest "total edginess" you'll end up always choosing the largest crop, which is bad for the type of "small single subject" images mentioned above. If you choose the highest average edginess (total edginess divided by area of the crop) instead, you'll favor small, cramped crops with a lot of detail but no visual context.
Center of edginess:
Adjusted average edginess:
My solution is to maximize an "adjusted average edginess" metric that, instead of dividing total edginess by the area, divides it by some power of the area. The parameter can be tuned by trial and error to get the right amount of "breathing room" in a crop. If , the adjusted average edginess simplifies to average edginess, and we favor small crops as we discussed above. If , adjusted average edginess simplifies to total edginess and the biggest crop is selected. I liked the results from test crops with , but for really small thumbnails (which require significant rescaling), the tighter crop given by a higher (i.e. closer to 1) might be preferable.
Figure 4. Cropping around the center-of-edginess yields "good" crops for most images. Compare to Fig. 2 above. Increasing increases the tightness of the crop.
Opticrop was written to be smarter than easily available alternatives, but because the strategy is relatively simple, it still makes the "wrong" crop on certain images. There are caveats to both the methods of choosing where to crop and how much to crop.
As to where to crop, choosing the center-of-edginess is best suited to single-subject images, and gives poor results on two-subject or multi-subject images. If a picture has 2 areas of interest, Opticrop will crop to the region between them, because the center-of-edginess is an average over the entire image and gives no information about local "pockets" of edginess. A solution, suggested by Dave, may be to find "local maxima of edginess", or the modes of edginess, rather than a single average. I'm open to ideas on how to implement such an approach.
Another possibility is an "iterative search" that will start at the center-of-edginess and meander around, subject to certain constraints, until it settles on a region that is comparatively more "edgy" than where it started. This kind of algorithm tends to enlist some kind of recursion in refining the answer, which generally leads to a superior result without too much added computation. But the devil is in the details of implementation.
The decision of how large an area to crop (or how much "breathing room" to give the cropped subject, assuming there is one) could also be accomplished in a completely different way. The current version simply tries a number of different sizes and picks the best one. I've defined "best" as "highest ", but using a different criterion may yield other desired crop properties. A refined search method might also yield better crops.
You can download the script, and see usage and implementation details, on this post.