On one of my programs, cv::kmeans is clearly the bottleneck.

Besides, I see that inside OpenCV [[OpenCV]] itself, cv::kmeans is used more and more. A simple grep on 2.3 sources gives :
modules/calib3d/src/circlesgrid.cpp
modules/features2d/src/bagofwords.cpp
modules/imgproc/src/grabcut.cpp
modules/ml/src/em.cpp

I see in kmeans sources (modules/core/src/matrix.cpp) that SSE2, if available, is already used to compute distances.
So maybe code can not be easily optimized further for one CPU core.

However, kmeans algorithm should be easy to parallelize as computations in inner loops are done on independent data.

It would be very useful to have a TBB implementation of kmeans.