Image and video retargeting using Graph Cuts

Graph Cuts theory has been widely applied in the fields of network flow analysis, computer vision, computer graphics, and so on. In this paper, we use an approach of Graph Cuts to realize image and video retargeting. We regard image retargeting as a problem of energy minimization, so we construct a residual and directed graph based on the gradient of pixel value to find the cut path with minimal energy. Using pre-flow push algorithm and breadth-first search (BFS) algorithm, we obtain a labeled graph which is saturated. According to the labeled graph, we can find the minimal cut path, which is removed to reduce one row or column of image. On the basis of image retargeting, we retarget a video by taking the relevance of frames in temporal into account. We consider the inserted energy due to new edges created by previously non adjacent pixels that become neighbors after the cut removing. Experiments show that our method is satisfactory in image and video retargeting in visual effect.