Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images
Abstract
In this paper we describe a new technique for general purpose interactive segmentation of N-dimensional images. The user marks certain pixels as "object" or "background" to provide hard constraints for segmentation. Additional soft constraints incorporate both boundary and region information. Graph cuts are used to find the globally optimal segmentation of the N-dimensional image. The obtained solution gives the best balance of boundary and region properties among all segmentations satisfying the constraints. The topology of our segmentation is unrestricted and both "object" and "background" segments may consist of several isolated parts. Some experimental results are presented in the context of photo/video editing and medical image segmentation. We also demonstrate an interesting Gestalt example. A fast implementation of our segmentation method is possible via a new max-flow algorithm.
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?
Fixing topological artifacts typically requires handcrafted refinement rules or architectures specialized to a particular task.
“Fixing these artifacts typically requires handcrafted refinement rules or architectures specialized to a particular task.”
From rNCA: Self-Repairing Segmentation Masks (2025) · cites this paper as [16]
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 [8]
GrabCut works with a user-provided bounding box and requires fewer interactions than Graph Cuts, but its performance is limited by the representativity of the underpinning GMM.
“GrabCut [9] works with a user-provided bounding box to start the segmentation and requires fewer interactions compared with Graph Cuts [8], but the performance is still limited by the representativity of the underpinning GMM.”
From DeepIGeoS: A Deep Interactive Geodesic Framework for Medical Image Segmentation (2019) · cites this paper as [8]
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 [8]
Graph Cuts can be used to minimize Eq. (6) when the pairwise potential is submodular, such as when the segmentation is binary with the compatibility being the delta function and the pairwise function being positive.
“Graph Cuts [8], [46] can be used to minimize Eq. (6) when”
From DeepIGeoS: A Deep Interactive Geodesic Framework for Medical Image Segmentation (2019) · cites this paper as [8]
Cites
Kass, M., Witkin, A., & Terzopoulos, D. (1988) · International Journal of Computer Vision · doi:10.1007/bf00133570 · Cited by 17,165 · see citing works
Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations
Osher, S., & Sethian, J. A. (1988) · Journal of Computational Physics · doi:10.1016/0021-9991(88)90002-2 · Cited by 14,196 · see citing works
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 · see citing works
Self-citationFord, D. R., & Fulkerson, D. R. (1962) · Cited by 4,080 · see citing works
Haralock, R. M., & Shapiro, L. G. (1991) · Addison-Wesley Longman Publishing Co., Inc. eBooks · Cited by 3,942 · see citing works
On active contour models and balloons
Cohen, L. D. (1991) · CVGIP Image Understanding · doi:10.1016/1049-9660(91)90028-n · Cited by 2,164 · see citing works
Region competition: unifying snakes, region growing, and Bayes/MDL for multiband image segmentation
Zhu, S. C., & Yuille, A. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.537343 · Cited by 1,928 · see citing works
A new approach to the maximum-flow problem
Goldberg, A. V., & Tarjan, R. E. (1988) · Journal of the ACM · doi:10.1145/48014.61051 · Cited by 1,895 · see citing works
Wu, Z., & Leahy, R. M. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.244673 · Cited by 1,144 · see citing works
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,066 · see citing works
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2002) · 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.1997.609407 · Cited by 861 · see citing works
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 547 · see citing works
User-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. (1998) · Graphical Models and Image Processing · doi:10.1006/gmip.1998.0475 · Cited by 481 · see citing works
Markov random fields with efficient approximations
Boykov, Y., Veksler, O., & Zabih, R. (2002) · 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.1998.698673 · Cited by 424 · see citing works
Self-citationAn Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in Vision
Boykov, Y. Y., & Kolmogorov, V. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44745-8_24 · Cited by 322 · see citing works
Self-citationInteractive Organ Segmentation Using Graph Cuts
Boykov, Y., & Jolly, M. (2000) · Lecture notes in computer science · doi:10.1007/978-3-540-40899-4_28 · Cited by 244 · see citing works
Self-citationExact voxel occupancy with graph cuts
Snow, D., Viola, P. A., & Zabih, R. (2002) · 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.2000.855839 · Cited by 175 · see citing works
Segmentation by grouping junctions
Ishikawa, H., & Geiger, D. (2002) · 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.1998.698598 · Cited by 165 · see citing works
"Ratio regions": a technique for image segmentation
Cox, I. J., Rao, S. B., & Zhong, Y. (1996) · Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition · doi:10.1109/icpr.1996.546886 · Cited by 146 · see citing works
Yuille, A., & Hallinan, P. (1993) · Cited by 86 · see citing works
Globally optimal regions and boundaries
Jermyn, I. H., & Ishikawa, H. (1999) · IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.1999.790318 · Cited by 46 · see citing works
Hierarchical Segmentation Satisfying Constraints
Griffin, L. D., Colchester, A. C. F., Röll, S. A., & Studholme, C. (1994) · British Machine Vision Conference (BMVC) · doi:10.5244/c.8.13 · Cited by 24 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
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 · see citing works
Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps
Simonyan, K., Vedaldi, A., & Zisserman, A. (2013) · arXiv · doi:10.48550/arxiv.1312.6034 · Cited by 5,370 · see citing works
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 · see citing works
Self-citationAutomated Flower Classification over a Large Number of Classes
Nilsback, M.-E., & Zisserman, A. (2008) · 2008 Sixth Indian Conference on Computer Vision, Graphics & Image Processing · doi:10.1109/icvgip.2008.47 · Cited by 3,442 · see citing works
Learning Hierarchical Features for Scene Labeling
Farabet, C., Couprie, C., Najman, L., & LeCun, Y. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.231 · Cited by 2,620 · see citing works
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 · see citing works
BiSeNet V2: Bilateral Network with Guided Aggregation for Real-Time Semantic Segmentation
Yu, C., Gao, C., Wang, J., Yu, G., Shen, C., & Sang, N. (2021) · International Journal of Computer Vision · doi:10.1007/s11263-021-01515-2 · Cited by 1,813 · see citing works
Embracing imperfect datasets: A review of deep learning solutions for medical image segmentation
Tajbakhsh, N., Jeyaseelan, L., Li, Q., Chiang, J. N., Wu, Z., & Ding, X. (2020) · Medical Image Analysis · doi:10.1016/j.media.2020.101693 · Cited by 1,095 · see citing works
“…a pre-trained segmentation model, the suggested framework alternates between 2 steps: 1) refining the current segmentation mask through the application of Graph Cut Boykov and Jolly (2001), and 2) minimizing segmentation loss for the test image by creating a pseudo ground truth segmentation mask.”
MethodInteractive medical image segmentation using deep learning with image-specific fine tuning
Wang, G., Li, W., Zuluaga, M. A., Pratt, R., Patel, P. A., Aertsen, M., Doel, T., David, A. L., Deprest, J., Ourselin, S., et al. (2018) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2018.2791721 · Cited by 843 · see citing works
Deep Features for Text Spotting
Jaderberg, M., Vedaldi, A., & Zisserman, A. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-10593-2_34 · Cited by 653 · see citing works
Improved Automatic Detection and Segmentation of Cell Nuclei in Histopathology Images
Al-Kofahi, Y., Lassoued, W., Lee, W., & Roysam, B. (2010) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2009.2035102 · Cited by 681 · see citing works
DeepIGeoS: A Deep Interactive Geodesic Framework for Medical Image Segmentation
Wang, G., Zuluaga, M. A., Li, W., Pratt, R., Patel, P. A., Aertsen, M., Doel, T., David, A. L., Deprest, J., Ourselin, S., et al. (2019) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2840695 · Cited by 502 · see citing works
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 · see citing works
Deep Interactive Object Selection
Xu, N., Price, B., Cohen, S., Yang, J., & Huang, T. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.47 · Cited by 460 · see citing works
Context based object categorization: A critical survey
Galleguillos, C., & Belongie, S. (2010) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2010.02.004 · Cited by 351 · see citing works
Automatic 3D liver location and segmentation via convolutional neural network and graph cut
Lu, F., Wu, F., Hu, P., Peng, Z., & Kong, D. (2017) · International Journal of Computer Assisted Radiology and Surgery · doi:10.1007/s11548-016-1467-3 · Cited by 284 · see citing works
“method using sparse representation of global and local image information for automatic 3D liver segmentation. Graph cut based methods, the extension of the classic graph cut proposed by Boykov et al. [6,5], are popular in liver segmentation [3,1,30]. A et al. [1] proposed a graph cut algorithm based on the iteratively…”
BackgroundMethodTumor-Cut: Segmentation of Brain Tumors on Contrast Enhanced MR Images for Radiosurgery Applications
Hamamci, A., Kucuk, N., Karaman, K., Engin, K., & Unal, G. (2012) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2011.2181857 · Cited by 286 · see citing works
GeoS: 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 · see citing works
A Survey of Data-driven and Knowledge-aware eXplainable AI
Li, X.-H., Cao, C. C., Shi, Y., Bai, W., Gao, H., Qiu, L., Wang, C., Gao, Y., Zhang, S., Xue, X., et al. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.2983930 · Cited by 224 · see citing works
Automatic Liver Segmentation Based on Shape Constraints and Deformable Graph Cut in CT Images
Li, G., Chen, X., Shi, F., Zhu, W., Tian, J., & Xiang, D. (2015) · IEEE Transactions on Image Processing · doi:10.1109/tip.2015.2481326 · Cited by 185 · see citing works
Luo, X., Wang, G., Song, T., Zhang, J., Aertsen, M., Deprest, J., Ourselin, S., Vercauteren, T., & Zhang, S. (2021) · Medical Image Analysis · doi:10.1016/j.media.2021.102102 · Cited by 126 · see citing works
Visual Tracking via Probability Continuous Outlier Model
Wang, D., & Lu, H. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2014.445 · Cited by 113 · see citing works
Volumetric memory network for interactive medical image segmentation
Zhou, T., Li, L., Bredell, G., Li, J., Unkelbach, J., & Konukoglu, E. (2023) · Medical Image Analysis · doi:10.1016/j.media.2022.102599 · Cited by 109 · see citing works
Wang, G., Zuluaga, M. A., Pratt, R., Aertsen, M., Doel, T., Klusmann, M., David, A. L., Deprest, J., Vercauteren, T., & Ourselin, S. (2016) · Medical Image Analysis · doi:10.1016/j.media.2016.04.009 · Cited by 73 · see citing works
The Shape Boltzmann Machine: A strong model of object shape
Eslami, S. M. A., Heess, N., & Winn, J. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247702 · Cited by 61 · see citing works
Li, H., Su, X., Wang, J., Kan, H., Han, T., Zeng, Y., & Chai, X. (2018) · Artificial Intelligence in Medicine · doi:10.1016/j.artmed.2017.11.001 · Cited by 59 · see citing works
Interactive segmentation of image volumes with Live Surface
Armstrong, C. J., Price, B. L., & Barrett, W. A. (2007) · Computers & Graphics · doi:10.1016/j.cag.2006.11.015 · Cited by 53 · see citing works
Porcine liver anatomy applied to biomedicine
Eberlova, L., Maleckova, A., Mik, P., Tonar, Z., Jirik, M., Mirka, H., Palek, R., Leupen, S., & Liska, V. (2020) · Journal of Surgical Research · doi:10.1016/j.jss.2019.12.038 · Cited by 45 · see citing works
Weideman, H. J., Stewart, C. V., Parham, J. R., Holmberg, J., Flynn, K., Calambokidis, J., Paul, D. B., Bedetti, A., Henley, M., Lepirei, J., et al. (2020) · 2020 IEEE Winter Conference on Applications of Computer Vision (WACV) · doi:10.1109/wacv45572.2020.9093266 · Cited by 32 · see citing works
A deep learning-based interactive medical image segmentation framework with sequential memory
Mikhailov, I., Chauveau, B., Bourdel, N., & Bartoli, A. (2024) · Computer Methods and Programs in Biomedicine · doi:10.1016/j.cmpb.2024.108038 · Cited by 15 · see citing works
Dynamically Balanced Online Random Forests for Interactive Scribble-Based Segmentation
Wang, G., Zuluaga, M. A., Pratt, R., Aertsen, M., Doel, T., Klusmann, M., David, A. L., Deprest, J., Vercauteren, T., & Ourselin, S. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-46723-8_41 · Cited by 14 · see citing works
Li, G., Zhang, G., & Qin, C. (2021) · Sensors · doi:10.3390/s21186100 · Cited by 2 · see citing works
Qian, C., Yang, H., & Li, J. (2023) · 2023 IEEE International Conference on Systems, Man, and Cybernetics (SMC) · doi:10.1109/smc53992.2023.10393973 · Cited by 1 · see citing works
Correction-aware interactive 3D tumor segmentation with sparse and revisable prompts
Li, H., & Li, H. (2026) · The Visual Computer · doi:10.1007/s00371-026-04560-5
“Instead of requiring the model to produce an acceptable mask in a single pass, the user can guide the model with simple prompts and correct remaining errors after seeing the prediction [4, 28].”
rNCA: Self-Repairing Segmentation Masks
Silbernagel, M., Alonso, A., Petersen, J., Ibragimov, B., de Bruijne, M., & Wyburd, M. K. (2025) · arXiv · doi:10.48550/arxiv.2512.13397
“Classical post-processing methods promote local smoothness but struggle to repair complex topology [16, 17], while learned refiners, such as CRF-RNN [18], integrate similar operations into an end-to-end framework, yet remain limited to local consistency rather than topological repair.”
- Authors
- Boykov, Y. Y., & Jolly, M.-P.
- Affiliations
- Siemens (United States) (US)
- ORCID
- Boykov, Y.Y.
- Venue
- Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-13
- Volume
- 1
- Pages
- 105-112
- OpenAlex
- W2169551590
- Cited by
- 3,674
- References
- 22
- Citations by year
- 2026: 38 · 2025: 58 · 2024: 65 · 2023: 70 · 2022: 87 · 2021: 126 · 2020: 151 · 2019: 161 · 2018: 177 · 2017: 222 · 2016: 243 · 2015: 264 · 2014: 289 · 2013: 305 · 2012: 275
- FWCI
- 11.46
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE/CVF International Conference on Computer Vision (ICCV) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Medical Image Segmentation Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Neural Network Applications
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Digital Image Processing Techniques
- Keywords
- interactive segmentation, graph cuts, hard and soft constraints, max-flow algorithm, medical image segmentation, video editing, Gestalt principles, object-background segmentation
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
