Noise reduction is one of the most important topics of digital image processing and despite the fact that it has been studied for a long time it remains the subject of active research. In the following work, we present an extension of the Mean Shift technique, which is efficiently reducing the Gaussian noise, so that it is able to cope with the impulsive disturbances. Furthermore, the elaborated technique can be applied to enhance the images corrupted by a mixture of strong Gaussian and impulsive noise, severely decreasing the quality of color digital images. By means of our approach, which is based on a novel similarity measure between a pixel and a patch located in the center of the processing block, even heavily disturbed images can be effectively restored, which enables the success of further stages of the image processing pipeline. We evaluate the efficiency of the proposed method using a publicly available database of test color images and compare the restored images applying a set of standard quality metrics with the results delivered by state-of-the-art denoising methods. Additionally, we compare our method with the Medoid and Quick Shift techniques, accelerating the original Mean Shift algorithm, in terms of objective quality criteria and computational complexity. The results of the performed experiments indicate that the proposed technique is superior to the widely used denoising techniques and can be used as a robust extension of the Mean Shift procedure. In the paper, a particular emphasis is placed on the ability of the presented algorithm to preserve and enhance image edges. The performed experiments evaluated with the use of the Pratt's index, quantitatively confirm the superiority of the proposed design over the Mean Shift and standard denoising methods. The preservation of edges and even their sharpening is a very important feature of our algorithm whereas the final goal is segmentation, playing a crucial role in various computer vision tasks. The proposed algorithm is intended for the mixed noise reduction in color images, but it can be also applied in multispectral imaging and clustering of multidimensional data. To enable the comparison of our method with the standard denoising techniques and to help applying it in other image processing fields, we made its code freely available.