Abstract: Considering tremendous relativity on the luminance and chromatic channels for pixels between image neighborhoods, we proposed a new search method for grayscale image colorization.First, the algorithm selected some pixels by constant step incremental way spatially, and then colorized them using global optimization search strategy that the best matching color sample was selected from the color image.Next, the algorithm finished the colorization procedure for the other uncolored pixels using local optimization search strategy from the neighborhoods pixels.The experiments demonstrate that the new search strategy improves the speed of colorizing obviously, keeps the continuity of the colored image in color space and does not damage the colorizing quality.In order to avoid channel-cross, the colorization procedure for grayscale image was done in laβ color space, which was developed to minimize correlation among three coordinate axes in color space.