Abstract: Video cutout refers to extracting moving objects from videos, which is an important step in many video editing tasks. Recent algorithms have limitations in terms of efficiency, interaction style and robustness. This paper presents a novel method for progressive video cutout with less user interaction and fast feedback. By exploring local and compact features, an optimization is constructed based on a graph model which establishes spatial and temporal relationship of neighboring patches in video frames. This optimization enables an efficient solution for progressive video cutout using graph cuts. Furthermore, a sampling-based method for temporally coherent matting is proposed to further refine video cutout results. Experiments demonstrate that our video cutout by paint selection is more intuitive and efficient for users than previous stroke-based methods, thus could be put into practical use.