×

Serial and parallel approaches for image segmentation by numerical minimization of a second-order functional. (English) Zbl 1426.65083

Summary: Because of its attractive features, second order segmentation has shown to be a promising tool in remote sensing. A known drawback about its implementation is computational complexity, above all for large set of data. Recently in [M. Zanetti et al., “Numerical minimization of a second-order functional for image segmentation”, Commun. Nonlinear Sci. Numer. Simul. 36, 528–548 (2016; doi:10.1016/j.cnsns.2015.12.018)], an efficient version of the block-coordinate descent algorithm (BCDA) has been proposed for the minimization of a second order elliptic approximation of the Blake-Zissermann functional. Although the parallelization of linear algebra operations is expected to increase the performance of BCDA when addressing the segmentation of large-size gridded data (e.g., full-scene images or Digital Surface Models (DSMs)), numerical evidence shows that this is not sufficient to get significant reduction of computational time. Therefore a novel approach is proposed which exploits a decomposition technique of the image domain into tiles. The solution can be computed by applying BCDA on each tile in parallel way and combining the partial results corresponding to the different blocks of variables through a proper interconnection rule. We prove that this parallel method (OPARBCDA) generates a sequence of iterates which converges to a critical point of the functional on the level set devised by the starting point. Furthermore, we show that the parallel method can be efficiently implemented even in a commodity multicore CPU. Numerical results are provided to evaluate the efficiency of the parallel scheme on large images in terms of computational cost and its effectiveness with respect to the behavior on the tile junctions.

MSC:

65K10 Numerical optimization and variational techniques
49J45 Methods involving semicontinuity and convergence; relaxation
65K05 Numerical mathematical programming methods

Software:

Thrust; CUSP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zanetti, M.; Ruggiero, V.; Miranda Jr., M., Numerical minimization of a second-order functional for image segmentation, Commun. Nonlinear Sci. Numer. Simul., 36, 528-548 (2016) · Zbl 1470.94026
[2] Mumford, D.; Shah, J., Optimal approximations by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42, 5, 577-685 (1989) · Zbl 0691.49036
[3] Blake, A.; Zisserman, A., Visual reconstruction, MIT Press Series in Artificial Intelligence (1987), MIT Press: MIT Press Cambridge, MA
[4] Carriero, M.; Leaci, A.; Tomarelli, F., A second order model in image segmentation: Blake & Zisserman functional, Variational Methods for Discontinuous Structures (Como, 1994), 25, 57-72 (1996), Birkhäuser: Birkhäuser Basel · Zbl 0915.49004
[5] Carriero, M.; Leaci, A.; Tomarelli, F., A survey on the Blake-Zisserman functional, Milan J. Math., 83, 2, 397-420 (2015) · Zbl 1330.49010
[6] Ambrosio, L.; Tortorelli, V. M., Approximation of functionals depending on jumps by elliptic functionals via Γ-convergence, Comm. Pure Appl. Math., 43, 8, 999-1036 (1990) · Zbl 0722.49020
[7] D’Ambra, P.; Tartaglione, G., Solution of Ambrosio-Tortorelli model for image segmentation by generalized relaxation method, Commun. Nonlinear Sci. Numer. Simul., 20, 3, 819-831 (2015)
[8] Bellettini, G.; Coscia, A., Approximation of a functional depending on jumps and corners, Bollettino Unione Matematica Italiana B (7), 8, 1, 151-181 (1994) · Zbl 0808.49014
[9] Bellettini, G.; Coscia, A., Discrete approximation of a free discontinuity problem, Numer. Funct. Anal. Optim., 15, 3-4, 201-224 (1994) · Zbl 0806.49002
[10] Ambrosio, L.; Faina, L.; March, R., Variational approximation of a second order free discontinuity problem in computer vision, SIAM J. Math. Anal., 32, 6, 1171-1197(electronic) (2001) · Zbl 0996.46014
[11] Grippo, L.; Sciandrone, M., Globally convergent block-coordinate techniques for unconstrained optimization, Optim. Methods Softw., 10, 4, 587-637 (1999) · Zbl 0940.65070
[12] Zanetti, M.; Zanella, R.; Bruzzone, L., A tiling procedure for second-order variational segmentation of large size remote sensing images, Proceedings of IEEE International Geoscience and Remote Sensing Symposium, 6902-6905 (2016)
[13] Zanella, R.; Zanetti, M.; Ruggiero, V., A parallel approach for image segmentation by numerical minimization of a second order functional, 1776, 090035 (2016)
[14] Noll, D.; Rondepierre, A., Convergence of linesearch and trust-region methods using the Kurdyka-Łojasiewicz inequality, Computational and Analytical Mathematics. Computational and Analytical Mathematics, Springer Proceedings in Mathematics & Statistics, 50, 593-611 (2013), Springer: Springer New York · Zbl 1283.65061
[15] Attouch, H.; Bolte, J.; Svaiter, B. F., Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., Ser. A, 137, 91-129 (2013) · Zbl 1260.49048
[16] Bolte, J.; Sabach, S.; Teboulle, M., Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., Ser. A, 146, 459-494 (2014) · Zbl 1297.90125
[17] Carriero, M.; Leaci, A.; Tomarelli, F., Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates, J. Optim. Theory Appl., 165, 3, 874-900 (2015) · Zbl 1316.49039
[18] Mangasarian, O. L., Parallel gradient distribution in unconstrained optimization, SIAM J. Optim., 33, 1916-1925 (1995) · Zbl 0843.90111
[21] Ortega-Arjona, J. L.; Roberts, G. R., Architectural patterns for parallel programming, Proceedings of the Third European Conference on Pattern Languages of Programming and Computing (EuroPLoP98) (1988), Kloster Irsee: Kloster Irsee Germany
[22] Butenhof, D. R., Programming with POSIX Threads (1997), Addison-Wesley Professional
[23] Sutter, H.; Alexandrescu, A., CPP Coding Standards: 101 Rules, Guidelines and Best Practices (2004), Addison-Wesley Longman
[24] Goldstein, T.; Osher, S., The split Bregman method for L1-regularized problems, SIAM J. Imaging Sci., 2, 2, 323-343 (2009) · Zbl 1177.65088
[26] D’Ambra, P.; Filippone, S., A parallel generalized relaxation method for high-performance image segmentation on GPUs, J. Comput. Appl. Math., 293, 35-44 (2016) · Zbl 1322.65071
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.