Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

GPU implementations of a relaxation scheme for image partitioning: GLSL versus CUDA

  • Published:
Computing and Visualization in Science

Abstract

The GPU programmability opens a new perspective for algorithms that have not been studied and used for real applications on commodity state-of-the-art hardware due to their computational expenses. In this paper, we present three implementations of a partitioning algorithm for multi-channel images, which extends an original algorithm for single-channel images presented in the early 1990’s. The segmentation algorithm is based on the information theory concept of minimum description length, which leads to the formulation of an energy functional. The optimal solution is obtained by minimizing the functional. The minimization approach follows a graduated non-convexity approach, which leads to a fully explicit scheme. As the scheme is applied to all pixels of the image simultaneously, it is naturally parallelizable. Besides the optimized sequential implementation in C++ we developed a GLSL version of the algorithm using vertex and fragment shaders as well as a CUDA version using global memory, shared memory, and texture memory. We compare the performance of the implementations, discuss the implementation details, and show that suitability of this algorithm for GPU allows it to become a comparable alternative to the modern partitioning algorithm (multi-label Graph-Cuts).

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.

References

  1. Blake A., Zisserman A.: Visual Reconstruction. MIT Press, Cambridge, MA (1987)

    Google Scholar 

  2. Boykov Y., Veksler O., Zabih R.: Efficient restoration of multicolor image with independent noise. Technical report (1998)

  3. Boykov Y., Veksler O., Zabih R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell.23(11), 1222–1239 (1999)

    Article  Google Scholar 

  4. CUDA:http://www.nvidia.com/

  5. Figueiredo M.A.T., Leitão J.M.N.: Unsupervised image restoration and edge location using compound gauss-markov random fields and the MDL principle. IEEE Trans. Image Process.6(8), 1089–1102 (1997)

    Article  Google Scholar 

  6. GCC:http://gcc.gnu.org/

  7. Geman S., Geman D.: Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. Readings in uncertain reasoning (1990)

  8. GLSL:http://www.opengl.org/documentation/glsl/

  9. Goeddeke D.:http://www.mathematik.uni-dortmund.de/goeddeke/gpgpu/tutorial.html

  10. Gruenwald P.D.: The Minimum Description Length principle. The MIT Press, Cambridge, MA (2007)

    Google Scholar 

  11. Ivanovska T.: Efficient multichannel image partitioning: theory and application. Ph.D. thesis, Jacobs University Bremen (2009)

  12. Ivanovska T., Hahn H.K., Linsen L.: On global mdl-based multichannel image restoration and partitioning. In: 20th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG) (2012)

  13. Leclerc Y.G.: Constructing simple stable descriptions for image partitioning. J. Comput. Vis.3(1), 73–102 (1989)

    Article  Google Scholar 

  14. Lehmann E.L., Casella G.: Theory of Point Estimation (Springer Texts in Statistics). Springer, Berlin (2003)

    Google Scholar 

  15. Li S.Z.: Markov Random Field Modeling in Image Analysis. Springer, New York, Inc. (2001)http://portal.acm.org/citation.cfm?id=381180

  16. Mumford D., Shah J.: Optimal approximation by piecewise smooth functions and associated variational problems. Commun. Pure Appl. Math.42, 577–684 (1989)

    Article MathSciNet MATH  Google Scholar 

  17. Owens J.D., Houston M., Luebke D., Green S., Stone J.E., Phillips J.C.: Gpu computing. Proc. IEEE96 (5), 879–899 (2008). doi:10.1109/JPROC.2008.917757.http://dx.doi.org/10.1109/JPROC.2008.917757

  18. Owens J.D. et al.: A survey of general-purpose computation on graphics hardware. Comput. Graph. Forum26(1), 80–133 (2007)

    Article  Google Scholar 

  19. Rost R.J.: OpenGL Shading Language. Addison-Wesley Professional, Reading, MA (2006)

    Google Scholar 

  20. Szeliski R., Zabih R., Scharstein D., Veksler O., Kolmogorov V., Agarwala A., Tappen M., Rother C.: A comparative study of energy minimization methods for markov random fields with smoothness-based priors. IEEE Trans. Pattern Anal. Mach. Intell.30(6), 1068–1080 (2008)

    Article  Google Scholar 

  21. Vineet V., Narayanan P.J.: Cuda cuts: Fast graph cuts on the gpu. Vis. Pattern Recogn. Workshop0, 1–8 (2008). doi:10.1109/CVPRW.2008.4563095

    Google Scholar 

  22. Vineet V., Narayanan P.J.: Solving multilabel mrfs using incremental alpha-expansion on the gpus. In: Ninth Asian Conference on Computer Vision (ACCV 2009), vol. poster (2009)

  23. Vision:http://vision.middlebury.edu/MRF/

Download references

Author information

Authors and Affiliations

  1. Institute of Community Medicine, Ernst-Moritz-Arndt University, Greifswald, Germany

    Tetyana Ivanovska & Henry Völzke

  2. School of Engineering and Science, Jacobs University, Bremen, Germany

    Lars Linsen

  3. Fraunhofer MeVis, Bremen, Germany

    Horst K. Hahn

Authors
  1. Tetyana Ivanovska
  2. Lars Linsen
  3. Horst K. Hahn
  4. Henry Völzke

Corresponding author

Correspondence toTetyana Ivanovska.

Additional information

Communicated by: Gabrid Wittum.

Rights and permissions

About this article

Cite this article

Ivanovska, T., Linsen, L., Hahn, H.K.et al. GPU implementations of a relaxation scheme for image partitioning: GLSL versus CUDA.Comput. Visual Sci.14, 217–226 (2011). https://doi.org/10.1007/s00791-012-0176-x

Download citation

Keywords

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp