We present a learning-based approach to complete the missing parts of an image. Besides the conventional adopted image continuity and coherency heuristics, learnt image patches are used to better regularize the completion result. Through the learning process from a collection of commonly encountered natural images, we built a synthetic world consisting of scenes and their corresponding images. We further model the inter-patch relationships with a Markov Network. A belief propagation scheme is then used to choose and update a latent scene structure based on a maximal posterior probability estimation of the given image. The above operation usually converges within a few iterations. The obtained image is visually realistic.