Are there any algorithms available for analyzing the complexity of an image? Basically I'm writing a Perl script that will use the system() function to launch MPlayer in the background to generate 10 to 20 screenshots for the input video file and I'd like it to be able to discard any simple images such as a shot of the sky, or a black background, and other simple images and keep just 3 of those images with the highest complexity or most number of colors. Is there a module or a separate program I can use to accomplish this? I'm guessing maybe Image::Magick can take care of this.
A:
You might consider doing an FFT and looking for high-frequency information in the images... That would give you a rough idea of complexity.
Skilldrick
2010-03-10 20:39:23
A:
I don't know of a ready-made library method, but there are some algorithms to measure this ...
You could try to add up the absolute values of the differences of one pixel to the next, separately per color channel. The sample image with the highest result would win, then. Still, it would be a very rough measurement...
Bit of pseudo-code, since I don't know perl:
complexity = 0
// image coordinates start at [0,0]
for x = 1 to image.max_x:
for y = 1 to image.max_y:
complexity += abs(image[x,y].red - image[x,y-1].red)
complexity += abs(image[x,y].red - image[x-1,y].red)
complexity += abs(image[x,y].blue - image[x,y-1].blue)
complexity += abs(image[x,y].blue - image[x-1,y].blue)
complexity += abs(image[x,y].green - image[x,y-1].green)
complexity += abs(image[x,y].green - image[x-1,y].green)
maligree
2010-03-10 20:49:33
This will prefer "noisy" images to "information-dense" images. Consider a frame of white-noise/snow.
Joe Koberg
2010-03-10 21:01:57
Okay, that's right. But in typical cases, this would also work. The only movie from which I remember noisy images would be "The Ring" -- and that frame would be a rather typical preview for the movie, I think ;-)By the way, you could also measure what this algo would spew out for a white noise image and disallow anything above a threshold a bit below that measurement.And, to be fair, this algo would only produce valuable information on images that have the same dimensions. OTOH, in the application the OP mentioned, that would inherently be the case.
maligree
2010-03-11 11:34:09
+5
A:
See how small a JPEG-compressed copy is. JPEG works hard to remove redundancies in image information and "complex" images simply don't have as much redundancy to remove.
Joe Koberg
2010-03-10 20:54:31
This is a good idea - compare the bitmap size of an image with the jpeg file size, the larger the difference between the two, the simpler the image.
Kazar
2010-03-10 20:57:47
This might work for photographic images, but I have a feeling it wouldn't do so well on line art, text, or other stuff that jpeg doesn't handle well. However, for those kinds of images, you could use the same technique with a png or gif.
Seth
2010-03-10 21:03:01
This WORKS surprisingly well, I've used it to pick the best thumbnail from a set of thumbnails before and it's great for getting rid of the black-only ones
Hightechrider
2010-03-10 21:08:53
+1
A:
My first answer would be the JPEG method but somebody already suggested it, so my next answer would be to compute a histogram ($image->Histogram()). Just look at the number of different colors in the image. For photos (things like the sky), the more colors in an image, the more complex it is.
Gabe
2010-03-10 21:05:43
I disagree. Monochrome/bilevel images can be very information-dense http://obeygiant.com/images/2008/10/obey-floral-red-500x490.jpg .... You did say "photos" though.
Joe Koberg
2010-03-10 21:19:44
Joe: That's why I qualified it with "For photos". His example was "black background" or "sky", both of which imply color photos. In fact, he even asked how to count colors, which is the answer I gave.
Gabe
2010-03-10 21:24:02
Well that image is a photo of a drawing! But yes, I see your point and I agree that you did provide the solution to the question.
Joe Koberg
2010-03-10 22:35:50
+2
A:
Great paper here on the subject. It considers the more narrow problem of matching images in a military application, but surveys the research and contains plenty of different metrics of image complexity that have been considered by various authors. It's possible you might need only one or two of the methods in your particular task. Check it out.
Grembo
2010-03-10 21:12:34