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

21–30 of 39 posts

Re: Parallel Seam Carving

#21

Post by quelltext »

compthrowaway wrote: post #15
Uehreka wrote: post #14

Earlier quoted context omitted.

That... that was mind-blowing. This discovery is 13 years old. Although it has clear limitations when it comes to humans, I'm surprised I don't see this kind of resize feature available in more software. Does Photoshop have this hidden in a drawer somewhere? Does imagemagick support this?

I seriously cannot decide if your post is satire. Directly from the wikipedia article: http://www.photoshopsupport.com/photoshop-cs4/what-is-new-in... http://www.imagemagick.org/Usage/resize/#liquid-rescale

Hmm, I knew it was implemented in a bunch of plugins or dedicated software like PS. However I am surprised it's not found all over the place by now as part of default apps / preview / OS builtin software / img tag options, etc.

Also none of the implementations I have tried (last time I checked, not up to date on this) were as slick / realtime / interactive as the SIGGRAPH demo.

Re: Parallel Seam Carving

#22

Post by cgearhart »

repsilat wrote: post #11

Does repeated single-pixel seam-carving minimise energy for the "remove n seams" problem? If not, is the global algorithm in P? Also, I guess this is beside the point, but surely almost all of the DP structure can be reused if you're repeatedly removing seams...

No, it’s a greedy algorithm. I don’t think it would be in P to solve it globally. Naively you could perform any graph search to find minimum total cost to depth N where the cost between nodes is the energy removed. In that case it’s exponential.

Because the seam is defined such that each pixel in the next row is within 1 column of the pixel in the preceding row, you can reuse all the calculations except for a pyramid shaped area around the last removed seam (in the worst case). However, that area is on the order of half the total number of pixels, so it doesn’t save _too_ much to reuse the other half.

Re: Parallel Seam Carving

#23

Post by repsilat »

cgearhart wrote: post #22
repsilat wrote: post #11

Does repeated single-pixel seam-carving minimise energy for the "remove n seams" problem? If not, is the global algorithm in P? Also, I guess this is beside the point, but surely almost all of the DP structure can be reused if you're repeatedly removing seams...

No, it’s a greedy algorithm. I don’t think it would be in P to solve it globally. Naively you could perform any graph search to find minimum total cost to depth N where the cost between nodes is the energy removed. In that case it’s exponential. Because the seam is defined such that each pixel in the next row is within 1 column of the pixel in the preceding row, you can reuse all the calculations except for a pyramid…

Ah, makes sense.

> in the worst case

I wonder if typical data is more forgiving. If, for example, we cut an optimal seam down the column n=x, and the DP algorithm tells us that the best seams starting at (0,x-1) and at (0,x+1) are also column seams, the next iteration can happen in linear time in the number of rows. (Plus number of columns -- pessimistically -- if the next-optimal seam isn't "nearby".)

Basically, you're checking the things that crossed the old seam, and I'd guess that'd happen often enough, but I don't know how far the effects would typically spread. Maybe it would work worse in "sparse" images like blue sky, and better in "noisier" images like forests and crowds and dogs' fur.

I'm not sure how much cost that data-dependence would incur though. Might not be worthwhile.

Re: Parallel Seam Carving

#24

Post by thamer »

If folks are interested in a simple implementation to read or reuse, here's a JS version I wrote back when HTML5 and were new and exciting (over 10 years ago now): https://nicolasff.github.io/canvas-seam-carving/

The button says "warning: very slow" but JavaScript performance has significantly improved since then :-)

Still a very cool technique, and pretty easy to implement.

Re: Parallel Seam Carving

#25

Post by etaioinshrdlu »

This is probably also a very interesting technique for data augmentation for computer vision ML. (That is, seam carving. Not much to do with the parallel version...)

Unlike other typical data augmentation operations, spatial relationships are altered in nonlinear but still realistic ways.

Re: Parallel Seam Carving

#26

Post by goldenkey »

boothby wrote: post #19
repsilat wrote: post #11

Does repeated single-pixel seam-carving minimise energy for the "remove n seams" problem? If not, is the global algorithm in P? Also, I guess this is beside the point, but surely almost all of the DP structure can be reused if you're repeatedly removing seams...

> Also, I guess this is beside the point, but surely almost all of the DP structure can be reused if you're repeatedly removing seams... It's not besides the point at all. If you can reduce this linear-time algorithm to, say, amortized constant, then you'll handily beat parallelism. After you remove a seam, you need to recompute the cones below every removed pixel -- which ends up being the cone below the topmost rem…

Can't the image just be rotated if it is tall and skinny? Then unrotated after the transformation?

Re: Parallel Seam Carving

#27

Post by almostarockstar »

goldenkey wrote: post #26
boothby wrote: post #19

Earlier quoted context omitted.

> Also, I guess this is beside the point, but surely almost all of the DP structure can be reused if you're repeatedly removing seams... It's not besides the point at all. If you can reduce this linear-time algorithm to, say, amortized constant, then you'll handily beat parallelism. After you remove a seam, you need to recompute the cones below every removed pixel -- which ends up being the cone below the topmost rem…

Can't the image just be rotated if it is tall and skinny? Then unrotated after the transformation?

Rotating as you suggest would be equivalent of swapping between vertical and horizontal seams. A tall and skinny image with vertical seams has the same problems that a long and wide image has with horizontal seams.

Re: Parallel Seam Carving

#28

Post by dguest »

etaioinshrdlu wrote: post #25

This is probably also a very interesting technique for data augmentation for computer vision ML. (That is, seam carving. Not much to do with the parallel version...) Unlike other typical data augmentation operations, spatial relationships are altered in nonlinear but still realistic ways.

Cases where data augmentation works always pose a fun challenge: clearly if there's some way to manipulate the data which shouldn't alter the algorithm output, there's also some way to make the ML invariant to that manipulation. If you can create an invariant algorithm then the augmentation should be unnecessary.

There is some interesting work on making ML invariant to rotations and such, but I'd be curious if there's an algorithm which is invariant to this. I could imagine that convolutions and pooling might be relatively invariant to this technique, for example, as long as the algorithm isn't doing a lot with the large scale structure of the image.

Re: Parallel Seam Carving

#29

Post by wongarsu »

Uehreka wrote: post #14
echelon wrote: post #3

Earlier quoted context omitted.

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.

That... that was mind-blowing. This discovery is 13 years old. Although it has clear limitations when it comes to humans, I'm surprised I don't see this kind of resize feature available in more software. Does Photoshop have this hidden in a drawer somewhere? Does imagemagick support this?

You will probably see it appear everywhere in 10 years when the patent expires.

https://patents.google.com/patent/US8213745B2/en

Re: Parallel Seam Carving

#30

Post by [deleted] »

wongarsu wrote: post #29
Uehreka wrote: post #14

Earlier quoted context omitted.

That... that was mind-blowing. This discovery is 13 years old. Although it has clear limitations when it comes to humans, I'm surprised I don't see this kind of resize feature available in more software. Does Photoshop have this hidden in a drawer somewhere? Does imagemagick support this?

You will probably see it appear everywhere in 10 years when the patent expires. https://patents.google.com/patent/US8213745B2/en

[deleted]
Post reply on HN