Seam carving: resizing that respects content
In August 2007 at SIGGRAPH Shai Avidan (MERL) and Ariel Shamir (Interdisciplinary Center Herzliya) showed how to change an image’s proportions without distorting what matters: the program repeatedly removes or inserts a seam, a connected chain of the least noticeable pixels from top to bottom or left to right.
Why it matters
Until then an image could only be stretched or cropped. Here the machine itself decided which pixels did not matter and removed those, so the sky narrowed while the people stayed. The same device removed a marked object and gave images that fit the size of a page in real time. A year later the device appeared in Photoshop CS4 as Content-Aware Scaling.
ACM Transactions on Graphics 26(3), article 10. Dynamic programming finds the best seam under an energy function: gradient magnitude, saliency, eye-gaze data or a face detector’s output. Reducing 400 x 500 to 100 x 100 takes about 2.2 seconds. The authors say the method does not work on every image: where there are no "less important" areas, no content-aware resizing will help. Avidan joined Adobe in August 2007, writes Adobe’s John Nack in his blog. Adobe announced Photoshop CS4 with Content-Aware Scaling, which "automatically recomposes an image as it is resized, preserving vital areas", on 23 September 2008 and began shipping it on 15 October. Adobe’s releases do not name seam carving; that it is the same method is said by Nack on 13 December 2008: "Shai Avidan, the co-creator of seam carving (Content-Aware Scaling)". These are an Adobe employee’s words, not a description of the product’s algorithm.