The following problem appeared as an assignment in the ** Algorithm Course** (

The Seam Carving Problem

is a*Seam-carving*technique where the image is*content-aware image resizing**reduced*in*size*by*one pixel*of*height*(or*width*)*at a time*.

- A
in an image is a*vertical seam*of*path**pixels*connected from the*top*to the*bottom*with one pixel in each row.

- A
is a*horizontal seam*of pixels connected from the left to the right with one pixel in each column.**path**

- Although the underlying algorithm (the original paper from MERL) is simple and elegant, it was not discovered until 2007. Now, it is now a core feature in Adobe Photoshop and other computer graphics applications.

- Unlike standard content-agnostic resizing techniques (such as cropping and scaling),
the*seam carving**preserves*(*most interesting features**aspect ratio*,*set of objects present*, etc.) of the image.

- In this assignment, a data type needs to be created that
a*resizes**W*-by-*H*image using thetechnique.**seam-carving**

and**Finding**a**removing**involves three parts:**seam**

**Energy calculation***.*The first step is to calculate the

of a*energy*, which is a measure of its*pixel**importance*—the*higher*the*energy*, the*less**likely*that the*pixel*will be included as part of a*seam*(as you will see in the next step).In this assignment, we shall use the

, which is described below.*dual-gradient energy function*With the**Computing the energy of a pixel**., the*dual-gradient energy function*of**energy***pixel**(x,y*is given by the following:*)***Seam identification**.The next step is to find a

of*vertical seam*. (Finding a**minimum total energy***horizontal seam*is analogous.) This is similar to thein an**classic shortest path problem***edge-weighted digraph*, but there are three important differences:- The
*weights*are on the*vertices*instead of the edges. - The goal is to find the shortest path from
*any*of the*W*pixels in the top row to*any*of the*W*pixels in the bottom row. - The digraph is
*acyclic*, where there is a downward edge from pixel (*x*,*y*) to pixels (*x*− 1,*y*+ 1), (*x*,*y*+ 1), and (*x*+ 1,*y*+ 1). assuming that the coordinates are in the prescribed ranges. - Also, Seams cannot
*wrap*around the image (e.g., a vertical seam cannot cross from the leftmost column of the image to the rightmost column). - As described in the paper, the
can be found using*optimal seam*. The first step is to traverse the image from the second row to the last row and compute the cumulative minimum energy M for all possible connected seams for each*dynamic programming**pixel (i, j)*:

- The
*Seam removal.*The final step is

from the image all of the**remove***pixels*along the*vertical*or*horizontal**seam*.

The following image is the original ** 507×284 pixel **input image taken from the same assignment. The next few images and animations show the outputs of the

**Input Original Image**

Removing the Vertical Seams

After Removing 200 Vertical Seams

Removing the Vertical and the Horizontal Seams in alternating manner

After Removing 100 Vertical Seams and 100 Horizontal Seams

The following is the original * 1024×576* image of the

**Output image after removing 500 Vertical Seams**

The next image is the original dolphin * 239×200* image taken from the paper, along with the removed vertical seams with

** After removing 112 Vertical Seams**

The next image is the original ** 750×498 bird **image taken from the paper, along with the removed vertical seams with

** After Removing 297 Vertical Seams**

The next image is the original ** 450×299 sea **image taken from the paper, along with the removed vertical seams with

The next image is the original ** 628×413 cycle **image taken from the paper, along with the removed vertical seams with

**After Removing 99 Vertical Seams**

The next image is the original ** 697×706 Fuji **image again taken from the paper, along with the removed vertical seams with

** After Removing 282 Vertical Seams**

The same technique can be applied with mask to remove objects from an image. For example. consider the following image of the shoes taken from the same paper.

Let’s use a black mask to remove a shoe that we don’t want, as shown in the next figure.

Finally the * vertical seams* can be forced to go through the

**Output after removing the shoe with content-aware image resize algorithm**

© 2019 Data Science Central ® Powered by

Badges | Report an Issue | Privacy Policy | Terms of Service

**Most Popular Content on DSC**

To not miss this type of content in the future, subscribe to our newsletter.

**Technical**

- Free Books and Resources for DSC Members
- Learn Machine Learning Coding Basics in a weekend
- New Machine Learning Cheat Sheet | Old one
- Advanced Machine Learning with Basic Excel
- 12 Algorithms Every Data Scientist Should Know
- Hitchhiker's Guide to Data Science, Machine Learning, R, Python
- Visualizations: Comparing Tableau, SPSS, R, Excel, Matlab, JS, Pyth...
- How to Automatically Determine the Number of Clusters in your Data
- New Perspectives on Statistical Distributions and Deep Learning
- Fascinating New Results in the Theory of Randomness
- Long-range Correlations in Time Series: Modeling, Testing, Case Study
- Fast Combinatorial Feature Selection with New Definition of Predict...
- 10 types of regressions. Which one to use?
- 40 Techniques Used by Data Scientists
- 15 Deep Learning Tutorials
- R: a survival guide to data science with R

**Non Technical**

- Advanced Analytic Platforms - Incumbents Fall - Challengers Rise
- Difference between ML, Data Science, AI, Deep Learning, and Statistics
- How to Become a Data Scientist - On your own
- 16 analytic disciplines compared to data science
- Six categories of Data Scientists
- 21 data science systems used by Amazon to operate its business
- 24 Uses of Statistical Modeling
- 33 unusual problems that can be solved with data science
- 22 Differences Between Junior and Senior Data Scientists
- Why You Should be a Data Science Generalist - and How to Become One
- Becoming a Billionaire Data Scientist vs Struggling to Get a $100k Job
- Why do people with no experience want to become data scientists?

**Articles from top bloggers**

- Kirk Borne | Stephanie Glen | Vincent Granville
- Ajit Jaokar | Ronald van Loon | Bernard Marr
- Steve Miller | Bill Schmarzo | Bill Vorhies

**Other popular resources**

- Comprehensive Repository of Data Science and ML Resources
- Statistical Concepts Explained in Simple English
- Machine Learning Concepts Explained in One Picture
- 100 Data Science Interview Questions and Answers
- Cheat Sheets | Curated Articles | Search | Jobs | Courses
- Post a Blog | Forum Questions | Books | Salaries | News

**Archives**: 2008-2014 | 2015-2016 | 2017-2019 | Book 1 | Book 2 | More

**Most popular articles**

- Free Book and Resources for DSC Members
- New Perspectives on Statistical Distributions and Deep Learning
- Time series, Growth Modeling and Data Science Wizardy
- Statistical Concepts Explained in Simple English
- Machine Learning Concepts Explained in One Picture
- Comprehensive Repository of Data Science and ML Resources
- Advanced Machine Learning with Basic Excel
- Difference between ML, Data Science, AI, Deep Learning, and Statistics
- Selected Business Analytics, Data Science and ML articles
- How to Automatically Determine the Number of Clusters in your Data
- Fascinating New Results in the Theory of Randomness
- Hire a Data Scientist | Search DSC | Find a Job
- Post a Blog | Forum Questions

## You need to be a member of Data Science Central to add comments!

Join Data Science Central