3 ms·

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

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.

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.