C++ Template of Mean Shift

Introduction

This is a simple C++ template of Mean Shift method implemented by Shuo Jin.

Date Structure:

• ms_vec - a simple vector with some basic operations
• ms_vec_clstr - a cluster (mode) generated from mean shift
• mean_shift - mean shift method

The result of mean shift is dependent on the predefined parameters:

1. epsilon - the condition to determine the termination of a mean shift process.
2. mode_bound - the condition to determine if a vector generated by mean shift belongs to an existing cluster.
3. max_iter_ size - the allowed maximum step in doing mean shift for a vector
4. knn_search_num - the number of nearest neigbors to compute mean shift locally for speedup

Please refer to the comments in mean_shift.h for more information.

Example

#include "mean_shift.h"
#include <random>

int main()
{
    // generate random 2D samples for testing
    std::normal_distribution<double> rand_generator1(0.0, 1.0);
    std::normal_distribution<double> rand_generator2(5.0, 1.0);
    std::normal_distribution<double> rand_generator3(-5.0, 1.0);

    std::default_random_engine gen;

    mean_shift_d2 ms_clstr;  // or mean_shift<double, 2>

    ms_vec_d2 vec;  // or ms_vec<double, 2>

    for (size_t i = 0; i < 500; ++i)
    {       
        vec[0] = rand_generator1(gen);
        vec[1] = rand_generator1(gen);

        ms_clstr.add_vec(vec);
    }

    for (size_t i = 0; i < 500; ++i)
    {
        vec[0] = rand_generator2(gen);
        vec[1] = rand_generator2(gen);

        ms_clstr.add_vec(vec);
    }

    for (size_t i = 0; i < 500; ++i)
    {
        vec[0] = rand_generator3(gen);
        vec[1] = rand_generator3(gen);

        ms_clstr.add_vec(vec);
    }

    // set the mode_bound
    ms_clstr.set_mode_bound(4);

    // do mean shift for all vectors
    ms_clstr.find_modes(); 

    // output
    ms_clstr.output_on_console();

    // get the cluster index of each vector which it belongs to
    //for (size_t i = 0; i < 300; ++i)
    //{
    //  std::cout << ms_clstr.clstr_idx_of_vec(i) << " ";
    //}

    return 0;
}

Output

Init...
Mean Shift Progress: 100%
Total time: 0.506 secs
[0.00470099 6.70585e-005]
[5.0497 5.01514]
[-4.98043 -4.97895]
MS CLSTR COUNT = 3

Dependency

ANN Library should be configured properly to use this template. You can specify the path at the beginning of mean_shift.h

Download

The code is available here.

Reference

1. Mean shift: a robust approach toward feature space analysis. [Link]
2. The variable bandwidth mean shift and data-driven scale selection. [Link]
3. A blog introducing mean shift. [Link]