15-463: Computational Photography
Project #3 Seam Carving
Jiaqi Xing (jxing)
10/1/2012
Description
This project is oriented on seam carving as described in SIGGRAPH paper Seam Carving for Content-Aware Image Resizing by SHai Avidan and Ariel Shamir. The goal of this assignment is to design a matlab program which can shrink an image (either horizontally or vertically) to a given dimension without over skewing content shape.
My Approach
In order to choose the right pixels to remove from the image, I used dynamic programming as described in the paper. My approach includes two main parts:
- Generate the energy function for a given image.
- Search for the line with lowest total energy and remove it until it reaches the given dimension.
I tried with different energy functions introduced in the paper.
e_1(I) = |\frac{\partial} {\partial x} I| + |\frac{\partial} {\partial y} I|
e_2(I) = \sqrt{(\frac{\partial} {\partial x} I)^2 + (\frac{\partial} {\partial y} I)^2}
e_{HoG}(I) =\frac{|\frac{\partial} {\partial x} I| + |\frac{\partial} {\partial y} I|} {max(HoG(I(x,y)))}
-
The first energy function works pretty well with most of my images. However for images with noisy background it no longer retain the important parts of the image.
-
The second energy function does a better job in terms of minimizing the effect of background noise.
-
The third function with HoG involved seems to be better at finding the important objects than the above two.
Besides the energy functions, I worked with laplacian filter and region of interest (ROI) masks. I applied laplacian filter (to the grayscale image) before carving the picture, and it does work for a few images. I also tried to add mask to the image with the matlab interactive polygon tool: roipoly and increased mask values in the energy function, it helped when some of the important objects got removed or skewed.
The searching for minimum seam line is just a dynamic program problem. I followed the algorithm described in the paper to minimize seam costs.
So for each pass, search for the minimum seam line and remove that.
- First compute the cumulative minimum energy:
q(i,j) = e(i,j) + min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))
- Backtrace from the minimum value in the last row and find the whole seam line for each pass.
The search algorithm is written to remove vertical lines. To also carve horizontally, I transposed the image before carving and after seam carving is done, just transpose the result image again.
Results
Result 1
The first two images are Chinese landscape painting. The common character between them is that they both have really stable background which makes the carving job easier. However when I removed 100 horizontal pixels from the first image, the fish at the bottom was squeezed extensively. I applied the BOI mask and the result is much better. Also the signature at the top left is kept pretty well in both results.
original image (378 * 200) |
removed 100 horizontal pixels (fail) |
BOI Mask
BOI Mask |
carve with BOI mask (278*200) |
Result 2
I again applied the BOI mask to the boat. The result looks pretty good with the writing, the boat and the stamp in good shape.
original image |
BOI mask |
removed 200 horizontal pixels |
Result 3
For this image of CMU campus, I started with e1 energy function, but the noise from background people and building comes in the way, and the sign of "Carnegie Mellon U.." was squeezed. I then applied the laplacian filter and the resulting image is on the right.
original image (size: 280 * 445) |
removed 10 horizontal and 100 vertical pixels |
Result 4
Again a CMU scene. The initial carving was not good since the blue building on the right was cropped by a lot. I then applied the laplacian filter and it works better though the Tepper building and the blue building still got remove extensively.
original image (size: 400 * 650) |
removed 100 horizontal and 5 vertical pixels (fail) |
removed 100 horizontal and 5 vertical pixels (laplacian filtered) |
Result 5
This is a model standing before a wall. I intended to carve it vertically and make it to a more regular image size like (500*500 or 300*400).
original image |
Seam Results (removed 200 vertical pixels):
I first tried with e1 and e2 energy functions. The results were all like the one shown on the left. A couple pixels were removed from the model's hair. After applying the laplician filter (right image), it actually looks much better.
used e1/e2 energy function (fail) |
applied laplacian filter to image |
Applying BOI (removed 200 vertical pixels):
Then I also tried to use BOI mask. This time the result seems to be similar to the laplacian filtered result.
BOI mask |
applied laplacian filter and BOI mask |
Result 6:
A panorama of the Pittsburgh downtown area. In this image there are a lot of details along the river. The initial carving turns out to be bad as the bridge on the right is skewed. Then I used the third energy function introducing the HoG of the image. This time the right bridge is a lot better, however the left bridge and some building in the middle went out of shape. The HoG is definitely a fix here, though there are more details that will be done to make this image better.
original image (size: 212 * 900) |
removed 300 vertical pixels (Failure Case) |
added HOG to energy function (212*599) (still needs fix) |
Other Results
Result 7
original image (size: 468 * 640) |
removed 80 horizontal and 80 vertical pixels |
Result 8
original image (size: 500*500) |
removed 80 horizontal and 10 vertical pixels |
Result 9
original image |
removed 100 vertical pixels |
Refrences:
Shai Avidan, and Ariel Shamir. 'Seam Carving for Content-Aware Image Resizing'. 2007.
O. Ludwig, D. Delgado, V. Goncalves, and U. Nunes, 'Trainable Classifier-Fusion Schemes: An Application To Pedestrian Detection,' In: 12th International IEEE Conference On Intelligent Transportation Systems, 2009, St. Louis, 2009. V. 1. P. 432-437.
Picuture Links:
