6 ms·

Show HN: Improved Seam Carving Using Forward Energy

99 points by seam_carver 8y ago

seam_carver 8y ago
Don't think most people know about the improved seam carving algorithm (since only the original is taught in most CS curriculums) and thought you might think this is cool!
- jaytaylor 8y ago
  It is a neat algorithm, hope you are able to get it merged into scikit-image [0] without too much fuss~ good luck! [0] https://github.com/scikit-image/scikit-image/issues/3082 https://github.com/scikit-image/scikit-image/issues/3082
  - deleted 8y ago
    [deleted]
xg15 8y ago
> Both papers introduce different ways to "calculate the energy of a pixel, which is a measure of its importance—the higher the energy, the less likely that the pixel will be included as part of a seam." If I understand correctly, this function is basically how the algorithm decides which parts of the image to cut (or stretch). So it seems like it could be interesting to experiment with a range of different functions here. Has anyone tried to e.g. plug in a CNN?
- seam_carver 8y ago
  I'm unfamiliar with CNN's, but you can draw masks manually to protect/remove parts of an image, or use a face recognition thing, or a motion detection thing, etc.
  - mlthoughts2018 8y ago
    You could use a one-hot encoding to represent the resizing operation that’s desired ([0, 0, 1] for horizontal shrink, [0, 1, 0] for vertical shrink, and [0, 1, 1] for shrinking both, then use first component of 1 for expansion). The input to a CNN model could then be the input image and the one-hot encoded resize instruction. And the “label” could be the pixel map of the chosen seam-carving seam that produces the resize step. The CNN output will be a softmax pixel map, optimized to reproduce the seam-carving result. Then at runtime, you would just have to add a slight post-processing step that ensures the CNN’s predicted seam doesn’t violate any constraints for the intended output shape of the resize operation chosen. You could use the existing seam carving algorithm to generate the training data, but would need to be careful the training set covers a huge variety of image statistics to avoid overfitting resizing to a particular subset of image features (or conversely, you could try to learn “better” than seam carving for specialized resizing on subclasses of images, like specialized for faces, cityscapes, etc.)
    - seam_carver 8y ago
      I don't know most of the terms you just said... I guess I should try learning some ML? I heard the Andrew Ng Coursera course is a good place to start.
  - TTPrograms 8y ago
    The biggest value of ML here would likely be to create a more useful energy function. This could be informed either by object detection data or hand drawn "energy" masks. The other big change that could be useful would be to go with a non-greedy approach. Say you want to scale down a crowd of people - how do you remove, say, one person from the crowd instead of removing "low-energy" strips from multiple people. The people in the crosswalk image sort of demonstrates the difficulty of using basic energy metrics there. One interesting idea would be to use GANs - come up with some parameterized seam removal function (with number of seams a input) such that the resulting image is still highly probable under the data distribution. So you can't cut objects into weird shapes since there aren't images like that in the dataset.
imranq 8y ago
This is the third assignment in Princeton’s Algorithms II course on Coursera - highly recommended!
- seam_carver 8y ago
  That assignment only covers the original seam carving algorithm; this post also covers the improved seam carving algorithm!
innagadadavida 8y ago
14 sec per image is excessive, is there either an implementation or algorithm that can handle do this in less than 500ms per image?
- seam_carver 8y ago
  It's 14 seconds to remove 200 seams on the 512-by-342 bench image, but I note potential optimizations in the notebook. Right now, the seam_carve function in scikit-image accepts an energy matrix, which it then uses to generate the accumulated energy matrix. Forward energy calculates the accumulated energy matrix directly, but I calculate the energy matrix backward from it to be able to use scikit's seam_carve function. If I write my own seam removal function or change scikit's, I think I could be able to make the speed comparable to backwards energy. Furthermore, the accumulated energy matrix calculation step in scikit uses a double for loop, which might be able to replaced with some np stuff for a speedup for both forward and backwards energy. I should probably raise this as an issue on GitHub... thanks!
  - seam_carver 8y ago
    I actually realized I was doing a lot of unnecessary computation in my dynamic programming step. I removed it and from 14 s it's now 8 s.
    - seam_carver 8y ago
      After talking with some friends, basically I could get this to be a lot faster if I just wrote it in Cython. (the skimage.transform.seam_carve function is written in Cython). Also, I realize now that the double for loop in Cython is actually fast, so that means that the skimage implementation of dynamic programming is optimal. But I can still change it to accept the accumulated energy matrix!
- WhiteNoiz3 8y ago
  For anyone interested, Photoshop has had this feature for a long time - Content Aware Scaling. It's also much faster.
chatmasta 8y ago
Seam carving is really cool, not just for the typical application of changing images, but also as a method of fingerprinting images (and the other side, anonymizing them). There are some interesting papers on these use cases via Google scholar [0]. There are a lot of potential businesses that could be built around image fingerprinting. Off the top of my head those include the obvious copyright/IP monitoring, and also more novel ideas like "meme tracking" to observe the propagation of memes across the Internet. [0] https://scholar.google.co.uk/scholar?hl=en&as_sdt=0%2C5&q=seam+carving+fingerprint&btnG= https://scholar.google.co.uk/scholar?hl=en&as_sdt=0%2C5&q=se...
- seam_carver 8y ago
  That looks pretty cool! Thanks for the link! I'll look more into it soon.

