# American Institute of Mathematical Sciences

May  2011, 5(2): 407-429. doi: 10.3934/ipi.2011.5.407

## A regularized k-means and multiphase scale segmentation

 1 School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, United States 2 Physical Optics Corporation, Torrance, CA 90501-1821, United States 3 Department of Mathematics, National University of Singapore, 10, Lower Kent Ridge Road, 119076, Singapore

Received  September 2010 Revised  March 2011 Published  May 2011

We propose a data clustering model reduced from variational approach. This new clustering model, a regularized k-means, is an extension from the classical k-means model. It uses the sum-of-squares error for assessing fidelity, and the number of data in each cluster is used as a regularizer. The model automatically gives a reasonable number of clusters by a choice of a parameter. We explore various properties of this classification model and present different numerical results. This model is motivated by an application to scale segmentation. A typical Mumford-Shah-based image segmentation is driven by the intensity of objects in a given image, and we consider image segmentation using additional scale information in this paper. Using the scale of objects, one can further classify objects in a given image from using only the intensity value. The scale of an object is not a local value, therefore the procedure for scale segmentation needs to be separated into two steps: multiphase segmentation and scale clustering. The first step requires a reliable multiphase segmentation where we applied unsupervised model, and apply a regularized k-means for a fast automatic data clustering for the second step. Various numerical results are presented to validate the model.
Citation: Sung Ha Kang, Berta Sandberg, Andy M. Yip. A regularized k-means and multiphase scale segmentation. Inverse Problems & Imaging, 2011, 5 (2) : 407-429. doi: 10.3934/ipi.2011.5.407
##### References:
 [1] V. Caselles, A. Chambolle and M. Navaga, Uniqueness of the Cheeger set of a convex body,, Pacific Journal of Mathematics, 232 (2007), 77. doi: 10.2140/pjm.2007.232.77. Google Scholar [2] T. Chan, B. Sandberg and L. Vese, Active contours without edges for vector-valued images,, Journal of Visual Communication and Image Representation, 11 (2000), 130. doi: 10.1006/jvci.1999.0442. Google Scholar [3] T. Chan and L. Vese, Active contours without edges,, IEEE Trans. Image Processing, 10 (2001), 266. doi: 10.1109/83.902291. Google Scholar [4] J. Chung and L. Vese, Energy minimization based segmentation and denoising using a multilayer level set approach,, EMMCVPR, 3457 (2005), 439. Google Scholar [5] J. Delon, A. Desolneux, J-L. Lisani and A-B. Petro, A non parametric approach for histogram segmentation,, IEEE Transactions on Image Processing, 16 (2007), 253. doi: 10.1109/TIP.2006.884951. Google Scholar [6] R. O. Duda, P. E. Hart and D. G. Stork, "Pattern Classification,", Wiley-Interscience, (2001). Google Scholar [7] A. Figalli, F. Maggi and A. Pratelli, A note on Cheeger sets,, Proc. Amer. Math. Soc., 137 (2009), 2057. doi: 10.1090/S0002-9939-09-09795-0. Google Scholar [8] M. A. T. Figueiredo and A. K. Jian, Unsupervised learning of finite mixture models,, IEEE Trans. Pattern Anal. Machine Intell., 24 (2002), 381. doi: 10.1109/34.990138. Google Scholar [9] E. W. Forgy, Cluster analysis of multivariate data: efficiency vs interpretability of classifications,, Biometrics, 21 (1965), 768. Google Scholar [10] S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,, IEEE Trans. Pattern Anal. Machine Intell., 6 (1984), 721. doi: 10.1109/TPAMI.1984.4767596. Google Scholar [11] F. Gibou and R. Fedkiw, Fast hybrid k-means level set algorithm for segmentation,, Proc. of the 4th Annual Hawaii Int. Conf. on Stat. and Math.,, (2002). Google Scholar [12] J. A. Hartigan and M. A. Wong, A K-means clustering algorithm,, Applied Statistics, 28 (1979), 100. doi: 10.2307/2346830. Google Scholar [13] R. He, W. Xu, J. Sun and B. Zu, Balanced k-means algorithm for partitioning areas in large-scale vehicle routing problem,, In, 3 (2009), 87. doi: 10.1109/IITA.2009.307. Google Scholar [14] Y. M. Jung, S. H. Kang and J. Shen, Multiphase image segmentation via Modica-Mortola phase transition,, SIAM Applied Mathematics, 67 (2007), 1213. doi: 10.1137/060662708. Google Scholar [15] N. B. Karayiannis, Meca: Maximum entropy clustering algorithm,, IEEE World Congress on Computational Intelligence, 1 (1994), 630. Google Scholar [16] K. Krishna and M. Narasimha Murty, Genetic k-means algorithm,, IEEE Trans. Systems, 29 (1999), 433. Google Scholar [17] Y. N. Law, H. K. Lee and A. M. Yip, Semi-supervised subspace learning for mumford-shah model based texture segmentation,, Optics Express, 18 (2010), 4434. doi: 10.1364/OE.18.004434. Google Scholar [18] M. J. Li, M. K. Ng, Y. Cheung and J. Z. Huang, Agglomerative fuzzy $k$-means clustering algorithm with selection of number of clusters,, IEEE Transactions on Knowledge and Data Engineering, 20 (2008), 1519. doi: 10.1109/TKDE.2008.88. Google Scholar [19] J. Lie, M. Lysaker and X.-C. Tai, A variant of the level set method and applications to image segmentation,, AMS Mathematics of Computation, 75 (2006), 1155. doi: 10.1090/S0025-5718-06-01835-7. Google Scholar [20] S. P. Lloyd, Least squares quantization in PCM,, IEEE Transaction Information Theory, 28 (1982), 129. Google Scholar [21] B. Luo, J.-F. Aujol and Y. Gousseau, Local scale measure from the topographic map and application to remote sensing images,, SIAM Journal on Multiscale Modeling and Simulation, 8 (2009), 1. doi: 10.1137/080730627. Google Scholar [22] J. B. MacQueen, Some methods for classification and analysis of multivariate observations,, In, (1967), 281. Google Scholar [23] G. Mchlachlan and D. Peel, "Finite Mixture Models,", John Wiley and Sons, (2000). doi: 10.1002/0471721182. Google Scholar [24] S. Miyamoto and M. Mukaidono, Fuzzy $c$-means as a regularization and maximum entropy approach,, In, (1997), 86. Google Scholar [25] D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems,, Comm. Pure Appl. Math., 42 (1989), 577. doi: 10.1002/cpa.3160420503. Google Scholar [26] K. Ni, X. Bresson, T. Chan and S. Esedoglu, Local histogram based segmentation using the wasserstein distance,, International Journal of Computer Vision, 84 (2009). Google Scholar [27] G. Palubinskas, X. Descombes and F. Kruggel, An unsupervised clustering method using the entropy minimization,, Proceedings. Fourteenth International Conference on Pattern Recognition, 2 (1998), 1816. doi: 10.1109/ICPR.1998.712082. Google Scholar [28] J. Peng and Y. Xia, A cutting algorithm for the minimum sum-of-squared error clustering,, In, (2005), 150. Google Scholar [29] K. Rose, E. Gurewitz and C. G. Fox, A deterministic annealing approach to clustering,, Pattern Recognition Letters, 11 (1990), 589. doi: 10.1016/0167-8655(90)90010-Y. Google Scholar [30] B. Sandberg and T. Chan, "Logic Operators for Active Contours On Multi-channel Images,", UCLA CAM report 02-12, (2002), 02. Google Scholar [31] B. Sandberg, T. Chan and L. Vese, "A Level-Set and Gabor-Based Active Contour Algorithm for Segmenting Textured Images,", UCLA CAM report 02-39, (2002), 02. Google Scholar [32] B. Sandberg, S. H. Kang and T. Chan, Unsupervised multiphase segmentation: A phase balancing model,, IEEE Transaction in Image Processing, 19 (2010), 119. doi: 10.1109/TIP.2009.2032310. Google Scholar [33] J. Shi and J. Malik, Normalized cuts and image segmentation,, IEEE Trans. Pattern Anal. Machine Intell., 22 (2000), 888. doi: 10.1109/34.868688. Google Scholar [34] B. Song and T. Chan, "A Fast Algorithm for Level Set Based Optimization,", UCLA CAM Report 02-68, (2002), 02. Google Scholar [35] D. Strong, J.-F. Aujol and T. Chan, Scale recognition, regularization parameter selection, and Meyer's G norm in total variation regularization,, SIAM Journal on Multiscale Modeling and Simulation, 5 (2006), 273. doi: 10.1137/040621624. Google Scholar [36] X.-C. Tai and T. Chan, A survey on multiple level set methods with applications for identifying piecewise constant functions,, International J. Numer. Anal. Modelling, 1 (2004), 25. Google Scholar [37] L. Tan, Y. Gong and G. Chen, A balanced parallel clustering protocol for wireless sensor networks using k-means techniques,, In, (2008), 300. doi: 10.1109/SENSORCOMM.2008.45. Google Scholar [38] G. C. Tseng, Penalized and weighted k-means for clustering with scattered objects and prior information in high-througput biological data,, Bioinformatics, 23 (2007), 2247. doi: 10.1093/bioinformatics/btm320. Google Scholar [39] Z. W. Tu and S. C. Zhu, Image segmentation by Data-Driven Markov Chain Monte Carlo,, IEEE Trans. Pattern Anal. Machine Intell., 24 (2002), 657. doi: 10.1109/34.1000239. Google Scholar [40] L. Vese and T. Chan, A multiphase level set framework for image segmentation using the Mumford and Shah model,, International Journal of Computer Vision, 50 (2002), 271. doi: 10.1023/A:1020874308076. Google Scholar [41] J. Ward, Hierarchical grouping to optimize an objective function,, J. Amer. Statist. Assoc., 58 (1963), 236. doi: 10.2307/2282967. Google Scholar [42] S. Yan, H. Zhang, Y. Hu and B. Zhang, Discriminant analysis on embedded manifold,, In, (2004), 121. Google Scholar

