Detecting the most interesting part of an image

Hi,

I'm making a program that generates a random band name from an article on wikipedia, a random album name by cutting up quotations from the quotations page and a random image for the album cover from flickr.
However, sometimes the images that flickr returns are of unusual shape etc and I need to crop them, resize them so they make a nice square image for the album cover.
What would be the best method to work out where in the image is the most interesting/colourful/feature-rich part so I can decide which bit to center my crop on?
Would I have to do a pixel-by-pixel analysis, or is there some sort of sampling technique?
Are there any open-source implementations of this?
I would be finally implementing the solution in PHP.

Thanks.
-j

bump, anyone?

Your problem isn't well defined mathematically, but real-world problems rarely are.

I'm not an expert on this, but I'll try to help anyway. You might still need to do some research on your own. First, it's hard to imagine being able to figure out how "interesting" some part of an image is from a sample unless that sample is pretty dense. That said, it's surprising how much you can tell about data slices from the real world given relatively few parameters, so it might well be possible. However, you would probably need some cutting-edge tools like compressed sensing.

Working at the pixel level wouldn't require those sophisticated techniques. You should first choose a definition of "interesting." It doesn't necessarily have to be very good, since even pretty simplistic metrics will weed out the least interesting parts of an image, like regions of near-constant color. For example, you could score a subrectangle of an image by (in order of complexity and probably quality) the variances of the pixel values, the average squared first partial derivatives, the average squared Laplacian, etc.

There probably are open-source implementations, and the first place I'd look is the OpenCV library.

Thanks for your reply.
Yes, I was looking into it, my first thoughts were to take the colour gradient between pixels and reasoning that the places of most colour gradient are therefore the most colourful and interesting parts.
As you say, I will research partial derivatives etc. and try to glean some answers from that.

Yep, that sounds like a perfectly reasonable approach. If we understand "gradient" the same way, then the gradient is the first partial derivatives of the color components. The reason to consider higher derivatives (like the Laplacian) is that regions of smoothly varying color get zeroed out, while places where the color isn't smooth get large spikes. However, high-order derivatives take more time to compute. (The term "derivative" here is a slight misnomer; it's really all finite differences. It's not calculus, just arithmetic.) Also, as far as I know, the foreground could contain regions of smooth color, so zeroing those out could be undesirable. It's probably worthwhile to experiment with different methods; ideally, you'll find some already implemented.