Background dominant colors extraction method based on color image quick fuzzy c-means clustering algorithm

Zun-yang Liu,Feng Ding,Ying Xu,Xu Han

College of Electronic Engineering,National University of Defense Technology,No.460,Huangshan Road,Shushan District,Hefei,Anhui,230037,China

Keywords: Dominant colors extraction Quick clustering algorithm Clustering spatial mapping Background image Camouflage design

ABSTRACT A quick and accurate extraction of dominant colors of background images is the basis of adaptive camouflage design.This paper proposes a Color Image Quick Fuzzy C-Means (CIQFCM) clustering algorithm based on clustering spatial mapping.First,the clustering sample space was mapped from the image pixels to the quantized color space,and several methods were adopted to compress the amount of clustering samples.Then,an improved pedigree clustering algorithm was applied to obtain the initial class centers.Finally,CIQFCM clustering algorithm was used for quick extraction of dominant colors of background image.After theoretical analysis of the effect and efficiency of the CIQFCM algorithm,several experiments were carried out to discuss the selection of proper quantization intervals and to verify the effect and efficiency of the CIQFCM algorithm.The results indicated that the value of quantization intervals should be set to 4,and the proposed algorithm could improve the clustering efficiency while maintaining the clustering effect.In addition,as the image size increased from 128×128 to 1024×1024,the efficiency improvement of CIQFCM algorithm was increased from 6.44 times to 36.42 times,which demonstrated the significant advantage of CIQFCM algorithm in dominant colors extraction of large-size images.

1.Introduction

Dominant colors extraction technology has been widely used in the fields of camouflage design [1].camouflage assessment [2-4],image segmentation [5],image mixing [6],image retrieval [7,8],remote sensing image analysis [9],and medical image analysis[10,11].

At present,the existing dominant colors extraction methods of background image are mainly based on principal component analysis[10],linear block algorithm[7],K-means clustering[8],and Fuzzy C-Means (FCM) clustering algorithm [9].Where,FCM clustering algorithm proposed by Dunn [12] in 1973 has been widely used in image processing as a clustering algorithm in recent years owe to its high clustering accuracy and relatively wide applicability.Moreover,several improved methods based on FCM clustering algorithm have been developed [5,9,13-16].FCM clustering algorithm is a kind of iterative random hill climbing algorithm,of which two problems need to be addressed.One is that if the initial class centers are not correctly selected,the clustering effect will be worse or it will be impossible to converge to the optimal solution.The other is that too many clustering samples will lead to a significant increase in the amount of cluster calculation[17].

At present,when clustering,pixels in the image are generally taken as cluster samples.Therefore,as the image size increases,the number of the cluster samples inevitably increases sharply,resulting in a significant increase in computation overhead.Researchers have tried different methods to improve clustering efficiency.DING [18] proposed a quick FCM clustering (QFCM)algorithm,which is only applicable to grayscale images rather than to color images.PENG [19] proposed the use ofI1component(I1=(R+G+B)/3) of the RGB color space as the one-dimensional feature set of the color image to realize quick clustering of color images,but only using theI1component as the feature vector will cause abundant loss of color information,resulting in failure of obtaining dominant colors accurately.

The purpose of this study is to propose an algorithm that can extract dominant colors quickly and accurately.In view of this,a Color Image Quick Fuzzy C-Means (CIQFCM) clustering algorithm suitable for dominant colors extraction of color image is proposed.By mapping cluster samples to the color matrix quantized in CIE Lab space[20],the number of clustering samples is greatly reduced and the clustering efficiency is improved greatly while maintaining the clustering effect.At the same time,the improved pedigree clustering algorithm is used to obtain the initial class centers,which further ensures the clustering effect of CIQFCM and realizes the quick and accurate extraction of dominant colors of color image.

2.The FCM algorithm

The basic idea of FCM clustering algorithm [12] is to dividensamplesxi(i=1,2,…,n) into c fuzzy clusters,and find the clustering center of each cluster to minimize the objective function defined as

