The l0 gradient regularization is an inverse problem which penalizes the l0 norm of the reconstructed image's gradient; it has several applications in image processing, ranging from edge extraction, clip-Art JPEG artifact removal to X-ray CT reconstruction. Current state-of-The art algorithms for solving these problems are ADMM based since the proximal operator resulting from a direct gradient-based approach is non-Trivial. In this paper we propose to use a quadratic envelope relaxation to the l0 gradient regularization problem, which results in a novel edge-preserving filtering model. To develop our new fast gradient-based algorithm we combine the use of convex envelopes for non-convex functionals along with the accelerated proximal gradient methodology. Our initial numerical results (Python based) show that our proposed algorithm, which currently targets the denoising problem, is competitive with the state-of-The-Art.