15-862 Computational Photography

Project 2: Seam Carving
by: Lisa Chan

Index:

1. Horizontal Seam Carving
2. Vertical Seam Carving
3. Seam Carving vs Human Interaction

4. Dynamic Seam Carving

5. Optimal Diagonal Carving

6. Seam Insertion

7. Object Removal

8. Seam Carving in Movies

9. Image Sources

Project Details:

The two energy functions implemented to find the seams were entropy and image gradients. In some images, the entropy function will work better while in others the image gradient function will give better results. Unless one of the carved images are blatantly horrific, sometimes, it's very difficult to judge which energy function yielded a better result, as seen in the "Equally Good" results section. Without human interaction, the program 'seam_carve_heuristic.m' will help evaluate which energy function was really the better one to use. The program is based on the idea that the badly carved image will have greater image gradient problems than the properly carved one. The difference between the maxmium dx,dy and the mininum dx,dy are first calculated for the three images. The difference of these values between the original image and the carved images are then used to evaluate which carving method will yield the smallest global gradient change. Vertical seam carving was simply done by rotating the images by 90 degrees and then applying the same code used for horizontal seam carving.

1. Horizontal Seam Carving:

A. Entropy Is Better:

 Original Image Entropy Seam Carved Image Gradient Seam Carved

 Original Image Entropy Seam Carved Image Gradient Seam Carved

C. Equally Good:
 Original Image Entropy Seam Carved Image Gradient Seam Carved

D. Nothing Works:
 Original Image Entropy Seam Carved Image Gradient Seam Carved

2. Vertical Seam Carving:

A. Entropy Is Better:

 Original Image Entropy Seam Carved Image Gradient Seam Carved

 Original Image Entropy Seam Carved Image Gradient Seam Carved

C. Nothing Works:
 Original Image Entropy Seam Carved Image Gradient Seam Carved

3. Seam Carving vs Human Interaction:

The photo editing by human involvement was performed on Photoshop 6.0.
The layer images show what each layer in Photoshop was. Anything in white should really be transparent, so that as each layer is added, then the objects in the lower layer will be seen. First, the left side of the image was selected and transformed to be "skinnier". Parts of the image were "erased" so that the original parts of that object could be maintained. Next, the house in the foreground was selected with the lasso tool, pasted onto a new layer, and shifted over to the corresponding location. A layer gradient was applied to the house layer (see layer4) so that the hard edges of the copied items will be blurred to create a nicer blend into the other objects. Finally, the houses in the background were selected, then transformed to fit into the narrow space between the trees on the left, and the house on the right.

 Original Image Entropy Seam Carved Manually Seam Carved

 Layer 1 Layer 2 Layer 3 Layer 4

4. Dynamic Seam Carving:

Because I do not know how to create a GUI on Matlab, I created two programs. The first, 'seam_carve_store.m' will calculate the seams required to reduce the image up to 75% reduction, and output the seams to a text file. Then the program, 'seam_carve_getsize.m' will read in the text file, and seam carve the image approximately 12 times faster than using just the normal program. Here I simply output an image for every seam I've carved, and then compiled the images into animated gifs with Adobe ImageReady 3.0 to create the same effect as recording the usage of a GUI.
Click on the images to see them be seam carved in action!

5. Optimal Diagonal Carving:

Diagonal seam carving is really finding the correct sequence to alternate between horizontal and vertical seam carving. The path energy per unit length calculated for vertical and horizontal carving were compared to find the optical seam to carve at each step.
Click on the original image to see the first image be seam carved in action!

 Original Image Diagonally Seam Carved

6. Seam Insertion:

Seam insertion was coded the exact way as the paper mentionned. The first k seams to be removed are found, and then at each seam, the average pixel value between the neighbors were found and inserted into the image.

 Original Image Seam Inserted Image

7. Object Removal:

Because I do not know how to bring up some sort of GUI to select the object to be removed, I simply created a mask in Photoshop that selects the area of the object. With the mask, I simply had the program read in the mask, and whenever the pixel is not white on the mask, the energy of that pixel will be lowered to a negative value. This way, any seams that passes through the pixels with the mask, the cost should be negative.
Click on the original images to see them be seam carved in action!

8. Seam Carving in Movies:

This is just another "just for fun" ideas. Most movie fans prefer the widescreen version over the fullscreen version of movies. Especially with the older movies, the adaptation from widescreen to fullscreen involved the usage of "pan and scan", which only focuses on one portion of the total frame. According to widescreen.org, as much as 45% of the visuals are lost in the fullscreen version! Below are 2 second clips taken from Star Wars IV: A New Hope which shows the problems involved with Pan & Scan. I attempted to seam carve each frame in this clip in hopes of improving it but instead, funny artifacts were created. For example, the background looks very shifty, and Luke seems to have lost a lot of weight!

 Widescreen Fullscreen Image Gradient Seam Carved

9. Image Sources: (in order of appearance)

1. Horizontal Seam Carving
1. Entropy Is Better
• From:Webshots By:leene50 Album:The Golden Hours
• From:Webshots By:bioprof Album:Audubon in south New Jersey
• From:Webshots By:ajez123 Album:EGYPT - Sunrises & Sunsets
• From:internet By:Kurtis J. Moore
• From:internet By:Kurtis J. Moore
• From:Me Taken at:Disneyworld in Orlando

