0
$\begingroup$

I am working on an online image feature recognition program(BOW histograms) that gets objects in a live cam and extracts the SIFT features. After getting a bunch of pictures, I get the kmeans of the batch and create a global cluster. Next, I repeat the step all over and get more pics to create a new separate batch of clusters. Ideally though, I want to limit the number of clusters that I have and clusters all images at once, but this is impossible since there is an infinite amount of new data coming in. I'm not quite sure how to approach this.

Here is how my code works right now:

1.Image is taken from live video feed, once enough pictures are saved, get kmeans of sift features.(get 200 clusters)

2.Repeat step 1, a new batch of live feed pictures, get kmeans again. Combine the kmeans vectors with the previous kmeans like :[A B],(total 400 clusters)

You can see that this is bad, because I quickly get too much clusters, and each batch of clusters will definitely have overlaps with another batch.

What I want:

1.Image taken from live video feed, once pics are saved, get kmeans(200 clusters)

2.Repeat step 1, get kmeans again, which updates the the previous clusters. (still 200 clusters, but some clusters have been updated or changed)

Nothing that I've seen could accommodate that, unless I'm just not understanding them correctly. many implementations, such as data-streaming, seemingly only allows you to make the cluster in one go. After all the data are streamed, it doesn't seem so easy to update the existing cluster. I would assume though that this should be possible, but none of the code I found seems to back that up. I would appreciate any help on clearing this up.

Thanks!

$\endgroup$
1
$\begingroup$

What you are looking for is the online (also called incremental or sequential) version of the k-means algorithm. In this lecture notes you can find the algorithm.

$\endgroup$
3
  • $\begingroup$ are there existing implementations that I can use? $\endgroup$ – mugetsu Aug 17 '12 at 18:04
  • $\begingroup$ I'm not aware of any existing implementations but isn't it very easy to implement it? It's basically this: initialize 200 means randomly and create an array of size 200 which will keep the number of data points assigned to each cluster. Then, as a new data point comes, assign it to the closest cluster, update the cluster's mean, and increment its count. That's it. $\endgroup$ – emrea Aug 17 '12 at 18:22
  • $\begingroup$ Which programming language are you using? $\endgroup$ – emrea Aug 22 '12 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.