Computer Vision: Mean-Shift algorithm

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

kocheez75
Posts: 1
Joined: Thu Feb 24, 2011 5:50 am UTC

Computer Vision: Mean-Shift algorithm

Hello,

I'm working on some image segmenting techniques for an independent study project, and I'm having some trouble figuring out how to implement the mean-shift algorithm. I understand the basic idea in that you have a window of values to compute, find the mean within the window, and re-center the window around the mean (repeat until convergence). What I'm not sure of is:

- How to decide the size of the window
- What the initial point should be
- How this is implemented multiple times (needs to be done for each segment, correct?)

Basically, I have an intensity histogram from an image, and I want to find the peaks (or modes) using this technique (since these indicate the color segments of the image).

I have successfully implemented the K-means clustering for segmentation, but the results are a little less than ideal, and the parameters must be defined beforehand. I have been searching online for hours, and have yet to find a basic explanation of mean-shift segmentation that is not just pulled quotes and formulas from the original papers on the subject (mathematical models scare me ).

If anyone has any experience with this topic and could possibly give some guidance on how to go about implementing the algorithm (or provide a resource that has a good explanation) it would be greatly appreciated!

Thanks!

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Computer Vision: Mean-Shift algorithm

Is this an implementation of what you are trying to do:
http://coewww.rutgers.edu/riul/research ... index.html
?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: Computer Vision: Mean-Shift algorithm

kocheez75 wrote:and the parameters must be defined beforehand.

Welcome to the land of computer vision where the national pastime is parameter fiddling. Have fun.

If you just need an implementation of mean shift that you know probably works, just use OpenCV. It's in the motion analysis and object tracking library.
http://opencv.willowgarage.com/document ... -meanshift

If you want to understand it instead, then you probably are going to want to understand those mathematical models that scare you. Otherwise, reinventing the wheel is a waste of time unless you make it better and if you don't understand the wheel as it is, then what's the point?

If you want a book to study from, the Szeliski book draft is still available online.
http://szeliski.org/Book/

I'm not really sure how popular mean shift is anymore for segmentation. Maybe it is, maybe it is not. I just don't use it and I don't know of any peers who use it. It's probably easier to understand a graph cuts approach since you can probably get the idea with one or two specific papers and then it's pretty simple to code up. Plus, graph cuts are trendy.