MRF models have shown state-of-the-art performance for many computer vision tasks. In this work, we propose a non-local MRF model for image completion problem. The goal of image completion is to fill user specified "target" region with patches of "source" regions in a way that is visually plausible to an observer. We represent the patches in the target region of the image as random variables in an MRF, and introduce a novel energy function on these variables. Each variable takes a label from a label set which is a collection of patches of the source region. The quality of the image completion is determined by the value of the energy function. The non-locality in the MRF is achieved through long range pairwise potentials. These long range pairwise potentials are defined to capture the inherent repeating patterns present in heritage architectural images. We minimize this energy function using Belief Propagation to obtain globally optimal image completion. We have tested our method on a wide variety of images and shown superior performance over previously published results for this task. © 2012 ACM.