Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning
Enrique Fita Sanmartin · Sebastian Damrich · Fred Hamprecht

Wed Dec 11th 10:45 AM -- 12:45 PM @ East Exhibition Hall B + C #81

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.

Author Information

Enrique Fita Sanmartin (Heidelberg University)
Sebastian Damrich (Heidelberg University)
Fred Hamprecht (Heidelberg University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors