Robust Large-Scale Visual Codebook Construction

Techniques for construction of a visual codebook are described herein. Feature points may be extracted from large numbers of images. In one example, images providing N feature points may be used to construct a codebook of K words. The centers of each of K clusters of feature points may be initialized. In a looping or iterative manner, an assignment step assigns each feature point to a cluster and an update step locates a center of each cluster. The feature points may be assigned to a cluster based on a lesser of a distance to a center of a previously assigned cluster and a distance to a center derived by operation of an approximate nearest neighbor algorithm having aspects of randomization. The loop terminates when the feature points have sufficiently converged to their respective clusters. Centers of the clusters represent visual words, which may be used to construct the visual codebook.