Abstract: Grayscale image colorization requires user interactions to complete the colorization optimization process.Existing methods only aims to the colorization effect and do not take into consideration the interaction experience.A novel GPU-accelerated near real-time image colorization method is proposed by taking advantage of high-performance parallelism of the GPU.In the preprocessing step,this method uses a patch-based Patch Match algorithm to search K-nearest neighbors for each pixel on the global image space and then introduces a parallel construction algorithm for the compressed symmetry sparse matrix to ensure the equivalent propagation of colors between neighboring pixels.During the user interaction,this method builds an energy function according to the user input and outputs the colorized image by using the parallel conjugate gradient solver.Experimental results show that the proposed method can not only produce high-quality colorized images but also achieve near real-time performance.