Seam carving

From Wikipedia, the free encyclopedia

Seam carving is an algorithm for image resizing (primarily shrinking) developed by Shai Avidan and Ariel Shamir.

It operates on "seams", i.e. sequences of orthogonally or diagonally adjacent pixels that run from one side of the image to the other, one per column (horizontal seams) or one per row (vertical seams). Removing all pixels in a seam reduces the height or width of the image by one row or column; repeated selection of seams to remove can achieve any amount of shrinking. Seam carving can be adapted to image enlargement by duplicating the pixels in a seam.

Results can be controlled by selecting seams; Avidan and Shamir adopted dynamic programming to extend the "best" seam starting at every pixel of an image edge, according to an "importance" function that represents the penalty for removing each pixel. The importance of a pixel is generally estimated by its contrast when compared with its neighbor pixels, but other measures may be used.

Additionally, it's possible to manually define protected areas in which pixels may not be removed (e.g. to leave important subjects untouched and affect background pixels only), or conversely to designate pixels that must be deleted (e.g. to remove whole objects from photographs along with an automatically computed part of the background).

It is possible with seam carving to scale pictures by a larger amount while still retaining details. In normal image scaling, scale factors greater than 2 or less than 0.5 usually result in visible image quality degradation. Seam carving artifacts usually consist of deformed objects (whenever seams are not uniformly distributed: smoother textures are deleted first) or of visibly damaged details (where seams affect high contrast areas).