  Structural regularities in man-made environments reflect in the distribution
of their surface normals. Describing these surface normal distributions is
important in many computer vision applications, such as scene understanding,
plane segmentation, and regularization of 3D reconstructions. Based on the
small-variance limit of Bayesian nonparametric von-Mises-Fisher (vMF) mixture
distributions, we propose two new flexible and efficient k-means-like
clustering algorithms for directional data such as surface normals. The first,
DP-vMF-means, is a batch clustering algorithm derived from the Dirichlet
process (DP) vMF mixture. Recognizing the sequential nature of data collection
in many applications, we extend this algorithm to DDP-vMF-means, which infers
temporally evolving cluster structure from streaming data. Both algorithms
naturally respect the geometry of directional data, which lies on the unit
sphere. We demonstrate their performance on synthetic directional data and real
3D surface normals from RGB-D sensors. While our experiments focus on 3D data,
both algorithms generalize to high dimensional directional data such as protein
backbone configurations and semantic word vectors.
