OpenCV中K-means源码解析

#include "opencv2/highgui.hpp"
#include "opencv2/core.hpp"
#include "opencv2/imgproc.hpp"
#include <iostream>

using namespace cv;
using namespace std;

// static void help()
// {
//     cout << "\nThis program demonstrates kmeans clustering.\n"
//             "It generates an image with random points, then assigns a random number of cluster\n"
//             "centers and uses kmeans to move those cluster centers to their representitive location\n"
//             "Call\n"
//             "./kmeans\n" << endl;
// }

int main( int argc, char** argv )
{
    const int MAX_CLUSTERS = 5;
    Scalar colorTab[] =
    {
        Scalar(0, 0, 255),
        Scalar(0,255,0),
        Scalar(255,100,100),
        Scalar(255,0,255),
        Scalar(0,255,255)
    };

    Mat img(500, 500, CV_8UC3);
   
    RNG rng(12345); // 随机数产生器

    for(;;)
    {  
        int k, clusterCount = rng.uniform(2, MAX_CLUSTERS+1);
        int i, sampleCount = rng.uniform(1, 1001);
        int d=img.channels();
        Mat points(sampleCount, d, CV_32F,Scalar(10)), labels;
        
        clusterCount = MIN(clusterCount, sampleCount);
        std::vector<Point2f> centers;
 
        /* generate random sample from multigaussian distribution */
        for( k = 0; k < clusterCount; k++ )
        {
            Point center;
            center.x = rng.uniform(0, img.cols);
            center.y = rng.uniform(0, img.rows);
            Mat pointChunk = points.rowRange(k*sampleCount/clusterCount,
                                             k == clusterCount - 1 ? sampleCount :
                                             (k+1)*sampleCount/clusterCount);
            rng.fill(pointChunk, RNG::NORMAL, Scalar(center.x, center.y), Scalar(img.cols*0.05, img.rows*0.05));
        }
       
        randShuffle(points, 1, &rng);
       
        //聚类3次，取结果最好的那次，聚类的初始化采用PP特定的随机算法。
        //传入的center类型有问题
       /* double compactness = kmeans(points, clusterCount, labels,
            TermCriteria( TermCriteria::EPS+TermCriteria::COUNT, 10, 1.0),
               3, KMEANS_PP_CENTERS, centers);*/

 Mat Centers(clusterCount,1,points.type());//存储聚类后的中心点
          TermCriteria criteria=
    TermCriteria(TermCriteria::EPS+TermCriteria::COUNT,10,0.1);
    
    double compactness=kmeans(points, clusterCount, labels,criteria,3,KMEANS_PP_CENTERS,Centers);

       
       //用不同颜色显示
        img = Scalar::all(0);

        for( i = 0; i < sampleCount; i++ )
        {
            int clusterIdx = labels.at<int>(i);
            Point ipt = points.at<Point2f>(i);
            circle( img, ipt, 2, colorTab[clusterIdx], FILLED, LINE_AA );
        }
 
        // 每个聚类的中心来绘制圆
       // for (i = 0; i < (int)centers.size(); ++i)
      //  {
       //     Point2f c = centers[i];
       //     circle( img, c, 40, colorTab[i], 1, LINE_AA );
       // }

          //打印最后聚类中心点的坐标
   for(int i=0;i<Centers.rows;i++)
   {
       int x=Centers.at<float>(i,0);
       int y=Centers.at<float>(i,1);

       cout<<"centers: "<<i<<" "<<x<<" "<<y<<" "<<endl;
       circle( img, Point(x,y), 40, colorTab[i], 1, LINE_AA );
   }
       cout << "Compactness: " << compactness << endl;

        imshow("clusters", img);

        char key = (char)waitKey();
        if( key == 27 || key == 'q' || key == 'Q' ) // 'ESC'
            break;
    }

    return 0;
}

 void RNG::fill
(
  InputOutputArray mat,
  int distType, 
  InputArray a, 
  InputArray b, 
  bool saturateRange=false 
)

 void randShuffle
(
  InputOutputArray dst, 
  double iterFactor=1., 
  RNG* rng=0 
)

//_data:特征向量集；K:聚类中心个数；_bestLabels:每个特征向量隶属聚类中心索引
 //criteria:迭代算法终止条件；attempts：尝试次数；
 //第一次尝试初始化采取策略；_centers：存放聚类中心   