99 points by seam_carver 8y ago

Don't think most people know about the improved seam carving algorithm (since only the original is taught in most CS curriculums) and thought you might think this is cool!

jaytaylor 8y ago
It is a neat algorithm, hope you are able to get it merged into scikit-image [0] without too much fuss~ good luck! [0] https://github.com/scikit-image/scikit-image/issues/3082 https://github.com/scikit-image/scikit-image/issues/3082
- deleted 8y ago
  [deleted]

xg15 8y ago

> Both papers introduce different ways to "calculate the energy of a pixel, which is a measure of its importance—the higher the energy, the less likely that the pixel will be included as part of a seam." If I understand correctly, this function is basically how the algorithm decides which parts of the image to cut (or stretch). So it seems like it could be interesting to experiment with a range of different functions here. Has anyone tried to e.g. plug in a CNN?

seam_carver 8y ago
I'm unfamiliar with CNN's, but you can draw masks manually to protect/remove parts of an image, or use a face recognition thing, or a motion detection thing, etc.
- mlthoughts2018 8y ago
  You could use a one-hot encoding to represent the resizing operation that’s desired ([0, 0, 1] for horizontal shrink, [0, 1, 0] for vertical shrink, and [0, 1, 1] for shrinking both, then use first component of 1 for expansion). The input to a CNN model could then be the input image and the one-hot encoded resize instruction. And the “label” could be the pixel map of the chosen seam-carving seam that produces the resize step. The CNN output will be a softmax pixel map, optimized to reproduce the seam-carving result. Then at runtime, you would just have to add a slight post-processing step that ensures the CNN’s predicted seam doesn’t violate any constraints for the intended output shape of the resize operation chosen. You could use the existing seam carving algorithm to generate the training data, but would need to be careful the training set covers a huge variety of image statistics to avoid overfitting resizing to a particular subset of image features (or conversely, you could try to learn “better” than seam carving for specialized resizing on subclasses of images, like specialized for faces, cityscapes, etc.)
  - seam_carver 8y ago
    I don't know most of the terms you just said... I guess I should try learning some ML? I heard the Andrew Ng Coursera course is a good place to start.
- TTPrograms 8y ago
  The biggest value of ML here would likely be to create a more useful energy function. This could be informed either by object detection data or hand drawn "energy" masks. The other big change that could be useful would be to go with a non-greedy approach. Say you want to scale down a crowd of people - how do you remove, say, one person from the crowd instead of removing "low-energy" strips from multiple people. The people in the crosswalk image sort of demonstrates the difficulty of using basic energy metrics there. One interesting idea would be to use GANs - come up with some parameterized seam removal function (with number of seams a input) such that the resulting image is still highly probable under the data distribution. So you can't cut objects into weird shapes since there aren't images like that in the dataset.

imranq 8y ago

This is the third assignment in Princeton’s Algorithms II course on Coursera - highly recommended!

seam_carver 8y ago
That assignment only covers the original seam carving algorithm; this post also covers the improved seam carving algorithm!

innagadadavida 8y ago

14 sec per image is excessive, is there either an implementation or algorithm that can handle do this in less than 500ms per image?

seam_carver 8y ago
It's 14 seconds to remove 200 seams on the 512-by-342 bench image, but I note potential optimizations in the notebook. Right now, the seam_carve function in scikit-image accepts an energy matrix, which it then uses to generate the accumulated energy matrix. Forward energy calculates the accumulated energy matrix directly, but I calculate the energy matrix backward from it to be able to use scikit's seam_carve function. If I write my own seam removal function or change scikit's, I think I could be able to make the speed comparable to backwards energy. Furthermore, the accumulated energy matrix calculation step in scikit uses a double for loop, which might be able to replaced with some np stuff for a speedup for both forward and backwards energy. I should probably raise this as an issue on GitHub... thanks!
- seam_carver 8y ago
  I actually realized I was doing a lot of unnecessary computation in my dynamic programming step. I removed it and from 14 s it's now 8 s.
  - seam_carver 8y ago
    After talking with some friends, basically I could get this to be a lot faster if I just wrote it in Cython. (the skimage.transform.seam_carve function is written in Cython). Also, I realize now that the double for loop in Cython is actually fast, so that means that the skimage implementation of dynamic programming is optimal. But I can still change it to accept the accumulated energy matrix!
WhiteNoiz3 8y ago
For anyone interested, Photoshop has had this feature for a long time - Content Aware Scaling. It's also much faster.

chatmasta 8y ago

Seam carving is really cool, not just for the typical application of changing images, but also as a method of fingerprinting images (and the other side, anonymizing them). There are some interesting papers on these use cases via Google scholar [0]. There are a lot of potential businesses that could be built around image fingerprinting. Off the top of my head those include the obvious copyright/IP monitoring, and also more novel ideas like "meme tracking" to observe the propagation of memes across the Internet. [0] https://scholar.google.co.uk/scholar?hl=en&as_sdt=0%2C5&q=seam+carving+fingerprint&btnG= https://scholar.google.co.uk/scholar?hl=en&as_sdt=0%2C5&q=se...

seam_carver 8y ago
That looks pretty cool! Thanks for the link! I'll look more into it soon.