A novel image inpainting method based on sparse representation which combined image clustering and dictionary learning was proposed to solve the problems of long iteration time, bad adaptation and non-ideal results when using one single dictionary. Firstly, the broken image was divided into blocks and generated index matrix. Then Steering Kernel Regression Weight (SKRW) algorithm was used for image clustering. By exploring the inner structures of image and the information of intact area, blocks were sorted into categories based on their similarities of SKRW. Then each category had their own overcomplete dictionary by self-adaptive locality-sensitive dictionary learning. By building a self-adaptive local adaptor, the rate of convergence and the adaptability of sparse dictionary were improved. Multi-dictionaries were matched with different image structures, so the image would have a more accurate sparse representation. The dictionaries were updated until convergence, along with sparse coefficients as well. The image was finally restored after replacing patches back. Experimental results show that the proposed algorithm can repair the damaged images better than the state-of-the-art algorithms in both visual effect and objective evaluations. In addition, the time consumption is greatly reduced in comparison with the other algorithms.