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

[xenocide2]

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.

Prior art

[SamP2]

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

Before [wikipedia.org]

After [wikipedia.org]

Insignificant person removed.

Re:The paper via ACM

[spydir31]

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

Re:The paper via ACM

[Anonymous Coward]

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:A picture speaks a thousand words...

[Fred Ferrigno]

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:The Commissar Vanishes

[ArcherB]

http://www.newseum.org/berlinwall/commissar_vanish es/vanishes.htm [newseum.org]

Fixed [newseum.org] that link for ya.

Re:The paper via ACM

[DotDotSlasher]

This excellent website http://trowley.org/sig2007.html [trowley.org] has a host of links to almost all of the papers presented at SIGGRAPH 2007.

Re:DP Approach

[pclminion]

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 deserves little mention."

Ariel Shamir

[Schraegstrichpunkt]

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

Video is on youtube....

[Tmack]

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

Clicky [youtube.com]

Tm

Re:Prior art

[francium de neobie]

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.