The DOI matches its Crossref record; 22 of the 22 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 have applied this approach to segmenting static images and found results very encouraging.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
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
Self-citationAlgorithms for Clustering Data
Sarle, W. S. (1990) · Technometrics · doi:10.1080/00401706.1990.10484648 · Cited by 7,865
Algorithms for clustering data
Flury, B. (1989) · Journal of Statistical Planning and Inference · doi:10.1016/0378-3758(89)90033-5 · Cited by 6,432
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
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
Blake, A., & Zisserman, A. (1987) · The MIT Press eBooks · doi:10.7551/mitpress/7132.001.0001 · Cited by 2,105
Partitioning Sparse Matrices with Eigenvectors of Graphs
Pothen, A., Simon, H. D., & Liou, K.-P. (1990) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0611030 · Cited by 1,684
Laws of organization in perceptual forms.
Wertheimer, M. (1938) · A source book of Gestalt psychology. · doi:10.1037/11496-005 · Cited by 1,493
Cited by
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
Self-citationFortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
Belkin, M., & Niyogi, P. (2003) · Neural Computation · doi:10.1162/089976603321780317 · Cited by 7,621
Efficient Graph-Based Image Segmentation
Felzenszwalb, P. F., & Huttenlocher, D. P. (2004) · International Journal of Computer Vision · doi:10.1023/b:visi.0000022288.19776.77 · Cited by 6,176
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
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
Learning patterns of activity using real-time tracking
Stauffer, C., & Grimson, W. E. L. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868677 · Cited by 3,248
SIMPLIcity: semantics-sensitive integrated matching for picture libraries
Wang, J. Z., Li, J., & Wiederhold, G. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.955109 · Cited by 2,196
Learning a classification model for segmentation
Ren, & Malik (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238308 · Cited by 1,765
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
Object Recognition as Machine Translation: Learning a Lexicon for a Fixed Image Vocabulary
Duygulu, P., Barnard, K., de Freitas, J. F. G., & Forsyth, D. A. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47979-1_7 · Cited by 1,608
Quattoni, A., & Torralba, A. (2009) · 2009 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2009.5206537 · Cited by 1,463
Colorization using optimization
Levin, A., Lischinski, D., & Weiss, Y. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015780 · Cited by 1,411
Mechanism Design via Differential Privacy
McSherry, F., & Talwar, K. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.66 · Cited by 1,371
Multiclass spectral clustering
Yu, & Shi (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238361 · Cited by 947
Robust Object Detection with Interleaved Categorization and Segmentation
Leibe, B., Leonardis, A., & Schiele, B. (2008) · International Journal of Computer Vision · doi:10.1007/s11263-007-0095-3 · Cited by 933
Spectral feature selection for supervised and unsupervised learning
Zhao, Z., & Liu, H. (2007) · Proceedings of the 24th international conference on Machine learning · doi:10.1145/1273496.1273641 · Cited by 906
Segmentation using eigenvectors: a unifying view
Weiss, Y. (1999) · Proceedings of the Seventh IEEE International Conference on Computer Vision · doi:10.1109/iccv.1999.790354 · Cited by 729
Spectral Biclustering of Microarray Data: Coclustering Genes and Conditions
Kluger, Y., Basri, R., Chang, J. T., & Gerstein, M. (2003) · Genome Research · doi:10.1101/gr.648603 · Cited by 726
Criminisi, A. (2011) · now publishers, Inc. eBooks · doi:10.1561/9781601985415 · Cited by 703
Using Multiple Segmentations to Discover Objects and their Extent in Image Collections
Russell, B. C., Freeman, W. T., Efros, A. A., Sivic, J., & Zisserman, A. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 (CVPR'06) · doi:10.1109/cvpr.2006.326 · Cited by 617
Ranking-based clustering of heterogeneous information networks with star network schema
Sun, Y., Yu, Y., & Han, J. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557107 · Cited by 513
A Closed Form Solution to Natural Image Matting
Levin, A., Lischinski, D., & Weiss, Y. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 1 (CVPR'06) · doi:10.1109/cvpr.2006.18 · Cited by 446
Zelnik-Manor, L., & Irani, M. (2005) · Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001 · doi:10.1109/cvpr.2001.990935 · Cited by 391
Semantic Modeling of Natural Scenes for Content-Based Image Retrieval
Vogel, J., & Schiele, B. (2007) · International Journal of Computer Vision · doi:10.1007/s11263-006-8614-1 · Cited by 384
On clusterings-good, bad and spectral
Kannan, R., Vempala, S., & Veta, A. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892125 · Cited by 372
Class-Specific, Top-Down Segmentation
Borenstein, E., & Ullman, S. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47967-8_8 · Cited by 364
Learning Eigenfunctions Links Spectral Embedding and Kernel PCA
Bengio, Y., Delalleau, O., Roux, N. L., Paiement, J.-F., Vincent, P., & Ouimet, M. (2004) · Neural Computation · doi:10.1162/0899766041732396 · Cited by 345
Motion segmentation and tracking using normalized cuts
Shi, J., & Malik, J. (2002) · Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271) · doi:10.1109/iccv.1998.710861 · Cited by 336
Self-citationA factorization approach to grouping
Perona, P., & Freeman, W. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0055696 · Cited by 299
Image segmentation with ratio cut
Wang, S., & Siskind, J. M. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1201819 · Cited by 293
Bipartite graph partitioning and data clustering
Zha, H., He, X., Ding, C., Simon, H., & Gu, M. (2001) · Proceedings of the tenth international conference on Information and knowledge management · doi:10.1145/502585.502591 · Cited by 291
Star Shape Prior for Graph-Cut Image Segmentation
Veksler, O. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88690-7_34 · Cited by 287
Improving Spatial Support for Objects via Multiple Segmentations
Malisiewicz, T., & Efros, A. A. (2007) · Procedings of the British Machine Vision Conference 2007 · doi:10.5244/c.21.55 · Cited by 280
Joulin, A., Bach, F., & Ponce, J. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247719 · Cited by 279
Textons, contours and regions: cue integration in image segmentation
Malik, J., Belongie, S., Shi, J., & Leung, T. (1999) · Proceedings of the Seventh IEEE International Conference on Computer Vision · doi:10.1109/iccv.1999.790346 · Cited by 273
Self-citationAdaptive Graph Completion Based Incomplete Multi-View Clustering
Wen, J., Yan, K., Zhang, Z., Xu, Y., Wang, J., Fei, L., & Zhang, B. (2021) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2020.3013408 · Cited by 256
Fast multiscale image segmentation
Sharon, E., Brandt, A., & Basri, R. (2002) · Proceedings IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2000 (Cat. No.PR00662) · doi:10.1109/cvpr.2000.855801 · Cited by 253
Chen, M., Zhang, Z., Wang, T., Backes, M., Humbert, M., & Zhang, Y. (2022) · Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3548606.3559352 · Cited by 133
Discovering genetic ancestry using spectral graph theory
Lee, A. B., Luca, D., Klei, L., Devlin, B., & Roeder, K. (2010) · Genetic Epidemiology · doi:10.1002/gepi.20434 · Cited by 108
“Finding the partition with the minimum cut is a well-studied problem; however, the minimum cut criterion favors separating individual vertices or ‘‘outliers’’ from the rest of the graph [Shi and Malik, 1997].”
BackgroundMental 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
“To obtain hard clusters of words we use spectral clustering (Shi and Malik, 2000; Ng et al., 2002).”
Method
Metadata
- Authors
- Shi, J., & Malik, J.
- Venue
- Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-22
- Pages
- 731-737
- ISSN
- 1063-6919 (ISSN-L)
- OpenAlex
- W2140000690
- Cited by
- 849
- References
- 22
- FWCI
- 31.57
- Type
- conference paper
- 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.