where,m>1is a constant that can control the degree of ambiguity of the clustering result,Jmis the objective function,is the distance from the samplexkto thei-th cluster center vi,μikis the membership function ofksample fori-th category,which requires that the sum of membership degree of a sample for each cluster is 1,as shown in Eq.(2).

To achieve the minimumJm,the membership degreeμikand cluster center viare updated according to Eqs.(3) and (4).When updating μik,there are two cases to be discussed based on whetherdikhas a value of 0.DefineIkandI kasusebto represent the number of iterations,sovalue is

The steps of the FCM clustering algorithm can be described in Table 1.

Table 1 Steps of the FCM clustering algorithm.

FCM clustering algorithm believes that each sample belongs to different categories with a certain degree of membership.Such fuzzy processing method retains more information about the interconnection between the samples,and is particularly suitable for dominant colors extraction due to the overlaps in the distribution of data samples.

However,in each iteration of the FCM clustering algorithm,it is required to calculate the membershipUof all pixels to each cluster center and the new cluster centersV,where the number of operations to calculateUandVis bothn×c.Therefore,the timecomplexity of the FCM clustering algorithm is O(n×c×b).Where,nis the sample data amount,cis the number of clusters,andbis the number of iterations.When using FCM clustering algorithm to extract dominant colors of a background image,the sample data amount is the number of pixels.Therefore,for a large-size image,the complexity of calculation will be very high.In addition,FCM clustering algorithm is sensitive to the initial centers,and the result can be easily trapped in local optimal solution rather than global optimal solution.

3.Principle of CIQFCM algorithm in dominant colors extraction

To solve the problem of big cluster sample size and initial class centers selection,the CIQFCM clustering algorithm is proposed.The basic idea is to map the cluster sample space from the pixels in an image to the quantized color space so as to reduce the amount of cluster samples significantly.In addition,the improved pedigree clustering algorithm is used to acquire proper initial class centers.

3.1.Cluster space mapping

3.1.1 Basic idea of mapping

The purpose of cluster space mapping is to map the cluster samples from the image pixels to the quantized color space so as to reduce the amount of cluster samples while retaining the original information as much as possible.The CIELAB measure is a correlate to perceived lightness ranging from 0.0 for black to 100.0 for a diffuse white,and theaandbdimensions correlate approximately with red-green (-120 to 120) and yellow-blue (-120 to 120),respectively[21].The number of colors that can be represented by the CIELAB color space is far beyond what human eyes can distinguish.So,a reasonable compression of the number of colors will not affect the extraction of dominant colors.There are several methods for quantization of colors[22].With the purpose of minimizing the coordinate distortion,the equal proportion quantization method was adopted,in which the three coordinatesL,a,andbwere compressed by a variable called the quantization interval.For example,if the quantization interval is set to 5,the three coordinatesL,aandbwill be divided intonL=100/5,na=240/5,andnb=240/5 levels,respectively.At this time,there areNc=nL×na×nb=46080 quantized colors.For each level,its intermediate color value is used to represent the color of that level.The sketch of clustering sample spatial mapping is shown in Fig.1.

LetPbe the sample set of pixels in an image,then ?pi∈P,pi=[Li,ai,bi].Li,ai,biare the color values of thei-th pixel.LetCbe the quantized color matrix,thenWhereLjare thej-th quantized color values.

Define the mapping relationshipMfrom setPto setCas:

Fig.1.Sketch of clustering sample spatial mapping.

where,Npis the number of pixels in the image;are the lower and upper limits of the quantized colorandare the lower and upper limits of the quantized colorare the lower and upper limits of the quantized colorrespectively.

StatisticalNPofPonCmeans the number of pixels corresponding to each quantized colorNP=｛NP1，NP2，…NPNc｝,then

where,Npis the number of elements in the setP,that is,the number of pixels in the image;Ncis the number of elements in the setC,that is,the number of quantized colors.

3.1.2.Method to compress the clustering samples

