Abstract: An image inpainting algorithm based on dictionary update and optimal similarity search was proposed in this paper. by analysis sparse representation of signals, to find the relationship between the target signal and the dictionary matrix and the coefficient vector, define SSIM index used to generate a dictionary matrix; then, the maximum value of linear combination approximation based on SSIM index is calculated, used to select the optimal atom in dictionary matrix, and calculate the optimal coefficient vector, use the optimal coefficient vector calculate the sum of the SSIM index to becomes the highest, and update each atom in dictionary matrix, to generate a new dictionary matrix; finally, the target patch is approximated by a sparse linear combination of the atoms of the new dictionary matrix using, introduce the SSIM index as the approximation performance, the optimal reconstruction results maximizing the SSIM index can be obtained, to complete the image inpainting. The experiment results showed that: this algorithm had better visual effect and structural similarity, reduce the blurring effect, and overcome the discontinuous texture effect in inpainting of images with large area damaged image.