# is K-Means clustering suited to real time applications?

I want to segment a sequence of RGB images (basically it's a video) based on their colors in real time. KMeans is an easy and intuitive algorithm to use in this case, but it's execution time is very sensitive to the clusters' centers initialization and to the number of clusters, and the algorithm conversion is not guaranteed. It gave good results on the few images I tested it on using OpenCV, but for an image of 960x1280 for example it takes 8 seconds to cluster the image, knowing that I used kmeans++ for centers initialization and fixed the number of clusters to 4. Obviously such an execution time is not adapted to processing a video sequence in real time, but I intend on implementing it on an FPGA, and I hope it'll goes from 8 seconds with C++ to a few microseconds with VHDL (maybe my hopes are not well-grounded ). Are there any real time applications that use K-Means for clustering?

• Can you clarify whether you are talking about (a) clustering images with similar images based on their colors, or (b) clustering similar color regions within an image? I initially read this as (b) but now think you may be talking about (a) – Jake Westfall Sep 9 '17 at 16:11
• @Jake Westfall, sorry I think I didn't make that clear in my question. Actually it's (b): I process one image at a time, and segment it to regions. This has nothing to do with the other images. – user2651062 Sep 9 '17 at 17:18
• You might still be much faster if you find an algorithm that can take the clusters from the last frame and adapt them to the new frame instead of redoing the whole clustering. – David Ernst Sep 9 '17 at 17:29
• @user7019377 I can't agree with you more. Actually I've already tried to do that with the openCV function cv::kmeans() but the execution time nearly doubled! From 8 seconds on the first image to 14 seconds on the second, it's intriguing. The centers of the first image clusters are initialized with kmeans++, while the centers of the following image are initialized by the centers of the first image obtained by kmeans. I haven't been able to find an explanation so far. – user2651062 Sep 9 '17 at 17:36
• My intuition (with no actual experience to back it up) is that because the color regions likely have weird, irregular shapes, almost any centroid-based clustering algorithm (such as k-means) may have a hard time producing sensible results. You might consider something like hierarchical or spectral clustering instead. – Jake Westfall Sep 9 '17 at 17:46

Check RTEFC or RTMAC, which are efficient, simple real-time variants of K-means, suited for tracking sequences of similar vectors. RTEFC in particular. See http://gregstanleyandassociates.com/whitepapers/BDAC/Clustering/clustering.htm

RTEFC is non-iterative, so suitable for high-speed, predictable execution time. But it does assume that just storing the centroids rather than the original data is good enough for your purposes. For this application, it sounds like you'd have to modify the algorithm slightly to delete old clusters after a period of non-use. These methods were originally conceived for process control applications where it was important to remember old but uncommon cases - probably not your situation. These methods do assume a fixed cluster radius, which also might be an issue for you. Some variant might be needed.

Maybe it's not entirely real-time (it's rather minibatch) but Spark has streaming k-means which apparently are used to cluster data as it comes from Kafka.

I think you have other problems before you optimize the execution time of the algorithm.

K-means clustering will lead to approximately spherical clusters in a 3D space because it minimizes the sum of Euclidean distances towards those cluster centers.

Now your application is not in 3D space at all. That in itself wouldn't be a problem. 2D and 3D examples are printed in the textbooks to illustrate the concept. The whole point of machine learning algorithms is to also work in higher dimensional spaces that we cannot easily imagine. k-means will produce approximate hyperspheres in 4D, 5D etc.

In your case however, dimensionality is extremely high. If we assume grayscale pictures and you have $1280\times 960=1228800$ dimensions. Three times that for color images. You will fall victim to the curse of dimensionality, more precisely the distance concentration effect. All your distances will look almost the same since Euclidean distance is just not designed for spaces with that high dimensions.

Other practical problems arise irrespective of the distance concentration effect: take an image with much intricate detail, for example a tree with many leaves. Now take a similar image, say the very next frame from the video that contains the same tree but a little more to the right in the picture because the camera was sweeping across the tree. Euclidean distance may tell you that those two pictures are very different. Due to the camera sweep, small areas that displayed a leaf shadow in the one picture overlap with areas that display the leaf in the sunlight in the other picture and vice versa. Almost no pixels show the same colors in both images. Intuitively, the images are very similar but not according to euclidean distance. So not only does euclidean distance concentrate your distances, in some cases it misinterprets them.

To solve this problem, sophisticated distance measures based for example on artificial neural networks have been designed for images.

In some cases, you can be fine with euclidean distances nevertheless. That is when the manifold assumption holds, when your credible candidates of images you might come across do not occupy all of the high dimensional space equally but are in fact concentrated in some separated manifolds of much lower dimension embedded in the high dimensional space. In a space with more than a million dimensions like yours, most images would be pure noise and not representative of credible frames you might find in a video. Therefore, you are not really dealing with this vast high dimensional space but only lower dimensional sub-spaces embedded within it. The manifold assumption can counteract the curse of dimensionality. Though, for it to hold, you usually use smaller images (cropped and scaled) and you know more about them than that they are from a same video. For example if you knew that they all are photos of a limited number of different objects taken in similar circumstances, as you would in image classificatio, you could reasonable make the manifold assumption.

In any case, even if the manifold assumption were to hold, there is not much reason to believe those manifolds would be in the form of spheres which would warrant k-means.

• Maybe I'm missing something, but I don't see how having images of size 1280 x 960 makes this a 1228800-dimensional problem. Doesn't increasing the size of the image just increase the number of data points, not the dimensionality? – Jake Westfall Sep 9 '17 at 15:59
• When he says he wants to segment a sequence of images I read it as clustering images with similar images, not clustering areas within each image. The points of high dimensionality would then not apply but the point about spheres would still apply. – David Ernst Sep 9 '17 at 16:03
• Ah... I just realized that it's a little ambiguous ("segment a sequence of images"), but you may be right! Will ask for clarification – Jake Westfall Sep 9 '17 at 16:09
• You probably are right. But I still wouldn't do spherical kmeans clusters within an image. – David Ernst Sep 9 '17 at 16:10
• @user7019377 Thank you for your detailed answer, but Jake Westfall has a point. When I said "segment a sequence of RGB images" I meant segment each image independently from the other images by clustering areas within each image. – user2651062 Sep 9 '17 at 17:26

You cannot give good guarantees for the runtime. The number of iterations can be very large. So I doubt it qualifies as being "realtime capable".

You could try to do some approximations, for example limit the number of iterations.

Also pay attention to the much better algorithms for kmeans than the textbook Lloyd's algorithm, which is pretty wasteful.

But usually, clustering can be quite unreliable. So I'd be concerned about reliability whenever using it in an automated system.

just chiming in here, but I am working with a clustering algorithm that is extremely lightweight computationally and from a memory footprint perspective. We have been benchmarking in several applications against k-means, streaming versions of it, and other algos and have been delivering comparable results (accuracy) but are 500 - 1000x the speed on a single CPU core. We are also in the process of porting to FPGA, both with Xilinx (Zinq) and Altera (Arria 10). We are currently applying our algo to a medical imaging solution as well as a computer vision application in streaming video, leveraging a Linux environment and some OpenCV preprocessing. From a methodology perspective, we are breaking down high resolution images into multiple smaller windows (say a 1080x720 into 4,800 smaller pixel regions) and conducting clustering on them. Our runtime on a single core of an Intel i5 is 20 microseconds/vector with very few false positives. One of our applications in OpenCV running HD video on a go pro stream was able to maintain runtime at 50fps without degrading performance, even after the cluster count grew well past 400 clusters (think Autonomous driving). I think this might be something you would be interested in.