## DN MS - Denoise - Mean Shift

(3/10/11)

PURPOSE

Denoise and smooth an image or volume using a mean shift filter. The mean shift filter is a dynamic nonlinear filter linked to a bilateral filter, and achieves high quality discontinuity-preserving filtration.   Example.

 CE FIT [Contrast Enhancement - FIT the histogram] CE GNC [Contrast Enhancement - Graduated Non Convex restoration] DN AD [Denoise - Anisotropic Diffusion] DN MED [Denoise - Median Filtering]

USAGE

.OPERATION: DN MS

.INPUT FILE: PIC001
[Enter name of image/volume to be processed.]

.OUTPUT FILE: PIC002
[Enter name of file receiving the output image/volume.]

[Enter filter radius. This is the half-width of the spatial window. Radii in the range 3-7 pixels/voxels are commonly used.]

.DENSITY DISTANCE FACTOR (or <CR> for default): 1.0
[Enter a factor which will be multiplied by the standard deviation of densities in the input file to obtain a density distance. For our images a density distance in the range 0.5...2 times standard deviation often yields good results.

NOTES

1. A two or three dimensional (2D or 3D) mean shift filter is applied to the image or volume file. Uniform circular and spherical kernels are used for 2D or 3D files respectively in this implementation.

2. Algorithm:
a. Start at a point 'A'.
b. Select the pixels/voxels falling within a certain spatial distance (kernel) and within certain density distance.
c. Calculate the center of mass of the set of selected pixels/voxels, and displace the center of kernel to the center of mass.
d. Repeat iteratively until the spatial variation is lower than 2/3 of a kernel radius.
e. Apply the mean density of selected pixels around the final point 'B' (the mode) to starting point 'A'. Calculation of mean density inside kernel involves only pixels/voxels within an appointed density distance. In some other implementations the density of final point 'B' itself is used.
f. Repeat for all pixels/voxels in the image.

3. As proposed (Comaniciu & Meer), the mean shift algorithm will always converge, but this convergence is only guaranteed for infinitesimal steps. We observed "bad circling" in some points of real EM micrographs (presumably, due to a rounding of the centers of mass to discrete values), and inserted code to limit the iterations by the setting a lower bound for the magnitude of the mean shift (2/3 of a kernel radius) and by a hard limitation on number of iterations.

4. References: K. Fukunaga K and L.D. Hostetler.
"The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition"
IEEE Trans. Information Theory, vol.: 21, 32-40 (1975).
Comaniciu, D. and P. Meer.
"Mean Shift: A Robust Approach Toward Feature Space Analysis"
IEEE. Trans. Pattern Analysis and Machine Intelligence, vol: 24, 603-619 (2002).
Bilbao-Castro, J.R., Sorzano,C.O.S, García, I, and J.J. Fernández.
"XMSF: Structure-preserving noise reduction and pre-segmentation in electron microscope tomography"
Bioinformatics vol: 26, 2786-2787 (2010).

5. Implemented by Gregory Kishchenko.

SUBROUTINES

MEANSHIFT

CALLER

UTIL7