show all references

##### References:
 [1] V. Caselles, A. Chambolle and M. Navaga, Uniqueness of the Cheeger set of a convex body,, Pacific Journal of Mathematics, 232 (2007), 77. doi: 10.2140/pjm.2007.232.77. Google Scholar [2] T. Chan, B. Sandberg and L. Vese, Active contours without edges for vector-valued images,, Journal of Visual Communication and Image Representation, 11 (2000), 130. doi: 10.1006/jvci.1999.0442. Google Scholar [3] T. Chan and L. Vese, Active contours without edges,, IEEE Trans. Image Processing, 10 (2001), 266. doi: 10.1109/83.902291. Google Scholar [4] J. Chung and L. Vese, Energy minimization based segmentation and denoising using a multilayer level set approach,, EMMCVPR, 3457 (2005), 439. Google Scholar [5] J. Delon, A. Desolneux, J-L. Lisani and A-B. Petro, A non parametric approach for histogram segmentation,, IEEE Transactions on Image Processing, 16 (2007), 253. doi: 10.1109/TIP.2006.884951. Google Scholar [6] R. O. Duda, P. E. Hart and D. G. Stork, "Pattern Classification,", Wiley-Interscience, (2001). Google Scholar [7] A. Figalli, F. Maggi and A. Pratelli, A note on Cheeger sets,, Proc. Amer. Math. Soc., 137 (2009), 2057. doi: 10.1090/S0002-9939-09-09795-0. Google Scholar [8] M. A. T. Figueiredo and A. K. Jian, Unsupervised learning of finite mixture models,, IEEE Trans. Pattern Anal. Machine Intell., 24 (2002), 381. doi: 10.1109/34.990138. Google Scholar [9] E. W. Forgy, Cluster analysis of multivariate data: efficiency vs interpretability of classifications,, Biometrics, 21 (1965), 768. Google Scholar [10] S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,, IEEE Trans. Pattern Anal. Machine Intell., 6 (1984), 721. doi: 10.1109/TPAMI.1984.4767596. Google Scholar [11] F. Gibou and R. Fedkiw, Fast hybrid k-means level set algorithm for segmentation,, Proc. of the 4th Annual Hawaii Int. Conf. on Stat. and Math.,, (2002). Google Scholar [12] J. A. Hartigan and M. A. Wong, A K-means clustering algorithm,, Applied Statistics, 28 (1979), 100. doi: 10.2307/2346830. Google Scholar [13] R. He, W. Xu, J. Sun and B. Zu, Balanced k-means algorithm for partitioning areas in large-scale vehicle routing problem,, In, 3 (2009), 87. doi: 10.1109/IITA.2009.307. Google Scholar [14] Y. M. Jung, S. H. Kang and J. Shen, Multiphase image segmentation via Modica-Mortola phase transition,, SIAM Applied Mathematics, 67 (2007), 1213. doi: 10.1137/060662708. Google Scholar [15] N. B. Karayiannis, Meca: Maximum entropy clustering algorithm,, IEEE World Congress on Computational Intelligence, 1 (1994), 630. Google Scholar [16] K. Krishna and M. Narasimha Murty, Genetic k-means algorithm,, IEEE Trans. Systems, 29 (1999), 433. Google Scholar [17] Y. N. Law, H. K. Lee and A. M. Yip, Semi-supervised subspace learning for mumford-shah model based texture segmentation,, Optics Express, 18 (2010), 4434. doi: 10.1364/OE.18.004434. Google Scholar [18] M. J. Li, M. K. Ng, Y. Cheung and J. Z. Huang, Agglomerative fuzzy $k$-means clustering algorithm with selection of number of clusters,, IEEE Transactions on Knowledge and Data Engineering, 20 (2008), 1519. doi: 10.1109/TKDE.2008.88. Google Scholar [19] J. Lie, M. Lysaker and X.-C. Tai, A variant of the level set method and applications to image segmentation,, AMS Mathematics of Computation, 75 (2006), 1155. doi: 10.1090/S0025-5718-06-01835-7. Google Scholar [20] S. P. Lloyd, Least squares quantization in PCM,, IEEE Transaction Information Theory, 28 (1982), 129. Google Scholar [21] B. Luo, J.-F. Aujol and Y. Gousseau, Local scale measure from the topographic map and application to remote sensing images,, SIAM Journal on Multiscale Modeling and Simulation, 8 (2009), 1. doi: 10.1137/080730627. Google Scholar [22] J. B. MacQueen, Some methods for classification and analysis of multivariate observations,, In, (1967), 281. Google Scholar [23] G. Mchlachlan and D. Peel, "Finite Mixture Models,", John Wiley and Sons, (2000). doi: 10.1002/0471721182. Google Scholar [24] S. Miyamoto and M. Mukaidono, Fuzzy $c$-means as a regularization and maximum entropy approach,, In, (1997), 86. Google Scholar [25] D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems,, Comm. Pure Appl. Math., 42 (1989), 577. doi: 10.1002/cpa.3160420503. Google Scholar [26] K. Ni, X. Bresson, T. Chan and S. Esedoglu, Local histogram based segmentation using the wasserstein distance,, International Journal of Computer Vision, 84 (2009). Google Scholar [27] G. Palubinskas, X. Descombes and F. Kruggel, An unsupervised clustering method using the entropy minimization,, Proceedings. Fourteenth International Conference on Pattern Recognition, 2 (1998), 1816. doi: 10.1109/ICPR.1998.712082. Google Scholar [28] J. Peng and Y. Xia, A cutting algorithm for the minimum sum-of-squared error clustering,, In, (2005), 150. Google Scholar [29] K. Rose, E. Gurewitz and C. G. Fox, A deterministic annealing approach to clustering,, Pattern Recognition Letters, 11 (1990), 589. doi: 10.1016/0167-8655(90)90010-Y. Google Scholar [30] B. Sandberg and T. Chan, "Logic Operators for Active Contours On Multi-channel Images,", UCLA CAM report 02-12, (2002), 02. Google Scholar [31] B. Sandberg, T. Chan and L. Vese, "A Level-Set and Gabor-Based Active Contour Algorithm for Segmenting Textured Images,", UCLA CAM report 02-39, (2002), 02. Google Scholar [32] B. Sandberg, S. H. Kang and T. Chan, Unsupervised multiphase segmentation: A phase balancing model,, IEEE Transaction in Image Processing, 19 (2010), 119. doi: 10.1109/TIP.2009.2032310. Google Scholar [33] J. Shi and J. Malik, Normalized cuts and image segmentation,, IEEE Trans. Pattern Anal. Machine Intell., 22 (2000), 888. doi: 10.1109/34.868688. Google Scholar [34] B. Song and T. Chan, "A Fast Algorithm for Level Set Based Optimization,", UCLA CAM Report 02-68, (2002), 02. Google Scholar [35] D. Strong, J.-F. Aujol and T. Chan, Scale recognition, regularization parameter selection, and Meyer's G norm in total variation regularization,, SIAM Journal on Multiscale Modeling and Simulation, 5 (2006), 273. doi: 10.1137/040621624. Google Scholar [36] X.-C. Tai and T. Chan, A survey on multiple level set methods with applications for identifying piecewise constant functions,, International J. Numer. Anal. Modelling, 1 (2004), 25. Google Scholar [37] L. Tan, Y. Gong and G. Chen, A balanced parallel clustering protocol for wireless sensor networks using k-means techniques,, In, (2008), 300. doi: 10.1109/SENSORCOMM.2008.45. Google Scholar [38] G. C. Tseng, Penalized and weighted k-means for clustering with scattered objects and prior information in high-througput biological data,, Bioinformatics, 23 (2007), 2247. doi: 10.1093/bioinformatics/btm320. Google Scholar [39] Z. W. Tu and S. C. Zhu, Image segmentation by Data-Driven Markov Chain Monte Carlo,, IEEE Trans. Pattern Anal. Machine Intell., 24 (2002), 657. doi: 10.1109/34.1000239. Google Scholar [40] L. Vese and T. Chan, A multiphase level set framework for image segmentation using the Mumford and Shah model,, International Journal of Computer Vision, 50 (2002), 271. doi: 10.1023/A:1020874308076. Google Scholar [41] J. Ward, Hierarchical grouping to optimize an objective function,, J. Amer. Statist. Assoc., 58 (1963), 236. doi: 10.2307/2282967. Google Scholar [42] S. Yan, H. Zhang, Y. Hu and B. Zhang, Discriminant analysis on embedded manifold,, In, (2004), 121. Google Scholar
 [1] Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022 [2] Matthew S. Keegan, Berta Sandberg, Tony F. Chan. A multiphase logic framework for multichannel image segmentation. Inverse Problems & Imaging, 2012, 6 (1) : 95-110. doi: 10.3934/ipi.2012.6.95 [3] Jianping Zhang, Ke Chen, Bo Yu, Derek A. Gould. A local information based variational model for selective image segmentation. Inverse Problems & Imaging, 2014, 8 (1) : 293-320. doi: 10.3934/ipi.2014.8.293 [4] Micol Amar, Andrea Braides. A characterization of variational convergence for segmentation problems. Discrete & Continuous Dynamical Systems - A, 1995, 1 (3) : 347-369. doi: 10.3934/dcds.1995.1.347 [5] Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial & Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565 [6] Sebastián Ferrer, Francisco Crespo. Parametric quartic Hamiltonian model. A unified treatment of classic integrable systems. Journal of Geometric Mechanics, 2014, 6 (4) : 479-502. doi: 10.3934/jgm.2014.6.479 [7] Ghendrih Philippe, Hauray Maxime, Anne Nouri. Derivation of a gyrokinetic model. Existence and uniqueness of specific stationary solution. Kinetic & Related Models, 2009, 2 (4) : 707-725. doi: 10.3934/krm.2009.2.707 [8] Faker Ben Belgacem. Uniqueness for an ill-posed reaction-dispersion model. Application to organic pollution in stream-waters. Inverse Problems & Imaging, 2012, 6 (2) : 163-181. doi: 10.3934/ipi.2012.6.163 [9] Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems & Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030 [10] Eugene Kashdan, Svetlana Bunimovich-Mendrazitsky. Multi-scale model of bladder cancer development. Conference Publications, 2011, 2011 (Special) : 803-812. doi: 10.3934/proc.2011.2011.803 [11] Erik Kropat, Silja Meyer-Nieberg, Gerhard-Wilhelm Weber. Bridging the gap between variational homogenization results and two-scale asymptotic averaging techniques on periodic network structures. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 223-250. doi: 10.3934/naco.2017016 [12] Guillaume Duval, Andrzej J. Maciejewski. Integrability of potentials of degree $k \neq \pm 2$. Second order variational equations between Kolchin solvability and Abelianity. Discrete & Continuous Dynamical Systems - A, 2015, 35 (5) : 1969-2009. doi: 10.3934/dcds.2015.35.1969 [13] Weigao Ge, Li Zhang. Multiple periodic solutions of delay differential systems with $2k-1$ lags via variational approach. Discrete & Continuous Dynamical Systems - A, 2016, 36 (9) : 4925-4943. doi: 10.3934/dcds.2016013 [14] Christopher DuBois, Jesse Farnham, Eric Aaron, Ami Radunskaya. A multiple time-scale computational model of a tumor and its micro environment. Mathematical Biosciences & Engineering, 2013, 10 (1) : 121-150. doi: 10.3934/mbe.2013.10.121 [15] Egil Bae, Xue-Cheng Tai, Wei Zhu. Augmented Lagrangian method for an Euler's elastica based segmentation model that promotes convex contours. Inverse Problems & Imaging, 2017, 11 (1) : 1-23. doi: 10.3934/ipi.2017001 [16] Riccardo March, Giuseppe Riey. Analysis of a variational model for motion compensated inpainting. Inverse Problems & Imaging, 2017, 11 (6) : 997-1025. doi: 10.3934/ipi.2017046 [17] G. Idone, A. Maugeri. Variational inequalities and a transport planning for an elastic and continuum model. Journal of Industrial & Management Optimization, 2005, 1 (1) : 81-86. doi: 10.3934/jimo.2005.1.81 [18] Wei Wang, Na Sun, Michael K. Ng. A variational gamma correction model for image contrast enhancement. Inverse Problems & Imaging, 2019, 13 (3) : 461-478. doi: 10.3934/ipi.2019023 [19] Grigor Nika, Bogdan Vernescu. Rate of convergence for a multi-scale model of dilute emulsions with non-uniform surface tension. Discrete & Continuous Dynamical Systems - S, 2016, 9 (5) : 1553-1564. doi: 10.3934/dcdss.2016062 [20] Emiliano Cristiani, Elisa Iacomini. An interface-free multi-scale multi-order model for traffic flow. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 6189-6207. doi: 10.3934/dcdsb.2019135

2018 Impact Factor: 1.469