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?
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.
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.
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.