Seam carving

Seams

Seams can be either vertical or horizontal. A vertical seam is a path of pixels connected from top to bottom in an image with one pixel in each row. A horizontal seam is similar with the exception of the connection being from left to right. The importance/energy function values a pixel by measuring its contrast with its neighbor pixels.

{{anchor|algorithm}}Process

The below example describes the process of seam carving:

The seams to remove depends only on the dimension (height or width) one wants to shrink. It is also possible to invert step 4 so the algorithm enlarges in one dimension by copying a low energy seam and averaging its pixels with its neighbors.

Computing seams

Computing a seam consists of finding a path of minimum energy cost from one end of the image to another. This can be done via Dijkstra's algorithm, dynamic programming, greedy algorithm or graph cuts among others.

Dynamic programming

Dynamic programming is a programming method that stores the results of sub-calculations in order to simplify calculating a more complex result. Dynamic programming can be used to compute seams. If attempting to compute a vertical seam (path) of lowest energy, for each pixel in a row we compute the energy of the current pixel plus the energy of one of the three possible pixels above it.

The images below depict a DP process to compute one optimal seam. Each square represents a pixel, with the top-left value in red representing the energy value of that pixel. The value in black represents the cumulative sum of energies leading up to and including that pixel. File:DynamicProgrammingLeastEnergyPathA.svg|The top row has nothing above it, so the energies are the same as the source image. File:DynamicProgrammingLeastEnergyPathB.svg|For each pixel in the rest of the rows, the energy is its own energy plus the minimal of the three energies above. Repeat until the bottom is reached. File:DynamicProgrammingLeastEnergyPathC.svg|For the lowest energies we have at the end, work back up the minimals to recover the seam with minimal energy.

The energy calculation is trivially parallelized for simple functions. The calculation of the DP array can also be parallelized with some interprocess communication. However, the problem of making multiple seams at the same time is harder for two reasons: the energy needs to be regenerated for each removal for correctness and simply tracing back multiple seams can form overlaps. Avidan 2007 computes all seams by removing each seam iteratively and storing an "index map" to record all the seams generated. The map holds a "nth seam" number for each pixel on the image, and can be used later for size adjustment.

If one ignores both issues however, a greedy approximation for parallel seam carving is possible. To do so, one starts with the minimum-energy pixel at one end, and keep choosing the minimum energy path to the other end. The used pixels are marked so that they are not picked again. Local seams can also be computed for smaller parts of the image in parallel for a good approximation.

Issues

1. The algorithm may need user-provided information to reduce errors. This can consist of painting the regions which are to be preserved. With human faces it is possible to use face detection.
2. Sometimes the algorithm, by removing a low energy seam, may end up inadvertently creating a seam of higher energy. The solution to this is to simulate a removal of a seam, and then check the energy delta to see if the energy increases (forward energy). If it does, prefer other seams instead.

Implementations

File:Broadway_tower_seam_carving_interactive.svg|thumb|250px|Interactive SVG demonstrating seam-carving using ImageMagick's liquid-rescale function. In the SVG file, hover over the percentages to compare the original image (top), its width rescaled to the percentage using seam-carving (middle), and rescaled to the same size using interpolation (bottom). default http://upload.wikimedia.org/wikipedia/commons/b/bf/Broadway_tower_seam_carving_interactive.svg File:Creation_of_Adam_seam_carving_interactive.svg|thumb|250px|Interactive SVG demonstrating seam-carving using ImageMagick's liquid-rescale function. In the SVG file, hover over the percentages as above. Note that the faces are affected less than their surroundings. default http://upload.wikimedia.org/wikipedia/commons/5/53/Creation_of_Adam_seam_carving_interactive.svg Adobe Systems acquired a non-exclusive license to seam carving technology from MERL, and implemented it as a feature in Photoshop CS4, where it is called Content Aware Scaling. As the license is non-exclusive, other popular computer graphics applications (e. g. GIMP, digiKam, and ImageMagick) as well as some stand-alone programs (e. g. iResizer) also have implementations of this technique, some of which are released as free and open source software. There also exists an implementation for webpages.

Improvements and extensions

• Better energy function and application to video by introducing 2D (time+1D) seams.
  • Faster implementation on GPU.
  • Application of this forward energy function to static images.
• Multi-operator: Combine with cropping and scaling.
• Much faster removal of multiple seams.
• Removing seams through neural deformation fields to extend to continuous domains like 3D scenes.

A 2010 review of eight image retargeting methods found that seam carving produced output that was ranked among the worst of the tested algorithms. It was, however, a part of one of the highest-ranking algorithms: the multi-operator extension mentioned above (combined with cropping and scaling).{{cite journal

References

References

1. (July 2007). "ACM SIGGRAPH 2007 papers".
2. Vidya Setlur. (December 2005). "Proceedings of the 4th international conference on Mobile and ubiquitous multimedia - MUM '05".
3. (2016). "Parallel Seam Carving".
4. (November 2009). "Fast JND-Based Video Carving With GPU Acceleration for Real-Time Video Retargeting". IEEE Transactions on Circuits and Systems for Video Technology.
5. [http://www.faculty.idc.ac.il/arik/site/seam-video.asp Improved Seam Carving for Video Retargeting.] Michael Rubinstein, Ariel Shamir, Shai Avidan. SIGGRAPH 2008.
6. [https://archive.today/20130201110145/http://www.reuters.com/article/pressRelease/idUS175954+16-Dec-2008+BW20081216 Mitsubishi Electric press release], Business Wire, December 16, 2008.
7. [http://www.photoshopsupport.com/photoshop-cs4/what-is-new-in-photoshop-cs4.html Adobe Photoshop CS4 new feature list].
8. [http://www.iresizer.com iResizer Content aware image resizing software by Teorex]
9. [http://liquidrescale.wikidot.com/en:examples Liquid Rescale], seam carving plug-in for [[GIMP]]
10. [http://www.digikam.org/node/439 Announcement of inclusion] in [[digiKam]]
11. [http://www.imagemagick.org/Usage/resize/#liquid-rescale Seam carving capability included] in [[ImageMagick]]
12. (2025-08-11). "trekhleb/js-image-carver". trekhleb.
13. (2025-06-22). "VoiceNGO/img-responsive". VoiceNGO.
14. "Improved seam carving with forward energy".
15. [https://faculty.runi.ac.il/arik/site/multi-op.asp Multi-operator Media Retargeting.] Michael Rubinstein, Ariel Shamir, Shai Avidan. SIGGRAPH 2009.
16. [http://vmcl.xjtu.edu.cn/Real-Time%20Content-Aware%20Image%20Resizing.files/real_time_content_aware_image_resizing.pdf Real-time content-aware image resizing] Science in China Series F: Information Sciences, 2009 SCIENCE IN CHINA PRESS. {{webarchive. link. (July 7, 2011)
17. [https://eccv.ecva.net/virtual/2024/poster/1316 Retargeting Visual Data with Deformation Fields.] Tim Elsner, Julia Berger, Victor Czech, Lin Gao, Leif Kobbelt. ECCV 2025.