Seam Carving

Seam Carving for Content-Aware Image Resizing

Also known as liquid rescaling
It functions by establishing a number of seams(paths of least importance) in an image and automatically removes seams to reduce image size or inserts seams to extend it. Seam carving also allows manually defining areas in which pixels may not be modified, and features the ability to remove whole objects from photographs.
The purpose of the algorithm is image retargeting, which is the problem of displaying images without distortion on media of various sizes (cell phones, projection screens) using document standards, like HTML, that already support dynamic changes in page layout and text but not images.

Seams

Vertical Seam

A vertical seam is a path of pixels connected from top to bottom in an image with one pixel in each row.

Horizontal Seam

A horizontal seam is similar with the exception of the connection being from left to right.

Working

Find energy function in an image (gradient magnitude)

Find connected path of pixels or seams from one side of the image to other that contain the least energy

Find the least amount of information and remove them

The importance/energy function values a pixel by measuring its contrast with its neighbor pixels.

Computing Seams

Computing the seam consists of finding the path of minimum energy cost from one end of the image to another. This can be done via Dijkstra's algorithm, dynamic programming, greedy algorithm or graph cuts among others.

To find the energy function to represent least amount of information

Gradient (acts like an edge detector in an image)
Entropy
Histogram of Oriented Gradients (HoG)

Advanced

Use forward energy instead of backward energy (remove the seams that insert least amount of energy inserted to the picture after their removal)
Use negative energy for object deletion
Use motion detection (motion saliency) and face detection to preserve the context
Can be used to stabilize shaky camera videos.