Speckle noise is a characteristic artifact in breast ultrasound images, which hinders substantive information essential for clinical diagnosis. In this article, we have investigated the use of Non-local means (NLM) filter, which is robust against severe noise, to remove speckle noise in breast ultrasound images. Medical diagnosis systems cannot employ traditional NLM filters, which exhibit the slowest performance due to their computational burden during the weighted averaging process. We have integrated a novel automated clustering based preclassification scheme using spatial regularized fuzzy c means (FCM) to alleviate the process. The appropriate number of clusters for each image is calculated automatically through Gap statistics. Moreover, the rotationally invariant moment distance measure increases the chance of getting more similar regions for NLM process. The algorithm is evaluated on a breast ultrasound database, which consists of 54 images including 28 benign and 26 malignant. Two statistical measures, Pratt’s figure of merit (PFM) and equivalent number of looks (ENL), are used to evaluate the noise suppression performance as well as the capability of preserving the fine details. The results of the proposed method are compared with the other three state of the art methods quantitatively. The proposed method demonstrated excellent despeckling performance with PFM of 0.91 and ENL of 7.415. The robustness against speckle noise and the acceptable processing time make the method more appropriate for computer aided diagnosis systems.