Image of the tomb mural has rich color, once destroyed it will lose a lot of structural information. Traditional algorithms restoring such image haven"t considered the priority of accurate restoration of strong structural information which results in repair area over extended and incoherent. To solve this problem, an image restoration algorithm based on structure factor and color clustering is proposed. Firstly, structure factor items are added in the priority calculation of repairing block. Secondly, search for similar block by color FCM clustering algorithm. Finally, depending on the size relationship between Average sum of Squared Differences (ASSD) and the set threshold, adaptively adjust the size of the repair block to achieve accurate matching of complex structure of the region. In this paper, experimental results show that a method of image restoration for the Northern Qi Dynasty tomb murals has a good result. Compared with Criminisi algorithm, structural similarity (SSIM) upgrades at least 5.68%.