Timezone: »
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)
-
2019 Spotlight: Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning »
Wed. Dec 11th 06:30 -- 06:35 PM Room West Exhibition Hall C + B3
More from the Same Authors
-
2022 Poster: Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources »
Peter Lippmann · Enrique Fita SanmartĂn · Fred Hamprecht -
2021 Poster: Directed Probabilistic Watershed »
Enrique Fita Sanmartin · Sebastian Damrich · Fred Hamprecht -
2021 Poster: On UMAP's True Loss Function »
Sebastian Damrich · Fred Hamprecht -
2017 Poster: Sparse convolutional coding for neuronal assembly detection »
Sven Peter · Elke Kirschbaum · Martin Both · Lee Campbell · Brandon Harvey · Conor Heins · Daniel Durstewitz · Ferran Diego · Fred Hamprecht -
2017 Poster: Cost efficient gradient boosting »
Sven Peter · Ferran Diego · Fred Hamprecht · Boaz Nadler -
2016 : Fred Hamprecht : Motif Discovery in Functional Brain Data »
Fred Hamprecht -
2014 Poster: Sparse Space-Time Deconvolution for Calcium Image Analysis »
Ferran Diego Andilla · Fred Hamprecht -
2014 Spotlight: Sparse Space-Time Deconvolution for Calcium Image Analysis »
Ferran Diego Andilla · Fred Hamprecht -
2013 Poster: Learning Multi-level Sparse Representations »
Ferran Diego Andilla · Fred Hamprecht -
2011 Poster: Structured Learning for Cell Tracking »
Xinghua Lou · Fred Hamprecht