Content-Aware Image Resizing

An anonymous reader writes "At the SIGGRAPH 2007 conference in San Diego, two Israeli professors, Shai Avidan and Ariel Shamir, have demonstrated a new method to shrink images. The method is called 'Seam Carving for Content-Aware Image Resizing' (PDF paper here) and it figures out which parts of an image are less significant. This makes it possible to change the aspect ratio of an image without making the content look skewed or stretched out. There is a video demonstration up on YouTube."

The paper via ACM

The author's website was pegged serving that 20MB PDF before slashdot got ahold of it, I doubt it'll survive now. The paper is also hosted by the ACM [acm.org], if you're a subscriber.

Re:The paper via ACM

The Coral Cache" [nyud.net] has it also.

Re:The paper via ACM

I used a lossy compression algorithm on their paper and got this...

Shrink image:
Step 1: Run an edge detection algorithm.
Step 2: Find minimal energy (least amount of edges crossed) path from top to bottom or left to right (graph-cut algorithm).
Step 3: Remove pixels along that path.
Step 4: Repeat steps 2 and 3 as necessary.

Extend image:
Step 1: Run an edge detection algorithm.
Step 2: Find minimal energy (least amount of edges crossed) path from top to bottom or left to right (graph-cut algorithm).
Step 3: Insert pixels along that path (interpolated from neighbors)
Step 4: Repeat steps 2 and 3 as necessary.

Remove objects:
Step 1: Run an edge detection algorithm.
Step 2: Mask object by giving its pixels low/negative energy values.
Step 3: Find minimal energy (least amount of edges crossed) path from top to bottom or left to right (graph-cut algorithm).
Step 4: Remove pixels along that path.
Step 5: Repeat steps 3 and 4 as necessary.

Re:The paper via ACM

I think you've got it except for a small detail in the "Remove objects", which the narrator alludes to around timestamp 4:01 of the video. You might want to add:

Step 6: Extend image to match original size using the previous extend image algorithm

(Of course, I leave the obligatory Profit step as an exercise for the reader).

Video is on youtube....

Been up for a while now too, at least I saw it a few days ago...

Clicky [youtube.com]

Tm

Impressive

Watching the video, this seems pretty impressive. It's also neat to see them use the same technology to remove items (people in this case) from an image with only about 10 seconds of work.

I Think You'll Find

10 Seconds of work there, most probably a good deal longer finding a picture that is easy to do it to...

nice!

It seems like a little bit of work is left to make it as completely automated as you would need to have it just "always work" on any platform or device, but it seems like they're already working on that...

Other than that though, that's pretty awesome... I'm sure there's more instances where it doesn't look right than what they showed, but it's definitely cool how well it works as it stands!

I can imagine it would be extremely useful for ex-boyfriends or ex-girlfriends; just load up all their photos of them and their ex, wave the magic eraser, and *boom* you don't have to delete all your old vacation shots ;)

I wonder how well it would work for the porn industry too; nice automatic resizing of breasts without ruining the picture! Fetishists will be SO happy! :)

Re:

It seems like a little bit of work is left to make it as completely automated as you would need to have it just "always work"

Completely right, yes. The images in the video have been selected to show this technique in the best possible light. There's a great variety of images that'll really not work quite right with a completely automated treatment. Speaking from experience havi

Re:

Problem is you have to remember to keep some nice featureless space between you and your boy/girlfriend in case you want to erase them afterwards. Unless you don't mind becoming an amputee in your photos, that is.

Re:nice!

I'd never understod this hate-your-ex-thing? The person where part of your life for some time but you have decided to hate it and want to erase it from it?
Better never get a partner then at all if you are going to hate the person once it doesn't work longer.

But then I'm a regular slashdot visitor and don't have any exs so what do I know.

Practical uses

Finally, a way to reduce the space between surgically augmented breasts and lengthen wangs on Flickr!

Re:

> Finally, a way to reduce the space between surgically augmented breasts and lengthen wangs on Flickr!