• From:Webshots By:papomena Album:Bavaro Beach, Punta Cana, Dominican Republic
• From:Webshots By:sgss_1965 Album:Leo Lam Chu Hung's portfolio
• From:Webshots By:bioprof Album:Audubon in south New Jersey
• From:Webshots By:bioprof Album:Audubon in south New Jersey
• From:Webshots By:jokipeti Album:Mountains, Ocean, Skyline, Nature - Canada
• From:Webshots By:jokipeti Album:Mountains, Ocean, Skyline, Nature - Canada
• From:Webshots By:rjscholten Album:Oregon Coast 2007
• From:Webshots By:rjscholten Album:Oregon Coast 2007
• From:Webshots By:franpc128 Album:Fondos
• From:Webshots By:foxilein Album:Winter in Australia
• From:Webshots By:kevintrieu Album:North Palisade via U-Notch & Chimney 05/12-05/13 2006
• From:Webshots By:kevintrieu Album:North Palisade via U-Notch & Chimney 05/12-05/13 2006
• From:Webshots By:sharwils2 Album:Canadian Rocky Mountains, Lake Louise and Banff
• From:Webshots By:sharwils2 Album:Canadian Rocky Mountains, Lake Louise and Banff
• From:Webshots By:sharwils2 Album:Canadian Rocky Mountains, Lake Louise and Banff
• From:Me Taken at:New River Gorge, Ohio
• From:Me Taken at:Home, this is my cute cute dog!

3. Equally Good
• From:Webshots By:jokipeti Album:Mountains, Ocean, Skyline, Nature - Canada
• From:Webshots By:foxilein Album:Winter in Australia
• From:Webshots By:foxilein Album:Winter in Australia
• From:Webshots By:delgatty Album:Rocky Mountain Wildlife & Backcountry
• From:Webshots By:sharwils2 Album:Canadian Rocky Mountains, Lake Louise and Banff
• From:internet By: Kurtis J. Moore

4. Nothing Works
• From:Webshots By:bioprof Album:Audubon in south New Jersey
• From:Webshots By:bioprof Album:Audubon in south New Jersey
• From:Webshots By:bioprof Album:Audubon in south New Jersey
• From:Webshots By:jokipeti Album:Mountains, Ocean, Skyline, Nature - Canada
• From:Webshots By:jokipeti Album:Mountains, Ocean, Skyline, Nature - Canada
• From:Webshots By:jokipeti Album:Mountains, Ocean, Skyline, Nature - Canada
• From:Webshots By:franpc128 Album:Fondos
• From:Webshots By:delgatty Album:Rocky Mountain Wildlife & Backcountry
• From:Me Taken at:Home

2. Vertical Seam Carving
1. Entropy Is Better
• From:Webshots By:franpc128 Album:Fondos
• From:Webshots By:sharwils2 Album:Canadian Rocky Mountains, Lake Louise and Banff
• From:Webshots By:delgatty Album:Rocky Mountain Wildlife & Backcountry
• From:Webshots By:assistantchief84 Album:Great Smoky Mountains Cades Cove File

• From:Webshots By:worldtripper3 Album:London - Magical nights and days on the Thames
• From:Webshots By:sharwils2 Album:Canadian Rocky Mountains, Lake Louise and Banff
• From:Webshots By:kevintrieu Album:North Palisade via U-Notch & Chimney 05/12-05/13 2006
• From:Webshots By:ajez123 Album:EGYPT - Sunrises & Sunsets
• From:Webshots By:bioprof Album:Audubon in south New Jersey

3. Nothing Works
• From:Webshots By:foxilein Album:Winter in Australia
• From:Webshots By:bioprof Album:Audubon in south New Jersey

3. Seam Carving vs Human Interaction
• From:Me Taken at:Disneyworld, Florida

4. Dynamic Seam Carving
5. From:Webshots By:papomena Album:Bavaro Beach, Punta Cana, Dominican Republic
6. From:Webshots By:foxilein Album:Winter in Australia
7. From:Webshots By:kevintrieu Album:North Palisade via U-Notch & Chimney 05/12-05/13 2006
8. From:Webshots By:franpc128 Album:Fondos
9. From:Webshots By:worldtripper3 Album:London - Magical nights and days on the Thames

10. Optimal Diagonal Carving
• From:Webshots By:victorian381 Album:Canada Winter 2005 with Blue Moose Tours
• From:Webshots By:sharwils2 Album:Canadian Rocky Mountains, Lake Louise and Banff

11. Seam Insertion
• From:Webshots By:sgss_1965 Album:Leo Lam Chu Hung's portfolio
• From:Webshots By:jokipeti Album:Mountains, Ocean, Skyline, Nature - Canada
• From:Webshots By:jokipeti Album:Mountains, Ocean, Skyline, Nature - Canada
• From:Webshots By:foxilein Album:Winter in Australia
• From:Webshots By:sharwils2 Album:Canadian Rocky Mountains, Lake Louise and Banff

12. Object Removal