1
$\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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ are there existing implementations that I can use? $\endgroup$
    – mugetsu
    Commented Aug 17, 2012 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
    Commented Aug 17, 2012 at 18:22
  • $\begingroup$ Which programming language are you using? $\endgroup$
    – emrea
    Commented Aug 22, 2012 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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