Color image segmentation using mean shift and improved ant clustering

Abstract

To improve the segmentation quality and efficiency of color image, a novel approach which combines the advantages of the mean shift (MS) segmentation and improved ant clustering method is proposed. The regions which can preserve the discontinuity characteristics of an image are segmented by MS algorithm, and then they are represented by a graph in which every region is represented by a node. In order to solve the graph partition problem, an improved ant clustering algorithm, called similarity carrying ant model (SCAM-ant), is proposed, in which a new similarity calculation method is given. Using SCAM-ant, the maximum number of items that each ant can carry will increase, the clustering time will be effectively reduced, and globally optimized clustering can also be realized. Because the graph is not based on the pixels of original image but on the segmentation result of MS algorithm, the computational complexity is greatly reduced. Experiments show that the proposed method can realize color image segmentation efficiently, and compared with the conventional methods based on the image pixels, it improves the image segmentation quality and the anti-interference ability.

Keywords

color image segmentation / improved ant clustering / graph partition / mean shift

References

[1] VijayaG., Dr VasudevanV.. A simple algorithm for image denoising based on ms segmentation [J]. International Journal of Computer Applications, 2010, 2(6): 9-10

[2] LeeJ.-d., SuH.-r., ChengP. E., LiouM., AstonJ. A. D., TsaiA. C., ChenC.-yu.. MR image segmentation using a power transformation approach [J]. IEEE Transactions on Medical Imaging, 2009, 28(6): 894-905

[3] FarmerM. E., JainA. K.. A wrapper-based approach to image segmentation and classification [J]. IEEE Transactions on Image Processing, 2005, 14(12): 2060-2072

[4] MakrogiannisS., EconomouG., FotopoulosS.. A region dissimilarity relation that combines feature-space and spatial information for color image segmentation [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part b: Cybernetics, 2005, 35(1): 44-53

[5] JacobsD. W., WeinshallD., GdalyahuY.. Classification with nonmetric distances: Image retrieval and class representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(6): 583-585

[6] AwadM., ChehdiK., NasriA.. Multicomponent image segmentation using a genetic algorithm and artificial neural network [J]. IEEE Geoscience and Remote Sensing Letters, 2007, 4(4): 571-575

[7] LE T H, JUNG S W, CHOI K S, KO S J. Image segmentation based on modified graph-cut algorithm [N]. Electronics Letters, 2010-8-5, 46(16).

[8] GradyL., SchwartzE. L.. Isoperimetric graph partitioning for image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(3): 469-475

[9] ShiJ.-b., MalikJ.. normalized cuts and image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905

[10] LiX.-r., WuF.-c., HuZ.-yi.. Convergence of a Mean Shift algorithm [J]. Journal of Software, 2005, 6(3): 365-374. ^(in Chinese

[11] TaoW.-b., JinH., ZhangY.-min.. Color image segmentation based on Mean Shift and normalized cuts [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part b: Cybernetics, 2007, 37(5): 1382-1389

[12] LengM., YuS.-n., DingW., GuoQiang.. An effective multi-level algorithm based on ant colony optimization for graph bipartitioning [J]. Shanghai Univ (Engl Ed), 2008, 12(5): 426-432

[13] SunL., WangX.-c., LiuJiang.. Method of document image segmentation based on ncut [J]. Information Technology and Informatization, 2008, 6: 93-95

[14] IsaA. M., SalamahS. A., NgahU. K.. Adaptive fuzzy moving k-means clustering algorithm for image segmentation [J]. IEEE Transactions on Consumer Electronics, 2009, 55(4): 2145-2153

[15] YanC.-x., SangN., ZhangT.-xu.. Image segmentation by graph partition on histogram clustering [J]. Computer App locations, 2005, 25(3): 570-572

[16] HandJ., MeyerB.. Ant-based and swarm-based clustering [J]. Swarm Intelligence, 2007, 1(1): 95-113

[17] DENEUBOURG J L, GOSS S, FRANKS N, SENDOVA-FRANKS A, DETRAIN C, CHRÉTIEN L. The dynamics of collective sorting robot-like ants and ant-like robots [C]// Proceedings of the First International Conference on Simulation of Adaptive Behavior on from Animals to Animats. Cambridge, MA, USA, 1990: 356–363.

[18] KUNTZ P, LAYZELL P, SNYERS D. A colony of ant-like agents for partitioning in VLSI technology [C]// HUSBANDS P, HARVEY I, ed. Proceedings of Fourth European Conference on Artificial Life. Brighton, UK, 1997: 417–424.

[19] Glen Jeh, Jennifer Widom. SimRank: A measure of structural-context similarity [C]// Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Alberta, Canada, 2002: 538–543.

[20] SAMI SOLIMAN M, TAN Guan-zheng. Graph partitioning using improved ant clustering [C]//TAN Y, SHI Y, TAN K C, Eds. The International Conference on Swarm Intelligence 2010: Part I. Lecture Notes in Computer Science(LNCS)6145, The International Conference on Swarm Intelligence. Beijing, China, 2010: 231–240.

[21] COUR T, YU S, SHI J. Normalized cuts matlab code [EB/OL]. [2010-11-23]. http://www.cis.upenn.edu/~jshi/software.