This paper presents a novel gradient correlation similarity (Gcs) measure-based decolorization model for faithfully preserving the appearance of the original color image. Contrary to the conventional data-fidelity term consisting of gradient error-norm-based measures, the newly defined Gcs measure calculates the summation of the gradient correlation between each channel of the color image and the transformed grayscale image. Two efficient algorithms are developed to solve the proposed model. On one hand, due to the highly nonlinear nature of Gcs measure, a solver consisting of the augmented Lagrangian and alternating direction method is adopted to deal with its approximated linear parametric model. The presented algorithm exhibits excellent iterative convergence and attains superior performance. On the other hand, a discrete searching solver is proposed by determining the solution with the minimum function value from the linear parametric model-induced candidate images. The non-iterative solver has advantages in simplicity and speed with only several simple arithmetic operations, leading to real-time computational speed. In addition, it is very robust with respect to the parameter and candidates. Extensive experiments under a variety of test images and a comprehensive evaluation against existing state-of-the-art methods consistently demonstrate the potential of the proposed model and algorithms.