Jump to content

Seam carving: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Yobot (talk | contribs)
Bots
4,733,870 edits
m clean up, References after punctuation per WP:REFPUNC and WP:CITEFOOT using AWB (8792)
m →Improvements and extensions: new link for Multi-operator, found after original link redirect
 
(72 intermediate revisions by 50 users not shown)
Line 1: Line 1:
{{Short description|Rescaling algorithm intended to preserve important elements}}
[[File:Broadway tower edit.jpg|274px|thumb|Original image]]
[[File:Broadway tower edit scale.png|186px|thumb|Same image reduced in width using scaling...]]
[[File:Broadway tower edit.jpg|274px|thumb|Original image to be made narrower]]
[[File:Broadway tower edit cropped.png|186px|thumb|...cropping...]]
[[File:Broadway tower edit scale.png|186px|thumb|Scaling is undesirable because the castle is distorted.]]
[[File:Broadway tower edit Seam Carving.png|186px|thumb|...and ''seam carving'']]
[[File:Broadway tower edit cropped.png|186px|thumb|Cropping is undesirable because part of the castle is removed.]]
[[File:Broadway tower edit Seam Carving.png|186px|thumb|Seam carving]]
'''Seam carving''' (also known as '''image retargeting''', '''content-aware image resizing''', '''content-aware scaling''', '''liquid resizing''', or '''liquid rescaling'''), is an algorithm for [[image scaling|image resizing]], developed by [[Shai Avidan]], of [[Mitsubishi Electric Research Laboratories]] (MERL), and [[Ariel Shamir]], of the [[Interdisciplinary Center]] and MERL. It functions by establishing a number of ''seams'' (paths of least importance) in an image and automatically removes seams to reduce image size or inserts seams to extend it. Seam carving also allows manually defining areas in which pixels may not be modified, and features the ability to remove whole objects from photographs. The purpose of the algorithm is to display images without distortion on various media (cell phones, PDAs) using document standards, like HTML, that already support dynamic changes in page layout and text, but not images.<ref name=ACM1276390>[http://portal.acm.org/citation.cfm?id=1276390 Seam Carving for Content-Aware Image Resizing.] Shai Avidan, Ariel Shamir, 2007.</ref>
'''Seam carving''' (or '''liquid rescaling''') is an algorithm for content-aware [[image scaling|image resizing]], developed by [[Shai Avidan]], of [[Mitsubishi Electric Research Laboratories]] (MERL), and [[Ariel Shamir]], of the [[Interdisciplinary Center]] and MERL. It functions by establishing a number of ''seams'' (paths of least importance) in an image and automatically removes seams to reduce image size or inserts seams to extend it. Seam carving also allows manually defining areas in which pixels may not be modified, and features the ability to remove whole objects from photographs.

The purpose of the algorithm is image retargeting, which is the problem of displaying images without distortion on media of various sizes (cell phones, projection screens) using document standards, like HTML, that already support dynamic changes in page layout and text but not images.<ref name=ACM1276390>{{cite book |last1=Avidan |first1=Shai |last2=Shamir |first2=Ariel |title=ACM SIGGRAPH 2007 papers |chapter=Seam carving for content-aware image resizing |date=July 2007 |page=10 |doi=10.1145/1275808.1276390 |isbn=978-1-4503-7836-9 |language=en |doi-access=free}}</ref>

Image Retargeting was invented by Vidya Setlur, Saeko Takage, Ramesh Raskar, Michael Gleicher and Bruce Gooch in 2005.<ref>{{cite book |author=Vidya Setlur |author2=Saeko Takage |author3=Ramesh Raskar |author4=Michael Gleicher |author5=Bruce Gooch |title=Proceedings of the 4th international conference on Mobile and ubiquitous multimedia - MUM '05 |chapter=Automatic image retargeting |date=December 2005 |pages=59–68 |doi=10.1145/1149488.1149499 |isbn=0-473-10658-2 |language=EN |doi-access=free}}</ref> The work by Setlur et al. won the 10-year impact award in 2015{{Where|date=May 2022}}.


== Seams ==
== 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.<ref name=ACM1276390/> 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.
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.<ref name=ACM1276390/> 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 ==
=== Computing Seams ===
Computing the seam consists of finding the path of minimum cost from one end of the image to another.
This can be done via [[Dijkstra's algorithm]], dynamic programming, or [[Cut (graph theory)|graph cuts]].<ref name=ACM1276390/>


The below example describes the process of seam carving:
==== Dynamic Programming ====
{| class=wikitable style="max-width: 100%; overflow-y: scroll"
[[Dynamic programming]] is a programming method that stores the results of sub-calculations in order to simplify calculating a more complex result. Dynamic programming is used in seam carving for computing seams.
! Step !! Image
|-
| 1) Start with an image.
| [[File:BroadwayTowerSeamCarvingA.png|frame|none|alt=Starting image]]
|-
| 2) Calculate the weight/density/energy of each pixel. This can be done by various algorithms: gradient magnitude, entropy, visual saliency, eye-gaze movement.<ref name=ACM1276390/> Here we use gradient magnitude.
| [[File:BroadwayTowerSeamCarvingB.png|frame|none|alt=gradient magnitude energy]]
|-
| 3) From the energy, make a list of seams. Seams are ranked by energy, with low energy seams being of least importance to the content of the image. Seams can be calculated via the dynamic programming approach below.
| [[File:BroadwayTowerSeamCarvingC.png|frame|none|alt=seams with energy]]
|-
| 4) Remove low-energy seams as needed.
| [[File:BroadwayTowerSeamCarvingF.png|frame|none|alt=reduced energy image]]
|-
| 5) Final image.
| [[File:BroadwayTowerSeamCarvingE.png|frame|none|alt=final image]]
|}


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.<ref name=ACM1276390/>
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.


