A parallel generalized relaxation method for high-performance image segmentation on GPUs. (English) Zbl 1322.65071

Summary: Fast and scalable software modules for image segmentation are needed for modern high-throughput screening platforms in Computational Biology. Indeed, accurate segmentation is one of the main steps to be applied in a basic software pipeline aimed to extract accurate measurements from a large amount of images. Image segmentation is often formulated through a variational principle, where the solution is the minimum of a suitable functional, as in the case of the Ambrosio-Tortorelli model. Euler-Lagrange equations associated with the above model are a system of two coupled elliptic partial differential equations whose finite-difference discretization can be efficiently solved by a generalized relaxation method, such as Jacobi or Gauss-Seidel, corresponding to a first-order alternating minimization scheme. In this work we present a parallel software module for image segmentation based on the Parallel Sparse Basic Linear Algebra Subprograms (PSBLAS), a general-purpose library for parallel sparse matrix computations, using its Graphics Processing Unit (GPU) extensions that allow us to exploit in a simple and transparent way the performance capabilities of both multi-core CPUs and of many-core GPUs. We discuss performance results in terms of execution times and speed-up of the segmentation module running on GPU as well as on multi-core CPUs, in the analysis of 2D gray-scale images of mouse embryonic stem cells colonies coming from biological experiments.


65K10 Numerical optimization and variational techniques
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65Y05 Parallel numerical computation
68T45 Machine vision and scene understanding
65-04 Software, source code, etc. for problems pertaining to numerical analysis
Full Text: DOI


[1] Shariff, A.; Kangas, J.; Coelho, L. P.; Quinn, S.; Murphy, R. F., Automated image analysis for high content screening and analysis, J. Biomol. Screen., 15, 726-734, (2010)
[2] Aubert, G.; Kornprobst, P., Mathematical problems in image processing. partial differential equations and the calculus of variations, (2006), Springer-Verlag New York, USA · Zbl 1110.35001
[3] Bar, L., Mumford and Shah model and its applications to image segmentation and image restoration, (Handbook of Mathematical Methods in Imaging, Vol. I, (2011)), 1095-1157 · Zbl 1259.94009
[4] Vitti, A., The Mumford-Shah variational model for image segmentation: an overview of the theory, implementation and use, ISPRS J. Photogramm. Remote Sens., 69, 50-64, (2012)
[5] D’Ambra, P.; Tartaglione, G., Solution of ambrosio-tortorelli model for image segmentation by generalized relaxation method, Commun. Nonlinear Sci. Numer. Simul., 20, 819-831, (2015)
[6] Filippone, S.; Colajanni, M., PSBLAS: A library for parallel linear algebra computation on sparse matrices, ACM Trans. Math. Software, 26, 4, 527-550, (2000) · Zbl 1365.65128
[7] Filippone, S.; Buttari, A., Object-oriented techniques for sparse matrix computations in Fortran 2003, ACM Trans. Math. Software, 38, 4, 1-20, (2012) · Zbl 1365.65127
[8] Buttari, A.; D’Ambra, P.; di Serafino, D.; Filippone, S., 2LEV-D2P4: a package of high-performance preconditioners for scientific and engineering applications, Appl. Algebra Engrg. Comm. Comput., 18, 223-239, (2007) · Zbl 1122.65046
[9] D’Ambra, P.; di Serafino, D.; Filippone, S., MLD2P4: a package of parallel algebraic multilevel domain decomposition preconditioners in Fortran 95, ACM Trans. Math. Software, 37, 3, 7-23, (2010) · Zbl 1364.65276
[10] Cardellini, V.; Filippone, S.; Rouson, D., Design patterns for sparse-matrix computations on hybrid CPU/GPU platforms, Sci. Program., 22, 1, 1-19, (2014)
[11] Ambrosio, L.; Tortorelli, V. M., Approximation of functional depending on jumps by elliptic functionals via \(\Gamma\)-convergence, Comm. Pure Appl. Math., 43, 999-1036, (1990) · Zbl 0722.49020
[12] Braides, A., \(\Gamma\)-convergence for beginners, (2002), Oxford University Press Oxford, UK · Zbl 1198.49001
[13] Ruge, J.; Stüben, K., Algebraic multigrid, (McCormick, S. F., Multigrid Methods, Frontiers in Applied Mathematics, (1987), SIAM Philadelphia, USA), 73-130
[14] Saad, Y., Iterative methods for sparse linear systems, (2003), SIAM Philadelphia, USA · Zbl 1002.65042
[15] Expósito, R. R.; Taboada, G. L.; Ramos, S.; Touriño, J.; Doallo, R., General-purpose computation on GPUs for high performance cloud computing, Concurr. Comput.: Pract. Exp., 25, 12, 1628-1642, (2013)
[16] Bell, N.; Garland, M., Implementing sparse matrix-vector multiplication on throughput-oriented processors, (Proc. of Int. Conf. on High Performance Computing, Networking, Storage and Analysis, SC’09, (2009), ACM New York, NY, USA), 18:1-18:11
[17] Barbieri, D.; Cardellini, V.; Fanfarillo, A.; Filippone, S., Three storage formats for sparse matrices on GPGPUs, tech. rep. DICII RR-15.6, (2015), Università di Roma Tor Vergata, art.torvergata.it (February)
[18] F. Vázquez, G. Ortega, J.J. Fernández, E.M. Garzón, Improving the performance of the sparse matrix vector product with GPUs, in: Proc. of 10th IEEE Int. Conf. on Computer and Information Technology, CIT’10, 2010, pp. 1146-1151.
[19] Barbieri, D.; Cardellini, V.; Fanfarillo, A.; Filippone, S., Sparse matrix-vector multiplication on gpgpus, ACM Trans. Math. Software, (2015), submitted for publication · Zbl 1380.65079
[20] Grimes, R.; Kincaid, D.; Young, D., ITPACK 2.0 user’s guide, CNA-150, Center for Numerical Analysis, (1979), University of Texas
[21] NVIDIA Corp., CUDA cuSPARSE library, 2014. http://developer.nvidia.com/cusparse.
[22] C. Gregg, K. Hazelwood, Where is the data? Why you cannot debate CPU vs. GPU performance without the answer, in: Proc. of 2011 IEEE Int. Symp. on Performance Analysis of Systems and Software, ISPASS, 2011, pp. 134-144.
[23] PARALUTION user manual, tech. rep., (2015), www.paralution.com
[24] Langr, D.; Tvrdìk, P., Evaluation criteria for sparse matrix storage formats, IEEE Trans. Parallel Distrib. Syst., (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.