Abstract
Automatically partitioning images into regions (‘segmentation’) is challenging in terms of quality and performance. We propose a Minimum Spanning Tree-based algorithm with a novel graph-cutting heuristic, the usefulness of which is demonstrated by promising results obtained on standard images. In contrast to data-parallel schemes that divide images into independently processed tiles, the algorithm is designed to allow parallelisation without truncating objects at tile boundaries. A fast parallel implementation for shared-memory machines is shown to significantly outperform existing algorithms. It utilises a new microarchitecture-aware single-pass sort algorithm that is likely to be of independent interest.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Vanhamel, I., et al.: Scale Space Segmentation of Color Images Using Watersheds and Fuzzy Region Merging. In: ICIP (1), pp. 734–737 (2001)
Comaniciu, D., Meer, P.: Mean Shift Analysis and Applications. In: ICCV, pp. 1197–1203 (1999)
Wassenberg, J., Bulatov, D., Middelmann, W., Sanders, P.: Determination of Maximally Stable Extremal Regions in Large Images. In: Signal Processing, Pattern Recognition, and Applications (February 2008)
Felzenszwalb, P., Huttenlocher, D.: Efficient Graph-Based Image Segmentation. IJCV 59(2), 167–181 (2004)
Haralick, R., Shapiro, L.: Image Segmentation Techniques. CVGIP 29, 100–132 (1985)
Thomas, C., Ranchin, T., Wald, L., Chanussot, J.: Synthesis of Multispectral Images to High Spatial Resolution: A Critical Review of Fusion Methods Based on Remote Sensing Physics. IEEE Trans. Geoscience and Remote Sensing 46(5), 1301–1312 (2008)
Canny, J.: A Computational Approach to Edge Detection. In: RCV 1987, pp. 184–203 (1987)
Shin, D.H., Park, R.H., Yang, S., Jung, J.H.: Block-Based Noise Estimation Using Adaptive Gaussian Filtering. IEEE Trans. Consum. Electron. 51, 218–226 (2005)
Amer, A., Dubois, E.: Fast and Reliable Structure-Oriented Video Noise Estimation. IEEE Trans. Circuits Syst. Video Techn. 15(1), 113–118 (2005)
Weber, A.: The USC-SIPI Image Database, http://sipi.usc.edu/database/ (accessed 2008-10-06)
Buades, A., Coll, B., Morel, J.: The Staircasing Effect in Neighborhood Filters and its Solution. IEEE Trans. Image Processing 15(6), 1499–1505 (2006)
Dial, G., Bowen, H., Gerlach, F., Grodecki, J., Oleszczuk, R.: IKONOS satellite, imagery, and products. Remote Sensing of Environment 88(1-2), 23–36 (2003)
Sutter, H.: The Free Lunch is Over: A Fundamental Turn Toward Concurrency. Dr. Dobb’s Journal (March 2005)
Osipov, V., Sanders, P., Singler, J.: The Filter-Kruskal Minimum Spanning Tree Algorithm. In: Finocchi, I., Hershberger, J. (eds.) ALENEX, pp. 52–61. SIAM, Philadelphia (2009)
Wassenberg, J., Middelmann, W., Sanders, P.: An Efficient Parallel Algorithm for Graph-Based Image Segmentation (June 2009), http://algo2.iti.uni-karlsruhe.de/wassenberg/wassenberg09parallelSegmentation.pdf
Zunic, J., Sladoje, N.: Efficiency of Characterizing Ellipses and Ellipsoids by Discrete Moments. IEEE Trans. Pattern Anal. Mach. Intell. 22(4), 407–414 (2000)
Nistér, D., Stewénius, H.: Linear Time Maximally Stable Extremal Regions. In: Forsyth, D., Torr, P., Zisserman, A. (eds.) ECCV 2008, Part II. LNCS, vol. 5303, pp. 183–196. Springer, Heidelberg (2008)
Harfst, G., Reingold, E.: A Potential-Based Amortized Analysis of the Union-Find Data Structure. SIGACT 31, 86–95 (2000)
Paris, S., Durand, F.: A fast approximation of the bilateral filter using a signal processing approach. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3954, pp. 568–580. Springer, Heidelberg (2006)
Robust Image Understanding Lab: EDISON System, http://www.caip.rutgers.edu/riul/research/code/EDISON/doc/segm.html (accessed 2008-09-23)
Felzenszwalb, P.: Efficient Graph-Based Image Segmentation (March 2007), http://people.cs.uchicago.edu/~pff/segment/ (accessed 2008-01-11)
Besedin, D.: RightMark Memory Analyzer, http://cpu.rightmark.org (accessed 2009-01-09)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wassenberg, J., Middelmann, W., Sanders, P. (2009). An Efficient Parallel Algorithm for Graph-Based Image Segmentation. In: Jiang, X., Petkov, N. (eds) Computer Analysis of Images and Patterns. CAIP 2009. Lecture Notes in Computer Science, vol 5702. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03767-2_122
Download citation
DOI: https://doi.org/10.1007/978-3-642-03767-2_122
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03766-5
Online ISBN: 978-3-642-03767-2
eBook Packages: Computer ScienceComputer Science (R0)