Abstract: Ancient mural paintings are often suffered from damages such as color degradation, pigment peeling and even large-area shedding. Image inpainting techniques are widely used to virtually repair these damages. Firstly, we utilize the human-computer interaction techniques to complete missing structure information in the damaged areas according to the line drawings. Secondly, according to the classification of patches into textures and structures, a novel patch selection scheme from texture patch to structure patch is designed. Then, the order of patch structure complexity and the global randomly-selected strategy increase the inpainting accuracy and the efficiency. Finally, the sparse linear combination of candidate patches is constructed to sharply estimate the selected patch to be filled in a framework of sparse representation. Experimental results show the superior performance of the proposed method on damaged Dunhuang mural images.