The nonlocal means (NLM) filter has become a popular approach for denoising medical images due to its excellent performance. However, its heavy computational load has been an important shortcoming preventing its use. NLM works by averaging pixels in nonlocal vicinities, weighting them depending on their similarity with the pixel of interest. This similarity is assessed based on the squared difference between corresponding pixels inside local patches centered at the locations compared. Our proposal is to reduce the computational load of this comparison by checking only a subset of salient features associated to the pixels, which suffice to estimate the actual difference as computed in the original NLM approach. The speedup achieved with respect to the original implementation is over one order of magnitude, and, when compared to more recent NLM improvements for MRI denoising, our method is nearly twice as fast. At the same time, we evidence from both synthetic and in vivo experiments that computing of appropriate salient features make the estimation of NLM weights more robust to noise. Consequently, we are able to improve the outcomes achieved with recent state of the art techniques for a wide range of realistic Signal-to-Noise ratio scenarios like diffusion MRI. Finally, the statistical characterization of the features computed allows to get rid of some of the heuristics commonly used for parameter tuning.