Fast multiscale image segmentation
Published 7 November 2002
E. Sharon, Achi Brandt, Ronen Basri
Citations250
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A fast, multiscale algorithm for image segmentation that uses modern numeric techniques to find an approximate solution to normalized cut measures in time that is linear in the size of the image with only a few dozen operations per pixel.
Abstract
We introduce a fast, multiscale algorithm for image segmentation. Our algorithm uses modern numeric techniques to find an approximate solution to normalized cut measures in time that is linear in the size of the image with only a few dozen operations per pixel. In just one pass the algorithm provides a complete hierarchical decomposition of the image into segments. The algorithm detects the segments by applying a process of recursive coarsening in which the same minimization problem is represented with fewer and fewer variables producing an irregular pyramid. During this coarsening process we may compute additional internal statistics of the emerging segments and use these statistics to facilitate the segmentation process. Once the pyramid is completed it is scanned from the top down to associate pixels close to the boundaries of segments with the appropriate segment. The algorithm is inspired by algebraic multigrid (AMG) solvers of minimization problems of heat or electric networks. We demonstrate the algorithm by applying it to real images.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular BiologyEngineering
IEEE Transactions on Pattern Analysis and Machine IntelligenceStochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
17,980 Citations1984Stuart Geman, Donald Geman
The analogy between images and statistical mechanics systems is made and the analogous operation under the posterior distribution yields the maximum a posteriori (MAP) estimate of the image given the degraded observations, creating a highly parallel ``relaxation'' algorithm for MAP estimation.
Addison-Wesley Longman Publishing Co., Inc. eBooksComputer and Robot Vision
3,948 Citations1991Robert M. Haralock, Linda G. Shapiro
This two-volume set is an authoritative, comprehensive, modern work on computer vision that covers all of the different areas of vision with a balanced and unified approach.
Pattern RecognitionA review on image segmentation techniques
3,706 Citations1993Nikhil R. Pal, Sankar K. Pal
Attempts have been made to cover both fuzzy and non-fuzzy techniques including color image segmentation and neural network based approaches, which addresses the issue of quantitative evaluation of segmentation results.
Journal of the Royal Statistical Society Series A (General)Pattern Classification and Scene Analysis.
3,240 Citations1974Mairi Clarke, Richard O. Duda +1 more
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn optimal graph theoretic approach to data clustering: theory and its application to image segmentation
1,130 Citations1993Zhenyu Wu, Richard M. Leahy
A novel graph theoretic approach for data clustering is presented and its application to the image segmentation problem is demonstrated, resulting in an optimal solution equivalent to that obtained by partitioning the complete equivalent tree and is able to handle very large graphs with several hundred thousand vertices.
Normalized cuts and image segmentation
863 Citations2002Jianbo Shi, Jitendra Malik
This work treats image segmentation as a graph partitioning problem and proposes a novel global criterion, the normalized cut, for segmenting the graph, which measures both the total dissimilarity between the different groups as well as the total similarity within the groups.
Segmentation using eigenvectors: a unifying view
722 Citations1999Yaakov Weiss
A unified treatment of eigenvectors of block matrices based on eigendecompositions in the context of segmentation is given, and close connections between them are shown while highlighting their distinguishing features.
IEEE Transactions on Pattern Analysis and Machine IntelligenceEfficient Implementation of the Fuzzy c-Means Clustering Algorithms
622 Citations1986Robert Cannon, Jitendra V. Dave +1 more
An approximate fuzzy c-means (AFCM) implementation based upon replacing the necessary ``exact'' variates in the FCM equation with integer-valued or real-valued estimates enables AFCM to exploit a lookup table approach for computing Euclidean distances and for exponentiation.
IEEE Transactions on Pattern Analysis and Machine IntelligenceIntegrating region growing and edge detection
536 Citations1990T. Pavlidis, Yuh-Tay Liow
Lecture notes in computer scienceA factorization approach to grouping
296 Citations1998P. Perona, William T. Freeman
The foreground group in a scene may be ‘discovered’ and computed as a factorized approximation to the pairwise affinity of the elements in the scene, and an algorithm called ‘affinity factorization’ is obtained which may be used for grouping.
"Ratio regions": a technique for image segmentation
147 Citations1996Ingemar J. Cox, Satish Rao +1 more
A image segmentation algorithm in which the segmented region has both an exterior boundary cost and an interior benefit associated with it, and how to efficiently compute an approximation to common snakes under the additional constraint that it enclose a given point is shown.
SIAM Journal on Numerical AnalysisRigorous Quantitative Analysis of Multigrid, I. Constant Coefficients Two-Level Cycle with $L_2 $-Norm
144 Citations1994Achi Brandt
It is proved that, in the limit of small meshsizes, these predicted factors are indeed obtained, provided the cycle is supplemented with a proper processing at and near the boundaries, and costs negligible extra computer work.
Kluwer international series in engineering and computer scienceA Pyramid Framework for Early Vision
139 Citations1994Jean-Michel Jolion, Azriel Rosenfeld
Computer Vision and Image UnderstandingImage Segmentation from Consensus Information
75 Citations1997Kyu‐Jin Cho, Peter Meer
A new approach toward image segmentation is proposed in which a set of slightly different segmentations is derived from the same input and the final result is based on the consensus among them, using the hierarchical, RAG pyramid technique.
Pattern RecognitionImage segmentation using a dynamic thresholding pyramid
26 Citations1989M. Spann, Caspar Horne
Results show that the algorithm gives accurate segmentations even in low signal to noise ratios, and by applying a merging process followed by a classification step, accurate segmentation are obtained for both natural and synthetic images without the need for a priori knowledge.
Computer Vision Graphics and Image ProcessingVariable pyramid structures for image segmentation
16 Citations1990Stefano Baronti, Andrea Casini +3 more
The efficacy of increasing the span at the very last iterations in order to correct the link deficiency of the boundary nodes is reported and a method which separate segment roots at any level in the pyramid and mergess the segments under the constraint of the maximum number of regions to be distinguished is reported.
Learning to form large groups of salient image features
14 Citations2002Sudeep Sarkar
A novel strategy to adapt the perceptual organization process to an object and its contest in a scene and the significant role of photometric attributes in grouping and the ability to perform figure-ground segmentation from a set of local relations, each defined over a small number of primitives are offered.