[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

An Efficient Parallel Algorithm for Graph-Based Image Segmentation

  • Conference paper
Computer Analysis of Images and Patterns (CAIP 2009)

Part of the book series: Lecture Notes in Computer Science ((LNIP,volume 5702))

Included in the following conference series:

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

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Vanhamel, I., et al.: Scale Space Segmentation of Color Images Using Watersheds and Fuzzy Region Merging. In: ICIP (1), pp. 734–737 (2001)

    Google Scholar 

  2. Comaniciu, D., Meer, P.: Mean Shift Analysis and Applications. In: ICCV, pp. 1197–1203 (1999)

    Google Scholar 

  3. 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)

    Google Scholar 

  4. Felzenszwalb, P., Huttenlocher, D.: Efficient Graph-Based Image Segmentation. IJCV 59(2), 167–181 (2004)

    Article  Google Scholar 

  5. Haralick, R., Shapiro, L.: Image Segmentation Techniques. CVGIP 29, 100–132 (1985)

    Google Scholar 

  6. 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)

    Article  Google Scholar 

  7. Canny, J.: A Computational Approach to Edge Detection. In: RCV 1987, pp. 184–203 (1987)

    Google Scholar 

  8. 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)

    Article  Google Scholar 

  9. Amer, A., Dubois, E.: Fast and Reliable Structure-Oriented Video Noise Estimation. IEEE Trans. Circuits Syst. Video Techn. 15(1), 113–118 (2005)

    Article  Google Scholar 

  10. Weber, A.: The USC-SIPI Image Database, http://sipi.usc.edu/database/ (accessed 2008-10-06)

  11. Buades, A., Coll, B., Morel, J.: The Staircasing Effect in Neighborhood Filters and its Solution. IEEE Trans. Image Processing 15(6), 1499–1505 (2006)

    Article  Google Scholar 

  12. 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)

    Article  Google Scholar 

  13. Sutter, H.: The Free Lunch is Over: A Fundamental Turn Toward Concurrency. Dr. Dobb’s Journal (March 2005)

    Google Scholar 

  14. 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)

    Google Scholar 

  15. 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

  16. Zunic, J., Sladoje, N.: Efficiency of Characterizing Ellipses and Ellipsoids by Discrete Moments. IEEE Trans. Pattern Anal. Mach. Intell. 22(4), 407–414 (2000)

    Article  Google Scholar 

  17. 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)

    Chapter  Google Scholar 

  18. Harfst, G., Reingold, E.: A Potential-Based Amortized Analysis of the Union-Find Data Structure. SIGACT 31, 86–95 (2000)

    Article  Google Scholar 

  19. 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)

    Chapter  Google Scholar 

  20. Robust Image Understanding Lab: EDISON System, http://www.caip.rutgers.edu/riul/research/code/EDISON/doc/segm.html (accessed 2008-09-23)

  21. Felzenszwalb, P.: Efficient Graph-Based Image Segmentation (March 2007), http://people.cs.uchicago.edu/~pff/segment/ (accessed 2008-01-11)

  22. Besedin, D.: RightMark Memory Analyzer, http://cpu.rightmark.org (accessed 2009-01-09)

Download references

Author information

Authors and Affiliations

  1. FGAN-FOM, 76275, Ettlingen, Germany

    Jan Wassenberg & Wolfgang Middelmann

  2. Institute for Theoretical Informatics, Universität Karlsruhe, Germany

    Peter Sanders

Authors
  1. Jan Wassenberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wolfgang Middelmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Peter Sanders
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics and Computer Science, University of Münster, Einsteinstrasse 62, 48149, Münster, Germany

    Xiaoyi Jiang

  2. Institute of Mathematics and Computing Science, University of Groningen, Nijenborgh 9, 9747, Groningen, AG, The Netherlands

    Nicolai Petkov

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics