

Fig. 1 Comparison of seam carving and conventional image resizing (scaling). The signs are distorted in the scaled image, while keep the original shape in the image given by seam carving. In this project, I implemented Seam Carving [1], a technique proposed by Shai Avidan and Ariel Shamir to resize images without distorting the primary content of the images. This technique works by removing the seams (i.e. least noticeable pixelwide paths across or upanddown an image), until the image is of the desired smaller size. 

1. Basic AlgorithmThe overall process of constructing photometric stereos basically consists of four steps:1.1 Optimal seam: Formally, let I be an n×m image and define a vertical seam to be: （1） where x is a mapping x
: [1, …, n] → [1, …, m]. A vertical seam is an 8connected path of
pixels in the image from top to bottom, containing one, and only one,
pixel in each row of the image. Similarly, a horizontal seam is: (2) Note
that removing the pixels of a seam from an image is just shifting all
the pixels of the image are shifted right (or down) to compensate for
the missing path.Given an energy function e, we can define the cost of a seam as . The optimal seam is the one with minimum cost. The problem of looking for an optimal seam can be formulated as dynamic programming [1] or graph cut [2]. The dynamic programming approach consists of two steps: first, traverse the image from the first row to the last row and compute the cumulative minimum energy M (the energy of removing a partial seam for the top to the pixel (i, j)) for each entry (i, j): (3)
second, find the minimum value in the last row and track back to the first row to find the optimal path.1.2 Energy function: I use a simple energy function (4)
1.3 Optimal SeamsOrder: Image retargeting (i.e. an image I of size n×m is retargeted to size n0×m0) requires removing several horizontal and vertical seams. The order of romoving seams can be: vertical seams first, horizontal seams first, or alternate between the two. However, the optimal order can be found also using dynamic programming. The problem definition is (5)
where k = r + c, r = (m  m'), c = (n  n') and (αi denotes whether we remove a horizontal or vertical seam in step i).
The transport map T is (6) where T(r, c) is the minimum cost of removing r horizontal and c vertical seam 

 Copyright (c) 2009 Wei Zhang 