6 ms·

Happy to see this here! Seam carving is one of those neat little algorithms that hit a sweet spot, being a sum of a few moderately complex algorithms, comes fro

by rudi-c 9y ago

Happy to see this here! Seam carving is one of those neat little algorithms that hit a sweet spot, being a sum of a few moderately complex algorithms, comes from a readable paper, and gives very satisfying result. I had a lot of fun implementing it in undergrad. One thing that I always wondered is how Photoshop managed to make it so fast that you can resize in real-time. If n is the width or height of the image, then the dynamic programming part is O(n^2) and needs to be recomputed after every seam removed. Since every seam is a single pixel wide, resizing the image by a non-trivial amount (say half) is O(n^3). There are other papers that remove multiple seams at a time but the quality isn't as good. GPU acceleration perhaps? Another thing I learned while testing seam carving extensively is that it works nicely in certain scenes/situations, but tends to break down most of the time. The two most common scenarios are: 1) lines that are off by the horizontal by more than a few degrees get cutoff 2) objects loose their proportions and even when the manipulation is not directly obvious, it tends to feel off (in the uncanny valley sense). I expect some interesting work to use deep learning for content-aware resizing, since neural nets could theoretically be more semantically and holistically aware of objects in the image.

johndough 9y ago
I also thought about augmenting this algorithm with the semantic information output of a neural network, but couldn't come up with a good way to generate training data for semantic segmentation which wouldn't distort objects. For example, if you consider an image of a roof, the roof pixels will all be semantically similar, but if you remove any of them just based on that, the regular structure will be distorted. Do you have an idea how to solve this?
- rudi-c 9y ago
  There's one paper I found that explores this approach: https://arxiv.org/pdf/1708.02731.pdf https://arxiv.org/pdf/1708.02731.pdf I know little about deep learning though, so I can't really comment on it. For situations like the roof problem you describe, I think PatchMatch is more likely to work out well. The downside is that it's considerably harder to implement correctly than seam carving. http://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/patchmatch.pdf http://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/patchmatch....
jfries 9y ago
Do you really need to regenerate the whole dynamic programming table though? It seems to me that it could be kept more conservative and only recalculate the needed parts.
- blauditore 9y ago
  IIRC, the "energy" may affect up to 3 below pixels (left, right, center), so each pixel of a removed seam requires re-calculations downwards in the shape of a funnel going to the left and right with a maximum of 45°. In the worst case, this means re-calculatable pixels are in the form of a triangle with a top row pixel as its tip and a 90° angle there. So, for a landscape-oriented image of aspect ratio 2:1 that would mean re-calculating up to 50% of its pixels. For narrower ones, that percentage is even higher, so not too much to gain.
  - jfries 9y ago
    Sure, the worst case would have a large number of re-calculations. But it seems like the common case would converge quickly.
deleted 9y ago
[deleted]
vanderZwan 9y ago
Well, there is this paper called "Real-time content-aware image resizing", maybe that describes the method you are curious about? > In this paper, we present a more efficient algorithm for seam based content-aware image resizing, which searches seams through establishing the matching relation between adjacent rows or columns. We give a linear algorithm to find the optimal matches within a weighted bipartite graph composed of the pixels in adjacent rows or columns. https://web.archive.org/web/20110707030836/http://vmcl.xjtu.edu.cn/Real-Time%20Content-Aware%20Image%20Resizing.files/real_time_content_aware_image_resizing.pdf https://web.archive.org/web/20110707030836/http://vmcl.xjtu....
- rudi-c 9y ago
  That's the one I implemented -- with a bit of low-level hackery, it could run fast enough to resize at ~5-8 fps on mobile back in 2013. But the result didn't look great on most images if you resized by more than ~15%. The technique works by calculating the "importance" field of the image once, and all the seams upfront. Then you can just number the seams from 1-n and remove the first m seams when you resize the image by m. The runtime is then O(n^2) instead of O(n^3). In contrast, with regular seam carving, you'd often update the "importance" field every time you remove a seam. The result is that the seams that get removed are less likely to introduce artifacts. I think it's a similar problem as the forward energy v.s. backward energy problem discussed elsewhere in the thread, but worse.
  - vanderZwan 9y ago
    Hmm, then I don't know. Still, they mustn't have stood still since then and come up with new tricks. I wonder if you could do a kind of quad-tree version where you hone in on the precise seam and minimise recalculations to bubbling new energy up the tree. That might also give a way to weigh global-to-local structure.

by rudi-c 9y ago

johndough 9y ago

I also thought about augmenting this algorithm with the semantic information output of a neural network, but couldn't come up with a good way to generate training data for semantic segmentation which wouldn't distort objects. For example, if you consider an image of a roof, the roof pixels will all be semantically similar, but if you remove any of them just based on that, the regular structure will be distorted. Do you have an idea how to solve this?

rudi-c 9y ago
There's one paper I found that explores this approach: https://arxiv.org/pdf/1708.02731.pdf https://arxiv.org/pdf/1708.02731.pdf I know little about deep learning though, so I can't really comment on it. For situations like the roof problem you describe, I think PatchMatch is more likely to work out well. The downside is that it's considerably harder to implement correctly than seam carving. http://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/patchmatch.pdf http://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/patchmatch....

jfries 9y ago

Do you really need to regenerate the whole dynamic programming table though? It seems to me that it could be kept more conservative and only recalculate the needed parts.

blauditore 9y ago
IIRC, the "energy" may affect up to 3 below pixels (left, right, center), so each pixel of a removed seam requires re-calculations downwards in the shape of a funnel going to the left and right with a maximum of 45°. In the worst case, this means re-calculatable pixels are in the form of a triangle with a top row pixel as its tip and a 90° angle there. So, for a landscape-oriented image of aspect ratio 2:1 that would mean re-calculating up to 50% of its pixels. For narrower ones, that percentage is even higher, so not too much to gain.
- jfries 9y ago
  Sure, the worst case would have a large number of re-calculations. But it seems like the common case would converge quickly.

deleted 9y ago

[deleted]

vanderZwan 9y ago

Well, there is this paper called "Real-time content-aware image resizing", maybe that describes the method you are curious about? > In this paper, we present a more efficient algorithm for seam based content-aware image resizing, which searches seams through establishing the matching relation between adjacent rows or columns. We give a linear algorithm to find the optimal matches within a weighted bipartite graph composed of the pixels in adjacent rows or columns. https://web.archive.org/web/20110707030836/http://vmcl.xjtu.edu.cn/Real-Time%20Content-Aware%20Image%20Resizing.files/real_time_content_aware_image_resizing.pdf https://web.archive.org/web/20110707030836/http://vmcl.xjtu....

rudi-c 9y ago
That's the one I implemented -- with a bit of low-level hackery, it could run fast enough to resize at ~5-8 fps on mobile back in 2013. But the result didn't look great on most images if you resized by more than ~15%. The technique works by calculating the "importance" field of the image once, and all the seams upfront. Then you can just number the seams from 1-n and remove the first m seams when you resize the image by m. The runtime is then O(n^2) instead of O(n^3). In contrast, with regular seam carving, you'd often update the "importance" field every time you remove a seam. The result is that the seams that get removed are less likely to introduce artifacts. I think it's a similar problem as the forward energy v.s. backward energy problem discussed elsewhere in the thread, but worse.
- vanderZwan 9y ago
  Hmm, then I don't know. Still, they mustn't have stood still since then and come up with new tricks. I wonder if you could do a kind of quad-tree version where you hone in on the precise seam and minimise recalculations to bubbling new energy up the tree. That might also give a way to weigh global-to-local structure.