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 960×1280 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?
Solved – is K-Means clustering suited to real time applications
clusteringimage segmentationk-meansonline-algorithmsreal time
Best Answer
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.