An effective grayscale image colorization technique is presented in this paper by annotating the image with a few color scribbles. A cost function from a local linear model optimization assumption on Lab color channels is designed and derived. By taking advantage of the matting Laplacian matrix

the local linear model optimization can produce high quality colorizations as existing methods

while having better performance in color bleeding with sparse constraints. Our local linear model optimization is actually the global optimum of the cost function

which can be solved with a sparse linear system. We further improve the performance of our primary model to use diffusion distances instead of Euclidean distances for the construction of the matting Laplacian matrix. The experimental results show that fewer scribbles are required and better colorizations are produced with the improved diffusion distances based optimization model.