Seam Carving

Rating: 5
August 27th, 2007

carved_pagoda.jpg I recently watched this interesting video by Shai Avidan and Ariel Shamir from MERL. They developed an extremely cool image resizing technique called seam carving. They explain all about it in this article.

One of the coolest things about their idea is that is it easy to implement. I implemented a semi-optimized version of their algorithm in a couple of hours of coding. All the images in this post were generated by my code.

The following image of a pagoda will assist me in demonstrating the ideas to follow:

pagoda.jpg

First lets discuss the two image resizing methods currently used, namely scaling and cropping. Scaling consists of uniformly resizing the image. If for example we were to reduce an image 100 pixels wide to an image 50 pixels wide, we could simply average every two neighbouring pixels (a generalization of this technique can be applied even when the image’s new width does not divide the image’s original width, and of course to resizing both the width and the height of the image).

Scaling is efficient and, in some sense, you do not lose a lot of information from the original image. There are two big problems with scaling however:

  • If the new dimensions of the image are not proportionate to the original dimensions, the scaled image is distorted.
  • The method does not take into account the contents of the image at all (I will clarify this point shortly).

An example of the pagoda image scaled:

scaled_pagoda.jpg

A second widely used form of image resizing is cropping. Cropping consists of simply selecting a sub image of the desired proportions from the original image – i.e. removing the borders of the image. An important question now arises: how do we select which box of the image to keep (or equivalently, how do we select which borders to remove)?

Lets say we assign a weight to each of the pixels of the image, representing its importance. Then selecting the cropping box amounts to simply selecting the box containing the pixels whose sum of weights is highest. We will refer to the weights of the pixels as the energy of the pixels. So optimal cropping would select the box with the highest energy.

Now, all we are left to do is assign the weights to the pixels. Following Avidan and Shamir, we can use simple gradient magnitude as our energy function. Gradient magnitude simply means calculating the gradient at each pixel (regarding the image as a function from R2 to R) and taking its magnitude at each pixel. Here is the result of applying gradient magnitude on the pagoda image:

grad_mag.JPG

The perceptive reader would have noticed that a color image is usually a function from R2 to R3 and not to R (as there are usually three independent color channels). There are several ways to calculate the gradient magnitude in this case. The one I used in my code is to calculate the magnitudes of the three gradients separately and average the results. Note that averaging before calculating the gradients is a bad idea as a lot of information is lost in the process!

Note that the gradient magnitude of a pixel constitutes some measure of how likely that pixel is to be a border pixel (and thus more important).

Using all of this, an optimal cropping of the pagoda image is shown here:

croped_pagoda.jpg

The cropping is optimal in the sense that this is the sub-image of the given dimensions containing the most energy.

Note that all the water from the bottom of the image, and the flowers from the top are missing, as well as the left side of the white house on the left of the pagoda.

Now, unlike the scaling method, the cropping technique just presented takes into account the contents of the image. But what if the image contained two pagodas, one at each side of the image? Cropping would only be able to select one of them.

So what we are looking for is some way to automatically remove the uninteresting parts in the middle of the image, and bring the interesting bits closer together.

A naive solution, similar to regular cropping, would be to remove the columns of the image with the least amount of energy not necessarily from the border. This technique causes severe artifacts.

Avidan’s and Shamir’s seam carving technique is an improvement of this. They define a vertical seam as an 8-connected path from top-to-bottom of the image containing one pixel in each row. 8-connectedness means that if pixel (x,y) is in the vertical seam, then exactly one of the pixels (x+1, y+1), (x, y+1) or (x-1, y) is in the vertical seam as well (unless of course y = the height of the image). A horizontal seam is defined similarly.

Now instead of deleting the column (row) with the least energy, they suggest deleting the vertical (horizontal) seam with the least energy. The seam with the least energy can be easily found using dynamic programming.

The first seam to be removed in the pagoda image is depicted below:

seam.JPG

The process of reducing an image’s size via repeated deletions of the least important seams is called seam carving. The result of applying some seam carving to the pagoda image is shown here:

carved_pagoda.jpg

Note that although some artifacts are present in the image, it is the best among all the reduced images (at least – a mon avis).

A problem with seam carving, compared to scaling, is efficiency. I have some algorithmic ideas that I think might substantially reduce computation costs. I will let you know when I will have time to test them.

