Mean shift implementation in C++

Aly picture Aly · Mar 11, 2013 · Viewed 10.6k times · Source

Can anyone recommend a lightweight mean shift clustering implementation in C++? I am already using OpenCV, however their mean shift implementation is for tracking, not clustering. I have seen EDISON, however, this is for image segmentation and not clustering.

I could implement it myself, however would rather not invest the time, and not take the risk of bugs.

Thanks

Answer

physincubus picture physincubus · Oct 2, 2015

This is old, but I am working with mean shift right now so I thought it best to answer.

I think I understand the distinction you are making here, but when you say you are looking for mode detection this is vague in the technical sense as from the point of view of the algorithm as the algorithm inherently is for searching for "modes", which are the local minima or maxima depending on how you frame the optimization problem (Gradient descent or ascent).

This source, which was found on the EDISON site, claims to be a c++ implementation of the mean shift clustering algorithm, but as discussed above, clustering is the main implementation of the mode seeking behavior that all other uses of mean shift is based on, especially segmentation, so you can certainly use the EDISON source to find a clustering implementation, even if you have to search through it a bit.

I also found this Github project, for what it is worth, but I haven't worked with it before.

LAST NOTE: I also noticed you said "lightweight" implementation. Note that mean shift is not a very efficient algorithm (i think it is something like O(N^3), but I will check that). That said, it can still be efficiently implemented, though how that should be gauged is more ambiguous. Needless to say, Quick Shift, an attempt by UCLA researchers to solve the issues of the more efficient medoid shift, a similar non-parametric mode seeking algorithm, might be more like what you are looking for in a "lightweight" algorithm.