Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning
This work provides incremental improvements in graph-based segmentation and learning methods, primarily for computer vision and machine learning researchers.
The paper tackles the problem of seeded segmentation and semi-supervised learning by proposing the Probabilistic Watershed, which samples all spanning forests to compute connection probabilities between nodes and seeds, showing computational feasibility via Kirchhoff's matrix tree theorem and establishing new connections to Random Walker probabilities and the Power Watershed.
The seeded Watershed algorithm / minimax semi-supervised learning on a graph computes a minimum spanning forest which connects every pixel / unlabeled node to a seed / labeled node. We propose instead to consider all possible spanning forests and calculate, for every node, the probability of sampling a forest connecting a certain seed with that node. We dub this approach "Probabilistic Watershed". Leo Grady (2006) already noted its equivalence to the Random Walker / Harmonic energy minimization. We here give a simpler proof of this equivalence and establish the computational feasibility of the Probabilistic Watershed with Kirchhoff's matrix tree theorem. Furthermore, we show a new connection between the Random Walker probabilities and the triangle inequality of the effective resistance. Finally, we derive a new and intuitive interpretation of the Power Watershed.