As discussed above,when the quantization interval is set to 5,the number of quantization colors is 46080,which is still a large number.As the quantization interval is further reduced,the number of samples will be larger.Therefore,a method to compress the clustering samples was proposed.The colors appearing in an image usually do not cover the entire color space.Therefore,when quantizing,it is preferred to only consider the colors that appear in the image in each coordinate quantization.A method with two steps was recommended.In the first step,the maximum and minimum values of theL,a,andbwere obtained to set the coordinate ranges of color quantization;in the second step,after completing theNPstatistics,the elements with a statistic of 0 are removed from the color space to further reduce the amount of sample data.Experiment results show that such method can significantly reduce the number of sample data.

3.2.CIQFCM clustering algorithm

The CIQFCM clustering algorithm takes the mapped color values as cluster samples,so that the number of samples can be greatly reduced.The basic principle is to rewrite the calculation formulas of objective functionJm,fuzzy membershipuikand cluster center viof the FCM algorithm in Section 2 from Eqs.(1),(3),and(4)to Eqs.(8),(9) and (10).In order to distinguish it from FCM,the CIQFCM algorithm adoptsto represent the objective function,fuzzy membership matrix,and cluster center matrix,respectively.

In the above three formulas,bis the number of iterations,mis the clustering control parameter,cis the number of clustering categories,is the fuzzy membership ofk-th sample toi-th category,is the color value of thei-th cluster center,is the objective function,is the distance fromk-th sample toi-th cluster center,which is also the color difference betweenckandcalculated by CIE 94 color difference formula,[23].NPkis the number of pixels corresponding tok-th color,is thek-th color of the quantized color matrix.

The specific steps of the CIQFCM clustering algorithm are shownin Table 2.

Table 2 CIQFCM clustering algorithm steps.

3.3.Determination method of initial class centers

To ensure the clustering effect and efficiency,pedigree clustering algorithm is used to initialize class centers.The idea of pedigree clustering on the mapped clustering space is basically consistent with traditional pedigree clustering [24].However,the difference between them is that when calculating the new class centers after merging the categories with the minimum distance,it needs to use statisticsNPto weight the colors,as shown in Eq.(11).

where,vkis the center of thek-th class after merging;Nkis the number of samples in thek-th class;cirepresents the color value of thei-th sample in the class;NPirepresents the number of image pixels corresponding to the color ofi-th sample.

4.Analysis on CIQFCM algorithm effect and efficiency

4.1.Algorithm effect analysis

It can be proved that CIQFCM and FCM have basically equivalent effect in classifying samples when the quantization intervals are set appropriately.For any sampleckin the mapped color sample space,the samplepz（Lz，az，bz）in the image pixel sample space corresponding to it meetsM（pz）=ck,that is

Therefore,the membership of quantized colors）and pixelspz（Lz，az，bz）relative to the same class center is basically equal.That is,whenthe relationship shown in Eq.(13)can be obtained by referring to Eqs.(3) and (9).

With reference to Eqs.(4) and (10),the relationship shown in Eq.(14) can be obtained,that

Therefore,when initializationthere arefor anyb.

4.2.Algorithm efficiency analysis

4.2.1.Sample amount

Let the image size bem×nand the actual number of quantized color space samples beNc,then the number of samples in FCM clustering ism×n,and the number of clustering samples in CIQFCM algorithm isNc.The mapping method determines thatNcis always less thanm×n,meaning that the number of samples in CIQFCM algorithm is always less than that in FCM.The advantage of this algorithm is that as the image size increases,m×nwill increase quickly,butNcwill not.

4.2.2.Time complexity

In each iteration of the FCM clustering algorithm,it is required to calculate partition matrixUand cluster center vectorV.The complexity of the calculationUis the product of the number of categories and the number of samples,that is,the number of operations ism×n×ctimes.When calculatingV,each clustering center should be calculated bym×ntimes,and there are a total ofccenters,so the number of operations is alsom×n×ctimes.

Although the CIQFCM algorithm requires a certain amount of time for clustering spatial mapping,but for large-size images,this process takes much less time than the clustering process.

4.2.3.Space complexity

