如何修复OpenCV中KMeans算法运行缓慢的问题

Question

我在关于词袋的项目中使用了kmeans()函数，但是运行时间很长。如果我有600张图片，需要40-50分钟才能完成。我查看了源代码，发现这一部分占用了大部分时间：

for( i = 0; i < N; i++ )///very very slow part because N*K is huge
        {
            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 = normL2Sqr_(sample, center, dims);

                if( min_dist > dist )
                {
                    min_dist = dist;
                    k_best = k;
                }
            }


            compactness += min_dist;
            labels[i] = k_best;

        }

我尝试了很多次，但是无法缩短这一部分的时间。有没有更有效率的方法？每次循环需要22-23秒，导致程序运行需要等待40-50分钟，并且无法尝试其他视频或图像集合。如果有更好的C++ kmeans代码将有所帮助，如果有减少N（# of features）的方法也会有所帮助，但是K是字典大小，我无法减小它。从现在开始感谢你的帮助。

- oknsnl

---

k-means算法速度较慢 - 除了增加硬件投入外，没有太多可以做的。 - Roger Rowland

你好，根据你的描述，我不知道上下文中的“那一点”是什么。但如果它是从运行时找到NN，那么你可以尝试使用FLANN库的近似kNN，该库也随opencv一起提供。http://www.cs.ubc.ca/research/flann/，http://docs.opencv.org/trunk/modules/flann/doc/flann_fast_approximate_nearest_neighbor_search.html - QED

感谢您的时间和建议。 - oknsnl

Answer 1

OpenCV中的k-means实现非常低效，并且有许多技巧可以提高性能，但它们并没有使用。自己重新编写需要考虑很多工作量。 VLfeat中的实现为k-means提供了更好的算法，但我不知道其实现的质量如何。

- Raff.Edward