Random Walks for Image Segmentation
Abstract
A novel method is proposed for performing multilabel, interactive image segmentation. Given a small number of pixels with user-defined (or predefined) labels, one can analytically and quickly determine the probability that a random walker starting at each unlabeled pixel will first reach one of the prelabeled pixels. By assigning each pixel to the label for which the greatest probability is calculated, a high-quality image segmentation may be obtained. Theoretical properties of this algorithm are developed along with the corresponding connections to discrete potential theory and electrical circuits. This algorithm is formulated in discrete space (i.e., on a graph) using combinatorial analogues of standard operators and principles from continuous potential theory, allowing it to be applied in arbitrary dimension on arbitrary graphs.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Most interactive image segmentation methods rely on low-level features and require a relatively large amount of user interactions to deal with images with low contrast and ambiguous boundaries.
“However, most of these methods rely on low-level features and require a relatively large amount of user interactions to deal with images with low contrast and ambiguous boundaries.”
From DeepIGeoS: A Deep Interactive Geodesic Framework for Medical Image Segmentation (2019) · cites this paper as [7]
Random Walks and Graph Cuts learn from scribbles and allow additional scribbles for refinement, but need a large number of scribbles to get satisfactory segmentation.
“Random Walks [7] and Graph Cuts [8] learn from scribbles and allow the user to provide additional scribbles for refinement. They use Random Walker and Gaussian Mixture Model (GMM) as the underpinning model. However, they need a large number of scribbles to get satisfactory segmentation.”
From DeepIGeoS: A Deep Interactive Geodesic Framework for Medical Image Segmentation (2019) · cites this paper as [7]
R-Net is only trained with user interactions once since it takes a considerable time to re-train a CNN model with a large training set.
“Differently from previous works [55] that re-train the learning model each time when new user interactions are given, the proposed R-Net is only trained with user interactions once since it takes a considerable time to re-train a CNN model with a large training set.”
From DeepIGeoS: A Deep Interactive Geodesic Framework for Medical Image Segmentation (2019) · cites this paper as [55]
Interactive 2D slice-based segmentation is expected to achieve more robust results.
“Interactive 2D slice-based segmentation is expected to achieve more robust results [6], [55].”
From DeepIGeoS: A Deep Interactive Geodesic Framework for Medical Image Segmentation (2019) · cites this paper as [55]
The random walker algorithm allows semi-automated image segmentation, producing a 3-D outline of the placenta in considerably less time and a less operator dependent manner.
“The random walker algorithm allows for semi-automated image segmentation [37], which can produce a 3-D outline of the placenta in considerably less time and a less operator dependent manner.”
From Volume and vascularity: Using ultrasound to unlock the secrets of the first trimester placenta (2019) · cites this paper as [37]
The citation lists haven’t been fetched yet
References 79 · Cited by 2,624
- Authors
- Grady, L.
- Affiliations
- Siemens (United States) (US)
- Corresponding author
- Grady, L.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2006-11
- Volume
- 28
- Issue
- 11
- Pages
- 1768-1783
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W2125637308
- Cited by
- 2,624
- References
- 79
- Citations by year
- 2026: 53 · 2025: 91 · 2024: 109 · 2023: 122 · 2022: 122 · 2021: 167 · 2020: 148 · 2019: 176 · 2018: 179 · 2017: 179 · 2016: 179 · 2015: 191 · 2014: 162 · 2013: 181 · 2012: 163
- FWCI
- 63.02
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Pattern Analysis and Machine Intelligence (publishedVersion)
- PubMed (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Medical Image Segmentation Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Digital Image Processing Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Neural Network Applications
- Keywords
- random walks, image segmentation, interactive segmentation, graph-based segmentation, discrete potential theory, electrical circuits, graph Laplacian
- MeSH terms
- Algorithms, Artificial Intelligence, Image Enhancement, Image Interpretation, Computer-Assisted, Pattern Recognition, Automated, Sensitivity and Specificity, Reproducibility of Results, Models, Statistical, Information Storage and Retrieval
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
