Abstract: A novel two stage method of image completion is proposed to handle structure discontinuities and block artifacts caused by traditional exemplar-based image completion algorithms. With the relevance of adjacent patches taken into consideration, a patch associated matching restoration algorithm, which is able to fix main structure in image, is performed on the down-sampling image. Meanwhile, according to the linear correlation of pixels and their eight neighbors in different resolution images, a super-resolution method based on noisy low-rank matrix filling is proposed and employed to refine the target image. This operation ensures the continuity of the changes in the detail information of texture and color. Experimental results demonstrate that the proposed method has more outstanding performance on natural images with gradual features.