Non-Local Means (NLMs) play important roles in image denoising, restoration, inpainting etc. due to its simple theory but effective performance. In this paper, in order to better remove noise without loss of image details, we further develop the NLMs based denoising method. It is realized by introducing a graph Laplacian regularization based weighting model and a multi-layer residual compensation strategy. Unlike the patch similarity based weights in classic NLMs filters, the graph Laplacian regularization defines the weights by considering 1) the distance between target pixel and the candidate pixel, 2) the local gradient and 3) the patch similarity. The proposed NLMs filter performs in a multi-layer framework to better remove the noise and smooth the result. The corresponding residuals at each layer are finally combined with the smooth image with learned weights to recover the image details. Experimental results show that our method is effective and robust, especially for piecewise-smooth images.