Title: An introduction to Generalized K-means with image processing applications
Summary: In this era of digital Big Data, large scale collections of digital images are proliferating all over the place on and offline. For example
- users on Facebook upload more than 200 million photos every day
- in the medical imaging domain, over 68 million CT scans were performed in the US last year
- IT giants are building enormous visual maps of the world from massive collections of street view images
This explosive growth in image data poses serious challenges in terms of both storage – that is, how do we more efficiently compress rapidly growing collections of images? – and search – that is, how can we more effectively sort through image databases? – and in each case the best solutions developed so far rely heavily on machine learning techniques. Generalized K-means (G-K-means), more commonly called Dictionary Learning, is one of the key machine learning tools researchers such as my self are using to attack the storage problem. While at a high level this technique is really just exactly what you’d expect it to be – a generalized version of the standard K-means where you assign a data point to multiple clusters instead of just one – algorithm-wise it falls into the bucket of modern sparse statistical methods (e.g. compressive sensing, the lasso) which have been mentioned at some previous meetups.
This talk will be a user-friendly introduction to G-K-means with a practical algorithmic and application focus. I’ll first review the standard K-means algorithm and its popular application to single image compression. I’ll then show how, viewing K-means as a sparse statistical method, you can easily derive the analogous G-K-means model along with a natural greedy algorithm for solving it. Finally I’ll show some cool applications of G-K-means to the processing of large databases of images, and discuss its application to the storage problem – that is, to large scale image collection compression.