Project 2: Image Resizing using Seam Carving Method
Jingwei Cao
Project Description
Seam carving is a image resizing method which is developed by Shai Avidan and Ariel Shamir. This efficient resizing method consider not only the geometric property of the image but the content of the image as well.
The method produces a resized image by searching for the seam which has the lowest user-specified 'image energy'. A seam is a 8-path connected path of pixels on a single image from top to bottom, or left to right.
Each row and column has exactly only one pixel which is the part of the seam. By removing or inserting the vertical or horizonal seam iteratively, we can compress or stretch the image in both dimensions.
What we need to is to implement a function which takes an image as an input and produce a resized image in one dimension or two dimensions as an output which is expected by the users.
Implementation Methods
The seam with lowest energy can be found by applying the dynamic programmming method. For my implementation, I choose the simple image gradient for simplicity.
Firstly, the function calculates the approximate image gradient for every corresponding pixel. In this way, the function transforms the original RGB image to 2-dimension matrix.
The value of each entry of the matrix corresponds to the energy of the corresponding pixel.Secondly we scan from the first row to the last row and calculate the minimum accumulated energy for each entry of the matrix and store the result in a newly-defined matrix. Finally we use backtracking method to find all the possible path of the pixel which has the lowest energy.
Algorithm Implementation
Such is the list of the functions in my coding package.
| Name
| input
| output
|
| search_seam
| an original image
| 1 seam vector which store the path of the pixels with the lowest energy
2 the energy contained in the seam vector
|
| seam_removal
| 1 An input image
2 seam vector which store the path of the pixels with the lowest energy
| the resized image which is has been operated with seam removal
|
| seam_plot
| 1 an input image
2 seam vector which store the path of the pixels with the lowest energy
| the input image with the found seam superimposed on it
|
| seam_carving_vertical
| 1 an input image
2 the width of the resized image
| the resized image by removeing vertical seams
|
| seam_carving_horizonal
| 1 an input image
2 the height of resized image
| the resized image by removing horizonal seams
|
| image_transpose
| an input image
| the tranposed input image
|
| image_retargeting
| 1 an input image
2 the height of the resized image
3 the width of the resized image
| the resized image in both dimensions
|
| seam_insertion
| 1 an input image
2 the seam vector with the lowest energy
| the stretched image
|
| energy_function1
| an input image
| the energy matrix of the input image
|
Experimental Results
Image Resizing by Horizonal and Vertical Seam Removal
I carried out the experiment on not only the images that professor provided but also the images which is downloaded from internet such as google images.
For convenience the first images are always the original images and the second one is the resized image by removing vertical seams.
The third one is the resized images by removing the horizonal seams.
I display them together to make it easier for comparison.
| tower.jpg
| 640*434
| 430*434
| 640*315
|
| house_by_jim_mccann.jpg
| 512*384
| 350*384
| 512*280
|
| yo_couch_by_yuan2003.jpg
| 648*432
| 400*432
| 648*300
|
| pisa.jpg
| 500*334
| 350*334
| 500*234
|
| pyramid.jpg
| 550*352
| 400*352
| 550*250
|
| great_wall.jpg
| 800*600
| 520*600
| 800*400
|
| waterfall.jpg
| 648*432
| 400*432
| 648*300
|
| max_in_windsor.jpg
| 648*432
| 400*432
| 648*300
|
| eiffel.jpg
| 431*300
| 300*300
| 431*200
|
| niagara.jpg
| 1024*768
| 700*768
| 1024*500
|
| beach.jpg
| 307*230
| 220*230
| 307*150
|
| christmas.jpg
| 307*230
| 220*230
| 307*150
|
Discussion
As the results illustrated, most of images can gain a satisfied resized image by using the seam-carving method.
However, when you push the algorithm to the limit, the artifact- such as some distortion or unregular shape will appear.
When the image has a complex and unstructured layout of objects, the results often looks so strange.
Bells and Whistles
Image Retargeting
For image retargeting, I implement the function by combining the image_transpose, search_seam and seam_removal function.
The dynamic programming method is applied to search for the optimal order the vertical and horizonal seam removal operation.
Let T(r,c) denotes the cumulative removed energy for the r vertical seams and c horizonal seams.
We calculate from T(0,0). T(0,0)=0. So the choice of next step between T(1,0) and T(0,1) depends on the comparison result of the energy contained in the vertical and horizonal seam vector.
As r or c is reached to the targeted dimension, the rest of operation is just on the other dimension. In this way we can get the resized image by searching for the optimal order of seam removal operations
| tower.jpg
| 640*434
| 400*300
|
| pyramid.jpg
| 550*352
| 400*250
|
| house_by_jim_mccann.jpg
| 512*384
| 350*280
|
Image Stretching
For image stretching, we first use the search_seam function to find the seam with lowest energy, then we insert the seams in order of removal. But the stretching part seams strange.
The image scaling should be considered to get a better result.
| eiffel.jpg
| 431*300
| 581*300
|
| pyramid.jpg
| 550*352
| 700*352
|
Test of my own images
I took this photo in summer last year which is a beautiful scene of our university. I carried out multiple experiments ranging from vertical and horizonal seam removal and image retargeting and image stretching.
| laval.jpg
| 616*408
| 450*408
| 616*280
| 450*280
| 776*408
|
Acknowledgement
At last, I want to express appreciation to the author of the image that downloaded from the internet! Thanks to professor Jean-Francois for giving us such an amazing assignment to do!