Skip to content

A cool content-sensitive image-resizing algorithm that uses "seam-carving". Reduce just the width of an image without distortion.

Notifications You must be signed in to change notification settings

lydia-schiff/content-sensitive-image-resizing

Repository files navigation

content-sensitive-image-resizing

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!

matches

#####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).

matches

###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.

matches

matches

matches

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

About

A cool content-sensitive image-resizing algorithm that uses "seam-carving". Reduce just the width of an image without distortion.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published