Probabilistic Watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning
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.
Code (1)
Tasks
AllSimilar Papers 제목 키워드 기반
Directed Probabilistic Watershed
The Probabilistic Watershed is a semi-supervised learning algorithm applied on undirected graphs. Given a set of labeled nodes (seeds), it defines a Gibbs probability distribution over all possible spanning forests disco…
Learned Watershed: End-to-End Learning of Seeded Segmentation
Learned boundary maps are known to outperform hand- crafted ones as a basis for the watershed algorithm. We show, for the first time, how to train watershed computation jointly with boundary map prediction. The estimator…
SegmentationThe Mutex Watershed: Efficient, Parameter-Free Image Partitioning
Image partitioning, or segmentation without semantics, is the task of decomposing an image into distinct segments; or equivalently, the task of detecting closed contours in an image. Most prior work either requires seeds…
Clusteringgraph partitioningSegmentationAdaptive Morphological Reconstruction for Seeded Image Segmentation
Morphological reconstruction (MR) is often employed by seeded image segmentation algorithms such as watershed transform and power watershed as it is able to filter seeds (regional minima) to reduce over-segmentation. How…
Image SegmentationSegmentationSemantic SegmentationThe Mutex Watershed and its Objective: Efficient, Parameter-Free Graph Partitioning
Image partitioning, or segmentation without semantics, is the task of decomposing an image into distinct segments, or equivalently to detect closed contours. Most prior work either requires seeds, one per segment; or a t…
Clusteringgraph partitioningSegmentation