The talk consists of two parts. The first part introduces a new algorithm to generate homogeneous superpixels from the process of Markov random walks. We exploit the Markov cluster algorithm as the methodology, a generic graph clustering method based on stochastic flow circulation. In particular, we introduce a new graph pruning strategy called compact pruning in order to capture intrinsic local image structure, and thereby keep the superpixels homogeneous, i.e., uniform in size and compact in shape. We show that the proposed algorithm achieves an optimal performance in terms of qualitative measure at a decent computational speed compared with standard techniques.
The second part is about clustering data sets distributed in complex manifolds. Using a decision forest, we first generate multiple partitions of the same input space, one per tree. The partitions from all trees are merged by intersecting them, resulting in a partition of higher resolution. We construct a graph by assigning a node to each region and linking adjacent nodes, which turns the clustering problem in the feature space into a graph clustering task. We then solve it with the Markov cluster algorithm. The proposed algorithm is able to capture non-convex structure while being computationally efficient. We show the performance on synthetic data as well as on the task of video segmentation. Joint work with F. Perbet and B. Stenger.