Abstract: Image completion, which aims to remove objects or recover the damaged portions in a given image, is an important task in photo editing. Recently, exemplar-based methods are considered to complete images with large portions removed. However, structure inconsistency of the reconstructed texture often appear when using those methods. In this paper, a new exemplar-based algorithm is proposed to obtain global texture consistency by using global optimization. First, an energy function is defined for measuring the quality of the reconstructed region. Then, the image completion problem is formulated as minimization of the energy function which is done in an iterative form. Finally, the slight color differences between the known region and the filled region are revised by the Poisson image editing method. Compared with the existing exemplar-based methods which do greedy region-growing, the proposed method not only reconstructs the local color texture of missing region, but also preserves the global structural texture of the image. An adaptive sampling method, which is based on the saliency map of the image, is also adopted to construct the searching space. It dramatically reduces the searching space and accelerates the nearest neighbor searching. The effectiveness of the proposed method is demonstrated on several examples and comparisons.