In this paper, we present a novel formulation of exemplar-based image inpainting as a metric labeling problem, and solve it through the simulated annealing algorithm. Due to their greedy nature, exemplar-based methods sometimes produce inpainted images, which are visually inconsistent. These methods are highly dependent upon the initialization. To solve these problems, we generate five images with a different initialization. A suitable mixture of these five images produces a good inpainted image. The cost function of the proposed metric labeling problem consists of three components, namely, neighbor cost, total variation cost, and structure cost. A linear combination among these components is used to maintain better visual consistency in the inpainted region having smooth transition from the bordering regions of the source image. We use a quality measure to this end. Our experiments on a wide variety of images demonstrate that the proposed technique produces better inpainting images as compared with some other state-of-the-art techniques.