Archive

Posts Tagged ‘opencv’

openCV中kmeans++的实现

October 9th, 2011 No comments

上次看了一下OpenCV中kmeans算法的实现,现在来看看剩下部分的kmeans++的东西。kmeans++其实是在初始化cluster中心点的时候用到的算法。按照wiki上的说法这样做的好处解决了kmeans的一个问题: the approximation found can be arbitrarily bad with respect to the objective function compared to the optimal clustering.

下面是源代码

centers[0] = (unsigned)rng % N;//随机选择一个数据作为第一个center的中心点
for( i = 0; i < N; i++ )
{
    dist[i] = distance(data + step*i, data + step*centers[0], dims);//计算每一个数据点到第一个center的中心的距离
    sum0 += dist[i];//sum of the these distance
}
for( k = 1; k < K; k++ )//计算剩下的centers的中心点
{
    double bestSum = DBL_MAX;
    int bestCenter = 1;
    for( j = 0; j < trials; j++ )//在这里trials通常是3,原因我不清楚
    {
        double p = (double)rng*sum0, s = 0;//
        for( i = 0; i < N1; i++ )
            if( (p = dist[i]) <= 0 )
                break;//随机选择一个数据点,这个数据点貌似有什么特性,不过我没有看出来,为啥要这样做我还是不清楚
        int ci = i;//我们暂时找到了一个新的中心点
        for( i = 0; i < N; i++ )
        {
            tdist2[i] = std::min(distance(data + step*i, data + step*ci, dims), dist[i]);
            s += tdist2[i];//计算每个点到新的这个中心点的距离
        }
        
        if( s < bestSum )
        {//如果这个新的中心点比刚才找到的要好的话,就用这个了
            bestSum = s;
            bestCenter = ci;
            std::swap(tdist, tdist2);
        }
    }
    centers[k] = bestCenter;//这样查找3次以后我们得到了一个新的center的中心点
    sum0 = bestSum;
    std::swap(dist, tdist);
}
for( k = 0; k < K; k++ )
{//输出
    const float* src = data + step*centers[k];
    float* dst = _out_centers.ptr<float>(k);
    for( j = 0; j < dims; j++ )
        dst[j] = src[j];
}

虽然上面的代码很简单,但是因为没有理解算法所以不能完全搞懂。还需要一边看看算法一边在琢磨一下每一步在做什么和为什么要这么做。

Categories: programming Tags: , ,

OpenCV中kmean算法的实现

October 7th, 2011 No comments

  我自己的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: , ,