Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Parallel Seam Carving

shwestrick.github.io

Post reply on HN
Print view View original

1–10 of 39 posts

Re: Parallel Seam Carving

#3

Post by echelon »

solstice wrote: post #2

That's really neat. What are some practical applications for Seam Carving? Maybe in video games with dynamic resizing of landscapes?

Check out the original SIGGRAPH presentation on it. There are lots of really great demos. It's one thing to read about the algorithm, but to see it in action is magical.

https://www.youtube.com/watch?v=6NcIJXTlugc

This is still amazing all of these years later.

Re: Parallel Seam Carving

#4

Post by nwallin »

Barrier synchronization is always going to wreck parallel performance. When possible, it's good to break up your work so that data dependencies are explicit and fine grained. So instead of breaking up work like this:

    IIIIJJJJKKKKLLLL

    

    EEEEFFFFGGGGHHHH

    

    AAAABBBBCCCCDDDD
... where each row is dependent on the entire previous row, break it up like this:

    HHHHIIIIJJJJKKKK

    EEEEEEFFFFGGGGGG

    AAAABBBBCCCCDDDD
Where E is dependent on A and B, (and begins when they are done) H is dependent only on E, F is dependent on B and C, etc. This way you don't have to wait for the entire strip to finish, you can start work on E after A+B, but while D is still working. This also gives you weird block sizes for "free", which is a huge no-no with barrier synchronization. For instance, Es and Gs are size 6; if the first example had most elements of size 4, but one element of size 6, it would be catastrophic. All your threads would be done when the final thread is only 66% complete, and it's single threaded from there on out for that strip.

Re: Parallel Seam Carving

#5

Post by cgearhart »

solstice wrote: post #2

That's really neat. What are some practical applications for Seam Carving? Maybe in video games with dynamic resizing of landscapes?

It’s...not as useful as it first appears. It’s actually very computationally expensive to solve the mapping, and it can add quite of bit of space to the image to pre-compute the seam order (which is the proposal made by the original paper).

Each pixel can be tagged with a rank according to its seam number along each axis. If you have 4,000x4,000 pixels then each pixel needs a 12-bit integer value for each axis; and if you want the optimal map it’s another 1 bit per pixel. So something on the order of an extra 25-bits per pixel for a naive encoding, which almost doubles the size of an 8-bit per channel image.

It also has no explicit scene awareness. The energy function essentially defines an implicit heuristic of scene importance, which is surprisingly reasonable until you’re removing >25% of pixels along either axis.

I believe it shipped with Photoshop for a couple years (maybe still?) but in my experience it’s a bit more of an artistic effect than an automatic and scalable solution—and it would be really hard to make it run in real time at game frame rates. (I think the artifacts alone would make it not worth it for games.)

Re: Parallel Seam Carving

#6

Post by ivalm »

solstice wrote: post #2

That's really neat. What are some practical applications for Seam Carving? Maybe in video games with dynamic resizing of landscapes?

I think as a photo editing tool. The neatest nontrivial use i know is to “delete” objects. You can use segmentation algo to highlight an object and set its energy to 0 then seam carve out “naturally”.

Re: Parallel Seam Carving

#7

Post by hydroxideOH- »

solstice wrote: post #2

That's really neat. What are some practical applications for Seam Carving? Maybe in video games with dynamic resizing of landscapes?

I used seam carving in a side-project Chrome extension I developed [1]. The extension pull the top landscape photo from r/EarthPorn and resizes it to 1920x1080 using the seam carving library caire [2]. Then it uploads the resized image to Imgur where it can be used as the user's new tab wallpaper.

Perhaps using seam carving was a little bit overboard but I thought it would be interesting and it works really well for most Earth landscape photos. I only rarely see artifacts and minor distortions in the resized images it produces. Also since I only needed to resize one photo per day, the computational overhead was not a very big deal.

[1] https://github.com/micahcantor/dailypapers

[2] https://github.com/esimov/caire

Re: Parallel Seam Carving

#8

Post by wy35 »

solstice wrote: post #2

That's really neat. What are some practical applications for Seam Carving? Maybe in video games with dynamic resizing of landscapes?

A non-practical application is for funny memes. Someone figured out Photoshop's Content Aware Scaling feature can hilariously distort faces [1], and people have been using it memes since.

My current favorite: https://www.youtube.com/watch?v=NRB_ASog9QU

[1] https://knowyourmeme.com/memes/content-aware-scaling

Re: Parallel Seam Carving

#9

Post by ohazi »

wy35 wrote: post #8
solstice wrote: post #2

That's really neat. What are some practical applications for Seam Carving? Maybe in video games with dynamic resizing of landscapes?

A non-practical application is for funny memes. Someone figured out Photoshop's Content Aware Scaling feature can hilariously distort faces [1], and people have been using it memes since. My current favorite: https://www.youtube.com/watch?v=NRB_ASog9QU [1] https://knowyourmeme.com/memes/content-aware-scaling

that video is just a bunch of screaming... is that really the best example for this?

Re: Parallel Seam Carving

#10

Post by wy35 »

ohazi wrote: post #9
wy35 wrote: post #8

Earlier quoted context omitted.

A non-practical application is for funny memes. Someone figured out Photoshop's Content Aware Scaling feature can hilariously distort faces [1], and people have been using it memes since. My current favorite: https://www.youtube.com/watch?v=NRB_ASog9QU [1] https://knowyourmeme.com/memes/content-aware-scaling

that video is just a bunch of screaming... is that really the best example for this?

Never said it was the best example. Just said it was my favorite. It's pretty much content aware scaling on a still image.

If you want one on a real video, I guess there's this: https://www.youtube.com/watch?v=a8k3b-QNbhs

Post reply on HN