Another example is shown. The original image:

pagodas_small.jpg

Optimal cropping:

pagodas_small_cropped.jpg

Scaling:

pagodas_small_scaled.jpg

And finally, seam carving:

pagodas_small_carved.jpg

And just to convince you that the method doesn’t only work on pagodas:

hopper_landscape.jpg

And the carved version:

hopper_landscape_carved.jpg

41 Responses to “Seam Carving”

  1. Luca Mondini - » Seam carving: ridimensionamento intelligente delle immagini Says:

    [...] post esplicativo [...]

  2. Matan Says:

    Ultra cool!

  3. Seam Carving e Gimp: questo matrimonio s’ha da fare! « Daniele Says:

    [...] leviathanonline [...]

  4. Daniele Says:

    Your implementation could be usefull and well accepted by the Gimp project – http://www.gimp.org. Actually there is an active discussion on Developer mailing list.

  5. Dan Says:

    This technique really is very cool.

    About scaling, you said that “The method does not take into account the contents of the image at all”, which also appears to be the opinion of Avidan and Shamir. Now, I agree that scaling usually looks horrible when it’s disproportionate, but I think that it takes the content into account quite well – better than seam carving, even; it simply is almost lossless. Shrinking the image by a coefficient of two, say, retains pretty much all content. I am not sure what the formulas for non-integer proportions are, but in my experience proportionate scaling usually results in pictures that look pretty much the same. The only real loss is the resolution of the details, but all of the features remain, whereas in seam carving there’s no resolution loss, but some features (granted, the least significant ones) completely disappear. I think losing resolution is preferable in most cases.

    For example, consider the resized image of the two pagodas. While the scaled image isn’t good looking (as it is disproportionate), I don’t find the seam-carved image quite satisfactory. One of the lost details is that the pagodas are not, in fact, that close to each other, and I think that results in quite different content in the carved image.

    Now, say that you need to shrink a 600*400 picture into a 200*200 one. Simply scaling results in a terribly deformed picture. If you seam-carve, you carve away 400 vertical lines and 200 horizontal lines, which are two thirds of the width and one half of the height; that’s probably a lot of lost content. Now, if you proportionally scale the image to 300*200 and then carve it down to 200*200 (or perhaps carve it down to 400*400 and then scale, the difference is probably not that great but the former might be faster), you only need to carve away a third of the vertical lines, which is quite an improvement.

    I rather like this method of scale and carve. An important question would be when to stop scaling and start carving. Say that you have to resize the picture so that the new width is A*width and the new height is B*height. One of the options, used in the previous paragraph, is to scale it by the maximum of A and B, and then carve out what remains. This is perhaps an improvement to just carving, but it won’t improve the situation in cases such as the two pagodas, where one dimension stays fixed. It could also be potentially self defeating in cases where you need to increase one dimension.

    Another method would be to scale it by the minimum of A and B, and then carve-in the remainder. I like this version better, because carving in is detail-lossless. However, you do lose even more resolution, you end up with the least significant details extended, and adding seams is a harder technique which also doesn’t always look well.

    Finally, any other value between A and B can be used, and then you need to carve both in and out. My preferred value is the geometric mean of A and B; it seems the most natural choice to me… Although by two definition of optimization I used, the optimal choices were the maximum and the arithmetic mean – obviously, the definitions just weren’t good enough (:. I don’t think the maximum is optimal, but the arithmetic mean might be.

    If you feel like implementing this, as it’s probably not hard to add this to the existing seam-carving implementation, I’d really like to see how some of these values deal with the picture of the two pagodas. And sorry for the length of this thing, it’s likely that this post could be improved with some heavy seam-carving.

  6. Ramin Says:

    Great description !

    Maybe you want to take a look at http://www.thegedanken.com/retarget/ where you can download a prototype for Windows to play around a bit, still work to do …

    regards
    Ramin

  7. yaniv Says:

    Dan,

    Of course scaling does take into account the contents of the image (different input images usually generate different output images :-) ). What I meant is percisely that “unimportant” parts of the image get to occupy as much space in the output image as the important parts.

    Now, obviously all the forms of image shrinking loose information (there are num_colors^(original_width*original_height) input images and num_colors^(output_width*output_height) output images). So clearly, assuming the output size is small than the input size, several different input images get mapped to the same output image, thereby information is lost.

    Choosing what information to loose is a more of a philosophical question than a mathematical one. In some contexts, realizing that the two pagodas are not very close to each other is important, in others realizing the exact proportions of the base of the pagoda to its height are more important.

    I agree that scaling is less “lossy” in the sense that given a scaled down image and the original dimensions of it, the scaling process can be reversed quite efficiently (i.e. a source image very similar to the original input image can be found easily). Seam carving, on the other hand, is much harder to reverse.

    I do think that seam carving is extremely useful not only as an image resizing mechanism, but as an image processing tool. A tool that removes the insignificant parts of the image retaining only its essential bits (e.g. instead of using it as a function from one image to another we can use it as a function from one image to a set of images containing the important parts, etc.).

    Your idea of mixing scaling and carving sounds really good! It actually fits an other idea I had on improving image quality (but it is too long to describe in a comment…). A very interesting thing about seam carving is that by comparing the energy of the seam to remove vs. the total energy of the image we can get a very good idea of whether the seam is indeed irrelevant or whether we already reached a limit after which removing seams will delete important parts of the image.

    I.e. if we detect that the next seam to remove has a lot of energy vs. the whole image, then we might want to stop carving and start scaling.

    Implementing your ideas is a matter of minutes and I will sure do so (and let you know of the results ;-) ) after I get back to Israel!

    PS – Tonight I am flying to Prague to present an algorithm I developed in a conference. Be back in 2 weeks, and I will tell you more about it then.

  8. Dan Says:

    Good luck, and have fun at Prague!

  9. PiFou Says:

    Hi,

    I have made an open source java program of this algorithm. It can be found here : http://pierrefrancois.leon.free.fr/smart-resizing/.
    (but with a little difference : i recalculate the energy function at each sean removal)

  10. yaniv Says:

    Hi Pierre,

    My implementation also recalculates the energy at each seam removal (I think the algorithm will perform much worse if this wasn’t done). This can actually be done much more efficiently than recomputing the Gradient Magnitude of the entire image again (as most of it remains the same).

    Another thing that can be done, which I haven’t implemented yet, is instead of simply removing a seam, somehow averaging it with its surrounding seams. And of course there are all the suggestions of combining carving and scaling.

    I will look your implementation when I’ll get back from Prague (in about a week and a half).

    Merci pour la remarque!

  11. greger Says:

    Hi,

    I just got done making a version in C++, and tested it on a bunch of people on a beach. I was frustrated that the algorithm started removing seams containing people long before it had run out of empty beach. I realized that this was because the beach had many horizontal layers and therefore lots of energy i the y-direction. So I tried again removing vertical seams, but this time I used the magnitude of the x-component as energy function, which turned out great, removing all the background beach before attacking the foreground people.

    I haven’t really tested if this holds for many other pictures, but it seems to me that giving more weight to the x-gradient when calculating vertical seams, and conversly, more weight to y-gradient when removing horizontal seams, could be a good strategy. Any views?

  12. Peter Says:

    Hi, if anyone is interested, I, too, have implemented parts of the algorithm in C++. You can download the software from my site at http://www.peterw.000webhost.com/resizor/ . You can also do conventional scaling with it.

    I, too, recalculate the energy map at each iteration (in fact I “heal” it since only two parallel seams in the energy map are affected by the removal, unless you approximate the derivative with a radius higher than 1, which does not seem to be necessary at all). The seam cost map, however, has to be entirely recomputed.

  13. yaniv Says:

    Greger,

    Interesting idea. I will give it some thought and get back to you with my conclusions (although it will probably take me a couple of weeks as I am really busy now).

    Peter,

    You are absolutely right about “healing” the energy map instead of completely recalculating it, and I did the same in my code.
    I actually also “heal” the seam cost map, instead of entirely recomputing it. What I did is to propagate the changes forward in only the affected pixels. Of course this affects more pixels than are contained in 2 vertical seams but it still only affects part of the seam cost map.

  14. Amnon Says:

    cool stuff.
    How about explaining how to seamlessly stitch the two halves of the picture after carving out a column?

  15. cigarettes Says:

    Very nice this blog =)

  16. marlboro Says:

    Very nice this blog =)

  17. Wahoo Says:

    Thank you for sharing!

  18. Peter Says:

    @Amnon: You don’t really have to stitch the two “halves” together. Since the algorithm always selects the seam with the lowest energy, the “difference” between each pixel and its neighbour is minimal and removing the pixel will generally not leave artifacts behind but rather “compress” the original area into the new one.

    Maybe this becomes clear if we think through an example: If you have an image of an evenly colored blue square, removing a seam or a column from that will not leave any marks since putting blue next to the same blue is seamless.

    Let’s then repeat the experiment with an image of the same square, but filled with a linear horizontal gradient*, you will find that removing seams or columns will result in the gradient becoming “steeper”. To understand what is happening, let’s assume (without loss of generality) that we are removing columns rather than seams. The entire fill has the same energy at every point since the change Pfrom one column to the next is always the same since the gradient is linear. Now if you remove an arbitrary column, the gradient at the neighboring columns increases, since the step between them is now twice as large as before. That means that the seam carving algorithm is not going to select one of those neighboring columns in the next step, since there are plenty of other columns that still have a smaller energy. This means that in the end you have removed columns with an even spacing so that you end up with something that is similar to the result you would end up with had you used regular downsampling using a nearest neighbor algorithm.

    * Please note that when I’m talking about a gradient here, I mean the thing you would draw with Photoshop’s gradient tool (i.e. interpolated colors), not the mathemathical gradient. For the sake of simplicity, let’s assume that no dithering was used to render it.

    I hope that answers your qestion.
    Peter

  19. yaniv Says:

    Peter,

    I disagree with your answer. Removing the seam with the lowest energy may induce artifacts to the image (the energy of the seam with the lowest energy may still be high!).

    Consider the case of an extremely noisy image. Simply removing seams will generate a lot of artifacts and somehow averaging the removed seams back into the image might make the situation much better.

    You may argue that the seam carving method is inadequate for extremely noisy images, but consider the case of the pagoda image above – the vertical seams do not have a lot of energy (as the blue sky takes up most of them) but each of them is forced to pass through the wall and the water at the bottom – areas of high energy. Averaging the removed seams may reduce the artifacts occuring at those locations.

  20. Peter Says:

    yaniv,

    I completely agree with you. My understanding of Amnon’s question was that he/she wanted to know how the algorithm proposed in the paper deals with the issue. My answer is that it doesn’t deal with it at all (at least as far as I remember) because artifacts are often not very noticeable since most images have a lot of low energy regions, and I attempted to explain why the algorithm does not cause many strong artifacts in those regions. I should have made that clearer, and I should definitely not have used the term “generally”. English is not my native language, so please bear with me. I am really sorry if my post was misleading and caused any misconceptions. Again, you are absolutely right.

    Your suggestion to average the seams is a really good idea, although I would propose a weighted combination of the original values since they do not contribute equally to the resulting pixel. Say we are removing a vertical seam. If you have pixels ABC and you remove pixel B (which is on the seam) ending up with DE, my suggestion is that D = 2/3 * A + 1/3 * B; and E = 2/3 * C + 1/3 * B; You could think of it as splitting the removed pixel and assigning one half of it to each of the neighboring pixels. The results should be on par with conventional resampling in terms of quality, except for any rounding errors that might accumulate. The only problem is that it slows the algorithm down even more.

  21. Dan Says:

    Reading the several last comments about averaging instead of removing, I have thought about a slightly different way to define seams, which might improve things a little. I will talk about vertical seams, for simplicity. Instead of considering pixels to be removed, consider the “spaces” between two horizontally adjacent pixels, or rather, simply that pair of pixels. Give each such pair an energy equal to the distance between the colours (the 3d distance, that is; or gradient or whatever energy function you’re using). Then define the vertical seam similarly, but using pairs of pixels instead of pixels; what you get is a normal seam, but copied and pasted one pixel to the right. Define the energy of the seam as the sum of the energies of all pairs; then remove the seam by changing each pair into a single pixel, by averaging.

    I don’t think this will be a great improvement, but maybe a small one. I think that in this way, the vertical gradient is less important, because colours are merged horizontally instead of simply removed. Still haven’t seen the results of my other suggestions, though. No pressure. :)

  22. Dan Says:

    I had written my last reply before seeing Peter’s; I think his idea of averaging is pretty neat too, and perhaps better balanced and creates less artifacts than mine. Hard to say. I do think that the simplicity of averaging only two pixels, as well as calculating energy based only on two pixels (instead of 3? 5? 9?), has something to it, though.

  23. Brain_ReCall Says:

    I too have been playing around with the algorithm and have been getting very good results. http://brain.recall.googlepages.com/cair
    Written in C++ and multi-threaded, but currently lacking a GUI.

    On your gradient technique: I have been studying this for awhile, and conversion to grayscale before edge detection is generally an acceptable technique. There really isn’t much loss in the edge values, especially if you do a RGB->YUV conversion, such as seen here: http://en.wikipedia.org/wiki/YUV

    There are techniques to increase performance. One way is to avoid recalculating the gradients after every seam removal. I have some examples of this on my website. You can average the edge value back into the edge image much like you do the image. This has its limits, which some of my examples demonstrate.

    Unfortunately, the energy map MUST be recalculated after each removal. Any single change in the energy map affects all values above it in a tree pattern. At most in most circumstances, only about 1/3-1/2 of the energy map will remain unchanged, but specializing the code to avoid those regions might make it unwieldy.

    During removal, yes, I recommend averaging the removed pixel’s values back into its neighbors. This limits some of the harsh edges that are likely to develop. However, it is important NOT to average the results back in when an area is marked for removal, as this will average the unwanted content back into the two edges of the area.

    One thing that hasn’t been discussed here yet is enlarging by seam insertion. The paper’s method appears to be lacking, which I demonstrate on my website. The paper describes calculating all seams at once, then inserting next to each seam from least energy to most. Well, the problem is is that so many of the seams merge as they propagate up, producing horrible stretching. My test image that is 1024 pixels wide only had 4 distinct paths by the time they reach the top. The only solution that I have come up with (thanks to Ramin, who commented above), is to add artificial weight to both the least energy seam and the new inserted seam. Then, the least energy seam has to be recalculated. With the correct choosing the the artificial weight it can produce very good results.

    Other options not mentioned to increase quality are the transport map and frequency domain removal. Both of these would DRASTICALLY increase calculation time. The transport map, described in the paper, needs to calculate both the horizontal and vertical seam removal at each step, then determine which one removed the least amount of energy, and then go with that decision. This is entirely possible to implement, just that it would disable most of the optimizations that we have already discovered. The other quality improvement is frequency domain removal. This is in no way fast, as the frequency domain brings in a whole bunch of fun stuff like imaginary numbers. I have done some frequency domain filtering before, but I am uncertain on how to approach removal (the paper mentions another paper which I have only briefly looked over).

  24. samo zain lyrics Says:

    samo zain lyrics

    Thanks for the nice read, keep up the interesting posts..

  25. Jaudat Mamoon Says:

    Hi,
    I am having a problem to understand the concept of forming a transport map for optimal seam order selection. can some one describe in simple words how one can achieve this optimal seam order selection for seam removal in both directions

  26. Brain_ReCall Says:

    The transport map is intended for multi-directional seam removal (shrinking in both directions at once). The paper’s transport map is rather complicated because it’s used to store all seam removals for all possible resolutions.

    The simplest method to achieve the same results is this:
    1. Calculate vertical least-energy seam as normal. The energy of the seam is the bottom value in the energy map, where you started the seam from.
    2. Repeat step one except for the horizontal direction.
    3. Remove the seam from step 1 and 2 that has the least energy.

    Repeat these steps until one dimension of the image has reached its desired value. Then, you would have to perform the standard seam removal for the other dimension.

  27. Ivan Says:

    Hi, my name is disman-kl, i like your site and i ll be back ;)

  28. Seam carving for content aware image resizing: MATLAB implementation | DanLuong Says:

    [...] http://yaniv.leviathanonline.com/blog/math/seam-carving/ [...]

  29. Seam carving for content aware image resizing: MATLAB implementation & tutorial | danluong Says:

    [...] http://yaniv.leviathanonline.com/blog/math/seam-carving/ [...]

  30. Dan Luong Says:

    Thanks for the writeup, which was helpful when I implemented parts of the standard seam carving algorithm (with GUI) in MATLAB. You can download the software from my site at:

    http://danluong.com/2007/12/21/seam-carving-matlab-implementation-tutorial/

    There’s a variety of functionality in it, and the documentation should be thorough enough for anyone trying to figure out how the algorithm works. I calculate a single gradient image, and recalculate the energymap on every seam removal, and also include seam insertion functionality.

  31. jamal alzeban Says:

    guys, im implementing seam insertion or enlarging, what i need to know is the after i get k seams, do i insert like this:
    insert 1st seam on original image and call new image im2
    insert 2nd seam on im2 and call new image im3
    insert 3rd seam on im2 and call new image im4
    and so on
    or is there another way coz this way is cozing stretching.

    by the way , does any body know how does GIMP software do seam insertion, coz they did a good job and i need the trick. thanks

  32. ReShAdE Says:

    Hi,
    This resizing technique is pretty amazing, but I was looking for a free online tool to actually see it work, before trying to understand how it’s implemented. I wanted to see how it works on my very own pictures. I must confess that it took some time, but I finally found it .For those of you who are interested to see a high quality resizing online tool you can check it out at reshade.com

  33. Does ’seam carving’ generalize? Says:

    [...] found a seam carving implementation by Mike Swanson called Seamonster. This led me to a paper by seam carving’s creators, Dr. Shai Avidan and Dr. Ariel Shamir: Seam Carving [...]

  34. Alex Says:

    Thanks for this very interesting article.
    When you describe the 8-connected path, shouldn’t the third possible point be (x-1,y+1) instead of (x-1,y) ?
    Thanks once again.
    Alex.

  35. yaniv Says:

    Alex,

    You are of course right – thanks for your correction!

  36. john kramer Says:

    waht is the use of the image gradient in it wat is the utility of image gradient don’t write the to find out the pixel with minimum enery level i want the logical explanation,shamir document has no clear explanation for it,why use only sobel operater for gradient why not prewitt

  37. sandrar Says:

    Hi! I was surfing and found your blog post… nice! I love your blog. :) Cheers! Sandra. R.

  38. deepak Says:

    i am planning to implement the seam carving algortihm on TMS320C6713 DSK but i am having difficulty in converting the MATLAB code to a compatible C code. Does anybody know how to do this? i tried using mcc command but the resulting files are not compatible with CCS studio of the processor.

  39. Seam carving for content aware image resizing: MATLAB implementation & tutorial « Dan's Blog Says:

    [...] http://yaniv.leviathanonline.com/blog/math/seam-carving/ [...]

  40. Radha Says:

    I want to further enhance the technique of seam carving.What improvement should i do? Please help me because i want to do it in my dissertation.

  41. saurabh Aggarwal Says:

    Well ! a great research going over it I came to know adobe is still yet to apply the optimal algo for this. As I have noticed that the seam carving will not work in images which have high number of edges,for that purpose image scaling is much better option.In this algo first we have to find that image which is required to be resized can be done thru seam carvin or image scaling.

    In the Seam-Carving ,in the old algo that provided by SHamir i have noticed that many times the seamlocation comes adjacent to eachother which cause blur of image aftwer pixel duplication at this locations. SO, high seam density is to be avoided at any cost that should be our motto but density should be in controlled way means not should low not should high ,low density of seams can causes the seam can enter in edges. For this i Have cut the edge image in 2equal parts thru colums so number of seams required to be added is equally distributed, then the from the 8 neighbours of every pixels from which seam is passing u can add some value like 0.1 to 1 but be carefule if u dd high value the seam will start pass thorugh edges if uadd low value the seam will show same situation as the old one so the value which required to added should be optimal one. In addition to it ,the in Shamir Algo Seam backtracking start from the bottom with minimum value,but I think it is better that add the edge values along the cloumns of all rows nad the column which show min value ,shows that in that column ther i shigh probability of findin optimal seam i mean no edge seam.
    i requires ur comments on this and ur suggestion to more improve it. I hav lot more image outputs produced by my matlab code regarding this that my algo is much better than the ariel shamir’s that is images produced by duolang Matlab code .I will post in this blog if u ppl required.I am seeing how to launch papaer on it in tech conferences .

    Saurabh Aggarwal
    INDIA

Leave a Reply