To store image data,both FCM and CIQFCM algorithms require spacem×n× 3 × sizeof(float).To storeUandV,FCM algorithm requiresm×n×c×sizeof(float)andc×3×sizeof(float)bytes.To storeCIQFCM algorithm requiresNc×c×sizeof(float)andc×3×sizeof(float)bytes.Besides,CIQFCM algorithm still needs to storeNPandC.Where,NPoccupies a space ofNc× sizeof(int),Coccupies a space ofNc× 3 × sizeof(float).Hence,in addition to storing images,CIQFCM clustering algorithm requires a total storage space of less thanNc×(c+4)×sizeof(float).WhenNc×(c+4)

Fig.2.Experimental images.

5.Simulation and analysis

Several experiments were carried out to discuss the selection of proper quantization intervals and to verify the effect and efficiency of the CIQFCM algorithm.The computer for the simulating experiments was ThinkPad T480s,configured with CPU CORE i7 dualcore,and 8 GB memory.

5.1.Discussions on the quantization intervals

To study the influence of the quantization level on the accuracy and efficiency of the CIQFCM algorithm,several experiments were carried out.The scopes of three coordinates namedL,a,andbare(0,100),(-120,120),and (-120,120),respectively.If quantization intervals of all the three coordinates are 1,theNcwithout compression will be 100 × 240 × 240=5760000,which is a very large number.So,it is necessary to compress the amount ofNcand obtain the proper quantization intervals via analysis of the sample number,efficiency,and effect of the CIQFCM algorithm with different quantization intervals.Fig.2 shows three of the experimented images with different background,and the image sizes of Fig.2(a),(b),(c),and(d)are 400×400,540×540,900×900,and 469 × 469,respectively.Table 3 shows the results of experiments.For brevity,only the compressedNc,time consuming and differences of average colors of each case were shown in Table 3.The difference of average color can be regarded as the distance calculated by the CIE94 distance formula between average color value of the dominant color image [24] extracted using CIQFCM algorithm and that of original image.The dominant color images are obtained by replacing all the colors in the original image with the five dominant colors obtained by clustering.It can be obtained by replacing each pixel color in the image with the closest dominant color according to the color distance.Obviously,the closer the dominant color image is to the original image,the better the dominant color extraction effect is.The difference of average color can show the difference of the statistic information of colors in two images.Therefore,we use the difference of average colors between the dominant color image and original image to assess the effect of dominant colors extraction.

Analysis of Table 3 reveals that,firstly,the compression methodcan significantly reduce the number of sample data.For example,when quantization interval was 1,theNcafter compressing in Fig.2(a),Fig.2(b),Fig.2(c),and Fig.2(d)were reduced from 5760000 to 40153,33025,11576,and 40449,respectively;secondly,as the quantization intervals increased from 1 to 10,theNcdecreased gradually;thirdly,as the quantization intervals increased from 1 to 10,the time consuming of simulation decreased quickly first and slowly later.This is probably due to that when the number of samples was large,the reduction of number of samples led to a reduction of the time consuming;but when the number of samples was small enough,the reduction of number of samples affected the efficiency of algorithm weakly;fourthly,as the quantization intervals increased,the change law of average color difference was generally on the rise,but not on a monotonous rise trends.

Table 3 Influence of quantization intervals on efficiency and effect of the CIQFCM algorithm.

By comprehensive analysis of the trend ofNc,time consuming and difference of average color with different quantization intervals,we found that the when the quantization intervals was set to 4,a better calculation result could be obtained while consuming less time.

5.2.Algorithm effect verification

To verify the effect of the CIQFCM algorithm,4 cases with different style of images such as shrubbery,beach,wasteland,forest,and leafy were studied.The number of clusters was 5.The dominant colors were extracted based on PFCM algorithm which is an improved algorithm of FCM proposed by reference [24] and CIQFCM algorithm proposed in this work,with the value of quantization interval set to 4.The CIELab color space and CIE94 distance formula were adopted to calculate the color difference.The results are shown in Fig.3,in which a1,b1,c1,d1,and e1 are the original images;a2,b2,c2,d2,and e2 are the dominant color images extracted using PFCM clustering algorithm[24];a3,b3,c3,d3,and e3 are the dominant color images extracted using the CIQFCM clustering algorithm proposed in this work.

