The DOI matches its Crossref record; 71 of the 71 references it cites were found in a registry or an index.
Power Watershed: A Unifying Graph-Based Optimization Framework
Open accessAbstract
In this work, we extend a common framework for graph-based image segmentation that includes the graph cuts, random walker, and shortest path optimization algorithms. Viewing an image as a weighted graph, these algorithms can be expressed by means of a common energy function with differing choices of a parameter q acting as an exponent on the differences between neighboring nodes. Introducing a new parameter p that fixes a power for the edge weights allows us to also include the optimal spanning forest algorithm for watershed in this same framework. We then propose a new family of segmentation algorithms that fixes p to produce an optimal spanning forest but varies the power q beyond the usual watershed algorithm, which we term the power watershed. In particular, when q=2, the power watershed leads to a multilabel, scale and contrast invariant, unique global optimum obtained in practice in quasi-linear time. Placing the watershed algorithm in this energy minimization framework also opens new possibilities for using unary terms in traditional watershed segmentation and using watershed to optimize more general models of use in applications beyond image segmentation.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
GrabCut: Interactive foreground extraction using iterated graph cuts
Rother, C., Kolmogorov, V., & Blake, A. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015720 · Cited by 5,703
Watersheds in digital spaces: an efficient algorithm based on immersion simulations
Vincent, L., & Soille, P. (1991) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.87344 · Cited by 5,649
Optimal approximations by piecewise smooth functions and associated variational problems
Mumford, D., & Shah, J. (1989) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.3160420503 · Cited by 5,208
On the shortest spanning subtree of a graph and the traveling salesman problem
Kruskal, J. B. (1956) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1956-0078686-7 · Cited by 5,088
An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision
Boykov, Y., & Kolmogorov, V. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.60 · Cited by 4,577
Shortest Connection Networks And Some Generalizations
Prim, R. C. (1957) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1957.tb01515.x · Cited by 4,565
Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images
Boykov, Y. Y., & Jolly, M.-P. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937505 · Cited by 3,674
Random Walks for Image Segmentation
Grady, L. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.233 · Cited by 2,624
Self-citationBlake, A., & Zisserman, A. (1987) · The MIT Press eBooks · doi:10.7551/mitpress/7132.001.0001 · Cited by 2,105
Morphological grayscale reconstruction in image analysis: applications and efficient algorithms
Vincent, L. (1993) · IEEE Transactions on Image Processing · doi:10.1109/83.217222 · Cited by 1,923
Coifman, R. R., Lafon, S., Lee, A. B., Maggioni, M., Nadler, B., Warner, F., & Zucker, S. W. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0500334102 · Cited by 1,675
A Closed-Form Solution to Natural Image Matting
Levin, A., Lischinski, D., & Weiss, Y. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1177 · Cited by 1,616
Efficiency of a Good But Not Linear Set Union Algorithm
Tarjan, R. E. (1975) · Journal of the ACM · doi:10.1145/321879.321884 · Cited by 1,403
The Watershed Transform: Definitions, Algorithms and Parallelization Strategies
Roerdink, J. B. T. M., & Meijster, A. (2000) · Fundamenta Informaticae · doi:10.3233/fi-2000-411207 · Cited by 1,372
Meyer, F., & Beucher, S. (1990) · Journal of Visual Communication and Image Representation · doi:10.1016/1047-3203(90)90014-m · Cited by 1,163
On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem
Kruskal, J. B. (1956) · Proceedings of the American Mathematical Society · doi:10.2307/2033241 · Cited by 1,117
Li, Y., Sun, J., Tang, C.-K., & Shum, H.-Y. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015719 · Cited by 1,097
Constrained restoration and the recovery of discontinuities
Geman, D., & Reynolds, G. (1992) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.120331 · Cited by 1,085
Exact Maximum A Posteriori Estimation for Binary Images
Greig, D. M., Porteous, B. T., & Seheult, A. H. (1989) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1989.tb01764.x · Cited by 1,055
Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., & Rother, C. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.70844 · Cited by 966
"GrabCut": interactive foreground extraction using iterated graph cuts
Rother, C., Kolmogorov, V., & Blake, A. (2004) · ACM SIGGRAPH 2004 Papers · doi:10.1145/1186562.1015720 · Cited by 935
A generalized Gaussian image model for edge-preserving MAP estimation
Bouman, C., & Sauer, K. (1993) · IEEE Transactions on Image Processing · doi:10.1109/83.236536 · Cited by 884
The Morphological Approach to Segmentation: The Watershed Transformation
Beucher, S., & Meyer, F. (2018) · Mathematical Morphology in Image Processing · doi:10.1201/9781482277234-12 · Cited by 881
Robust Higher Order Potentials for Enforcing Label Consistency
Kohli, P., Ladický, L., & Torr, P. H. S. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-008-0202-0 · Cited by 853
Antiextensive connected operators for image and sequence processing
Salembier, P., Oliveras, A., & Garrido, L. (1998) · IEEE Transactions on Image Processing · doi:10.1109/83.663500 · Cited by 635
Global Minimum for Active Contour Models: A Minimal Path Approach
Cohen, L. D., & Kimmel, R. (1997) · International Journal of Computer Vision · doi:10.1023/a:1007922224810 · Cited by 625
The image foresting transform: theory, algorithms, and applications
Falcao, A. X., Stolfi, J., & de Alencar Lotufo, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1261076 · Cited by 614
Statistical methods for tomographic image reconstruction
Geman, S., & McClure, D. E. (1987) · Medical Entomology and Zoology · Cited by 579
Computing geodesics and minimal surfaces via graph cuts
Boykov, & Kolmogorov (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238310 · Cited by 555
Interactive Segmentation with Intelligent Scissors
Mortensen, E. N., & Barrett, W. A. (1998) · Graphical Models and Image Processing · doi:10.1006/gmip.1998.0480 · Cited by 546
Interactive Image Segmentation Using an Adaptive GMMRF Model
Blake, A., Rother, C., Brown, M., Perez, P., & Torr, P. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24670-1_33 · Cited by 527
Unsupervised segmentation of natural images via lossy data compression
Yang, A. Y., Wright, J., Ma, Y., & Sastry, S. S. (2008) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2007.07.005 · Cited by 509
Geodesic saliency of watershed contours and hierarchical segmentation
Najman, L., & Schmitt, M. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.546254 · Cited by 498
Self-citationUser-Steered Image Segmentation Paradigms: Live Wire and Live Lane
Falcão, A. X., Udupa, J. K., Samarasekera, S., Sharma, S., Hirsch, B. E., & Lotufo, R. D. A. (1998) · Graphical Models and Image Processing · doi:10.1006/gmip.1998.0475 · Cited by 481
Levitan, E., & Herman, G. T. (1987) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.1987.4307826 · Cited by 445
A Geodesic Framework for Fast Interactive Image and Video Segmentation and Matting
Bai, X., & Sapiro, G. (2007) · 2007 IEEE 11th International Conference on Computer Vision · doi:10.1109/iccv.2007.4408931 · Cited by 438
Attribute Openings, Thinnings, and Granulometries
Breen, E. J., & Jones, R. H. (1996) · Computer Vision and Image Understanding · doi:10.1006/cviu.1996.0066 · Cited by 433
Graph cut based image segmentation with connectivity priors
Vicente, S., Kolmogorov, V., & Rother, C. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587440 · Cited by 385
Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle
Cousty, J., Bertrand, G., Najman, L., & Couprie, M. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.173 · Cited by 352
Self-citationA minimum spanning tree algorithm with inverse-Ackermann type complexity
Chazelle, B. (2000) · Journal of the ACM · doi:10.1145/355541.355562 · Cited by 328
Watershed of a continuous function
Najman, L., & Schmitt, M. (1994) · Signal Processing · doi:10.1016/0165-1684(94)90059-0 · Cited by 317
Self-citationSinop, A. K., & Grady, L. (2007) · 2007 IEEE 11th International Conference on Computer Vision · doi:10.1109/iccv.2007.4408927 · Cited by 277
Self-citationGeoS: Geodesic Image Segmentation
Criminisi, A., Sharp, T., & Blake, A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88682-2_9 · Cited by 277
Li, Y., Sun, J., Tang, C.-K., & Shum, H.-Y. (2004) · ACM SIGGRAPH 2004 Papers · doi:10.1145/1186562.1015719 · Cited by 249
Grady, L. J., & Polimeni, J. R. (2010) · Springer eBooks · doi:10.1007/978-1-84996-290-2 · Cited by 230
Self-citationGuigues, L., Cocquerez, J. P., & Le Men, H. (2006) · International Journal of Computer Vision · doi:10.1007/s11263-005-6299-0 · Cited by 223
P3 & Beyond: Solving Energies with Higher Order Cliques
Kohli, P., Kumar, M. P., & Torr, P. H. S. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383204 · Cited by 223
Robust higher order potentials for enforcing label consistency
Kohli, P., Ladicky, L., & Torr, P. H. S. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587417 · Cited by 201
Watershed Cuts: Thinnings, Shortest Path Forests, and Topological Watersheds
Cousty, J., Bertrand, G., Najman, L., & Couprie, M. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.71 · Cited by 184
Self-citationFusionFlow: Discrete-continuous optimization for optical flow estimation
Lempitsky, V., Roth, S., & Rother, C. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587751 · Cited by 145 · cited 1×
“Viewed as energy minimization algorithms, graph cuts, random walker, and shortest paths have found many different applications in the computer vision field that go beyond image segmentation, such as stereo correspondence, optical flow, and image restoration (e.g., [82], [76], [ 53 ]).”
BackgroundLearning Gaussian Conditional Random Fields for Low-Level Vision
Tappen, M. F., Liu, C., Adelson, E. H., & Freeman, W. T. (2007) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2007.382979 · Cited by 139
Couprie, C., Grady, L. J., Najman, L. A., & Talbot, H. (2009) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2009.5459284 · Cited by 136
Self-citationGlobally minimal surfaces by continuous maximal flows
Appleton, B., & Talbot, H. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.12 · Cited by 129
Self-citationTVSeg - Interactive Total Variation Based Image Segmentation
Unger, M., Pock, T., Trobin, W., Cremers, D., & Bischof, H. (2008) · British Machine Vision Conference (BMVC) · doi:10.5244/c.22.40 · Cited by 119
A generative perspective on MRFs in low-level vision
Schmidt, U., Gao, Q., & Roth, S. (2010) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2010.5539844 · Cited by 117
Duchenne, O., Audibert, J.-Y., Keriven, R., Ponce, J., & Ségonne, F. (2008) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2008.4587419 · Cited by 111
Learning optimized MAP estimates in continuously-valued MRF models
Samuel, K. G. G., & Tappen, M. F. (2009) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2009.5206774 · Cited by 94
Stochastic watershed segmentation.
Angulo, J., & Jeulin, D. (2007) · Biblioteca Digital da Memória Científica do INPE (National Institute for Space Research) · Cited by 89
Some links between min cuts, optimal spanning forests and watersheds
Allène, C., Audibert, J.-Y., Couprie, M., Cousty, J., & Keriven, R. (2007) · HAL · Cited by 73
Some links between extremum spanning forests, watersheds and min-cuts
Allène, C., Audibert, J.-Y., Couprie, M., & Keriven, R. (2009) · Image and Vision Computing · doi:10.1016/j.imavis.2009.06.017 · Cited by 72
Minimal Surfaces Extend Shortest Path Segmentation Methods to 3D
Grady, L. J. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.289 · Cited by 65
Self-citationImage Statistics and Anisotropic Diffusion
Scharr, H., Black, M. J., & Haussecker, H. W. (2003) · JuSER (Forschungszentrum Jülich) · Cited by 49
Image statistics and anisotropic diffusion
Scharr, Black, & Haussecker (2003) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2003.1238435 · Cited by 42
Learning for Optical Flow Using Stochastic Optimization
Li, Y., & Huttenlocher, D. P. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88688-4_28 · Cited by 35
P-brush: Continuous valued MRFs with normed pairwise distributions for image segmentation
Singaraju, D., Grady, L. J., & Vidal, R. (2009) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2009.5206669 · Cited by 35
Self-citationEfficient segmentation based on Eikonal and diffusion equations
Alvino, C. V., Ünal, G., Slabaugh, G., et al. (2007) · International Journal of Computer Mathematics · doi:10.1080/00207160701324249 · Cited by 27
Stereo matching using random walks
Shen, R., Cheng, I., Li, X., & Basu, A. (2008) · Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition · doi:10.1109/icpr.2008.4761512 · Cited by 20
Grady, L. J. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88688-4_19 · Cited by 20
Self-citationDiffusion filtering without parameter tuning: Models and inference tools
Krajsek, K., & Scharr, H. (2010) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2010.5539959 · Cited by 14
Cited by
Microscopy Image Browser: A Platform for Segmentation and Analysis of Multidimensional Datasets
Belevich, I., Joensuu, M., Kumar, D., Vihinen, H., & Jokitalo, E. (2016) · PLOS Biology · doi:10.1371/journal.pbio.1002340 · Cited by 457
Lazy Random Walks for Superpixel Segmentation
Shen, J., Du, Y., Wang, W., & Li, X. (2014) · IEEE Transactions on Image Processing · doi:10.1109/tip.2014.2302892 · Cited by 339
GRAPH MATCHING AND LEARNING IN PATTERN RECOGNITION IN THE LAST 10 YEARS
FOGGIA, P., PERCANNELLA, G., & VENTO, M. (2014) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001414500013 · Cited by 337
Accurate and versatile 3D segmentation of plant tissues at cellular resolution
Wolny, A., Cerrone, L., Vijayan, A., Tofanelli, R., Barro, A. V., Louveaux, M., Wenzl, C., Strauss, S., Wilson-Sánchez, D., Lymbouridou, R., et al. (2020) · eLife · doi:10.7554/elife.57613 · Cited by 326
Multiscale X-ray tomography of cementitious materials: A review
Brisard, S., Serdar, M., & Monteiro, P. J. M. (2020) · Cement and Concrete Research · doi:10.1016/j.cemconres.2019.105824 · Cited by 260
Metadata
- Authors
- Couprie, C., Grady, L., Najman, L., & Talbot, H.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2011-07
- Volume
- 33
- Issue
- 7
- Pages
- 1384-1399
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2171147867
- Cited by
- 305
- References
- 71
- FWCI
- 27.27
- Type
- journal article
- Language
- en
- Open access
- green
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.