Home

Welcome to the Seam-Carving-C-implementation wiki!

Seam carving, also known as "Content-Aware Image Resizing" by the original author, is a technique to change the size of an image without hurting its important contents. The idea of the algorithm is to compute the "energy" of each pixel to represent its importance, and then use Dynamic Programming to compute the vertical or horizontal "seam" with the least energy so as to delete exactly one pixel from each row/column and ensure the deletion is continuous to maintain the shape of important foreground contents.

Algorithm

1. Without loss of generality, suppose we wish to shrink the horizontal size of the image by 1:

2. Taking the $l_1_$ norm of its gradient (central difference used here), define it as the energy of each pixel.

3. In order to get a "seam" with the least cumulative energy, Compute the cumulative energy of a pixel as [the minimum energy value of its adjacent pixels in the above row (i.e. upper-left, upper, upper-right)] plus [the energy value of itself]. Then compare the cumulative energy values in the bottom row of the image.

4. This seam is labeled as follows:

5. Delete more seams (10 and 30 respectively):

6. Outcome

7. Other Examples

• lena (10 seams)

• lena (30 seams)

Implementation

1. Files imglib.c and imagelib.h are copied from a ppm IO toolkit provided by Rosettacode. (It's recommended to use the codes here instead of the original version because that one have several typos and bugs)

2. Files seam_carving.c and seam_carving.h contain the functions.

3. main.c is the interface.

Different Kernels for edge detection

• Central difference: Note -- after filtering with a 3*3 window, the picture size will shrink for each direction. As a result, we must enlarge (continuously) the margin by 1, in order to make the outcome to be the same size of the original picture.

• Sobel Operatior: The 3*3 filter is given by:

Outcome:

10 seams with Sobel Detector (Compare with above)

30 seams with Sobel Detector

Comparison:

Original:

Seam-carve by half:

Outcome:

Comparison by scaling:

More ideas:

interface for picture formats through a pipe

With ImageMagick, one can easily implement a pipe of the function which allows arbitrary picture formats that ImageMagick can handle (commented in the code).

Horizontal shrinkage

It's exactly the same to delete seams that are horizontal (left-to-right), provided in the code.

Size Expansions (Enlarging)

Insert seams with averaging its two neighbors who have the least energy. Furthermore, "Content Amplification" is mentioned in the reference (which is as simple as scaling larger and applying Seam-carving).

interactive foreground/background area editing

The automatic-computed energy is usually not perfect, so it's helpful to adjust it manually, or with further modification, for example:

1. Face recognition (e.g. built-in in ImageMagick)
2. Mark manually with mouse (e.g. python-opencv, used in Implementation of GrabCut, co-authored with Orcuslc during undergrad)
3. Other energy functions, other than edge detection which is used here. e.g. Grabcut above (set foreground as 5 Gaussian clusters with EM), or as simple as Scaling energy as larger for pixels near the center, etc.