danluong

Having recently come across a paper by Shai Avidan and Ariel Shamir, and watching the totally awesome video about seam carving, I decided to try my hand at implementing their algorithm for myself. I’ve included a quick overview of what seam carving is, the MATLAB program I have created, a summary of the algorithm itself with some implementation details, as well as some notes on how to run my program, so without further ado…

The Program

You can download the zip file with all of my code here:

matlab-seam-carving.zip

If you would like to run this program on your copy of MATLAB, you will need to have the image processing toolbox. I will try to remove this dependency in a later update.

You are free to modify my code and add new features, etc, and redistribute it as you see fit, but I would like to hear about it, and be given credit where it is due.

Features and functionality

The program allows the user to resize an image by removing a continuous path of pixels (a seam) vertically or horizontally from a given image. A seam is defined as a continuous path of pixels running from the top to the bottom of an image in the case of a vertical seam, while a horizontal seam is a continuous line of pixels spanning from left to right in an image. An example of a seam overlaid on an image is shown in Figure 1.

Figure 1: Image with vertical seam

The GUI of the program I completed is included as Figure 2. The main overall functionalities include (in order from the top to bottom in the GUI) opening an image file, resetting the state of the program to initial values before the image was resized in any way, the removal of a single vertical running seam from the image, removal of a single horizontal seam from the image, input boxes for custom image resizing using repeated seam removals and/or insertions (maximum image size is 2xCurrentsize-1 in the horizontal and vertical directions), a listbox for user chosen display of the color RGB image, the gradient image, or the energymap image, and a checkbox to show the seam removed on one of the three chosen types of image chosen from the listbox.

Figure 2: Seam Carving GUI

Details of algorithm implementation

The first step in calculating a seam for removal or insertion involves calculating the gradient image for the original image. The gradient image is a common image that is used in both horizontal and vertical seam calculation, and can be calculated either from the luminance channel of a HSV image, or calculated for each of the R, G, and B channels, then averaging the three gradient images. Figure 3 is included as an example gradient image. The Sobel operator was chosen for calculation of the gradient image in this project, but other gradient operators may be used. (MATLAB function: findEnergy)

Figure 3: Gradient Image

Once the gradient image is calculated, the next step is to calculate the energymap image. The energymap image needs to be calculated separately for either vertical (Figure 4) or horizontal (Figure 5) seams, and also needs to be recalculated after every seam removal. It is calculated by the following process for the vertical seam case (a horizontal energy image can be calculated using the same function, where the input image is transposed): for each pixel (i,j) in the gradient image (see Table 1), the value at (i,j) in the energymap is the sum of the current value at (i,j) from the gradient image and the minimum of the three neighboring pixels in the previous row, i.e. min((i-1,j-1),(i-1,j),(i-1,j+1)), from the energymap. For i=1 (the initial row), the values in the energymap image are set to those in the gradient image, and for when the pixel (i,j) is along the edge of an image, only (i-1,j) and either (i-1,j-1) or (i-1,j+1) are used depending on if (i,j) is on the right or left edges, respectively. (MATLAB function: findSeamImg)

Table 1: Pixel indices

Figure 4: Vertical Seam Energymap

Figure 5: Horizontal Seam Energymap

Once the energymap is calculated, the method to find the optimal seam is to first find the minimum value in the last row (which becomes the (i,j)’th pixel), saving the pixel location for use in removal, then working backwards by finding the minimum of the 3 neighboring pixels of (i,j) in the (i-1)’th row and saving that pixel to the seam path. This process is repeated until the first row is reached, and results in the optimal seam, an example of which is shown in Figure 6. (MATLAB function: findSeam)

Figure 6: Energymap with vertical seam

After the optimal seam is found, the path of pixels that make up the seam are removed from both the gradient image and the original RGB image, and the remaining pixels are shifted right or up to form a continuous image.

The process can be repeated to remove a set of seams, horizontally or vertically and will result in an image with reduced dimensions, but with the overall scene content intact. An example of this is included as Figure 7, where the image was resized to 320×240 pixels, from 640×480 pixels and as can be seen, the resulting image will have artifacts if a large number of seams are removed.

Figure 7: Resized Image

For the case of seam insertion (increasing the image size), a seam can be calculated along a given direction, and the average of the two neighboring pixels along the seam can be inserted. If the desired image size is to be increased by N pixels in a given direction, the computation of the first N seams to be removed along that direction must first be completed (MATLAB function: removalMap), and then averaged pixels are inserted along each successive seam, hence the limitation on the maximum increase in image size in my implementation noted earlier in the features and functionality section. This method of calculating N seams is used to avoid inserting pixels along the same seam repeatedly.

Running the Program

To run the GUI, first extract the zip file to a location on your computer, then open MATLAB and browse to the extracted folder containing the SeamCutGUI.m file. Double click the file to open it, and run the file by pressing F5 on the keyboard. The GUI can also be run from the “guide” GUI editor in MATLAB by typing “guide” in the command window, clicking the “Open Existing GUI” tab, clicking “Browse”, opening the SeamCutGUI.fig file, then pressing the green play button in the GUI editor. Once the GUI appears, the basic functionality of the program can be accessed from each of the available buttons. The “Remove Horiz/Vert Seam” buttons will remove a single horizontal or vertical seam, respectively, while below the buttons, the user can enter desired dimensions for resizing where the size can range from 1×1 to (2*CurrentWidth-1)x(2*CurrentHeight-1). The “Display Image:” listbox will allow the user to choose one of the available RGB, gradient, or energymap images, and the “Show Seams” checkbox will plot the calculated seam on the chosen image from the textbox after the next operation.

Notes

While the seam carving method is a novel approach to image resizing, it is not without flaws. The one of the flaws with the results obtained using the method is that the impact of the distortion is image dependent. Some images will resize well with it, while others will have serious distortions with minimal seam removals. It is also very computationally expensive when compared to image scaling or cropping operations (resizing from 640×480 to 320×240 took somewhere around 30 mins for my admittedly ancient computer, a 1.4GHz AMD w/ 352MB of RAM).

Relevant Resources

Avidan, S. a. (2007). Seam carving for content-aware image resizing. International Conference on Computer Graphics and Interactive Techniques. ACM Press New York, NY, USA.

http://brain.recall.googlepages.com/cair

http://yaniv.leviathanonline.com/blog/math/seam-carving/

http://hectorgon.blogspot.com/2007/08/seam-carving-my-quick-and-dirty.html