Abstract: As an effective patch-based denoising method, non-local means (NLM) method achieves favorable denoising performance over its local counterparts and has drawn wide attention in image processing community. The implementation of NLM can formally be decomposed into two sequential steps, i.e., computing the weights and using the weights to compute the weighted means. In the first step, the weights can be obtained by solving a regularized optimization. And in the second step, the means can be obtained by solving a weighted least squares problem. Motivated by such observations, we establish a two-step regularization framework for NLM in this paper. Meanwhile, using the framework, we reinterpret several non-local filters in the unified view. Further, taking the framework as a design platform, we develop a novel non-local median filter for removing salt-pepper noise with encouraging experimental results.