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

Metrics

  • PDF downloads (16)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]