The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Normalized cuts and image segmentation
Abstract
We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We applied this approach to segmenting static images, as well as motion sequences, and found the results to be very encouraging.
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
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Cited by
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Martin, D., Fowlkes, C., Tal, D., & Malik, J. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937655 · Cited by 8,216
Self-citationFast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988
A Comprehensive Survey on Transfer Learning
Zhuang, F., Qi, Z., Duan, K., Xi, D., Zhu, Y., Zhu, H., Xiong, H., & He, Q. (2021) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3004555 · Cited by 6,678
Selective Search for Object Recognition
Uijlings, J. R. R., van de Sande, K. E. A., Gevers, T., & Smeulders, A. W. M. (2013) · International Journal of Computer Vision · doi:10.1007/s11263-013-0620-5 · Cited by 5,980
OrthoMCL: Identification of Ortholog Groups for Eukaryotic Genomes
Li, L., Stoeckert, C. J., & Roos, D. S. (2003) · Genome Research · doi:10.1101/gr.1224503 · Cited by 5,707
Dimensionality Reduction by Learning an Invariant Mapping
Hadsell, R., Chopra, S., & LeCun, Y. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 (CVPR'06) · doi:10.1109/cvpr.2006.100 · Cited by 5,336
Deep Clustering for Unsupervised Learning of Visual Features
Caron, M., Bojanowski, P., Joulin, A., & Douze, M. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-01264-9_9 · Cited by 2,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
Feature Selection: A Data Perspective
Li, J., Cheng, K., Wang, S., Morstatter, F., Trevino, R. P., Tang, J., & Liu, H. (2018) · ACM Computing Surveys · doi:10.1145/3136625 · Cited by 2,442
Statistical mechanics of community detection
Reichardt, J., & Bornholdt, S. (2006) · Physical Review E · doi:10.1103/physreve.74.016110 · Cited by 2,048
A Comprehensive Survey of Clustering Algorithms
Xu, D., & Tian, Y. (2015) · Annals of Data Science · doi:10.1007/s40745-015-0040-1 · Cited by 1,939
Graph Cuts and Efficient N-D Image Segmentation
Boykov, Y., & Funka-Lea, G. (2006) · International Journal of Computer Vision · doi:10.1007/s11263-006-7934-5 · Cited by 1,910
Graph embedding techniques, applications, and performance: A survey
Goyal, P., & Ferrara, E. (2018) · Knowledge-Based Systems · doi:10.1016/j.knosys.2018.03.022 · Cited by 1,801
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 survey of content-based image retrieval with high-level semantics
Liu, Y., Zhang, D., Lu, G., & Ma, W.-Y. (2007) · Pattern Recognition · doi:10.1016/j.patcog.2006.04.045 · Cited by 1,696
A whole brain fMRI atlas generated via spatially constrained spectral clustering
Craddock, R. C., James, G. A., Holtzheimer, P. E., Hu, X. P., & Mayberg, H. S. (2012) · Human Brain Mapping · doi:10.1002/hbm.21333 · Cited by 1,636
Graph based anomaly detection and description: a survey
Akoglu, L., Tong, H., & Koutra, D. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0365-y · Cited by 1,504
Fouss, F., Pirotte, A., Renders, J.-M., & Saerens, M. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.46 · Cited by 1,265
The hippocampus as a predictive map
Stachenfeld, K. L., Botvinick, M. M., & Gershman, S. J. (2017) · Nature Neuroscience · doi:10.1038/nn.4650 · Cited by 1,000
van den Heuvel, M. P., Mandl, R. C. W., Kahn, R. S., & Hulshoff Pol, H. E. (2009) · Human Brain Mapping · doi:10.1002/hbm.20737 · Cited by 987
Learning Representations for Automatic Colorization
Larsson, G., Maire, M., & Shakhnarovich, G. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-46493-0_35 · Cited by 946
Joint Unsupervised Learning of Deep Representations and Image Clusters
Yang, J., Parikh, D., & Batra, D. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.556 · Cited by 879
CNN: Single-label to Multi-label
Wei, Y., Xia, W., Huang, J., Ni, B., Dong, J., Zhao, Y., & Yan, S. (2014) · arXiv · doi:10.48550/arxiv.1406.5726 · Cited by 784
Three systems of insular functional connectivity identified with cluster analysis
Deen, B., Pitskel, N. B., & Pelphrey, K. A. (2011) · Cerebral Cortex · doi:10.1093/cercor/bhq186 · Cited by 716
Network Representation Learning: A Survey
Zhang, D., Yin, J., Zhu, X., & Zhang, C. (2020) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2018.2850013 · Cited by 714
Semantic Image Segmentation via Deep Parsing Network
Liu, Z., Li, X., Luo, P., Loy, C.-C., & Tang, X. (2015) · 2015 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.162 · Cited by 675
Consistency of spectral clustering
von Luxburg, U., Belkin, M., & Bousquet, O. (2008) · The Annals of Statistics · doi:10.1214/009053607000000640 · Cited by 540
Deep Clustering for Unsupervised Learning of Visual Features
Caron, M., Bojanowski, P., Joulin, A., & Douze, M. (2018) · arXiv · doi:10.48550/arxiv.1807.05520 · Cited by 533
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
Spread of (mis)information in social networks
Acemoglu, D., Ozdaglar, A., & ParandehGheibi, A. (2010) · Games and Economic Behavior · doi:10.1016/j.geb.2010.01.005 · Cited by 444
Morphological diversity of single neurons in molecularly defined cell types
Peng, H., Xie, P., Liu, L., Kuang, X., Wang, Y., Qu, L., Gong, H., Jiang, S., Li, A., Ruan, Z., et al. (2021) · Nature · doi:10.1038/s41586-021-03941-1 · Cited by 417
Perceiver: General Perception with Iterative Attention
Jaegle, A., Gimeno, F., Brock, A., Zisserman, A., Vinyals, O., & Carreira, J. (2021) · arXiv · doi:10.48550/arxiv.2103.03206 · Cited by 414
Convolutional Networks Can Learn to Generate Affinity Graphs for Image Segmentation
Turaga, S. C., Murray, J. F., Jain, V., Roth, F., Helmstaedter, M., Briggman, K., Denk, W., & Seung, H. S. (2010) · Neural Computation · doi:10.1162/neco.2009.10-08-881 · Cited by 376
Leveraging social media networks for classification
Tang, L., & Liu, H. (2011) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-010-0210-x · Cited by 360
The Use of Mobile Devices in Aiding Dietary Assessment and Evaluation
Zhu, F., Bosch, M., Woo, I., Kim, S., Boushey, C. J., Ebert, D. S., & Delp, E. J. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2010.2051471 · Cited by 355
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
Learning Depth with Convolutional Spatial Propagation Network
Cheng, X., Wang, P., & Yang, R. (2018) · arXiv · doi:10.48550/arxiv.1810.02695 · Cited by 345
Reassembling fractured objects by geometric matching
Huang, Q.-X., Flöry, S., Gelfand, N., Hofer, M., & Pottmann, H. (2006) · ACM Transactions on Graphics · doi:10.1145/1141911.1141925 · Cited by 329
Data Fusion and Multicue Data Matching by Diffusion Maps
Lafon, S., Keller, Y., & Coifman, R. R. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.223 · Cited by 312
Automatic breast ultrasound image segmentation: a survey
Xian, M., Zhang, Y., Cheng, H. D., Xu, F., Zhang, B., & Ding, J. (2018) · Pattern Recognition · doi:10.1016/j.patcog.2018.02.012 · Cited by 284
Unsupervised Semantic Segmentation by Contrasting Object Mask Proposals
Van Gansbeke, W., Vandenhende, S., Georgoulis, S., & Van Gool, L. (2021) · 2021 IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv48922.2021.00990 · Cited by 231
Crisp Boundary Detection Using Pointwise Mutual Information
Isola, P., Zoran, D., Krishnan, D., & Adelson, E. H. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-10578-9_52 · Cited by 199
Object Recognition in 3D Point Clouds Using Web Data and Domain Adaptation
Lai, K., & Fox, D. (2010) · The International Journal of Robotics Research · doi:10.1177/0278364910369190 · Cited by 152
Self-Supervised Transformers for Unsupervised Object Discovery using Normalized Cut
Wang, Y., Shen, X., Hu, S. X., Yuan, Y., Crowley, J. L., & Vaufreydaz, D. (2022) · 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr52688.2022.01414 · Cited by 155
Segmentation-Aware Convolutional Networks Using Local Attention Masks
Harley, A. W., Derpanis, K. G., & Kokkinos, I. (2017) · 2017 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.539 · Cited by 142
(2013) · Liverpool John Moores University · Cited by 133
Grauman, K., & Leibe, B. (2011) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.2200/s00332ed1v01y201103aim011 · Cited by 126
SegSort: Segmentation by Discriminative Sorting of Segments
Hwang, J.-J., Yu, S., Shi, J., Collins, M., Yang, T.-J., Zhang, X., & Chen, L.-C. (2019) · 2019 IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2019.00743 · Cited by 124
Self-citationDetermining sequencing depth in a single-cell RNA-seq experiment
Zhang, M. J., Ntranos, V., & Tse, D. (2020) · Nature Communications · doi:10.1038/s41467-020-14482-y · Cited by 112
${l_p}$-norms in One-Class Classification for Intrusion Detection in SCADA Systems
Nader, P., Honeine, P., & Beauseroy, P. (2014) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2014.2330796 · Cited by 122
Leveraging relational autocorrelation with latent group models
Neville, J., & Jensen, D. (2005) · Proceedings of the 4th international workshop on Multi-relational mining - MRDM '05 · doi:10.1145/1090193.1090201 · Cited by 121
New benchmark for image segmentation evaluation
Ge, F., Wang, S., & Liu, T. (2007) · Journal of Electronic Imaging · doi:10.1117/1.2762250 · Cited by 108
Evaluating Segmentation Error without Ground Truth
Kohlberger, T., Singh, V., Alvino, C., Bahlmann, C., & Grady, L. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33415-3_65 · Cited by 102
Semi-Supervised Classification of Network Data Using Very Few Labels
Lin, F., & Cohen, W. W. (2010) · 2010 International Conference on Advances in Social Networks Analysis and Mining · doi:10.1109/asonam.2010.19 · Cited by 96
Learning visual groups from co-occurrences in space and time
Isola, P., Zoran, D., Krishnan, D., & Adelson, E. H. (2015) · arXiv · doi:10.48550/arxiv.1511.06811 · Cited by 90
High-throughput histopathological image analysis via robust cell segmentation and hashing
Zhang, X., Xing, F., Su, H., Yang, L., & Zhang, S. (2015) · Medical Image Analysis · doi:10.1016/j.media.2015.10.005 · Cited by 87
Blind PRNU-Based Image Clustering for Source Identification
Marra, F., Poggi, G., Sansone, C., & Verdoliva, L. (2017) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2017.2701335 · Cited by 84
Algorithmic Challenges in Web Search Engines
Henzinger, M. R. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129079 · Cited by 81
Fine-Grained Urban Flow Prediction
Liang, Y., Ouyang, K., Sun, J., Wang, Y., Zhang, J., Zheng, Y., Rosenblum, D., & Zimmermann, R. (2021) · Proceedings of the Web Conference 2021 · doi:10.1145/3442381.3449792 · Cited by 89
Detecting multiple communities using quantum annealing on the D-Wave system
Negre, C. F. A., Ushijima-Mwesigwa, H., & Mniszewski, S. M. (2020) · PLOS ONE · doi:10.1371/journal.pone.0227538 · Cited by 80
Grouping with Asymmetric Affinities: A Game-Theoretic Perspective
Torsello, A., Bulo, S. R., & Pelillo, M. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 1 (CVPR'06) · doi:10.1109/cvpr.2006.130 · Cited by 71
Multilevel Combinatorial Optimization across Quantum Architectures
Ushijima-Mwesigwa, H., Shaydulin, R., Negre, C. F. A., Mniszewski, S. M., Alexeev, Y., & Safro, I. (2021) · ACM Transactions on Quantum Computing · doi:10.1145/3425607 · Cited by 57
Multi-scale Features for Detection and Segmentation of Rocks in Mars Images
Dunlop, H., Thompson, D. R., & Wettergreen, D. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383257 · Cited by 55
Mental Illness Detection at the World Well-Being Project for the CLPsych 2015 Shared Task
Preoţiuc-Pietro, D., Sap, M., Schwartz, H. A., & Ungar, L. (2015) · Proceedings of the 2nd Workshop on Computational Linguistics and Clinical Psychology: From Linguistic Signal to Clinical Reality · doi:10.3115/v1/w15-1205 · Cited by 54
DeepCut: Unsupervised Segmentation using Graph Neural Networks Clustering
Aflalo, A., Bagon, S., Kashti, T., & Eldar, Y. (2023) · 2023 IEEE/CVF International Conference on Computer Vision Workshops (ICCVW) · doi:10.1109/iccvw60793.2023.00010 · Cited by 53
Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss
HaoChen, J. Z., Wei, C., Gaidon, A., & Ma, T. (2021) · arXiv · doi:10.48550/arxiv.2106.04156 · Cited by 53
Magnetic eigenmaps for community detection in directed networks
Fanuel, M., Alaíz, C. M., & Suykens, J. A. K. (2017) · Physical Review E · doi:10.1103/physreve.95.022302 · Cited by 50
Peng, H., Xie, P., Liu, L., Kuang, X., Wang, Y., Qu, L., Gong, H., Jiang, S., Li, A., Ruan, Z., et al. (2019) · doi:10.1101/675280 · Cited by 47
On the Binding Problem in Artificial Neural Networks
Greff, K., van Steenkiste, S., & Schmidhuber, J. (2020) · arXiv · doi:10.48550/arxiv.2012.05208 · Cited by 102
Introspective Neural Networks for Generative Modeling
Lazarow, J., Jin, L., & Tu, Z. (2017) · 2017 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.302 · Cited by 49
Content-based image retrieval of digitized histopathology in boosted spectrally embedded spaces
Sridhar, A., Doyle, S., & Madabhushi, A. (2015) · Journal of Pathology Informatics · doi:10.4103/2153-3539.159441 · Cited by 34
Token Pooling in Vision Transformers
Marin, D., Chang, J.-H. R., Ranjan, A., Prabhu, A., Rastegari, M., & Tuzel, O. (2021) · arXiv · doi:10.48550/arxiv.2110.03860 · Cited by 34
The exact equivalence of distance and kernel methods in hypothesis testing
Shen, C., & Vogelstein, J. T. (2021) · AStA Advances in Statistical Analysis · doi:10.1007/s10182-020-00378-1 · Cited by 41
Meta-Evaluation of Image Segmentation Using Machine Learning
Zhang, H., Cholleti, S., Goldman, S. A., & Fritts, J. E. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 1 (CVPR'06) · doi:10.1109/cvpr.2006.185 · Cited by 32
Wei, Y., Chow, K.-P., & Yiu, S.-M. (2021) · Forensic Science International: Digital Investigation · doi:10.1016/j.fsidi.2021.301126 · Cited by 32
Wang, T., Peng, Q., Liu, B., Liu, Y., & Wang, Y. (2020) · Frontiers in Bioengineering and Biotechnology · doi:10.3389/fbioe.2020.00418 · Cited by 27
Detecting molecular subtypes from multi-omics datasets using SUMO
Sienkiewicz, K., Chen, J., Chatrath, A., Lawson, J. T., Sheffield, N. C., Zhang, L., & Ratan, A. (2022) · Cell Reports Methods · doi:10.1016/j.crmeth.2021.100152 · Cited by 18
Automatic Segmentation of Unknown Objects, with Application to Baggage Security
Grady, L., Singh, V., Kohlberger, T., Alvino, C., & Bahlmann, C. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33709-3_31 · Cited by 18
Pagnutti, G., Minto, L., & Zanuttigh, P. (2017) · IET Computer Vision · doi:10.1049/iet-cvi.2016.0502 · Cited by 14
Phylogenetic tree reconstruction via graph cut presented using a quantum-inspired computer
Onodera, W., Hara, N., Aoki, S., Asahi, T., & Sawamura, N. (2023) · Molecular Phylogenetics and Evolution · doi:10.1016/j.ympev.2022.107636 · Cited by 13
Local Regression Learning via Forest Classification for 2D/3D Deformable Registration
Chou, C.-R., & Pizer, S. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-05530-5_3 · Cited by 5
Metadata
- Authors
- Shi, J., & Malik, J.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2000
- Volume
- 22
- Issue
- 8
- Pages
- 888-905
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2121947440
- Cited by
- 15,502
- References
- 1
- FWCI
- 115.72
- Type
- journal article
- Language
- en
- Open access
- closed
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.