I see your reduced breasts and raise you a 'Seam Carvied Content-Aware Resized Image' midget porn. Guess who Elizabeth Hurley looks like now.

Slightly Strange

Okay, I get that they remove the pixels with least energy, so the unimportant information is lost when shrinking, it kinda works, looks a bit strange, but it's okay. however, when they make an image larger they also add the least information so you end up with a large image- but the useful information is the same size and the extra/useless low energy or background gets duplicated- to me, I think thats kinda pointless, I mean, you're adding stuff you've analysed and found NOT to be the focus of the picture. This may work for pictures with no obvious background, but lanscapes like one of the examples, have such an obvious background that only that gets enlarged and just gives you more background. You may aswell just add a nice blue frame round the edge of the picture to make it fit.

Re:

when they make an image larger they also add the least information so you end up with a large image- but the useful information is the same size and the extra/useless low energy or background gets duplicated- to me,

According to the video, the added backgro

Re:

You may aswell just add a nice blue frame round the edge of the picture to make it fit.

The whole point is to avoid artificial techniques that stand out, like frames. A trivial application would be expanding an image to fit as your desktop background. If you're trying to fit a picture into a rectangle with particular dimensions, you may wan

Re:

I just wish windows would support resizing an image for your desktop without changing the aspect ratio. I think they had this in Linux about 6 years ago. And I'm pretty sure it's still not in Windows Vista. Come on, it isn't that hard.

Re:Slightly Strange

I think you're missing the point of their method, which is to provide realistic images during rescaling that aren't corrupted by blind interpolation (equal averaging). In downscaling the images, it preserves parts of the images that would lose their information through downscaling (e.g. complex textures, people), while at the same time removing textures that would not lose information through downscaling (sky, water, sand). The sky, water and sand will still look like sky water and sand whether it's at 1/4 or 10x resolution, people however look much different if you try and downscale them or upscale them(they would appear blurry and hard to distinguish). The same works in reverse. The sky is still going to look like the sky whether you scale it to 10x or 5x-- it would still look natural. Tree's on the other hand, would not. Once you start to scale up the trees you would expect to be seeing different characteristics-- leaves, branches, etc. Any type of scaling up of a tree would make it seem very blurry and unnatural (lacking leaves, branches, etc.)-- you cannot create an additional information that isn't present in the original image. Therefore, the most natural looking image would be to increase the sky.

It's not perfect of course. I'm guessing that if you had a picture of two people next to each other, one with a solid colored shirt, and the other with a striped colored shirt, that the solid colored shirt guy would get skinner than the striped when shrinking, and the reverse when enlarging. However, it's a neat idea, and I look forward to reading the paper.

A picture speaks a thousand words...

So does this mean you're taking some of those words away?

There are probably a few situations where the 'unimportant' bits of an image are still as relevant as the rest. Sports photos for instance - especially those played on grass - would not give you a true picture (literally) of what's going on in the scene.

This'd be good for reference photos - like the animals at the start of the YouTube video, but applications where precision and distance are required wouldn't benefit. Nice bit of work though and I reckon with some smart scaling embedded too (rather than its 'folding effect'), it'd cater for most image retargetting requirements.

Re:

just to clarify, this is good for fitting content into spaces where it would not fit otherwise, not just a method to reduct image size. on a pda phone for instance, one might prefer to see the modified image of a football scene rather than not be able to

Re:

It's the Reader's Digest Abridged Version (Photo)!

There are circumstances where it makes sense to abridge (or retarget) and others where it makes more sense to simply rescale. Since this appears to allow the content provider to choose the method that will

Re:A picture speaks a thousand words...

It's not removing any more pixels than normal resizing or cropping would, it's just doing it such that the least important ones are removed first. Instead of:

he uic bownfoxjumed verthelaz yelowdog

You get:

Th qik brwn fx jmpd ovr th lzy ylo dog

Which reduces the total size by the same amount, but retains more information than treating every bit of information the same.

