Regularized Tree Partitioning and Its Application to Unsupervised Image Segmentation
- 20 February 2014
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Image Processing
- Vol. 23 (4) , 1909-1922
Abstract
In this paper, we propose regularized tree partitioning approaches. We study normalized cut (NCut) and average cut (ACut) criteria over a tree, forming two approaches: 1) normalized tree partitioning (NTP) and 2) average tree partitioning (ATP). We give the properties that result in an efficient algorithm for NTP and ATP. In addition, we present the relations between the solutions of NTP and ATP over the maximum weight spanning tree of a graph and NCut and ACut over this graph. To demonstrate the effectiveness of the proposed approaches, we show its application to image segmentation over the Berkeley image segmentation data set and present qualitative and quantitative comparisons with state-of-the-art methods.Keywords
Funding Information
- 973 Program (2013CB329503, 618711, 618510, N_HKUST607/11)
This publication has 42 references indexed in Scilit:
- Some links between extremum spanning forests, watersheds and min-cutsImage and Vision Computing, 2010
- An evaluation metric for image segmentation of multiple objectsImage and Vision Computing, 2009
- Unsupervised segmentation of natural images via lossy data compressionComputer Vision and Image Understanding, 2008
- Image segmentation with ratio cutIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003
- Globally optimal regions and boundaries as minimum ratio weight cyclesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- An optimal graph theoretic approach to data clustering: theory and its application to image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 1993
- Ratio cut partitioning for hierarchical designsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- Graph theoretical clustering based on limited neighbourhood setsPattern Recognition, 1982
- Picture Segmentation by a Tree Traversal AlgorithmJournal of the ACM, 1976