double cv::kmeans( InputArray _data, int K,
                   InputOutputArray _bestLabels,
                   TermCriteria criteria, int attempts,
                   int flags, OutputArray _centers )
{
    const int SPP_TRIALS = 3;
    Mat data = _data.getMat();
    int N = data.rows > 1 ? data.rows : data.cols;//N表示特征向量个数
    int dims = (data.rows > 1 ? data.cols : 1)*data.channels();//dims表示特征向量维度
    int type = data.depth();//数据类型，应为32位浮点数
 
    attempts = std::max(attempts, 1);//至少尝试一次
    CV_Assert( data.dims <= 2 && type == CV_32F && K > 0 );
 
    _bestLabels.create(N, 1, CV_32S, -1, true);//确定_bestLabels为N*1大小矩阵，类型为32为有符号整型，每个特征向量对应一个，
    
    Mat _labels, best_labels = _bestLabels.getMat();
    if( flags & CV_KMEANS_USE_INITIAL_LABELS )
    {
        CV_Assert( (best_labels.cols == 1 || best_labels.rows == 1) &&
                  best_labels.cols*best_labels.rows == N &&
                  best_labels.type() == CV_32S &&
                  best_labels.isContinuous());
        best_labels.copyTo(_labels);//如果首次是由用户指定的的，则将内容复制到_labels中
    }
    else
    {
        if( !((best_labels.cols == 1 || best_labels.rows == 1) &&
             best_labels.cols*best_labels.rows == N &&
            best_labels.type() == CV_32S &&
            best_labels.isContinuous()))
            best_labels.create(N, 1, CV_32S);
        _labels.create(best_labels.size(), best_labels.type());//否则，手动创建_labels，
    }
    int* labels = _labels.ptr<int>();//_labels中内容为32有符号整型数据
 
    Mat centers(K, dims, type), old_centers(K, dims, type);//创建centers，
    vector<int> counters(K);//用于计数每个center所管辖的特征向量数目
    vector<Vec2f> _box(dims);//在随机生成center，确定每一维的上下界
    Vec2f* box = &_box[0];
 
    double best_compactness = DBL_MAX, compactness = 0;//DBL_MAX,64位浮点数最大取值
    RNG& rng = theRNG();//Returns the default random number generator.随机数产生器
    int a, iter, i, j, k;
 
    if( criteria.type & TermCriteria::EPS )//stop the algorithm after the achieved algorithm-dependent accuracy becomes lower than epsilon
    //算法精度小于epsilon时结束循环
        criteria.epsilon = std::max(criteria.epsilon, 0.);
    else
        criteria.epsilon = FLT_EPSILON;
    criteria.epsilon *= criteria.epsilon;
 
    if( criteria.type & TermCriteria::COUNT )//最大迭代次数
        criteria.maxCount = std::min(std::max(criteria.maxCount, 2), 100);//最多迭代100次，最小为2次
    else
        criteria.maxCount = 100;
 
    if( K == 1 )
    {
        attempts = 1;//尝试一次，
        criteria.maxCount = 2;//最大循环次数为2次
    }
 
    const float* sample = data.ptr<float>(0);//获得第一个特征向量
    
    for( j = 0; j < dims; j++ )
        box[j] = Vec2f(sample[j], sample[j]);//box[j]是vec2f，内容是第一个特征向量的内容
 
    for( i = 1; i < N; i++ )
    {
        sample = data.ptr<float>(i);//获得第i个特征向量
        for( j = 0; j < dims; j++ )
        {
            float v = sample[j];
            box[j][0] = std::min(box[j][0], v);
            box[j][1] = std::max(box[j][1], v);
        }
    }
         //box中第i个元素中内容：[所有特征向量中第i维的最小值，特征向量第i维内容的最大值]。
    for( a = 0; a < attempts; a++ )//算法尝试次数为attempts次
    {
        double max_center_shift = DBL_MAX;//设定中心最大偏移为极大值
        for( iter = 0; iter < criteria.maxCount && max_center_shift > criteria.epsilon; iter++)//当迭代次数小于maxcount，中心偏移量大于epsilon时循环继续
        {
            swap(centers, old_centers);//交换
            //循环初始，需要对centers进行初始化操作，这里主要是两种，一个是random，另一个是kmeans++算法
            //之后根据初始化的centers对leibels进行分配
            //若为人工指定，labels，则直接进行else内容
            if( iter == 0 && (a > 0 || !(flags & KMEANS_USE_INITIAL_LABELS)) )
            {
                if( flags & KMEANS_PP_CENTERS )
                    generateCentersPP(data, centers, K, rng, SPP_TRIALS);
                else
                {
                    for( k = 0; k < K; k++ )
                        //随机产生K个center，每个center的每一维的内容是在_box[min,max]区间取值
                        generateRandomCenter(_box, centers.ptr<float>(k), rng);
                }
            }
            else//不再是 第一次循环或labels内容为人工指定，labels中已经存在值，且保存 old centers
            {
                if( iter == 0 && a == 0 && (flags & KMEANS_USE_INITIAL_LABELS) )
                {
                    for( i = 0; i < N; i++ )
                        CV_Assert( (unsigned)labels[i] < (unsigned)K );
                }
            
                // compute centers
                centers = Scalar(0);//对centers进行初始化操作，原本内容是old centers，需要进行清零操作
                for( k = 0; k < K; k++ )
                    counters[k] = 0;//对counter进行初始化操作，，是统计每个center包含特征向量个数么？
                
                //该for循环结束，每个center中的内容是所有隶属于该center的特征向量的数值,累加求和
                //counters计数隶属中心的特征向量的个数
                for( i = 0; i < N; i++ )//对每个特征向量进行分析
                {
                    sample = data.ptr<float>(i);//得到该特征向量
                    k = labels[i];//得到该特征向量隶属中心 索引。labels是在什么时候初始化的，labels在第一次循环时进行赋值，或人工指定，之后在每次循环中进行赋值
                    float* center = centers.ptr<float>(k);//得到该特征向量隶属聚类中心
                    //center中的值初始为零
                    //for循环的作用是将特征向量的内容累加到center中，，并且利用 +4 操作，减少循环次数
                    for( j = 0; j <= dims - 4; j += 4 )
                    {
                        float t0 = center[j] + sample[j];
                        float t1 = center[j+1] + sample[j+1];
 
                        center[j] = t0;
                        center[j+1] = t1;
 
                        t0 = center[j+2] + sample[j+2];
                        t1 = center[j+3] + sample[j+3];
 
                        center[j+2] = t0;
                        center[j+3] = t1;
                    }
                    //将上一个for循环中剩的一点尾巴累加进去
                    for( ; j < dims; j++ )
                        center[j] += sample[j];
                        
                    counters[k]++;
                }
 
                if( iter > 0 )
                    max_center_shift = 0;
 
                for( k = 0; k < K; k++ )
                {
                    float* center = centers.ptr<float>(k);//得到第k个中心内容，
                    //对第k个center取所隶属特征向量的均值
                    if( counters[k] != 0 )
                    {
                        float scale = 1.f/counters[k];
                        for( j = 0; j < dims; j++ )
                            center[j] *= scale;
                    }
                    else
                    //如果当前center中没有内容，也就是没有特征向量隶属于该中心，则重新生成center
                        generateRandomCenter(_box, center, rng);
                    //不再是第1次循环，，此时将存在old center,能够计算两次循环的中心偏移量
                    if( iter > 0 )
                    {
                        double dist = 0;
                        const float* old_center = old_centers.ptr<float>(k);
                        for( j = 0; j < dims; j++ )
                        {
                            double t = center[j] - old_center[j];
                            dist += t*t;
                        }
                        //此时将计算最大偏移量，如果小于设定值将结束循环
                        max_center_shift = std::max(max_center_shift, dist);
                    }
                }
            }
 
            // assign labels  重新分配labels
            compactness = 0;
            for( i = 0; i < N; i++ )
            {
                sample = data.ptr<float>(i);
                int k_best = 0;
                double min_dist = DBL_MAX;
                //该循环的结束将得到距离特征向量最近的聚类中心（该聚类中心是本次循环重新生成的）
                for( k = 0; k < K; k++ )
                {
                    const float* center = centers.ptr<float>(k);
                    double dist = distance(sample, center, dims);//计算该特征向量到某个center的距离
 
                    if( min_dist > dist )
                    {
                        min_dist = dist;
                        k_best = k;
                    }
                }
 
                compactness += min_dist;
                labels[i] = k_best;//对labels进行赋值，确定当前特征向量隶属聚类中心
            }
        }
        //compactness,将记录所有距离，这里的距离是指，所有的特征向量到其聚类中心的距离之和，用于评价当前的聚类结果
        if( compactness < best_compactness )
        {
            best_compactness = compactness;
            if( _centers.needed() )
                centers.copyTo(_centers);
            _labels.copyTo(best_labels);
        }
    }
 
    return best_compactness;
}