Optimal multiple surfaces searching for video/image resizing - a graph-theoretic approach

Content-aware video/image resizing is of increasing relevance to allow high-quality image and video resizing to be displayed on devices with different resolution. In this paper, we present a novel algorithm to find multiple 3-D surfaces simultaneously with globally optimal solution for video/image resizing. Our algorithm is based on graph theory and it first analyzes the video/image data to define the energy value for each voxel. Then, a 4-D graph is constructed and the costs are assigned according to the energy values. Finally, multiple 3-D surfaces are detected by a global optimization process which can be solved via s-t graph cuts. By removing or inserting these multiple 3-D surfaces, content-aware video/image resizing is achieved. We also have proved that our algorithm can find the globally optimal solution for crossing surfaces problem, in which several surfaces can cross each other. The proposed method is demonstrated on a variety of video/image data and compared to the state of the art in video/image resizing.