6 ms·

Great. Now adapt this to video (:

by ttoinou 7y ago

itronitron 7y ago
I noticed they don't provide any images with human faces.
- roywiggins 7y ago
  "Human faces? You can't handle human faces!" https://www.youtube.com/watch?v=zqeIqJGdA58 https://www.youtube.com/watch?v=zqeIqJGdA58
- akdas 7y ago
  The algorithm definitely has issues with faces. One part I didn't get into is artificial weights. The original paper discusses "painting" certain regions of the image as high energy, driving seams away from those regions. This ties into faces when the paper suggests face detection to automatically paint faces with high energy, avoiding these issues in the first place!
- shawnz 7y ago
  Probably intentional, the seam carving algorithm has a tendency to make faces look distorted: http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15463-f10/www/proj2/www/gmethvin/Obamas_at_White_House_Easter_Egg_Roll_4-13-09_2_resized.jpg http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15463-f1...
- jeffreyrogers 7y ago
  The basic algorithm doesn't work well with faces, but you can use facial recognition to add a large penalty to carving through regions with faces. So it can be extended pretty easily to handle this.
- a-priori 7y ago
  Since the human visual system is so highly sensitive to faces I think the best approach here would be to apply a facial detection algorithm, then boost the energy for the regions where faces are detected. Basically you'd apply a heuristic that because faces are so special to the human visual system, the perceived energy of a face is higher than the pixels would otherwise indicate. This would make seams avoid altering any faces in the scene.
  - akdas 7y ago
    > apply a facial detection algorithm, then boost the energy for the regions where faces are detected. Great intuition! The original paper actually goes into this, and they come up with that solution. This solution is a special case of allowing the user to apply positive and negative penalties as they wish. The latter allows targeted object removal.
gamegoblin 7y ago
A friend and I once tried this at a hackathon. If you do it naively like we did, frame-by-frame, you will find that the optimal seam to carve shifts around a lot as the lighting changes subtly. This results in characters in frame apparently moonwalking around. It's a really cool effect, but not good for actually resizing a film. Might make for a cool bit of a music video.
- ttoinou 7y ago
  Might make for a cool bit of a music video I was thinking the same!
- joshvm 7y ago
  What if also have an energy term for difference in interframe x-position along the seam? Or maybe doing histogram equalisation for pairs of adjacent frames before the seam cutting might help.
a-priori 7y ago
This same algorithm could be applied in three dimensions (X, Y, time) such that the seam connects along adjacent pixels through time as well as the Y axis. The seam here would be a 2D plane, rather than a 1D line as it is for a single image. If you visualize a video as a stack of frames, then the seam would cut through the stack, like cutting a cake with a knife, following the minimum-energy path through the stack. You'd do this by modifying the recurrence relation to add a term for the energy of pixels in the previous frame as well as the previous line in the current frame.
- gamegoblin 7y ago
  I don't think it's necessarily so simple, and I think the multi-frame case blows up the complexity of the algorithm. In the single frame case, each pixel is a 0 dimensional point, and for each pixel, you evaluate the 3 adjacent pixels in the row above. Then to find the seam you just pick the lowest energy pixel at the edge of the frame and follow the thread up. So the total runtime of this algorithm is O(pixels). In the multi-frame case, if you want the video to be totally smooth, you have to think higher-dimensionally. In the multi frame case, each seam is a 1 dimensional list of pixels, and for each seam, you evaluate the $HUGE_NUMBER of adjacent seams in the previous frame. That is, the 2D case's runtime is proportional to the image height times the number of adjacent pixels, which is a small constant (3). In the 3D case, the runtime is proportional to the number of frame times the number of adjacent seams, which is massive. I can imagine some heuristic optimizations that would allow you to guide your search, though. For instance, you could significantly downsample the video in both pixels and framerate and solve that, and then use that low-resolution solution to constrain and prune an approximate high-resolution search.
- dTal 7y ago
  I think this is the correct way to conceptualize generalizing this algorithm to moving video. I also think it's a fundamentally bad approach to resizing video. The problem is that humans watching the video will build a 3D mental model of the scene; any transform that modifies multiple frames must do so in such a way as to maintain global spatial consistency, or it will look odd. Seam carving is too primitive to do this. You will have shots where (for instance) someone is walking obliquely away from a building towards the camera, and yet making no headway because the algorithm is carving away the (low energy, yet perceptually indispensible) pixels that seperate them - the result will be that they appear to be walking in place (and growing).
steventhedev 7y ago
For what it's worth, that was exactly what they did: http://www.faculty.idc.ac.il/arik/SCWeb/vidret/index.html http://www.faculty.idc.ac.il/arik/SCWeb/vidret/index.html
ausbah 7y ago
It has been done! http://www.eng.tau.ac.il/~avidan/papers/vidret.pdf http://www.eng.tau.ac.il/~avidan/papers/vidret.pdf
marvy 7y ago
See this comment in this thread: https://news.ycombinator.com/item?id=20285242#unv_20290891 https://news.ycombinator.com/item?id=20285242#unv_20290891 (HN really should make it easier to make "anchor" links, so people don't have to load a new page just to see a sub-thread. That probably took me almost 5 minutes, which is like a quarter of the "anti-procrastination" budget with the default settings. It should have taken 10 seconds.)

Great. Now adapt this to video (:

itronitron 7y ago

I noticed they don't provide any images with human faces.

roywiggins 7y ago
"Human faces? You can't handle human faces!" https://www.youtube.com/watch?v=zqeIqJGdA58 https://www.youtube.com/watch?v=zqeIqJGdA58
akdas 7y ago
The algorithm definitely has issues with faces. One part I didn't get into is artificial weights. The original paper discusses "painting" certain regions of the image as high energy, driving seams away from those regions. This ties into faces when the paper suggests face detection to automatically paint faces with high energy, avoiding these issues in the first place!
shawnz 7y ago
Probably intentional, the seam carving algorithm has a tendency to make faces look distorted: http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15463-f10/www/proj2/www/gmethvin/Obamas_at_White_House_Easter_Egg_Roll_4-13-09_2_resized.jpg http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15463-f1...
jeffreyrogers 7y ago
The basic algorithm doesn't work well with faces, but you can use facial recognition to add a large penalty to carving through regions with faces. So it can be extended pretty easily to handle this.
a-priori 7y ago
Since the human visual system is so highly sensitive to faces I think the best approach here would be to apply a facial detection algorithm, then boost the energy for the regions where faces are detected. Basically you'd apply a heuristic that because faces are so special to the human visual system, the perceived energy of a face is higher than the pixels would otherwise indicate. This would make seams avoid altering any faces in the scene.
- akdas 7y ago
  > apply a facial detection algorithm, then boost the energy for the regions where faces are detected. Great intuition! The original paper actually goes into this, and they come up with that solution. This solution is a special case of allowing the user to apply positive and negative penalties as they wish. The latter allows targeted object removal.

gamegoblin 7y ago

A friend and I once tried this at a hackathon. If you do it naively like we did, frame-by-frame, you will find that the optimal seam to carve shifts around a lot as the lighting changes subtly. This results in characters in frame apparently moonwalking around. It's a really cool effect, but not good for actually resizing a film. Might make for a cool bit of a music video.

ttoinou 7y ago
Might make for a cool bit of a music video I was thinking the same!
joshvm 7y ago
What if also have an energy term for difference in interframe x-position along the seam? Or maybe doing histogram equalisation for pairs of adjacent frames before the seam cutting might help.

a-priori 7y ago

This same algorithm could be applied in three dimensions (X, Y, time) such that the seam connects along adjacent pixels through time as well as the Y axis. The seam here would be a 2D plane, rather than a 1D line as it is for a single image. If you visualize a video as a stack of frames, then the seam would cut through the stack, like cutting a cake with a knife, following the minimum-energy path through the stack. You'd do this by modifying the recurrence relation to add a term for the energy of pixels in the previous frame as well as the previous line in the current frame.

gamegoblin 7y ago
I don't think it's necessarily so simple, and I think the multi-frame case blows up the complexity of the algorithm. In the single frame case, each pixel is a 0 dimensional point, and for each pixel, you evaluate the 3 adjacent pixels in the row above. Then to find the seam you just pick the lowest energy pixel at the edge of the frame and follow the thread up. So the total runtime of this algorithm is O(pixels). In the multi-frame case, if you want the video to be totally smooth, you have to think higher-dimensionally. In the multi frame case, each seam is a 1 dimensional list of pixels, and for each seam, you evaluate the $HUGE_NUMBER of adjacent seams in the previous frame. That is, the 2D case's runtime is proportional to the image height times the number of adjacent pixels, which is a small constant (3). In the 3D case, the runtime is proportional to the number of frame times the number of adjacent seams, which is massive. I can imagine some heuristic optimizations that would allow you to guide your search, though. For instance, you could significantly downsample the video in both pixels and framerate and solve that, and then use that low-resolution solution to constrain and prune an approximate high-resolution search.
dTal 7y ago
I think this is the correct way to conceptualize generalizing this algorithm to moving video. I also think it's a fundamentally bad approach to resizing video. The problem is that humans watching the video will build a 3D mental model of the scene; any transform that modifies multiple frames must do so in such a way as to maintain global spatial consistency, or it will look odd. Seam carving is too primitive to do this. You will have shots where (for instance) someone is walking obliquely away from a building towards the camera, and yet making no headway because the algorithm is carving away the (low energy, yet perceptually indispensible) pixels that seperate them - the result will be that they appear to be walking in place (and growing).

steventhedev 7y ago

For what it's worth, that was exactly what they did: http://www.faculty.idc.ac.il/arik/SCWeb/vidret/index.html http://www.faculty.idc.ac.il/arik/SCWeb/vidret/index.html

ausbah 7y ago

It has been done! http://www.eng.tau.ac.il/~avidan/papers/vidret.pdf http://www.eng.tau.ac.il/~avidan/papers/vidret.pdf

marvy 7y ago

See this comment in this thread: https://news.ycombinator.com/item?id=20285242#unv_20290891 https://news.ycombinator.com/item?id=20285242#unv_20290891 (HN really should make it easier to make "anchor" links, so people don't have to load a new page just to see a sub-thread. That probably took me almost 5 minutes, which is like a quarter of the "anti-procrastination" budget with the default settings. It should have taken 10 seconds.)