Abstract: In the existing sparsity-based image inpainting algorithms, only color information is used to measure the similarity between the exemplar to be filled and other exemplars, and the match patches of the exemplar to be filled are searched in the whole image. These decrease the structure connectivity and the neighborhood consistence of texture region, and increase the time complexity of these algorithm. To address these problems, the color-gradient distance between two exemplars is defined by the color and gradient norm information of them. Using the color-gradient distance, the new patch structure sparsity is constructed to determine the filling order, and the new match criterion is obtained to find the most similar patch. Furthermore, the size of local search region is adaptively decided by the patch structure sparsity values to decrease the time complexity of this algorithm. Also the weighting coefficients of color information and gradient information are different in different images, which is verified through experiments. Experimental results demonstrate that the proposed method has better ability to maintain the structure connectivity and the neighborhood consistence of texture area. The PSNR of repaired image by the proposed scheme is 1dB higher than that by the existing algorithms. Additionally, the speed of the proposed scheme is about 4 to 11 times of that of the existing algorithms.