A super-cool content-sensitive image resizing algorithm using "seam-carving", based on this paper: (Avidan, Shamir 2007)
The idea is to figure out what's important in an image, and then reduce the image without distorting the important parts.
To automatically identify "interesting" parts of a image, I used gradient magnitude as an energy function. Then removed 8-connected one-pixel-wide seams, one at a time, based on minimizing the cumulative-sum of energy values along a seam using dynamic programming. The actual seam choice by the algorithm is provablly optimal!
#####Above: The gradient magnitude values at each pixel. #####Below: The cumulative-minimum-energy values at each pixel, (the cost of the cheapest path to that pixel in the previous image, if you start at the top).
###Results
These last three show the results generated by the Matlab script. They are compressed significanly, but even without preserving aspect ratio, there's no distortion of important parts. All the interesting bits look the same, but the distance between them has changed.
In this last one, the image is reduced in pixels by 75%, but all the balloons are still there, and they're all still the same size, which is highly-awesome. ####Problems with this implementation
It's super-duper slow for large images, because it's dynamic and not easily vectorizable and matlab is slow. The time complexity is O(n^3) where n is whichever dimension of the image is larger. I don't think that can be reduced, but it could definitely be rewritten in C.
// TODO: rewrite in C