Re:A picture speaks a thousand words...

while this is technically true, you're also rearranging the relative positioning of those pixels. cropping something out doesn't change the relationship of what is left in the photo (though it may remove critical details).

if you have 3 people in a picture and you crop it down to 2, you've erased a person, but you haven't changed who is seated next to whom. if you use this method and the middle person is erased, you make it appear as though the outer two people were in fact seated next to each other when they weren't.

we are used to the idea that a picture can be cropped (mentally considering what might be just outside the frame). We aren't yet used to the concept that the photo has effectively been cut and pasted together to create new relationships between the objects in the photo (though of course photoshop is getting us there).

to continue your analogy, if we take:
the quick brown fox jumped over the lazy dog

and drop letters, we can create:
the cow jumped over the dog

whereas "cropping" might let us say:
the quick brown fox jumped

I think it's clear that one of these is more misleading than the other, though in both cases you're just removing information. (in one case, some of that information happens to be spaces between letters/words)

Re:

I don't know whether I'm "used to it" or not, but after watching the video, I'm totally ready for more intelligent image resizing that isn't quite scaling. Most of the applications I see this being used in don't really require that the exact photographic

Re:

There are probably a few situations where the 'unimportant' bits of an image are still as relevant as the rest. Sports photos for instance - especially those played on grass - would not give you a true picture (literally) of what's going on in the scene.

DP Approach

This method is quiet interesting, though it falls over in situations where the detail level
or entropy of the background is as great as the foreground. Also the paper doesn't go into
too much details about the dynamic programming approach they used to find the path of least
energy, I guess that aspect of it is patentable. Another thing they could investigate is the
use of diagonal seams instead of just staggered vertical and horizontal seams.

All in all a very interesting read.

Re:

Also the paper doesn't go into too much details about the dynamic programming approach they used to find the path of least energy, I guess that aspect of it is patentable.

Not so much patentable, as "Easy enough for the reader to implement that it deser

Prior art

The technique was already invented by the Soviets in the '30s:

Before [wikipedia.org]

After [wikipedia.org]

Insignificant person removed.

Re:

No, your images is just an often-cited example of what image inpainting could do. And image inpainting has nothing to do with the new resize algorithm talked about in the article, although similar effects are achieved in this specific case.

Whao

Ths s rly gret !

Gimp!

Although they demonstrated on Windows, a friend of mine is one of their graduate students and was peripherally involved. He said it was originally developed as a GIMP plug in, but moved to a separate Windows app to show off the realtime resizing, etc. Hopefully they'll release the GIMP plugin? More likely Adobe will write them a check and license it to make sure that never happens.

Paranoia! It's not just for Gimps

"More likely Adobe will write them a check and license it to make sure that never happens."

Is that check going to cover the removal of their paper from above and the ACM archives, let alone OUR archives?

I can see the spam now

Shrink the rest of your body, and increase you penis size by up to 20 pixels!

Re:

"Shrink the rest of your body, and increase you penis size by up to 20 pixels!"

Open source alternative via the GIMP:

1. use the "magic wand" tool to select your "magic wand tool"
2. "convert selection to path"
3. "stroke path"

Feel free to experiment by repeate

Does Anyone Find It Ironic

I find a small irony in the fact that the video is posted on youtube, a site which stretches and squeezes video to fit into a 4:3 aspect ratio

Finally!

I TOLD you it's 10 inches! See? SEE???

(Yes, I know, this thread is worthless without pictures)

My Implementation

I thought it was pretty cool, so I made my own version after seeing the video. It obviously won't be as awesome as their one, but if you want to play around with it, you can get my C source [ultra-premium.com] and have a play around. It is GPL3.

Ariel Shamir

... not to be confused with Adi Shamir [wikipedia.org] (the cryptographer).

some code

Too much caffeine in the blog, couldn't sleep... I can't get my hand on the paper but the youtube presentation was extremely clear and I just wrote this C code based on libgd2. Basically it lowers the height of an image by 1 pixel, you can run it multiple time to remove more line.