=== Computing seams ===
This is better described by this image:
Computing a seam consists of finding a path of minimum energy cost from one end of the image to another.
[[File:DynamicProgrammingLeastEnergyPathA.png|frame|left|alt=DynamicProgrammingLeastEnergyPathA|Each square represents a pixel, with the top-left value in red representing the energy value of that said pixel. The value in black represents the cumulative sum of energies leading up to and including that pixel.]]
This can be done via [[Dijkstra's algorithm]], dynamic programming, [[greedy algorithm]] or [[Cut (graph theory)|graph cuts]] among others.<ref name=ACM1276390/>
{{clear left}}
The first row has no rows above it, so the sum (black) is just the energy value of the current pixel (red).


==== Dynamic programming ====
The second row, if we look at the second pixel for example, we see its energy value is 2 (red). If we look above it, it has a choice of either 1, 4, or 3 (black). Since 1 is the minimum number of the three values, we ignore the other two and set the sum of the pixel to its energy value which is 2 (red) plus 1 (black).
[[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.<ref name=ACM1276390/> 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.
After the above operation is carried out for every pixel in the second row, we go to the third row:
<gallery mode=packed>
[[File:DynamicProgrammingLeastEnergyPathB.png|frame|left|alt=DynamicProgrammingLeastEnergyPathB]]
File:DynamicProgrammingLeastEnergyPathA.svg|The top row has nothing above it, so the energies are the same as the source image.
{{clear left}}
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.
</gallery>


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.<ref name=ACM1276390/>
We repeat the process in row two in row three to end up with the final cumultive sums for the seams/paths. The lowest value or values are the seams with the lowest energy, which would be in this example the seams with '5' in the last row.


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.<ref>{{cite web |last1=Bist |last2=Palakkode |date=2016 |title=Parallel Seam Carving |url=http://www.andrew.cmu.edu/user/abist/results.html |website=www.andrew.cmu.edu}}</ref> Local seams can also be computed for smaller parts of the image in parallel for a good approximation.<ref name="jnd">{{cite journal |last1=Chen-Kuo Chiang |last2=Shu-Fan Wang |last3=Yi-Ling Chen |last4=Shang-Hong Lai |title=Fast JND-Based Video Carving With GPU Acceleration for Real-Time Video Retargeting |journal=IEEE Transactions on Circuits and Systems for Video Technology |date=November 2009 |volume=19 |issue=11 |pages=1588–1597 |doi=10.1109/TCSVT.2009.2031462|s2cid=15124131 }}</ref>
To trace the seam/path, work from the last row and follow the green arrows:
[[File:DynamicProgrammingLeastEnergyPathC.png|frame|left|alt=DynamicProgrammingLeastEnergyPathC]]
{{clear left}}

== Algorithm ==
1) We start with an image such as: [[File:BroadwayTowerSeamCarvingA.png|frame|none|alt=BroadwayTowerSeamCarvingA]]

2) We then calculate the weight/density/energy of each pixel.
This can be done by various algorithms: gradient magnitude, entropy, visual saliency, eye-gaze movement.<ref name=ACM1276390/>
Although gradient magnitude gives 'satisfactory results.'
[[File:BroadwayTowerSeamCarvingB.png|frame|none|alt=BroadwayTowerSeamCarvingB]]

3) After we have the energy of the image, we generate a list of seams. Seams are ranked by energy, with low energy seams being of least importance to the content of the image. We can choose to calculate seams via the dynamic programming approach.

Seams shown with the energy function:
[[File:BroadwayTowerSeamCarvingC.png|frame|none|alt=BroadwayTowerSeamCarvingC]]

Seams shown with the original image:
[[File:BroadwayTowerSeamCarvingD.png|frame|none|alt=BroadwayTowerSeamCarvingD]]

4) We then remove the seams from the image, reducing the size of the image as a result:
[[File:BroadwayTowerSeamCarvingE.png|frame|none|alt=BroadwayTowerSeamCarvingE]]

The recalculated energy function of the image would be:
[[File:BroadwayTowerSeamCarvingF.png|frame|none|alt=BroadwayTowerSeamCarvingF]]


== Issues ==
== Issues ==
# 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.
# 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.
# 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. If it does, prefer other seams instead.<ref name=SEAMVID>[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.</ref>
# 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.<ref name=SEAMVID>[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.</ref>


== Implementations ==
== Implementations ==
<imagemap>
[[Adobe Systems]] acquired a non-exclusive license to seam carving technology from MERL,<ref>[http://www.reuters.com/article/pressRelease/idUS175954+16-Dec-2008+BW20081216 Mitsubishi Electric press release], Business Wire, December 16, 2008.</ref> and implemented it as a feature in [[Photoshop]] CS4, where it is called Content Aware Scaling.<ref>[http://www.photoshopsupport.com/photoshop-cs4/what-is-new-in-photoshop-cs4.html Adobe Photoshop CS4 new feature list].</ref>
File:Broadway_tower_seam_carving_interactive.svg|thumb|250px|Interactive SVG demonstrating seam-carving using ImageMagick's liquid-rescale function. [http:/upwiki/wikipedia/commons/b/bf/Broadway_tower_seam_carving_interactive.svg 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).
As the license is non-exclusive, other popular computer graphics applications, among which are [[GIMP]], [[digiKam]], [[ImageMagick]], as well as some stand-alone programs, among which are iResizer,<ref>[http://www.iresizer.com iResizer Content aware image resizing software by Teorex]</ref> also have implementations of this technique, some of which are released as [[free and open source software]].<ref>[http://liquidrescale.wikidot.com/en:examples Liquid Rescale], seam carving plug-in for [[GIMP]]</ref><ref>[http://www.digikam.org/node/439 Announcement of inclusion] in [[digiKam]]</ref><ref>[http://www.imagemagick.org/Usage/resize/#liquid-rescale Seam carving capability included] in [[ImageMagick]]</ref>
default [http:/upwiki/wikipedia/commons/b/bf/Broadway_tower_seam_carving_interactive.svg]
</imagemap>
<imagemap>
File:Creation_of_Adam_seam_carving_interactive.svg|thumb|250px|Interactive SVG demonstrating seam-carving using ImageMagick's liquid-rescale function. [http:/upwiki/wikipedia/commons/5/53/Creation_of_Adam_seam_carving_interactive.svg In the SVG file], hover over the percentages as above. Note that the faces are affected less than their surroundings.
default [http:/upwiki/wikipedia/commons/5/53/Creation_of_Adam_seam_carving_interactive.svg]
</imagemap>
[[Adobe Systems]] acquired a non-exclusive license to seam carving technology from MERL,<ref>[https://archive.today/20130201110145/http://www.reuters.com/article/pressRelease/idUS175954+16-Dec-2008+BW20081216 Mitsubishi Electric press release], Business Wire, December 16, 2008.</ref> and implemented it as a feature in [[Photoshop]] CS4, where it is called Content Aware Scaling.<ref>[http://www.photoshopsupport.com/photoshop-cs4/what-is-new-in-photoshop-cs4.html Adobe Photoshop CS4 new feature list].</ref>
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)<ref>[http://www.iresizer.com iResizer Content aware image resizing software by Teorex]</ref> also have implementations of this technique, some of which are released as [[free and open source software]].<ref>[http://liquidrescale.wikidot.com/en:examples Liquid Rescale], seam carving plug-in for [[GIMP]]</ref><ref>[http://www.digikam.org/node/439 Announcement of inclusion] in [[digiKam]]</ref><ref>[http://www.imagemagick.org/Usage/resize/#liquid-rescale Seam carving capability included] in [[ImageMagick]]</ref>


== Improvements and extensions ==
== Improvements and extensions ==
* Better energy function and application to video.<ref name=SEAMVID/>
* Better energy function and application to video by introducing 2D (time+1D) seams.<ref name=SEAMVID/>
** Faster implementation on GPU.<ref name=jnd/>
* Combine with cropping and scaling.<ref>[http://www.faculty.idc.ac.il/arik/site/multi-op.asp Multi-operator Media Retargeting.] Michael Rubinstein, Ariel Shamir, Shai Avidan. SIGGRAPH 2009.</ref>
** Application of this forward energy function to static images.<ref>{{Cite web|url=https://avikdas.com/2019/07/29/improved-seam-carving-with-forward-energy.html|title = Improved seam carving with forward energy}}</ref>
* Much faster removal of multiple seams<ref>[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]{{Dead link|date=January 2011}} Science in Chine Series F: Information Sciences, 2009 SCIENCE IN CHINA PRESS.</ref>
* Multi-operator: Combine with cropping and scaling.<ref>[https://faculty.runi.ac.il/arik/site/multi-op.asp Multi-operator Media Retargeting.] Michael Rubinstein, Ariel Shamir, Shai Avidan. SIGGRAPH 2009.</ref>
* On-demand, server-side seam carving <ref>[http://imageresizing.net/plugins/seamcarving On-demand, server-side seam carving] based on CAIR</ref>
* Much faster removal of multiple seams<ref>[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 |url=https://web.archive.org/web/20110707030836/http://vmcl.xjtu.edu.cn/Real-Time%20Content-Aware%20Image%20Resizing.files/real_time_content_aware_image_resizing.pdf |date=July 7, 2011 }}</ref>

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).<ref>{{cite journal
|title=A Comparative Study of Image Retargeting
|journal=ACM Transactions on Graphics
|volume=29
|number=5
|date=2010
|first1=Michael |last1=Rubinstein
|first2=Diego |last2=Gutierrez
|first3=Olga |last3=Sorkine
|first4=Ariel |last4=Shamir
|pages=1–10
|doi=10.1145/1882261.1866186
|url=http://people.csail.mit.edu/mrub/papers/retBenchmark.pdf
}} See also the [http://people.csail.mit.edu/mrub/retargetme/ RetargetMe benchmark].</ref>


== See also ==
== See also ==
Line 75: Line 98:


== References ==
== References ==
{{reflist}}
{{reflist|30em}}


== External links ==
== External links ==
* [https://www.aryan.app/seam-carving/ Interactive demo of seam carving]
* Seam Carving demonstration videos:
* Seam Carving demonstration videos:
** [http://www.youtube.com/watch?v=vIFCV2spKtg on YouTube]
** [https://www.youtube.com/watch?v=vIFCV2spKtg on YouTube]
** [http://www.faculty.idc.ac.il/ARIK/site/seam-carve.asp on Ariel Shamir's pages] on the Interdisciplinary Center web site (higher resolution)
** [http://www.faculty.idc.ac.il/ARIK/site/seam-carve.asp on Ariel Shamir's pages] on the Interdisciplinary Center web site (higher resolution)
* [http://www.imagemagick.org/Usage/resize/#liquid-rescale Explanation of seam carving (Liquid rescaling)] at the [[ImageMagick]] website
* [http://www.imagemagick.org/Usage/resize/#liquid-rescale Explanation of seam carving (Liquid rescaling)] at the [[ImageMagick]] website
* [http://www.statfe.com/projects/csc5280_project4/ Implementation tutorial of seam carving]
* [https://www.hitpaw.com/hitpaw-object-remover.html HitPaw Video Object Remover]


{{Mitsubishi Electric}}
{{Mitsubishi Electric}}
Line 87: Line 113:
[[Category:Image processing]]
[[Category:Image processing]]
[[Category:Mitsubishi Electric products, services and standards]]
[[Category:Mitsubishi Electric products, services and standards]]

[[de:Inhaltsabhängige Bildverzerrung]]
[[es:Video Retargeting]]
[[fr:Seam carving]]

Latest revision as of 12:00, 5 November 2024

Original image to be made narrower
Scaling is undesirable because the castle is distorted.
Cropping is undesirable because part of the castle is removed.
Seam carving

Seam carving (or liquid rescaling) is an algorithm for content-aware image resizing, developed by Shai Avidan, of Mitsubishi Electric Research Laboratories (MERL), and Ariel Shamir, of the Interdisciplinary Center and MERL. It functions by establishing a number of seams (paths of least importance) in an image and automatically removes seams to reduce image size or inserts seams to extend it. Seam carving also allows manually defining areas in which pixels may not be modified, and features the ability to remove whole objects from photographs.

The purpose of the algorithm is image retargeting, which is the problem of displaying images without distortion on media of various sizes (cell phones, projection screens) using document standards, like HTML, that already support dynamic changes in page layout and text but not images.[1]

Image Retargeting was invented by Vidya Setlur, Saeko Takage, Ramesh Raskar, Michael Gleicher and Bruce Gooch in 2005.[2] The work by Setlur et al. won the 10-year impact award in 2015[where?].

Seams

[edit]

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.[1] 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.

Process

[edit]

The below example describes the process of seam carving:

Step Image
1) Start with an image.
Starting image
2) Calculate the weight/density/energy of each pixel. This can be done by various algorithms: gradient magnitude, entropy, visual saliency, eye-gaze movement.[1] Here we use gradient magnitude.
gradient magnitude energy
3) From the energy, make a list of seams. Seams are ranked by energy, with low energy seams being of least importance to the content of the image. Seams can be calculated via the dynamic programming approach below.
seams with energy
4) Remove low-energy seams as needed.
reduced energy image
5) Final image.
final image

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.[1]

Computing seams

[edit]

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.[1]

Dynamic programming

[edit]

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.[1] 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.

  • The top row has nothing above it, so the energies are the same as the source image.
    The top row has nothing above it, so the energies are the same as the source image.
  • 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.
    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.
  • For the lowest energies we have at the end, work back up the minimals to recover the seam with minimal energy.
    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.[1]

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.[3] Local seams can also be computed for smaller parts of the image in parallel for a good approximation.[4]

Issues

[edit]
  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.[5]

Implementations

[edit]
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).
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.

Adobe Systems acquired a non-exclusive license to seam carving technology from MERL,[6] and implemented it as a feature in Photoshop CS4, where it is called Content Aware Scaling.[7] 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)[8] also have implementations of this technique, some of which are released as free and open source software.[9][10][11]

Improvements and extensions

[edit]
  • Better energy function and application to video by introducing 2D (time+1D) seams.[5]
    • Faster implementation on GPU.[4]
    • Application of this forward energy function to static images.[12]
  • Multi-operator: Combine with cropping and scaling.[13]
  • Much faster removal of multiple seams[14]

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).[15]

See also

[edit]

References

[edit]
  1. ^ a b c d e f g Avidan, Shai; Shamir, Ariel (July 2007). "Seam carving for content-aware image resizing". ACM SIGGRAPH 2007 papers. p. 10. doi:10.1145/1275808.1276390. ISBN 978-1-4503-7836-9.
  2. ^ Vidya Setlur; Saeko Takage; Ramesh Raskar; Michael Gleicher; Bruce Gooch (December 2005). "Automatic image retargeting". Proceedings of the 4th international conference on Mobile and ubiquitous multimedia - MUM '05. pp. 59–68. doi:10.1145/1149488.1149499. ISBN 0-473-10658-2.
  3. ^ Bist; Palakkode (2016). "Parallel Seam Carving". www.andrew.cmu.edu.
  4. ^ a b Chen-Kuo Chiang; Shu-Fan Wang; Yi-Ling Chen; Shang-Hong Lai (November 2009). "Fast JND-Based Video Carving With GPU Acceleration for Real-Time Video Retargeting". IEEE Transactions on Circuits and Systems for Video Technology. 19 (11): 1588–1597. doi:10.1109/TCSVT.2009.2031462. S2CID 15124131.
  5. ^ a b Improved Seam Carving for Video Retargeting. Michael Rubinstein, Ariel Shamir, Shai Avidan. SIGGRAPH 2008.
  6. ^ Mitsubishi Electric press release, Business Wire, December 16, 2008.
  7. ^ Adobe Photoshop CS4 new feature list.
  8. ^ iResizer Content aware image resizing software by Teorex
  9. ^ Liquid Rescale, seam carving plug-in for GIMP
  10. ^ Announcement of inclusion in digiKam
  11. ^ Seam carving capability included in ImageMagick
  12. ^ "Improved seam carving with forward energy".
  13. ^ Multi-operator Media Retargeting. Michael Rubinstein, Ariel Shamir, Shai Avidan. SIGGRAPH 2009.
  14. ^ Real-time content-aware image resizing Science in China Series F: Information Sciences, 2009 SCIENCE IN CHINA PRESS. Archived July 7, 2011, at the Wayback Machine
  15. ^ Rubinstein, Michael; Gutierrez, Diego; Sorkine, Olga; Shamir, Ariel (2010). "A Comparative Study of Image Retargeting" (PDF). ACM Transactions on Graphics. 29 (5): 1–10. doi:10.1145/1882261.1866186. See also the RetargetMe benchmark.
[edit]
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Seam_carving&oldid=1255532446"