As existed exemplar-based image inpainting algorithms have low efficiency and poor quality for searching the best match exemplar using global searching methods, this paper analyzes the reasons that effect on the efficiency and quality of these algorithms and proposes an image inpainting algorithm based on the regional segmentation and varying exemplar. Firstly, an original image is shrunken to a downscaling image with a size in 0.02-0.25 times that of an original one by the downscaling method, and the pre-selected regions in the downscaled image are segmented as the source regions. Then, the adjustment rule of adaptive window size is used to determine the fixed window size. By searching a best-exemplar from pre-selected region, the image is inpainted. For the inpainted downscaled image, the sub-image segmentation method is used to inpaint the regions of incomplete restoration again, and then fill them into the inpainted region of the original image. Iterating the above steps until the whole image inpainting is completed. Obtained results demonstrate that this method is 5~100 times the efficiency of the existed method, meanwhile it shows good image quality.