Fast, Robust and Scalable Clustering Algorithms with Applications in Computer Vision
Vahan Petrosyan · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2018
In this thesis, we address a number of challenges in cluster analysis. We begin by investigating one of the oldest and most challenging problems: determining the number of clusters, k. For this problem, we propose a novel solution that, unlike previous techniques, delivers both the number of clusters and the clusters in one-shot (in contrast, conventional techniques run a given clustering algorithm several times for different values of k, and/or for several initialization with the same k). The second challenge we treat is the drawback, briefly mentioned above, of many conventional iterative clustering algorithms: how should they be initialized? We propose an initialization scheme that is applicable to multiple iterative clustering techniques that are widely used in practice (e.g., spectral clustering, EM-based, k-means). Numerical simulations demonstrate a significant improvement compared to many state-of-the-art initialization techniques. Third, we consider the computation of pairwise similarities between datapoints. A matrix of such similarities (the similarity matrix) constitutes the backbone of many clustering as well as unsupervised learning algorithms. In particular, for a given similarity metric, we propose a similarity transformation that promotes high similarity between the points within the cluster and deceases the similarity within the cluster overlapping regions. The transformation is particularly well-suited for many clustering and dimensionality reduction techniques, which we demonstrate in extensive numerical experiments. Finally, we investigate the application of clustering algorithms to image and video datasets (also known as superpixel segmentation). We propose a segmentation algorithm that significantly outperforms current state-of-the-art algorithms; both in terms of runtime as well as standard accuracy metrics. Based on this algorithm, we develop a tool for fast and accurate image annotation. Our findings show that our annotation technique accelerates the annotation processes by up to 20 times, without compromising the quality. This indicates a big opportunity to significantly speed up all AI computer vision tasks, since image annotation forms a crucial step in creating training data.