A regularized k-means and multiphase scale segmentation

Sung Ha Kang; Berta Sandberg; Andy M. Yip

doi:10.3934/ipi.2011.5.407

Article Contents

2011, Volume 5, Issue 2: 407-429. Doi: 10.3934/ipi.2011.5.407

This issue Previous Article A refinement and coarsening indicator algorithm for finding sparse solutions of inverse problems Next Article Recovering two Lamé kernels in a viscoelastic system

A regularized k-means and multiphase scale segmentation

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

Received: August 31, 2010

Revised: February 28, 2011

Published: April 2011

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 65D18, 94A08, 62H35.

Citation:

Related Papers

Cited by

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-90.doi: 10.2140/pjm.2007.232.77.
[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-141.doi: 10.1006/jvci.1999.0442.
[3]	T. Chan and L. Vese, Active contours without edges, IEEE Trans. Image Processing, 10 (2001), 266-277.doi: 10.1109/83.902291.
[4]	J. Chung and L. Vese, Energy minimization based segmentation and denoising using a multilayer level set approach, EMMCVPR, 3457 (2005), 439-455.
[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-261.doi: 10.1109/TIP.2006.884951.
[6]	R. O. Duda, P. E. Hart and D. G. Stork, "Pattern Classification," Wiley-Interscience, New York, 2nd edition, 2001.
[7]	A. Figalli, F. Maggi and A. Pratelli, A note on Cheeger sets, Proc. Amer. Math. Soc., 137 (2009), 2057-2062.doi: 10.1090/S0002-9939-09-09795-0.
[8]	M. A. T. Figueiredo and A. K. Jian, Unsupervised learning of finite mixture models, IEEE Trans. Pattern Anal. Machine Intell., 24 (2002), 381-396.doi: 10.1109/34.990138.
[9]	E. W. Forgy, Cluster analysis of multivariate data: efficiency vs interpretability of classifications, Biometrics, 21 (1965), 768-769.
[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-741.doi: 10.1109/TPAMI.1984.4767596.
[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.
[12]	J. A. Hartigan and M. A. Wong, A K-means clustering algorithm, Applied Statistics, 28 (1979), 100-108.doi: 10.2307/2346830.
[13]	R. He, W. Xu, J. Sun and B. Zu, Balanced k-means algorithm for partitioning areas in large-scale vehicle routing problem, In "Proc. 3rd Int. Symp. Intelligent Information Technology Application," volume 3, pages 87-90, Nanchang, China, (2009).doi: 10.1109/IITA.2009.307.
[14]	Y. M. Jung, S. H. Kang and J. Shen, Multiphase image segmentation via Modica-Mortola phase transition, SIAM Applied Mathematics, 67 (2007), 1213-1232.doi: 10.1137/060662708.
[15]	N. B. Karayiannis, Meca: Maximum entropy clustering algorithm, IEEE World Congress on Computational Intelligence, Fuzzy Systems, 1 (1994), 630-635.
[16]	K. Krishna and M. Narasimha Murty, Genetic k-means algorithm, IEEE Trans. Systems, Man and Cybernetics--Part B: Cybernetics, 29 (1999), 433-439.
[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-4448.doi: 10.1364/OE.18.004434.
[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-1534.doi: 10.1109/TKDE.2008.88.
[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-1174.doi: 10.1090/S0025-5718-06-01835-7.
[20]	S. P. Lloyd, Least squares quantization in PCM, IEEE Transaction Information Theory, 28 (1982), 129-137. Technical Note, Bell Laboratories (1957).
[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-29.doi: 10.1137/080730627.
[22]	J. B. MacQueen, Some methods for classification and analysis of multivariate observations, In "Proc. of 5th Berkeley Symposium on Mathematical Statistics and Probability, Volume I: Statistics," pages 281-297, (1967).
[23]	G. Mchlachlan and D. Peel, "Finite Mixture Models," John Wiley and Sons, New York, 2000.doi: 10.1002/0471721182.
[24]	S. Miyamoto and M. Mukaidono, Fuzzy $c$-means as a regularization and maximum entropy approach, In "Proc. Seventh Int'l Fuzzy Sysmtes Assoc. World Congress" (IFSA '97), 2 (1997), 86-92.
[25]	D. Mumford and J. Shah, Optimal approximation by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), 577-685.doi: 10.1002/cpa.3160420503.
[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).
[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-1818.doi: 10.1109/ICPR.1998.712082.
[28]	J. Peng and Y. Xia, A cutting algorithm for the minimum sum-of-squared error clustering, In "Hillol Kargupta, Jaideep Srivastava, Chandrika Kamath and Arnold Goodman, editors, Proc. of the 5th SIAM Int. Conf. on Data Mining," pages 150-160, Newport Beach, CA, 2005.
[29]	K. Rose, E. Gurewitz and C. G. Fox, A deterministic annealing approach to clustering, Pattern Recognition Letters, 11 (1990), 589-594.doi: 10.1016/0167-8655(90)90010-Y.
[30]	B. Sandberg and T. Chan, "Logic Operators for Active Contours On Multi-channel Images," UCLA CAM report 02-12, 2002.
[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.
[32]	B. Sandberg, S. H. Kang and T. Chan, Unsupervised multiphase segmentation: A phase balancing model, IEEE Transaction in Image Processing, 19 (2010), 119-130.doi: 10.1109/TIP.2009.2032310.
[33]	J. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Machine Intell., 22 (2000), 888-905.doi: 10.1109/34.868688.
[34]	B. Song and T. Chan, "A Fast Algorithm for Level Set Based Optimization," UCLA CAM Report 02-68, 2002.
[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-303.doi: 10.1137/040621624.
[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-48.
[37]	L. Tan, Y. Gong and G. Chen, A balanced parallel clustering protocol for wireless sensor networks using k-means techniques, In "Proc. 2nd Int. Conf. Sensor Technologies and Applications," pages 300-305, 2008.doi: 10.1109/SENSORCOMM.2008.45.
[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-2255.doi: 10.1093/bioinformatics/btm320.
[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-673.doi: 10.1109/34.1000239.
[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-293.doi: 10.1023/A:1020874308076.
[41]	J. Ward, Hierarchical grouping to optimize an objective function, J. Amer. Statist. Assoc., 58 (1963), 236-244.doi: 10.2307/2282967.
[42]	S. Yan, H. Zhang, Y. Hu and B. Zhang, Discriminant analysis on embedded manifold, In "Tomáš Pajdla and Jiři Matas, editors, Proc. 8th ECCV," pages 121-132, 2004.