http://rafb.net/p/jinioy45.html [rafb.net]

(yeah my coding sucks but it produces awesome results and I reversed engineered the algorithm from youtube so please grovel...)

I'll improve it soon to remove an arbitrary number of line, horizontally or vertically
  - no recalculation of gradient, only the gradient near the line needs to be recomputed
  - precomputes a file that store the order of the pixel needing to be removed

I need help with something though, I understand how the algorithm can precompute a file which says in which order pixel should be removed, but I don't see how this can work in *both* direction. Suppose you want to reduce vertically and horizontally at the same time, the horizontal change should completely break the precomputed vertical changes. How would you handle that?

Re:

here's an example produced by that code (this is Maine)

original
http://img96.imageshack.us/my.php?image=testxq4.jp g [imageshack.us]

somewhat reduced
http://img361.imageshack.us/my.php?image=outew8.pn g [imageshack.us]

very reduced
http://img484.imageshack.us/my.php?image=outas2.pn g [imageshack.us]

Re:

jpegin = fopen("test.png","rb");
  jpegout = fopen("out.png","wb");

WTF?

Re:I For One

It's not compression as we know it, Jim. It's more like scaling on totally overcool steroids. The basic idea seems rather simple. I would even imagine you could get a bit of enhanced picture quality by coding simplified vector info on seams, and then doing a normal JPEG of a downscaled picture. That would be a quite contrived way to get a kind of VBR-like behavior in normal JPEG. One issue with JPEG is, after all, that redundancy is detected and handled on the block level, while this algorithm works along arbitrary paths.

I'm really impressed. Again, maybe not too hard to implement at first, but probably damn hard to get working perfectly, and I might just be ignorant (and I'm entitled too, it's far from my field of work), but I've not seen anyone doing it before.

Re:Let us be wholly thankful...

It's times like this when I become truly aware of my own gaping inadequacies, and feel the deep, deep obligation to rectify my own short comings.

hehe... gaping... deep deep... rectum... i mean rectify... hehe

i need to get some sleep

Re:

"This technology could render very visually-convincing (but not computer/analytically convincing) image censorship or alteration. I am strongly reminded of this example of photo-editing from the 1940s:

http://www.newseum.org/berlinwall/commissar_vanish [newseum.org]

Re:

Yeah, Americans would never stoop so low - they gloriously reenact the photo op [iwojima.com]. Much more honest that way.

Re:

I think it's obvious that this technique is just plain cool and has great potential for beneficial use, even if it might be used for ill.

what do you expect? it's technology. technology works to the highest bidder, not the people with the highest morals.

Re:Not ready for Prime Time

It has nothing to do with edge detection. The algorithm simply detects paths of minimal gradient which lead from one side of the image to the opposite side. This can be used to produce a "pretty picture" which shows the edges -- but this is merely fallout.

They showed what I thought were several realistic photos with complex backgrounds, and the algorithm did well overall, except on structures where people are closely attuned to exact detail -- such as human faces. If we weren't innately wired to process faces in incredible detail, we wouldn't even notice the distortion.

So it's not perfect. Can you show me something in this world that is? And I don't think there has been any mention of "prime time" application, whatever that means.

Re:

I'm not sure what else you want.

for it to automatically remove less-significant faces.

Re:Great - We can do this, but should we?

Your comment seems to be similar to the headline on tabloids.. Just because a technology could be used for negative purposes does not mean that it should not be developed.. If your reasoning was used, we should have all been living in caves by now..

By your reasoning
Cars can be used by criminals to travel faster.
A knife can be used to kill
Electricity can be used to kill
Computers can be used by the govt to collect more information abt us effectively

Is that really what we want?

see the flaw in the logic?

Re:

Is that really what we want?

Reminds me of that Harry Enfield sketch.... Is that what you want? 'Cos that's what'll happen. [youtube.com] Won't make any sense to Americans, but who cares :-)