Home > programming > OpenCV中kmean算法的实现

OpenCV中kmean算法的实现

  我自己的Kmean算法的实现看起来是有大的问题了,虽然不能从代码中看出问题的所在,不过生成图像说明了一切,一个有蓝天白云的图片经过我的cluster算法以后白云居然不见了。我暂时还没有找到问题的所在。查找这种纯数据运算的算法bug真的是很费劲。这些天又在看OpenCV,于是就打算看看OpenCV里面的KMean算法的具体实现,在这里记录一下我的理解,以备查验。

  我的OpenCV的版本是2.3.1. 其中Kmean的实现在modulescoresrcmatrix.cpp里面,所有的实现都在

double cv::kmeans( InputArray _data, int K,  InputOutputArray _bestLabels, TermCriteria criteria, int attempts, int flags, OutputArray _centers ) 这个函数里面。

当然,其实我调用的函数是static double cppKMeans()这个函数,而这个函数只是简单的检查一下参数,最终还是会调用到 cv::kmeans(…)这个函数中去得

cv::kmeans()这个函数的参数对于我这种OpenCV的初学者来说也是一种很痛苦的东西,瞎弄了半天才搞清楚是怎么一回事。

_data: 这个就是你要处理的数据,例如是一个CvMat数据

K : 你需要最终生成的cluster的数量

_bestLabels: 当cv::kmeans执行完毕以后, _bestLabels里面储存的就是每一个对应的数据元素所在的cluster的index,这样你就可以更新你的数据了

criteria: 这个东西是用来告诉cv::kmeans以一个什么样的停止条件来运行,例如criteria.epsilon = 0.01f;criteria.type = CV_TERMCRIT_EPS; 这个表示centers在两轮cluster运行以后的距离差,如果这个距离小于等于criteria.epsilon就停止返回当前得到的centers,否则继续

attempts: 最多尝试多少次,文档上说一般设置为2

flags: 这个主要是传递一些配置参数,例如 初始的时候使用user code给定的label –KMEANS_USE_INITIAL_LABELS,使用kmeans++初始化算法– KMEANS_PP_CENTERS

_centers: 这个就是我们想要的结果了,该函数运行完毕以后,这个变量里面储存所有的center的数据,也就是你想要的东西了

下面我们来看看kmeans的具体实现。

前面部分的参数初始化和检验之类的就略过了,直接进入算法部分。

    for( a = 0; a < attempts; a++ )
    {//尝试多少次,一般为2
        double max_center_shift = DBL_MAX;
        for( iter = 0; iter < criteria.maxCount && max_center_shift > criteria.epsilon; iter++ )
        {//退出循环的条件是达到最大的循环次数criteria.maxCount 或者 center的差小于等于criteria.epsilon
            swap(centers, old_centers);//保存centers的数据到old_centers中去
 
            if( iter == 0 && (a > 0 || !(flags & KMEANS_USE_INITIAL_LABELS)) )
            {//如果是第一次运行且不使用user code提供的labels,那就由该算法提供center的初始化
                if( flags & KMEANS_PP_CENTERS )
                    generateCentersPP(data, centers, K, rng, SPP_TRIALS);//用kmeans++算法来初始化center,这个我没有没有搞懂是咋回事,略过
                else
                {
                    for( k = 0; k < K; k++ )
                        generateRandomCenter(_box, centers.ptr<float>(k), rng);
                }
            }
            else
            {
                if( iter == 0 && a == 0 && (flags & KMEANS_USE_INITIAL_LABELS) )
                {//如果是user code提供的labels,需要检查一下数据是否有效
                    for( i = 0; i < N; i++ )
                        CV_Assert( (unsigned)labels[i] < (unsigned)K );
                }
            
                // compute centers
                centers = Scalar(0);//不知道Scalar是个什么东西,不过可以猜到这个目的是为了将centers中的数据置为0,希望没有猜错
                for( k = 0; k < K; k++ )
                    counters[k] = 0;//同时清空所有center中数据的个数
 
                for( i = 0; i < N; i++ )
                {//遍历所有的数据
                    sample = data.ptr<float>(i);//取得当前需要的处理的数据
                    k = labels[i];//得到当前数据所在center的index
                    float* center = centers.ptr<float>(k);//取得centers[k]的数据
                    for( j = 0; j <= dims  4; j += 4 )//这个我着实没有搞懂是为啥,完全不理解,不过我的数据维度是3,这个部分完全不会被执行到,那就暂时放过它吧
                    {
                        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( ; j < dims; j++ )
                        center[j] += sample[j];//把每一个维度的数据都加到center中去
                    counters[k]++;//同时更新该center的数据个数
                }
 
                if( iter > 0 )
                    max_center_shift = 0;
 
                for( k = 0; k < K; k++ )
                {
                    float* center = centers.ptr<float>(k);
                    if( counters[k] != 0 )
                    {//如果该center有数据的话,就计算一下这些数据的平均值,以便得到centroid数据
                        float scale = 1.f/counters[k];
                        for( j = 0; j < dims; j++ )
                            center[j] *= scale;
                    }
                    else
                        generateRandomCenter(_box, center, rng);//这个是要干什么?如果有center中没有数据就要推到重来吗?没有搞懂,以后再说吧
                    
                    if( iter > 0 )
                    {//计算一下新旧center的centroid的差这个东西将会被作为循环停止的判断条件之一
                        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
            compactness = 0;
            for( i = 0; i < N; i++ )
            {//现在开始决定每一个数据到底该扔到哪一个center中
                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);
 
                    if( min_dist > dist )
                    {
                        min_dist = dist;
                        k_best = k;
                    }
                }//这个循环计算了当前的这个数据离哪一个center的centroid最近,
 
                compactness += min_dist;
                labels[i] = k_best;//这个数据就扔到哪个距离最近的center中去吧
            }
        }
 
        if( compactness < best_compactness )
        {//找到更好的center数据,用之
            best_compactness = compactness;
            if( _centers.needed() )
                centers.copyTo(_centers);
            _labels.copyTo(best_labels);
        }
    }
 

看完OpenCV的代码,我的感觉是我的代码和它的相差不是很大,但是为何用我的代码生成的图像就不正确呢,而用OpenCV的kmeans算法得到的图像就非常接近原图。 看来还得继续看看我的代码哪里错误,或者我直接使用OpenCV的kmeans算法实现算了

Categories: programming Tags: , ,
  1. No comments yet.
  1. No trackbacks yet.