Seam carving
Seam carving, also known as content-aware image resizing or liquid rescaling, is an algorithm that enables the resizing of images by selectively removing or inserting one-pixel-wide connected paths called seams, which follow low-energy regions to minimize distortion of important visual content.[1] Developed by Shai Avidan of Mitsubishi Electric Research Laboratories and Ariel Shamir of the Interdisciplinary Center in Israel, the technique was first introduced in a 2007 paper presented at the ACM SIGGRAPH conference.[1] It relies on an energy function, typically based on image gradients measuring pixel intensity changes, to identify seams via dynamic programming, allowing for efficient computation with linear time complexity relative to image size.[1] The algorithm supports both image reduction, by repeatedly carving out seams, and expansion, by inserting duplicated seams, making it suitable for adapting images to various display aspect ratios without uniform scaling that could warp key features like faces or objects.[1] Additional features include forward energy mapping to predict and reduce artifacts from sequential seam removals, as well as integration of user-provided saliency maps or scribbles to guide the process toward specific regions of interest.[2] Beyond basic resizing, seam carving facilitates applications such as object removal by targeting seams around specified areas and content enhancement through selective seam insertion.[1] Since its inception, seam carving has been extended to video retargeting by incorporating temporal coherence and graph-based optimization to handle frame-to-frame consistency, enabling real-time adaptation for mobile devices and web media.[2] Its impact lies in addressing the challenges of diverse screen sizes in digital media, with implementations influencing tools for image processing and influencing subsequent research in content-aware scaling techniques.[2]Introduction and History
Overview
Seam carving is an algorithm for content-aware image resizing that alters the dimensions of an image by systematically removing or inserting low-energy pixel paths, known as seams, to maintain the salience of important visual elements such as edges, textures, and structures.[1] This approach allows for flexible adjustments in image size and aspect ratio while prioritizing content preservation over uniform scaling.[1] The primary objective of seam carving is to enable non-uniform resizing that adapts images to diverse display formats, such as varying screen sizes or orientations, without introducing significant visual distortions that plague conventional methods like proportional scaling or rigid cropping.[1] Unlike scaling, which can stretch or compress the entire image and blur details, or cropping, which discards portions indiscriminately, seam carving targets less critical areas for modification.[1] For instance, in resizing a landscape photograph to fit a mobile device screen, the algorithm might narrow expansive sky regions while leaving the foreground subject, like a mountain or tree, intact.[1] Seam carving was introduced in 2007 by Shai Avidan of Mitsubishi Electric Research Laboratories (MERL) and Ariel Shamir of The Interdisciplinary Center, Herzliya, marking a significant advancement in image retargeting techniques.[1] At its core, the method relies on identifying seams—monotonic paths of pixels—and energy maps that quantify visual importance, though these elements are explored in greater detail elsewhere.[1]Development and Key Publications
The development of seam carving traces its origins to earlier efforts in content-aware image manipulation. In 2005, Vidya Setlur and colleagues published "Automatic Image Retargeting," which introduced a technique for resizing images by identifying and preserving regions of importance using saliency maps derived from visual attention models, though it relied on warping and cropping rather than seam removal.[3] The seminal contribution came in 2007 with the SIGGRAPH paper "Seam Carving for Content-Aware Image Resizing" by Shai Avidan of Mitsubishi Electric Research Laboratories (MERL) and Ariel Shamir of the Interdisciplinary Center Herzliya. This work formalized the seam carving algorithm, defining seams as optimal paths of low-energy pixels and using dynamic programming for efficient detection and removal to achieve content-preserving resizing for both reduction and expansion. Developed at MERL, the algorithm was released under a non-exclusive license to facilitate broad adoption.[1] Key extensions followed rapidly. In 2008, the algorithm received patent protection through U.S. Patent Application Publication No. 2008/0219587, titled "Method for Retargeting Images," assigned to MERL and covering the core seam insertion and deletion processes.[4] That same year, Adobe Systems integrated a version of the technology into Photoshop CS4 as "Content-Aware Scaling," marking its entry into commercial software and enabling users to resize images while minimizing distortion to salient features.[5] Subsequent publications built on these foundations. Avidan and Shamir's 2009 article "Seam Carving for Media Retargeting" in Communications of the ACM extended the method to video, incorporating temporal coherence to remove 2D seam manifolds across frames while preserving motion and structure.[6] In 2009, Shamir, along with Michael Rubinstein and Avidan, proposed a multi-operator framework in "Multi-Operator Media Retargeting," combining seam carving with cropping and uniform scaling, guided by image similarity metrics, to optimize retargeting outcomes and reduce artifacts in extreme resizings.[7] The open encouragement of implementations, including reference code provided by the authors on their project page, spurred rapid dissemination. By 2010, seam carving had seen widespread academic exploration in over 100 citations and commercial integration beyond Adobe, influencing tools in image processing libraries and mobile applications.[8]Core Concepts
Seams
In seam carving, a seam is defined as a connected path of pixels that traverses an image from one edge to the opposite edge, specifically either vertically from top to bottom or horizontally from left to right.[1] This path is monotonic, meaning it moves consistently in a single direction without reversing course, ensuring a smooth progression across the image dimensions.[1] Key properties of a seam include including exactly one pixel from each row for a vertical seam or each column for a horizontal seam, which maintains the structural integrity of the image grid during manipulation.[1] The path is 8-connected, with connectivity restricted such that each step moves to one of the three adjacent pixels in the next row (columns j-1, j, or j+1 for vertical seams) or next column (rows i-1, i, or i+1 for horizontal seams), while adhering to the monotonic constraint, which promotes smoothness and prevents abrupt jumps.[1] For instance, a vertical seam might snake through a uniform background region, such as a clear sky in a landscape photo, selecting pixels that minimally disrupt the overall visual content.[1] Seams play a central role in content-aware resizing by representing paths of minimal perceptual change; removing a seam shrinks the image by eliminating these pixels, while duplicating or inserting seams along similar paths expands it, thereby preserving important features like faces or objects.[1] Seam selection is guided by an energy function that quantifies pixel importance, though the structural definition of the seam itself remains independent of specific energy computations.[1]Energy Functions
In seam carving, the energy function assigns a numerical value to each pixel that quantifies its visual importance, or saliency, within the image. This measure typically assigns high energy to pixels in areas with strong edges, textures, or structural details, while assigning low energy to uniform or smooth regions, thereby guiding the algorithm to prioritize the preservation of salient content during resizing.[1] The foundational energy function, as introduced in the original seam carving algorithm, is based on the magnitude of the image gradient and is defined ase(I) = \left| \frac{\partial I}{\partial x} \right| + \left| \frac{\partial I}{\partial y} \right|,
where I represents the input image, and \frac{\partial I}{\partial x} and \frac{\partial I}{\partial y} denote the horizontal and vertical gradients, respectively. These gradients are commonly computed using discrete convolution operators, such as the Sobel kernel, to approximate the partial derivatives and emphasize edge information.[1] Variations of the energy function extend this basic gradient-based approach to better capture perceptual importance. For instance, the L2-norm variant replaces the L1 summation with the Euclidean norm of the gradients, e(I) = \sqrt{ \left( \frac{\partial I}{\partial x} \right)^2 + \left( \frac{\partial I}{\partial y} \right)^2 }, while more advanced functions incorporate additional cues like entropy over local windows or visual saliency maps derived from attention models. These alternatives aim to enhance seam selection by accounting for higher-level features beyond simple edges.[1] The resulting energy map is a two-dimensional array matching the dimensions of the input image, where each entry stores the computed energy value for the corresponding pixel. This map directs potential seams toward paths of minimal cumulative energy, ensuring that removed or inserted seams traverse low-importance regions to minimize visual disruption.[1] For example, in an image featuring a person's face against a uniform sky, the energy map would exhibit high values around the facial contours and eyes due to gradient discontinuities, while the sky background would show near-zero energy, allowing seams to preferentially route through the sky without altering the face.[1]
Algorithm Details
Computing the Energy Map
The computation of the energy map serves as a critical preprocessing step in seam carving, where an input image is analyzed to assign an energy value to each pixel based on its visual importance, typically derived from gradient magnitudes that highlight edges and structural features. For an RGB color image, one approach is to convert it to grayscale using a standard luminance formula, such as Y = 0.299R + 0.587[G](/page/G) + 0.114[B](/page/R), to simplify processing and focus on intensity changes. However, many implementations compute gradients separately for each RGB channel and sum the absolute magnitudes across channels: e(I) = \sum_{c \in \{R,[G](/page/G),B\}} (|\partial_x I_c| + |\partial_y I_c|), providing a color-aware measure without grayscale conversion.[9] Once prepared, gradient filters are applied via convolution to estimate the partial derivatives \partial_x I and \partial_y I for each pixel, with the energy e(I) then calculated as the sum of their absolute magnitudes: e(I) = |\partial_x I| + |\partial_y I|.[1] To compute these gradients accurately, Sobel operators are widely employed due to their effectiveness in edge detection while providing smoothing to reduce noise sensitivity. The horizontal gradient kernel \nabla_x is defined as the 3x3 matrix: \begin{bmatrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{bmatrix} and the vertical gradient kernel \nabla_y is its transpose: \begin{bmatrix} -1 & -2 & -1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{bmatrix}. Convolving the image with these kernels yields the gradient components, whose absolute values are summed to form the energy map, emphasizing pixels near high-contrast boundaries as having higher energy.[10] Boundary pixels pose edge cases in gradient computation, as neighboring values outside the image are unavailable; different implementations handle this differently. For example, some pad the image with a 1-pixel border of zero values (black pixels) to assume black outside, which can introduce high-energy artifacts at non-black borders.[11] Others use periodic boundary conditions, treating the image as toroidal to avoid such artifacts. Energy values in the resulting map may be normalized to the [0,1] range by dividing by the maximum energy found for visualization purposes, though this is not required for the algorithm.[1] The entire energy map computation achieves linear time complexity of O(N), where N is the total number of pixels, since the convolution operation processes each pixel in constant time using the fixed-size 3x3 kernels. This map then represents the image as a landscape where low-energy seams correspond to paths of minimal visual disruption.[1]Seam Detection via Dynamic Programming
Seam detection in seam carving involves identifying an optimal path of pixels, known as a seam, that minimizes the total energy across the image while adhering to connectivity constraints. For a vertical seam in an image I of size n \times m, the seam s is defined as a connected path of pixels s_k = (x_k, y_k) for k = 1 to n, where each pixel is 8-connected to the next, satisfying |x_k - x_{k-1}| \leq 1 and y_k = y_{k-1} + 1. The objective is to find the seam s^* that minimizes the sum of the energy function values along the path, E(s) = \sum_{k=1}^n e(I(s_k)), where e is the pixel energy derived from the image's gradient magnitude. This formulation ensures the seam removes or inserts pixels in low-importance regions, preserving salient content.[1] The standard approach to solving this optimization problem employs dynamic programming, which efficiently computes the minimum-energy path by building a cumulative energy table. Let M denote the minimum energy of any path ending at pixel (i, j). The table is initialized for the first row as M{{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}} = e(I(1, j)) for all columns j. For subsequent rows i = 2 to n, the recurrence relation is: M = e(I(i, j)) + \min \begin{cases} M[i-1][j-1] & \text{(if } j > 1\text{)} \\ M[i-1] \\ M[i-1][j+1] & \text{(if } j < m\text{)} \end{cases} This relation considers the three possible 8-connected predecessors from the previous row, selecting the one that yields the lowest cumulative energy. The table is filled row by row from top to bottom, ensuring each entry incorporates the optimal subpath to that pixel.[1] Once the dynamic programming table is complete, the optimal seam is recovered via backtracking. Identify the minimum value in the last row, \min_j M, which corresponds to the ending pixel of the lowest-energy seam. Then, trace backwards to the top row by following the predecessor that achieves the minimum in the recurrence at each step, reconstructing the seam path in reverse. This process yields the exact coordinates of the seam pixels.[1] The dynamic programming method operates in O(nm) time and space complexity, linear in the total number of pixels N = nm, making it highly efficient for large images without requiring excessive memory or computation. While alternatives such as Dijkstra's shortest path algorithm can model the problem as a graph where pixels are nodes and edges represent connectivity, dynamic programming is preferred due to its exploitation of the seam's row-ordered structure, avoiding the overhead of priority queues.[1]Resizing Operations
Seam carving achieves image resizing by iteratively applying seam detection and modification to adjust the dimensions while preserving important content. The process begins by defining the target width and height, which determines the number of seams to remove or insert. For shrinking, the algorithm repeatedly identifies and removes the lowest-energy seam until the desired size is reached, updating the image and recomputing the energy map after each removal to account for changes in pixel neighborhoods. This ensures that subsequent seams avoid regions already altered, maintaining structural integrity.[1] In the shrinking operation, vertical seams reduce the width by one pixel per row, while horizontal seams reduce the height by one pixel per column. To achieve balanced resizing, especially when altering the aspect ratio, the algorithm alternates between vertical and horizontal seam removals or uses a combined approach via a transport map that optimizes the sequence of operations across both directions. For instance, to resize an image from dimensions m \times n to m' \times n', exactly m - m' vertical seams and n - n' horizontal seams are removed in an interleaved manner. Each removal shifts the coordinates of affected pixels, requiring an update to the image representation.[1] The enlarging process reverses this by inserting seams rather than removing them. It identifies low-energy paths—typically the same seams that would be removed for shrinking—and duplicates them, interpolating pixel values along the seam by averaging with neighboring pixels to blend seamlessly and avoid visible artifacts. For expansion by k pixels, k such seams are inserted in the reverse order of a hypothetical removal sequence, ensuring content-aware growth. Gradient-based methods may further refine interpolation for seam pixels to match surrounding intensities. This mode supports moderate enlargements, with larger changes (exceeding 50% of original size) recommended in multiple passes to minimize distortion.[1] The full resizing workflow can be outlined in pseudocode as follows, assuming vertical shrinking for simplicity (adaptations for horizontal or insertion follow analogous steps):For insertion, replacefunction resize_shrink(image, target_width): current_image = image # Assume dimensions m x n, target m' < n num_seams_to_remove = n - target_width for i in 1 to num_seams_to_remove: energy_map = compute_energy(current_image) # O(m*n) time seam = find_min_energy_seam(energy_map) # Dynamic programming, O(m*n) current_image = remove_seam(current_image, seam) # Update image and coordinates return current_imagefunction resize_shrink(image, target_width): current_image = image # Assume dimensions m x n, target m' < n num_seams_to_remove = n - target_width for i in 1 to num_seams_to_remove: energy_map = compute_energy(current_image) # O(m*n) time seam = find_min_energy_seam(energy_map) # Dynamic programming, O(m*n) current_image = remove_seam(current_image, seam) # Update image and coordinates return current_image
remove_seam with insert_seam, which duplicates and interpolates along the seam path. The seam detection step integrates dynamic programming as described in prior sections.[1]
Performance-wise, each iteration requires time linear in the number of pixels N = m \times n, leading to a total complexity of O(N \cdot K) for removing or inserting K seams, where K is typically much smaller than N. On standard hardware, resizing a 400×500 image to 100×100 takes approximately 2.2 seconds. This efficiency stems from the localized nature of updates, avoiding global recomputation.[1]
Challenges and Mitigations
Distortion and Artifacts
Seam carving can introduce visual distortions, particularly in textured regions such as fur or grass, where repeated removal of low-energy seams leads to warping and unnatural deformations. These artifacts arise because the algorithm prioritizes energy minimization, often carving through repetitive patterns that lack distinct high-energy features, resulting in jagged edges or irregular pixel shifts that disrupt the texture's coherence. For instance, in images with dense foliage or animal fur, multiple iterations exacerbate the issue, creating visible discontinuities that degrade the overall visual quality.[12] Another common problem is content displacement, where salient objects shift positions unnaturally across resizing iterations, altering the image's compositional balance. This occurs as seams accumulate around important elements, forcing peripheral content to compress or expand disproportionately, which can make foreground subjects appear to "slide" or warp relative to the background. In busy backgrounds with complex patterns, such displacements become more pronounced, leading to failure cases where the algorithm struggles to isolate and preserve key structures amid competing energy signals. Similarly, faces often suffer deformation due to their curved, high-energy contours; seams may squeeze or stretch facial features, producing unnatural distortions that are particularly noticeable in portraits.[13][12] Over-removal poses additional challenges in uniform areas like skies or plain backgrounds, where low variance across the image prompts the algorithm to carve excessively, narrowing these regions and potentially eliminating them entirely. This is especially problematic in images with global low variance, where the lack of distinct seams causes the method to fail outright, as no "less important" areas exist for prioritization. Quantitative evaluations highlight these issues; for example, bidirectional similarity (BDS), a patch-based metric assessing structural preservation, often reveals higher distortion in seam-carved images compared to simple scaling, with BDS scores indicating poorer patch matching in textured or uniform regions. In comparative studies, seam carving exhibits elevated affine distortion metrics, such as global affine changes averaging 0.33 versus lower values for scaling, underscoring its tendency for non-uniform warping.[14][15]User Guidance and Enhancements
To mitigate distortions in seam carving, user guidance techniques allow for targeted protection of salient regions by incorporating human input or automated detection to modify the energy map. For instance, users can manually mark important areas, such as objects or faces, assigning them high energy values to prevent seam insertion or removal in those regions.[16] Automated salient object detection, exemplified by face detection using Haar cascades, identifies key features and boosts their energy in the map, ensuring seams avoid disrupting them.[16] Protection maps further enhance this by assigning infinite or very high energy to predefined important areas, derived from saliency detection methods like graph cuts, which segment the image into foreground and background based on visual cues to prioritize content preservation.[16] These maps integrate with the energy function to guide seam paths away from critical structures, reducing artifacts in resized outputs. A key algorithmic enhancement is forward energy, which addresses cumulative distortions from sequential seam removals by recomputing the energy map after each operation to account for the impact on future seams. Unlike backward energy, which uses the original map, forward energy measures the change in energy introduced by a seam's removal, selecting paths that minimize overall disruption. The forward energy cost for a pixel at position (i,j) incorporates directional differences post-removal: \begin{align*} C_L(i,j) &= |I(i,j+1) - I(i,j-1)| + |I(i-1,j) - I(i,j-1)|, \\ C_U(i,j) &= |I(i,j+1) - I(i,j-1)|, \\ C_R(i,j) &= |I(i,j+1) - I(i,j-1)| + |I(i-1,j) - I(i,j+1)|, \end{align*} where the minimum is taken over neighboring transitions to update the dynamic programming cost matrix M(i,j) = P(i,j) + \min\{M(i-1,j-1) + C_L(i,j), M(i-1,j) + C_U(i,j), M(i-1,j+1) + C_R(i,j)\}, with P(i,j) as the original pixel energy.[16] This approach integrates the effects of remaining seams, leading to smoother resizes. Additional mitigations include optimal seam ordering, such as removing all horizontal seams before vertical ones to preserve aspect ratios, and multi-scale carving, which processes the image at multiple resolutions for large-scale changes to avoid over-distortion in uniform areas.[17] Recent advances as of 2025 incorporate deep learning and large language models (LLMs) for enhanced saliency detection and dynamic energy adjustment, as well as hybrid methods combining seam carving with image stitching or Bezier curve optimization to further reduce deformations in complex scenes.[18][19][20] Evaluations on benchmarks like the RetargetMe dataset demonstrate that these enhancements, particularly forward energy and protection maps, improve Bidirectional Similarity (BDS) scores compared to basic seam carving, indicating reduced structural distortion while maintaining visual fidelity.[12]Implementations and Tools
Software Applications
Seam carving has been integrated into several commercial image editing tools, enabling users to perform content-aware resizing through intuitive interfaces. Adobe Photoshop, starting with version CS4 released in 2008, introduced the Content-Aware Scale feature, which applies seam carving principles to adjust image dimensions while preserving important visual elements such as faces or objects. This tool allows users to protect specific areas, like skin tones, during scaling operations, making it suitable for professional workflows in photography and graphic design. In open-source software, the GIMP image editor supports seam carving via the Liquid Rescale plugin, which implements the algorithm for non-uniform resizing and object removal by carving seams of low-energy pixels.[21] As of GIMP 3.0 (released March 2025), seam carving is also available through the G'MIC plugin's Seamcarve filter, with ongoing compatibility updates for the Liquid Rescale plugin.[22] This plugin provides options to mark protected regions and adjust rigidity parameters, facilitating tasks like aspect ratio changes without distortion.[23] Additionally, ImageMagick, a command-line tool for image manipulation, includes the -liquid-rescale option to apply seam carving directly in batch processing, allowing users to specify width, height, and delta parameters for precise control.[24] Standalone applications like Seam Carving GUI, developed in the late 2000s, offer a simple graphical interface for Windows users to load, resize, and save images using the algorithm, emphasizing ease of use for non-experts.[25] Mobile and web-based tools have also adopted seam carving for accessible editing. The LiquidScale iOS app, released around 2010, enables on-device content-aware resizing with a touch-friendly interface, allowing users to transform image aspect ratios quickly without cropping key content.[26] For web applications, the js-image-carver library provides a JavaScript-based implementation that runs in browsers, supporting real-time previews of seam carving effects; its GitHub repository was actively updated as recently as 2023.[27] In AI image generation tools, the ComfyUI-seam-carving node (released around 2023) integrates seam carving into ComfyUI workflows for resizing Stable Diffusion-generated images.[28] Early adoption of seam carving in software occurred between 2008 and 2010, coinciding with the algorithm's publication and initial implementations in tools like Photoshop and GIMP plugins, driven by the need for intelligent retargeting in digital media. Today, it remains a staple in photo editors for applications such as adapting images to different screen formats or enhancing compositions. A typical workflow in Photoshop involves selecting the image layer, enabling Content-Aware Scale from the Edit menu, and dragging handles to adjust dimensions while optionally protecting subjects via the Protect tool, resulting in resized images that maintain structural integrity without traditional cropping or stretching.Libraries and Frameworks
Seam carving has been implemented in various programming languages through open-source libraries, enabling developers to integrate content-aware resizing into applications. Early implementations often drew from the foundational 2007 paper by Avidan and Shamir at Mitsubishi Electric Research Laboratories (MERL), which described the algorithm but did not release official code; subsequent C++ libraries, such as those on GitHub, replicated the dynamic programming approach for seam detection and removal using standard image processing primitives.[29][30] In Python, scikit-image provided aseam_carve function in the transform module starting around version 0.12 in 2016, allowing users to perform both reduction and expansion by specifying target dimensions and an energy function, though it was removed in version 0.15 (2019) due to patent concerns over the algorithm.[31] More recent Python libraries, like li-plus/seam-carving (released in 2020), offer optimized implementations with NumPy integration for faster computation on large images, supporting forward energy maps to reduce distortions.[32]
Language-specific libraries have emerged for web and performance-critical environments. For JavaScript, the js-image-carver library by Trekhleb (2021) implements seam carving in TypeScript, suitable for browser-based image manipulation, with functions to carve seams vertically or horizontally and remove objects by marking low-energy regions.[27] In Rust, projects like lovasoa/seamcarving (2019) and Yanglin Zhao's WebAssembly port (2021) emphasize speed and safety, using the image crate for I/O and providing APIs such as resize(image, new_width, new_height) that leverage Rust's parallelism for dynamic programming steps.[33][34]
Frameworks like OpenCV facilitate seam carving through custom extensions in its contrib modules, where developers implement the algorithm atop OpenCV's core image handling and gradient computation functions, as seen in tutorials combining it with Python bindings for real-time resizing.[31] GPU acceleration via CUDA has been prototyped since the early 2010s, with implementations achieving up to 10x speedups over CPU versions for large images (e.g., 1000x1000 pixels) by parallelizing energy map computation and seam backtracking on NVIDIA hardware.[35][36] These libraries typically expose simple APIs, such as seam_carve(image, target_width, energy_map='gradient'), abstracting the core dynamic programming while allowing customization of energy functions for specific use cases.[27]