Advanced Search
Article Contents
Article Contents

A regularized k-means and multiphase scale segmentation

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 65D18, 94A08, 62H35.


    \begin{equation} \\ \end{equation}
  • [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.


    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.


    T. Chan and L. Vese, Active contours without edges, IEEE Trans. Image Processing, 10 (2001), 266-277.doi: 10.1109/83.902291.


    J. Chung and L. Vese, Energy minimization based segmentation and denoising using a multilayer level set approach, EMMCVPR, 3457 (2005), 439-455.


    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.


    R. O. Duda, P. E. Hart and D. G. Stork, "Pattern Classification," Wiley-Interscience, New York, 2nd edition, 2001.


    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.


    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.


    E. W. Forgy, Cluster analysis of multivariate data: efficiency vs interpretability of classifications, Biometrics, 21 (1965), 768-769.


    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.


    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.


    J. A. Hartigan and M. A. Wong, A K-means clustering algorithm, Applied Statistics, 28 (1979), 100-108.doi: 10.2307/2346830.


    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.


    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.


    N. B. Karayiannis, Meca: Maximum entropy clustering algorithm, IEEE World Congress on Computational Intelligence, Fuzzy Systems, 1 (1994), 630-635.


    K. Krishna and M. Narasimha Murty, Genetic k-means algorithm, IEEE Trans. Systems, Man and Cybernetics--Part B: Cybernetics, 29 (1999), 433-439.


    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.


    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.


    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.


    S. P. Lloyd, Least squares quantization in PCM, IEEE Transaction Information Theory, 28 (1982), 129-137. Technical Note, Bell Laboratories (1957).


    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.


    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).


    G. Mchlachlan and D. Peel, "Finite Mixture Models," John Wiley and Sons, New York, 2000.doi: 10.1002/0471721182.


    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.


    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.


    K. Ni, X. Bresson, T. Chan and S. Esedoglu, Local histogram based segmentation using the wasserstein distance, International Journal of Computer Vision, 84 (2009).


    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.


    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.


    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.


    B. Sandberg and T. Chan, "Logic Operators for Active Contours On Multi-channel Images," UCLA CAM report 02-12, 2002.


    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.


    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.


    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.


    B. Song and T. Chan, "A Fast Algorithm for Level Set Based Optimization," UCLA CAM Report 02-68, 2002.


    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.


    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.


    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.


    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.


    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.


    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.


    J. Ward, Hierarchical grouping to optimize an objective function, J. Amer. Statist. Assoc., 58 (1963), 236-244.doi: 10.2307/2282967.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(315) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint