Abstract: This paper presents a new exemplar-based framework for completing video with large space-time holes,considering video completion as a process of global optimization on a 3D graph embedded in the space-time video volume. It first sets up a 3D Markov Random Field (MRF) on the missing holes, then proposes a new global discrete optimization function, which converts the video completion into multi-label problem in MRF, and enforces global spatio-temporal consistency among patches that fill the holes, in terms of both color similarity and motion similarity. The optimization is accomplished by a novel algorithm, called smart belief propagation, which is significantly better than the standard belief propagation, in terms of completion quality, computational efficiency and storage size. In addition, by incorporating motion information, we introduce a more effective and accurate spatio-temporal patch similarity metric, which leads to more visually pleasing completion results. Experiments on several complex dynamic scenes demonstrate that the missing salient video structures and motion information are much better restored by the proposed methods than the existing ones.