{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T00:56:12Z","timestamp":1772844972698,"version":"3.50.1"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319781983","type":"print"},{"value":"9783319781990","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-78199-0_15","type":"book-chapter","created":{"date-parts":[[2018,3,21]],"date-time":"2018-03-21T00:13:52Z","timestamp":1521591232000},"page":"220-234","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A Convex Approach to K-Means Clustering and Image Segmentation"],"prefix":"10.1007","author":[{"given":"Laurent","family":"Condat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,22]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1145\/331499.331504","volume":"31","author":"AK Jain","year":"1999","unstructured":"Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: a review. ACM Comput. Surv. 31, 264\u2013323 (1999)","journal-title":"ACM Comput. Surv."},{"key":"15_CR2","series-title":"ASA-SIAM Series on Statistics and Applied Probability","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718348","volume-title":"Data Clustering: Theory, Algorithms, and Applications","author":"G Gan","year":"2007","unstructured":"Gan, G., Ma, C., Wu, J.: Data Clustering: Theory, Algorithms, and Applications. ASA-SIAM Series on Statistics and Applied Probability. SIAM, Philadelphia (2007)"},{"issue":"1","key":"15_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1348\/000711005X48266","volume":"59","author":"D Steinley","year":"2006","unstructured":"Steinley, D.: K-means clustering: a half-century synthesis. Br. J. Math. Stat. Psychol. 59(1), 1\u201334 (2006)","journal-title":"Br. J. Math. Stat. Psychol."},{"issue":"4","key":"15_CR4","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1016\/0196-6774(91)90039-2","volume":"12","author":"X Wu","year":"1991","unstructured":"Wu, X.: Optimal quantization by matrix searching. J. Algorithms 12(4), 663\u2013673 (1991)","journal-title":"J. Algorithms"},{"issue":"1","key":"15_CR5","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1109\/89.221364","volume":"1","author":"FK Soong","year":"1993","unstructured":"Soong, F.K., Juang, B.H.: Optimal quantization of LSP parameters. IEEE Trans. Speech Audio Process. 1(1), 15\u201324 (1993)","journal-title":"IEEE Trans. Speech Audio Process."},{"issue":"2","key":"15_CR6","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245\u2013248 (2009)","journal-title":"Mach. Learn."},{"key":"15_CR7","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tcs.2010.05.034","volume":"442","author":"M Mahajan","year":"2012","unstructured":"Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The planar k-means problem is NP-hard. Theor. Comput. Sci. 442, 13\u201321 (2012). Special Issue on the Workshop on Algorithms and Computation (WALCOM 2009)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Brun, L., Tr\u00e9meau, A.: Color quantization. In: Digital Color Imaging Handbook, pp. 589\u2013638. CRC Press (2012)","DOI":"10.1201\/9781420041484-9"},{"issue":"4","key":"15_CR9","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.imavis.2010.10.002","volume":"29","author":"ME Celebi","year":"2011","unstructured":"Celebi, M.E.: Improving the performance of k-means for color quantization. Image Vis. Comput. 29(4), 260\u2013271 (2011)","journal-title":"Image Vis. Comput."},{"key":"15_CR10","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s11263-006-8711-1","volume":"72","author":"D Cremers","year":"2007","unstructured":"Cremers, D., Rousson, M., Deriche, R.: A review of statistical approaches to level set segmentation: integrating color, texture, motion and shape. Int. J. Comput. Vis. 72, 195\u2013215 (2007)","journal-title":"Int. J. Comput. Vis."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1007\/978-0-387-92920-0_25","volume-title":"Handbook of Mathematical Methods in Imaging","author":"L Bar","year":"2015","unstructured":"Bar, L., Chan, T.F., Chung, G., Jung, M., Kiryati, N., Sochen, N., Vese, L.A.: Mumford and Shah model and its applications to image segmentation and image restoration. In: Scherzer, O. (ed.) Handbook of Mathematical Methods in Imaging, pp. 1095\u20131157. Springer, New York (2015). https:\/\/doi.org\/10.1007\/978-0-387-92920-0_25"},{"key":"15_CR12","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1002\/cpa.3160420503","volume":"42","author":"D Mumford","year":"1989","unstructured":"Mumford, D., Shah, J.: Optimal approximations by piecewise smooth functions and associated variational problems. Commun. Pure Appl. Math. 42, 577\u2013685 (1989)","journal-title":"Commun. Pure Appl. Math."},{"issue":"3","key":"15_CR13","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1137\/16M1075247","volume":"10","author":"L Condat","year":"2017","unstructured":"Condat, L.: Discrete total variation: new definition and minimization. SIAM J. Imaging Sci. 10(3), 1258\u20131290 (2017)","journal-title":"SIAM J. Imaging Sci."},{"issue":"4","key":"15_CR14","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.1137\/110856733","volume":"5","author":"A Chambolle","year":"2012","unstructured":"Chambolle, A., Cremers, D., Pock, T.: A convex approach to minimal partitions. SIAM J. Imaging Sci. 5(4), 1113\u20131158 (2012)","journal-title":"SIAM J. Imaging Sci."},{"issue":"12","key":"15_CR15","doi-asserted-by":"crossref","first-page":"1827","DOI":"10.1109\/LSP.2017.2752261","volume":"24","author":"N Pustelnik","year":"2017","unstructured":"Pustelnik, N., Condat, L.: Proximity operator of a sum of functions; application to depth map estimation. IEEE Sig. Process. Lett. 24(12), 1827\u20131831 (2017)","journal-title":"IEEE Sig. Process. Lett."},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-642-15567-3_28","volume-title":"Computer Vision \u2013 ECCV 2010","author":"J Yuan","year":"2010","unstructured":"Yuan, J., Bae, E., Tai, X.-C., Boykov, Y.: A continuous max-flow approach to potts model. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010. LNCS, vol. 6316, pp. 379\u2013392. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15567-3_28"},{"issue":"1","key":"15_CR17","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1109\/TPAMI.2013.105","volume":"36","author":"C Zach","year":"2014","unstructured":"Zach, C., H\u00e4ne, C., Pollefeys, M.: What is optimized in convex relaxations for multilabel problems: connecting discrete and continuously inspired MAP inference. IEEE Trans. Pattern Anal. Mach. Intell. 36(1), 157\u2013170 (2014)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"2","key":"15_CR18","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd, S.: Least squares quantization in PCM. IEEE Trans. Inform. Theory 28(2), 129\u2013136 (1982)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"1","key":"15_CR19","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/s11263-011-0499-y","volume":"98","author":"ES Brown","year":"2012","unstructured":"Brown, E.S., Chan, T.F., Bresson, X.: Completely convex formulation of the Chan-Vese image segmentation model. Int. J. Comput. Vis. 98(1), 103\u2013121 (2012)","journal-title":"Int. J. Comput. Vis."},{"key":"15_CR20","series-title":"Mathematics and Visualization","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/978-3-642-34141-0_19","volume-title":"Innovations for Shape Analysis: Models and Algorithms","author":"E Bae","year":"2013","unstructured":"Bae, E., Yuan, J., Tai, X.-C.: Simultaneous convex optimization of regions and region parameters in image segmentation models. In: Breu\u00df, M., Bruckstein, A., Maragos, P. (eds.) Innovations for Shape Analysis: Models and Algorithms. Mathematics and Visualization, pp. 421\u2013438. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-34141-0_19"},{"issue":"1","key":"15_CR21","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s10851-014-0507-2","volume":"51","author":"E Bae","year":"2015","unstructured":"Bae, E., Tai, X.-C.: Efficient global minimization methods for image segmentation models with four regions. J. Math. Imaging Vis. 51(1), 71\u201397 (2015)","journal-title":"J. Math. Imaging Vis."},{"issue":"4","key":"15_CR22","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1137\/090757617","volume":"3","author":"T Pock","year":"2010","unstructured":"Pock, T., Cremers, D., Bischof, H., Chambolle, A.: Global solutions of variational models with convex regularization. SIAM J. Imaging Sci. 3(4), 1122\u20131145 (2010)","journal-title":"SIAM J. Imaging Sci."},{"issue":"1","key":"15_CR23","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/s10107-015-0946-6","volume":"158","author":"L Condat","year":"2016","unstructured":"Condat, L.: Fast projection onto the simplex and the l1 ball. Math. Program. Ser. A 158(1), 575\u2013585 (2016)","journal-title":"Math. Program. Ser. A"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Quattoni, A., Carreras, X., Collins, M., Darrell, T.: An efficient projection for l1, $$\\infty $$ \u221e regularization. In: Proceedings of ICML, Montreal, Canada, June 2009, pp. 857\u2013864 (2009)","DOI":"10.1145\/1553374.1553484"},{"key":"15_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48311-5","volume-title":"Convex Analysis and Monotone Operator Theory in Hilbert Spaces","author":"HH Bauschke","year":"2011","unstructured":"Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011). https:\/\/doi.org\/10.1007\/978-3-319-48311-5"},{"key":"15_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-24785-9_24","volume-title":"Scale Space and Variational Methods in Computer Vision","author":"J Yuan","year":"2012","unstructured":"Yuan, J., Bae, E., Boykov, Y., Tai, X.-C.: A continuous max-flow approach to minimal partitions with label cost prior. In: Bruckstein, A.M., ter Haar Romeny, B.M., Bronstein, A.M., Bronstein, M.M. (eds.) SSVM 2011. LNCS, vol. 6667, pp. 279\u2013290. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-24785-9_24"},{"issue":"1","key":"15_CR27","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","volume":"40","author":"A Chambolle","year":"2011","unstructured":"Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120\u2013145 (2011)","journal-title":"J. Math. Imaging Vis."},{"issue":"2","key":"15_CR28","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/s10957-012-0245-9","volume":"158","author":"L Condat","year":"2013","unstructured":"Condat, L.: A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl. 158(2), 460\u2013479 (2013)","journal-title":"J. Optim. Theory Appl."},{"issue":"3","key":"15_CR29","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1002\/net.20128","volume":"48","author":"J Reese","year":"2006","unstructured":"Reese, J.: Solution methods for the p-median problem: an annotated bibliography. Networks 48(3), 125\u2013142 (2006)","journal-title":"Networks"},{"key":"15_CR30","unstructured":"Balinski, M.L.: On finding integer solutions to linear programs. In: Proceedings of the I.B.M. Scientific Computing Symposium on Combinatorial Problems, pp. 225\u2013248 (1966)"},{"key":"15_CR31","doi-asserted-by":"crossref","unstructured":"Li, S., Svensson, O.: Approximating k-median via pseudo-approximation. In: Proceedings of the forty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2013), Palo Alto, California, USA, June 2013, pp. 901\u2013910 (2013)","DOI":"10.1145\/2488608.2488723"},{"issue":"8","key":"15_CR32","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1080\/0094965031000136012","volume":"73","author":"M Laan Van der","year":"2003","unstructured":"Van der Laan, M., Pollard, K., Bryan, J.: A new partitioning around medoids algorithm. J. Stat. Comput. Simul. 73(8), 575\u2013584 (2003)","journal-title":"J. Stat. Comput. Simul."},{"key":"15_CR33","series-title":"Studies in Fuzziness and Soft Computing","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/11362197_4","volume-title":"Foundations and Advances in Data Mining","author":"J Peng","year":"2005","unstructured":"Peng, J., Xia, Y.: A new theoretical framework for K-means-type clustering. In: Chu, W., Young Lin, T. (eds.) Foundations and Advances in Data Mining. Studies in Fuzziness and Soft Computing, vol. 180, pp. 79\u201396. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11362197_4"},{"issue":"1","key":"15_CR34","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/050641983","volume":"18","author":"J Peng","year":"2007","unstructured":"Peng, J., Wei, Y.: Approximating K-means-type clustering via semidefinite programming. SIAM J. Optim. 18(1), 186\u2013205 (2007)","journal-title":"SIAM J. Optim."},{"key":"15_CR35","doi-asserted-by":"crossref","unstructured":"Awasthi, P., Bandeira, A.S., Charikar, M., Krishnaswamy, R., Villar, S., Ward, R.: Relax, no need to round: integrality of clustering formulations. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS), Rehovot, Israel, January 2015, pp. 191\u2013200 (2015)","DOI":"10.1145\/2688073.2688116"},{"key":"15_CR36","unstructured":"Pelckmans, K., De Brabanter, J., Suykens, J.A.K., De Moor, B.: Convex clustering shrinkage. In: Proceedings of Workshop on Statistics and Optimization of Clustering Workshop (PASCAL), London, UK, July 2005"},{"key":"15_CR37","unstructured":"Hocking, T., Vert, J.-P., Bach, F., Joulin, A.: Clusterpath: an algorithm for clustering using convex fusion penalties. In: Proceeding of the 28th International Conference on Machine Learning (ICML), Bellevue, USA, June 2011, pp. 745\u2013752 (2011)"},{"key":"15_CR38","doi-asserted-by":"crossref","unstructured":"Lindsten, F., Ohlsson, H., Ljung, L.: Clustering using sum-of-norms regularization: with application to particle filter output computation. In: Proceedings of Statistical Signal Processing Workshop (SSP), Nice, France, June 2011, pp. 201\u2013204 (2011)","DOI":"10.1109\/SSP.2011.5967659"},{"key":"15_CR39","unstructured":"Zhu, C., Xu, H., Leng, C., Yan, S.: Convex optimization procedure for clustering: theoretical revisit. In: Proceedings of NIPS, Montreal, Canada, December 2014, pp. 1619\u20131627 (2014)"},{"issue":"4","key":"15_CR40","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1080\/10618600.2014.948181","volume":"24","author":"EC Chi","year":"2015","unstructured":"Chi, E.C., Lange, K.: Splitting methods for convex clustering. J. Comput. Graph. Stat. 24(4), 994\u20131013 (2015)","journal-title":"J. Comput. Graph. Stat."},{"key":"15_CR41","unstructured":"K\u00e4rkk\u00e4inen, I., Fr\u00e4nti, P.: Dynamic local search algorithm for the clustering problem. Technical report A-2002-6, Department of Computer Science, University of Joensuu, Joensuu, Finland (2002)"},{"issue":"1","key":"15_CR42","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0604005","volume":"4","author":"ES Barnes","year":"1983","unstructured":"Barnes, E.S., Sloane, N.J.A.: The optimal lattice quantizer in three dimensions. SIAM J. Algebr. Discret. Methods 4(1), 30\u201341 (1983)","journal-title":"SIAM J. Algebr. Discret. Methods"}],"container-title":["Lecture Notes in Computer Science","Energy Minimization Methods in Computer Vision and Pattern Recognition"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-78199-0_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,13]],"date-time":"2019-10-13T01:53:57Z","timestamp":1570931637000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-78199-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319781983","9783319781990"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-78199-0_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]}}}