CS1290 Project 3: Seam Carving

Algorithm Design

The basic idea of backward seam carving is that, we want to find the path that has the least accumulated energy and remove it. The assumption is that, patches or pixels with high energy generally come from the targets which want to focus, rather than remove them. Seam carving can be used to reduce width or height respectively, with width reduction, the path is from top to bottom and we select one pixel each row. And with height reduction, we just need to naively transpose the input image and do the same thing for width reduction. For two successive pixels in path, they should be successive pixels, not pixels far apart in the original image.

The energy map is computed using dynamic programming.

Results

Table 1 shows results of given test images using backward method.

original	Backward	Detail
		Backward: Left: width reduced by 200 Right: height reduced by 200
		Backward: Left: width reduced by 200 Right: both width and height reduced by 200
		Backward: width reduced by 200
		Left: height reduced by 200 Right: width reduced by 200 (a failure case) The reason maybe the energy of the hair part of Monalisa is lower than the energy of backgroud, so that the algorithm keeps background and removes hair.
		Backward: width reduced by 200
		Backward: width reduced by 200
		Backward: width reduced by 200

Forward

Instead of using backward method that removes the paths with least accumulated energy, we can use forward method to remove the paths that introduce less energy. Still we use dynamic programming.

The equation of dynamic programming becomes,

M(i, j) = P(i, j) + min{M(i-1, j-1) + CL(i, j), M(i-1, j) + CU(i, j), M(i-1, j+1) + CR(i, j)}

Table 2 shows improvements by using forward method.

Original	Backward	Forward

Human are very sensitive to straight lines, if backward method is applied to images containing a lot of straights, it will create a lot of zigzag line segments. But if you look at the rectange boxes areas of the images in table 2, forward method makes those lines more smooth.

The energy equation has two parts, the pixel energy and the accumulated part. Actually we don't know the weights of these two parts should be. So if we put a coefficient on the pixel energy part. The equation will become,

M(i, j) = alpha * P(i, j) + min{M(i-1, j-1) + CL(i, j), M(i-1, j) + CU(i, j), M(i-1, j+1) + CR(i, j)}

Table 3 shows per pixel energy of the forks image according to number of seams removed and different alpha values.

Graph	Detail
	The per-pixel-energy plot of the backward and forward method, as expected, forward method results in lower per-pixal-energy than backward method.
	We can see that as alpha increases, the per-pixel-energy is increasing. The bold line is backward method, and the lowest line is forward method with no individual pixel energy considered. We can't say the lower the energy, the better the results, because we're properly removing desired details with low alpha. It's hard to determin the weights.

More Results

Original	Results