Discontinuous Seam Carving for Video Retargeting

September 13, 2010

Posted by Matthias Grundmann and Vivek Kwatra, Google Research

Videos come in different sizes, resolutions and aspect ratios, but the device used for playback, may it be your TV, mobile phone, or laptop, only has a fixed resolution and form factor. As a result, you cannot watch your favorite old show that came in 4:3 on your new 16:9 HDTV without having black bars on the side, referred to as letterboxing. Likewise, widescreen movies and user-videos uploaded on YouTube are shot using various cameras with wide-ranging formats, so they do not fit completely on the screen. As an alternative to letterboxing, several devices try to upscale the content uniformly, which either changes the aspect ratio, making everything look stretched out, or simply crop the frame, thereby discarding any content that cannot fit the screen after scaling.

At Google Research, together with collaborators from Georgia Tech, we have developed an algorithm that resizes (or retargets) videos to fit the form factor of a given device without cropping, stretching or letterboxing. Our approach uses all of the screen’s precious pixels, while striving to deliver as much video-content of the original as possible. The result is a video that adapts to your needs, so you don’t have to adapt to the video.

Six frames from the result of our retargeting algorithm applied to a sub-clip of “Apologize”, © 2006 One Republic. Original frame is shown on the left, our resized result on the right. The original content is fit to a new aspect ratio.

The key insight is that we can separate the video into salient and non-salient content, which are then treated differently. Think of salient content as actors, faces, or structured objects, where the viewer anticipates specific, important details to perceive it as being correct and unaltered. We cannot change this content beyond uniform scaling without it being noticeable. On the other hand, non-salient content, such as sky, water or a blurry out-of-focus background can be squished or stretched without changing the overall appearance or the viewer noticing a dramatic change.

Our technique, which we call discontinuous seam carving -- named so because it modifies the video by adding or removing disconnected seams (or chains) of pixels -- allows greater freedom in the resizing process than previous approaches. By optimizing for the retargeted video to be consistent with the original, we carefully preserve the shape and motion of the salient content while being less restrictive with non-salient content. The key innovations of our research include: (a) a solution that maintains temporal continuity of the video in addition to preserving its spatial structure, (b) space-time smoothing for automatic as well as interactive (user-guided) salient content selection, and (c) sequential frame-by-frame processing conducive for arbitrary length and streaming video. The outcome is a scalable system capable of retargeting videos featuring complex motions of actors and cameras, highly dynamic content and camera shake. For more details, please refer to our paper or visit the project web-site.