It can be found that Fig.3(a2)is relatively close to Fig.3(a3),and although there are only 5 colors,the two images are consistent with Fig.3(a1)in overall tone and basic distribution of colors,indicating that the two methods have basically consistent clustering effect.Moreover,the images series of b,c,d,and e verifies that the CIQFCM clustering algorithm is applicable to all the 4 cases.

Table 4shows the average values of the original images and the two dominant color images in the CIELab color space,the difference in average color values between the two dominant color images and the original images,and the difference in average color values between the two dominant color images.Analysis of Table 4 reveals that the three images of each case have close average color values.The mean value of the difference in average color values between the two dominant color images is merely 0.1593.In addition,the mean values of the difference in average color values between original image and the dominant color images obtained by the two algorithms are merely 0.24976 and 0.15356,respectively.These suggest that the two dominant colors extraction algorithms have basically consistent effect,both of which can accurately extract the dominant colors information of the image.Besides,the maximum difference in mean color value between the two dominant color images and original images by using PFCM and CIQFCM algorithms is 0.3986 and 0.2799,respectively.It indicates that the proposed CIQFCM algorithm showed better performance in the experiments.

5.3.Algorithm efficiency verification

From the conclusion of 5.2,we can see that PFCM and CIQFCM algorithms have basically consistent clustering effect.To compare computational efficiency of them,the two clustering algorithms were used to process images with different size,and each image was repeatedly clustered 5 times.The average time consumption of each clustering algorithm was calculated,as shown in Table 5.

Table 5shows that the clustering time of PFCM algorithm increased rapidly with the image size.The time consumption in processing images with a size of 1024 × 1024 pixels was about 117.65 s;while the time consumption of CIQFCM algorithm varied little with the increase of image size.It took only about 3.23 s for CIQFCM algorithm to cluster an image with a size of 1024 × 1024 pixels.This is because PFCM algorithm took all pixels in the image as the clustering samples,so the number of clustering samples increased rapidly with the image size.In contrast,the CIQFCM algorithm took quantized colors as the clustering sample.As a result,the number of cluster samples increased very little with the image size,and clustering efficiency was less affected by image size.In this way,as the image size increased,the CIQFCM algorithm showed an increasingly advantage in clustering efficiency over the PFCM algorithm.When the image size was 1024×1024,the efficiency was increased by more than 36 times.

Table 4 Comparison of the average color value of the original images and that of the dominant color images under the two algorithms.

Table 5 Comparison of the efficiency of two algorithms in processing images with different sizes.

6.Conclusion

This paper proposes a quick clustering algorithm of color image based on clustering space mapping,which can extract dominant colors of large-size background images quickly and accurately.The superiority of the proposed CIQFCM algorithm is proved by theoretical derivation and simulation experiments.However,for CIQFCM algorithm,clustering spatial mapping is needed before FCM clustering,so the advantages of CIQFCM algorithm are not obvious when it is applied to small-size images.

Fig.3.Effect verification of CIQFCM clustering algorithm.(a1,b1,c1,and d1 are original images;a2,b2,c2,and d2 are dominant color images of PFCM algorithm;a3,b3,c3,and d3 are dominant color images of CIQFCM algorithm).

The following conclusions can be drawn from this study:

(1) The method to compress the clustering samples after mapping are of great importance to the improvement of the efficiency of the CIQFCM algorithm.The experiment results showed that when the quantization interval was set to 4,a better calculation result can be obtained with less time consumption.

(2) The CIQFCM algorithm has good clustering effect as that of the PFCM clustering algorithm.According to the results of four cases in the simulation experiments,the maximum color difference between the average color of the 5-color dominant color images obtained by CIQFCM clustering algorithm and average color of the original images was only 0.2799;

(3) According to the experiments,the CIQFCM algorithm can improve the clustering efficiency,and its advantage becomes more obvious as the image size increases.Simulation experiments showed that when the image size increased from 128 × 128 to 1024 × 1024,the efficiency improvement of CIQFCM algorithm was increased from 6.44 times to 36.42 times.

The algorithm proposed in this work can quickly extract dominant colors of large-size images,which can be applied to the fields such as camouflage painting design,image tone analysis and image segmentation.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.