Click or drag to resize
Accord.NET (logo) MeanShift Class
Mean shift clustering algorithm.
Inheritance Hierarchy
SystemObject
  Accord.MachineLearningParallelLearningBase
    Accord.MachineLearningMeanShift

Namespace:  Accord.MachineLearning
Assembly:  Accord.MachineLearning (in Accord.MachineLearning.dll) Version: 3.4.0
Syntax
[SerializableAttribute]
public class MeanShift : ParallelLearningBase, IClusteringAlgorithm<double[]>, 
	IUnsupervisedLearning<IClusterCollection<double[]>, double[], int>, 
	IUnsupervisedLearning<MeanShiftClusterCollection, double[], int>
Request Example View Source

The MeanShift type exposes the following members.

Constructors
  NameDescription
Public methodMeanShift
Creates a new MeanShift algorithm.
Top
Properties
  NameDescription
Public propertyBandwidth
Gets or sets the bandwidth (radius, or smoothness) parameter to be used in the mean-shift algorithm.
Public propertyClusters
Gets the clusters found by Mean Shift.
Public propertyComputeLabels
Gets or sets whether cluster labels should be computed at the end of the learning iteration. Setting to False might save a few computations in case they are not necessary.
Public propertyComputeProportions
Gets or sets whether cluster proportions should be computed at the end of the learning iteration. Setting to False might save a few computations in case they are not necessary.
Public propertyDimension
Gets the dimension of the samples being modeled by this clustering algorithm.
Public propertyDistance
Public propertyMaximum
Gets or sets the maximum number of neighbors which should be used to determine the direction of the mean-shift during the computations. Default is zero (unlimited number of neighbors).
Public propertyMaxIterations
Gets or sets the maximum number of iterations to be performed by the method. If set to zero, no iteration limit will be imposed. Default is 0.
Public propertyParallelOptions
Gets or sets the parallelization options for this algorithm.
(Inherited from ParallelLearningBase.)
Public propertyToken
Gets or sets a cancellation token that can be used to cancel the algorithm while it is running.
(Inherited from ParallelLearningBase.)
Public propertyTolerance
Gets or sets the relative convergence threshold for stopping the algorithm. Default is 1e-5.
Public propertyUseAgglomeration
Gets or sets whether to use the agglomeration shortcut, meaning the algorithm will stop early when it detects that a sample is going to follow the same path as another sample when running in parallel.
Public propertyUseParallelProcessing Obsolete.
Gets or sets whether the algorithm can use parallel processing to speedup computations. Enabling parallel processing can, however, result in different results at each run.
Public propertyUseSeeding
Gets or sets whether to use seeding to initialize the algorithm. With seeding, new points will be sampled from an uniform grid in the range of the input points to be used as seeds. Otherwise, the input points themselves will be used as the initial centroids for the algorithm.
Top
Methods
  NameDescription
Public methodCompute(Double) Obsolete.
Divides the input data into clusters.
Public methodCompute(Double, Int32) Obsolete.
Divides the input data into clusters.
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Public methodLearn(Double, Double)
Learns a model that can map the given inputs to the desired outputs.
Public methodLearn(Double, Int32)
Learns a model that can map the given inputs to the desired outputs.
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Top
Extension Methods
  NameDescription
Public Extension MethodHasMethod
Checks whether an object implements a method with the given name.
(Defined by ExtensionMethods.)
Public Extension MethodToTOverloaded.
Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime.
(Defined by ExtensionMethods.)
Public Extension MethodToTOverloaded.
Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime.
(Defined by Matrix.)
Top
Remarks

Mean shift is a non-parametric feature-space analysis technique originally presented in 1975 by Fukunaga and Hostetler. It is a procedure for locating the maxima of a density function given discrete data sampled from that function. The method iteratively seeks the location of the modes of the distribution using local updates.

As it is, the method would be intractable; however, some clever optimizations such as the use of appropriate data structures and seeding strategies as shown in Lee (2011) and Carreira-Perpinan (2006) can improve its computational speed.

References:

  • Wikipedia, The Free Encyclopedia. Mean-shift. Available on: http://en.wikipedia.org/wiki/Mean-shift
  • Comaniciu, Dorin, and Peter Meer. "Mean shift: A robust approach toward feature space analysis." Pattern Analysis and Machine Intelligence, IEEE Transactions on 24.5 (2002): 603-619. Available at: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1000236
  • Conrad Lee. Scalable mean-shift clustering in a few lines of python. The Sociograph blog, 2011. Available at: http://sociograph.blogspot.com.br/2011/11/scalable-mean-shift-clustering-in-few.html
  • Carreira-Perpinan, Miguel A. "Acceleration strategies for Gaussian mean-shift image segmentation." Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on. Vol. 1. IEEE, 2006. Available at: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1640881

Examples

The following example demonstrates how to use the Mean Shift algorithm for a simple clustering data task.

// Use a fixed seed for reproducibility
Accord.Math.Random.Generator.Seed = 0;

// Declare some data to be clustered
double[][] input = 
{
    new double[] { -5, -2, -4 },
    new double[] { -5, -5, -6 },
    new double[] {  2,  1,  1 },
    new double[] {  1,  1,  2 },
    new double[] {  1,  2,  2 },
    new double[] {  3,  1,  2 },
    new double[] { 11,  5,  4 },
    new double[] { 15,  5,  6 },
    new double[] { 10,  5,  6 },
};

// Create a uniform kernel density function
UniformKernel kernel = new UniformKernel();

// Create a new Mean-Shift algorithm for 3 dimensional samples
MeanShift meanShift = new MeanShift(dimension: 3, kernel: kernel, bandwidth: 2);

// Learn a data partitioning using the Mean Shift algorithm
MeanShiftClusterCollection clustering = meanShift.Learn(input);

// Predict group labels for each point
int[] labels = clustering.Decide(input);

// As a result, the first two observations should belong to the
//  same cluster (thus having the same label). The same should
//  happen to the next four observations and to the last three.

The following example demonstrates how to use the Mean Shift algorithm for color clustering. It is the same code which can be found in the color clustering sample application.

 int pixelSize = 3;   // RGB color pixel
 double sigma = 0.06; // kernel bandwidth

 // Load a test image (shown below)
 Bitmap image = ...

 // Create converters
 ImageToArray imageToArray = new ImageToArray(min: -1, max: +1);
 ArrayToImage arrayToImage = new ArrayToImage(image.Width, image.Height, min: -1, max: +1);

 // Transform the image into an array of pixel values
 double[][] pixels; imageToArray.Convert(image, out pixels);

 // Create a MeanShift algorithm using given bandwidth
 //   and a Gaussian density kernel as kernel function.
 MeanShift meanShift = new MeanShift(pixelSize, new GaussianKernel(3), sigma);

 // We will compute the mean-shift algorithm until the means
 // change less than 0.5 between two iterations of the algorithm
 meanShift.Tolerance = 0.05;
 meanShift.MaxIterations = 10;

// Learn the clusters in the data
 var clustering = meanShift.Learn(pixels);

 // Use clusters to decide class labels
 int[] idx = clustering.Decide(pixels);

 // Replace every pixel with its corresponding centroid
 pixels.ApplyInPlace((x, i) => meanShift.Clusters.Modes[idx[i]]);

 // Retrieve the resulting image in a picture box
 Bitmap result; arrayToImage.Convert(pixels, out result);

The original image is shown below:

The resulting image will be:

See Also