李賀 江登英 黃樟燦 王占占

摘 要：針對(duì)K-means聚類算法在彩色圖像顏色量化問題中對(duì)初始條件依賴性較強(qiáng)而易陷入局部最優(yōu)的缺點(diǎn)，以及傳統(tǒng)智能優(yōu)化算法在尋優(yōu)時(shí)只考慮了種群層內(nèi)個(gè)體的相互競(jìng)爭(zhēng)而忽略種群層間相互協(xié)作的問題，提出了一種基于K-means的金字塔結(jié)構(gòu)演化策略（PES）彩色圖像量化算法。首先，將K-means聚類算法中的聚類損失函數(shù)作為新算法的適應(yīng)度函數(shù);其次，運(yùn)用PES對(duì)色彩進(jìn)行種群初始化、分層、探索、加速以及聚類等操作;最后，利用新算法對(duì)4幅標(biāo)準(zhǔn)彩色測(cè)試圖像進(jìn)行不同色彩量化級(jí)的量化。實(shí)驗(yàn)結(jié)果表明，所提算法能夠改善K-means聚類算法以及傳統(tǒng)智能算法的上述缺陷，在類內(nèi)均方誤差評(píng)判準(zhǔn)則下，圖像的平均失真率比基于PES的算法低12.25%，比差分進(jìn)化算法低15.52%，比粒子群優(yōu)化（PSO）算法低58.33%，比K-means算法低15.06%，且隨著色彩量化級(jí)的減少，算法量化后的圖像失真率比其他算法降低更多，此外，算法量化圖像的視覺效果優(yōu)于其他算法。

關(guān)鍵詞：圖像量化;金字塔結(jié)構(gòu);K均值聚類;粒子群優(yōu)化算法;智能算法

中圖分類號(hào)：TP317.4

文獻(xiàn)標(biāo)志碼：A

Method for solving color images quantization problem of color images

LI He， JIANG Dengying*， HUANG Zhangcan， WANG Zhanzhan

School of Science， Wuhan University of Technology， Wuhan Hubei 430073， China

Abstract：

For the color quantization problem of color images， the K-means clustering algorithm has strong dependence on initial conditions and is easy to fall into local optimum， and the traditional intelligent optimization algorithms only consider the mutual competition between individuals in the population layer and ignores the mutual cooperation between the population layers. To solve the problems， a K-means-based PES （Pyramid Evolution Strategy） color image quantization algorithm was proposed. Firstly， the clustering loss function in K-means clustering algorithm was used as the fitness function of the new algorithm; secondly， PES was used for the population initialization， layering， exploration， acceleration and clustering of the colors; finally， the new algorithm was used to quantify four standard color test images at different color quantization levels. The experimental results show that the proposed algorithm can improve the defects of the K-means clustering algorithm and the traditional intelligent algorithm. Under the criterion of intra-class mean squared error， the average distortion rate of the image quantized by the new algorithm is 12.25% lower than that quantized by the PES-based algorithm， 15.52% lower than that quantized by the differential evolution algorithm， 58.33% lower than that quantized by the Particle Swarm Optimization （PSO） algorithm， 15.06% lower than that quantized by the K-means algorithm; and the less the color quantization levels， the more the image distortion rate reduced quantized by the new algorithm than that quantized by other algorithms. In addition， the visual effect of the image quantized by the proposed algorithm is better than that quantized by other algorithms.

Key words：

image quantization; pyramid structure; K-means clustering; Particle Swarm Optimization （PSO） algorithm; intelligent algorithm

0 引言

彩色圖像顏色量化是圖像處理領(lǐng)域的一項(xiàng)基本技術(shù)，它將圖像色彩從一個(gè)較大顏色集合映射到另一個(gè)較小顏色集合，通過(guò)選擇最優(yōu)的K種顏色建立目標(biāo)調(diào)色板，使得根據(jù)目標(biāo)調(diào)色板所得到的重建圖像失真度最小[1]。顏色量化在圖像處理的很多領(lǐng)域有著重要的作用，特別是彩色圖像的應(yīng)用領(lǐng)域，比如：圖像壓縮、圖像存儲(chǔ)、圖像分割[2]、圖像復(fù)原等。

目前顏色量化方法較多，如八叉樹[3]、K-means算法[4]、遺傳算法（Genetic Algorithm， GA）[5]以及粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法[6]等。許永峰等[7]把K-means聚類方法和粒子群優(yōu)化算法結(jié)合起來(lái)，對(duì)彩色圖像進(jìn)行聚類量化，該算法在峰值信噪比和均方根誤差評(píng)判準(zhǔn)則下可以得到更好的量化結(jié)果。Alamdar等[8]提出了一種基于遺傳算法和粒子群優(yōu)化算法的模糊C均值聚類 （the Fuzzy C-Means clustering， FCM） 混合算法，新算法結(jié)合了三種算法的優(yōu)點(diǎn)，聚類效果優(yōu)于其他算法。 Omran等[9]提出了一種基于PSO算法的彩色圖像顏色量化算法（Color Image Quantization

algorithm based on Particle Swarm Optimization， PSO-CIQ），該算法應(yīng)用PSO來(lái)細(xì)化從K-means聚類算法中獲得的質(zhì)心。蘇清華[10]提出了基于差分進(jìn)化的彩色圖像顏色量化算法DE-CIQ（Differential Evolution based Color Image Quantization algorithm），在DE/best/1策略中小概率的應(yīng)用K-means聚類策略進(jìn)行局部調(diào)整，提高了DE/best/1策略的量化效果和收斂速度。

以上所提到的K-means聚類算法是一種收斂速度較快的搜索算法，但它對(duì)初始條件依賴性較強(qiáng)，一旦選定了初始聚類中心 ，則后面的迭代過(guò)程是完全確定的 ，即該算法缺乏探索新解的能力 ，所以它容易陷入局部最優(yōu)解，在重建彩色圖像時(shí)很可能會(huì)嚴(yán)重失真[11]，這與梯度下降法相似，初始值的選取決定著能否尋求到全局最優(yōu)解。而PSO、DE等智能算法雖然降低了對(duì)初始解的依賴，但這些算法將研究重心放在了個(gè)體之間的競(jìng)爭(zhēng)上，主要解決種群內(nèi)部個(gè)體開采與探索的矛盾，而忽略了種群內(nèi)部個(gè)體或者種群之間競(jìng)爭(zhēng)與協(xié)作的矛盾。談慶[12]在2018年提出了金字塔結(jié)構(gòu)演化策略（Pyramid Evolution Strategy， PES），它的并行搜索的特點(diǎn)克服了K-means極度依靠初始點(diǎn)的選擇的缺陷。此外，PES有著明確的分工機(jī)制與晉升機(jī)制，能夠兼顧平衡開采與探索、競(jìng)爭(zhēng)與協(xié)作的矛盾，彌補(bǔ)了傳統(tǒng)的演化算法顧此失彼的缺陷，有著很強(qiáng)的跳出局部最優(yōu)的優(yōu)點(diǎn)。

因此，本文將彩色圖像顏色量化作為一種NP問題，提出了一種基于K-means的PES彩色圖像顏色量化算法。首先，將K-means聚類算法中的聚類損失函數(shù)作為新算法的適應(yīng)度函數(shù);其次，根據(jù)金字塔結(jié)構(gòu)演化策略的分層機(jī)制將初始化種群分層，通過(guò)個(gè)體探索、加速、聚類、傳遞等過(guò)程進(jìn)行個(gè)體更新以及迭代;最后，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證該算法在類內(nèi)均方誤差評(píng)判準(zhǔn)則下得到失真度低于其他算法的量化圖像。

1 類內(nèi)均方誤差函數(shù)

設(shè)大小為m×n的彩色圖像Y記作：

Y（i， j）={YR（i， j），YG（i， j），YB（i， j）|1≤i≤m，1≤j≤n}

其中YR（i， j），YG（i， j），YB（i， j）分別表示了圖像Y的第i行第j列像素點(diǎn)所包含的紅、綠、藍(lán)三種顏色。

設(shè)量化后的圖像Y′記作：

Y′（i， j）= {Y′R（i， j），Y′G（i， j），Y′B（i， j）|1≤i≤m，1≤j≤n}

其中Y′R（i， j），Y′G（i， j），Y′B（i， j）分別表示量化后圖像Y′第i行第j列像素點(diǎn)所包含的紅、綠、藍(lán)三種顏色。

彩色圖像Y與其量化圖像Y′之間的顏色失真度一般用類內(nèi)均方誤差函數(shù)（Mean Squared Error， MSE）來(lái)度量[8]，其定義如下：

MSE=1m×n∑mi=1∑nj=1[（YR（i， j）-Y′R（i， j））2+

（YG（i， j）-Y′G（i， j））2+（YB（i， j）-Y′B（i， j）]1/2（1）

MSE值表示量化圖像的平均失真度，從式（1）中可以看出：MSE值越大，原圖像Y與量化后的圖像Y′之間的差別越大;MSE值越小，則原圖像Y與量化后的圖像Y′之間的差別越小，量化效果就越好[10]。

2 K-means聚類算法

K-means聚類算法是聚類算法的典型代表，其基本思想是：設(shè)X=（x1，x2，…，xn）是由n個(gè)樣本組成的樣本集，K（2≤K≤n）為預(yù)先設(shè)定的類別數(shù)目，k（k=1，2，…，K）為第k類樣本的中心，根據(jù)樣本點(diǎn)到某個(gè)樣本中心的距離dik=‖xi-k‖最小來(lái)判斷樣本點(diǎn)屬于某一類別，其中聚類損失函數(shù)為：

f=∑Kk=1∑ni=1dik（2）

聚類評(píng)判標(biāo)準(zhǔn)即聚類損失函數(shù)達(dá)到最小，經(jīng)過(guò)每次迭代后的聚類中心更新為：

k=（∑nki=1 xi∈Xkxi）/nk（3）

其中：Xk表示屬于第k類的所有樣本點(diǎn)，nk表示第k類樣本點(diǎn)的數(shù)目。

K-means聚類算法的具體流程如下：

1） 給定初始樣本點(diǎn)X，分類數(shù)目K以及終止條件ε>0（或最大迭代數(shù)目MAXGEN）。

2） 初始化聚類中心0= （01，02，…，0K），并計(jì)算聚類損失函數(shù)f，令gen=0。

3） 計(jì)算dgenik以及gen=（gen1，gen2，…，genK）。

4）計(jì)算fgen+1，如果‖fgen+1-fgen‖<ε（gen>MAXGEN），則停止迭代;否則令gen=gen+1，返回步驟3）。

3 金字塔演化策略

3.1 PES基本思想

將種群分為不同的層次，層內(nèi)個(gè)體相互競(jìng)爭(zhēng)，層間個(gè)體相互協(xié)作，分布在底層的個(gè)體競(jìng)爭(zhēng)范圍較廣，數(shù)量較多;分布在上層的個(gè)體競(jìng)爭(zhēng)范圍相對(duì)較小，數(shù)量較少。每層中的個(gè)體之間相互競(jìng)爭(zhēng)，優(yōu)秀的個(gè)體有上升到更高層的機(jī)會(huì)。例如，一家企業(yè)公司的組成可以由金字塔結(jié)構(gòu)進(jìn)行表示：由決策層做出一些重大決策，然后由管理層傳遞命令，最后由基層進(jìn)行實(shí)現(xiàn)，通過(guò)層與層之間的信息交互達(dá)到協(xié)作的目的。層與層之間不是固定的，而是存在競(jìng)爭(zhēng)協(xié)作流動(dòng)的，如果個(gè)體業(yè)績(jī)做好了，他會(huì)在同層之中脫穎而出，會(huì)有上升的機(jī)會(huì);反之，則有可能被淘汰[13]。

PES整體框架是一個(gè)金字塔形狀，由探索層、傳遞層、開采層組成，同層個(gè)體之間存在競(jìng)爭(zhēng)關(guān)系，層與層之間存在協(xié)作關(guān)系。

如圖1所示，在PES中，通過(guò)對(duì)種群進(jìn)行適應(yīng)度評(píng)估，適應(yīng)度值較小的個(gè)體側(cè)重于探索工作，被分配到第4層;適應(yīng)度值中等的個(gè)體負(fù)責(zé)開采、探索與傳遞工作，被分到2、3層;適應(yīng)度值最大的個(gè)體側(cè)重于開采工作，被分到第1層;由下至上每層個(gè)體數(shù)逐漸減少。

3.2 層內(nèi)競(jìng)爭(zhēng)

由于不同層分工的不同，競(jìng)爭(zhēng)策略也不一樣。探索層個(gè)體為了探索發(fā)現(xiàn)一些潛在優(yōu)質(zhì)個(gè)體，它們的產(chǎn)生具有較大的不確定性，產(chǎn)生范圍較廣（即搜索半徑大）;傳遞層位于探索層與開采層之間，個(gè)體不確定性有所限制，其主要是構(gòu)建開采與探索之間的橋梁并完成開采初步篩選，同時(shí)把潛在的優(yōu)秀個(gè)體傳輸給上一層;而位于頂層的開采層，它具有足夠強(qiáng)的開采能力去開采和深挖，可以把每一個(gè)潛在優(yōu)秀個(gè)體所對(duì)應(yīng)的區(qū)域開采完全[12]。

3.3 層間協(xié)作

層間協(xié)作主要由兩部分組成：傳遞過(guò)程與孵化過(guò)程。對(duì)于不同層之間，通過(guò)優(yōu)秀個(gè)體向上傳遞進(jìn)行升層操作;對(duì)于傳遞上去的新的潛在優(yōu)秀個(gè)體，需要進(jìn)行保護(hù)培養(yǎng)政策來(lái)孵化，充分挖掘他的潛力，而不是直接與該層中的優(yōu)秀個(gè)體競(jìng)爭(zhēng)[12]。

4 基于K-means的PES彩色圖像量化算法

由于K-means聚類算法對(duì)初始值敏感、易陷入局部極小值而得不到全局最優(yōu)解。本文將具有全局尋優(yōu)能力且考慮種群之間相互協(xié)作的PES和K-means聚類算法結(jié)合起來(lái)，將K-means聚類算法的聚類損失函數(shù)作為新算法的粒子適應(yīng)度函數(shù)，將類內(nèi)均方誤差作為評(píng)價(jià)準(zhǔn)則，對(duì)彩色圖像進(jìn)行不同量化級(jí)的量化。

4.1 參數(shù)設(shè)置

給定K作為彩色圖像量化后的色彩量化級(jí)，本文取K=16、32、64，各層種群個(gè)體數(shù)量所占比例divide=（0.1，0.2，0.3，0.4）[12]，各層搜索鄰域半徑R=（1，3，6，8），各層傳遞比例trans=（0.2，0.4，0.6）[12]，加速步長(zhǎng)lamta=0.3，迭代的最大次數(shù)MAXGEN=200[10]。

4.2 種群初始化

由于彩色圖像包括R、G、B三種顏色，設(shè)self（N，3）是大小為m×n的圖像Y所有顏色構(gòu)成的矩陣，根據(jù)下列公式可以將原圖像中不同顏色提取出來(lái)。

Dif_X0=unique（self，′rows′）（4）

其中：Dif_X0為原圖像中不同顏色的集合，self表示一幅圖像的所有顏色;rows是一個(gè)參數(shù)設(shè)置，用來(lái)獲取矩陣self中不同行向量構(gòu)成的矩陣;N=m×n，unique函數(shù)是把self（N，3）的不重復(fù)元素提取出來(lái);再選取原圖像中不同的K種顏色作為一個(gè)個(gè)體，記作：X（K，3，i）（i=1，2，…，NIND，NIND表示種群個(gè)數(shù)）。則初始種群X可記為X（K，3，NIND），其中每一個(gè)個(gè)體都被表示成一個(gè)K×3的矩陣。

4.3 個(gè)體更新

根據(jù)式（2）計(jì)算每個(gè)個(gè)體的適應(yīng)度值，將個(gè)體按照適應(yīng)度值大小順序以及分層比例進(jìn)行分層。在分配過(guò)程中：

num（i）=cumsum（length（F）×divided）（5）

其中：F是經(jīng)排序后的種群適應(yīng)度值向量，cumsum是對(duì)向量進(jìn)行累計(jì)求和，num（i）是每層所分配的最后一個(gè)個(gè)體在適應(yīng)度向量中所占的位置。

根據(jù)式（5）中的num（i），將全部種群個(gè)體分別分配到探索層、傳遞層2、傳遞層1和開采層，具體操作如下：

Xi′=X′（1：num（i）），?? ????i=1

X′（num（i-1）+1：num（i）），i=2，3，4（6）

Fi=F（1：num（i）），?????? i=1

F（num（i-1）+1：num（i）），i=2，3，4（7）

其中：Xi′表示每層個(gè)體，F(xiàn)i表示每層個(gè)體的適應(yīng)值。

通過(guò)式（5）～（7），將種群個(gè)體根據(jù)適應(yīng)值大小合理地分配給每一層。為了尋得最優(yōu)解，每一層的個(gè)體都需要進(jìn)行探索過(guò)程、加速過(guò)程、傳遞過(guò)程以及聚類過(guò)程。

4.3.1 探索過(guò)程

由于每一層的任務(wù)側(cè)重點(diǎn)不同，分工和探索半徑也不同，第四層主要側(cè)重探索，新個(gè)體的產(chǎn)生需要較大的隨機(jī)性，因此該層探索半徑較大。第一層的個(gè)體適應(yīng)性較好，主要側(cè)重于開采，為了把每一個(gè)潛在優(yōu)秀個(gè)體所對(duì)應(yīng)的區(qū)域開采完全，需要對(duì)其設(shè)置一個(gè)較小的探索半徑，搜索半徑反映了個(gè)體的開采與探索的能力。在文獻(xiàn)[12]中，每一層的搜索半徑是依據(jù)變量的上界U與下界L而選擇，如PES將第1層的搜索半徑設(shè)置為0.03*（U-L），第2層設(shè)置為0.05*（U-L），第3層設(shè)置為0.1*（U-L），第4層設(shè)置為0.55*（U-L）。在本文中，所研究的色彩值的每個(gè)分量是0～255之間的一個(gè)整數(shù)，為了方便起見，本文從第1層～第4層的搜索半徑依次設(shè)為1、3、6、8。 當(dāng)然，搜索半徑的大小影響著算法的尋優(yōu)能力，如果設(shè)置得過(guò)大，則算法的全局搜索能力變強(qiáng)，但局部搜索能力會(huì)變?nèi)?，反之亦然，它與差分進(jìn)化算法中的收縮因子F、遺傳算法中的交叉概率Pc等有著相似的作用，是影響算法性能的一個(gè)人為設(shè)置的參數(shù)。設(shè)每層探索半徑為Ri（i=1，2，3，4），則：

xnew=x+randperm（2*Ri+1，3）-Ri-1（8）

其中：xnew表示由原來(lái)個(gè)體x探索出的新個(gè)體。整個(gè)式（8）保證了個(gè)體x是在以自身為中心，半徑為Ri的鄰域內(nèi)搜索。

4.3.2 加速過(guò)程

在探索到新個(gè)體之后，為了能夠更好地完成初步篩選的功能，對(duì)其進(jìn)行加速操作。加速規(guī)則如下：

xspeed=xnew+ceil（λ（xnew-x））， f（x）≥f（xnew）

x+ceil（λ（x-xnew）），f（x）

其中： f為適應(yīng)度函數(shù)，xnew-x，x-xnew表明個(gè)體加速過(guò)程是朝著更優(yōu)的方向進(jìn)行的。步長(zhǎng)值設(shè)置為小數(shù)，是為了避免差值較大而錯(cuò)過(guò)最優(yōu)解，經(jīng)過(guò)調(diào)試，本文暫時(shí)將其設(shè)置為0.3。

4.3.3 傳遞過(guò)程

除了第一層，其他各層的傳遞過(guò)程均是從該層得到的新群體中選取一定比例的個(gè)體向上一層進(jìn)行傳遞，然后按照規(guī)模為2的隨機(jī)聯(lián)賽規(guī)則選取每一個(gè)被傳遞的個(gè)體。

傳遞過(guò)程充分體現(xiàn)了層與層之間的相互協(xié)作，優(yōu)秀的個(gè)體得到了晉升的機(jī)會(huì)，上升到上一層，在新的一層中會(huì)與同層個(gè)體再次進(jìn)行競(jìng)爭(zhēng)以獲得上升到更高層的機(jī)會(huì)。

4.3.4 K-means聚類

對(duì)每一個(gè)由探索、加速過(guò)程得到的新個(gè)體都需要進(jìn)行K-means聚類。首先根據(jù)式（3）得到新的聚類中心，即新的個(gè)體;然后根據(jù)式（2）計(jì)算新個(gè)體的適應(yīng)度值;最后將新舊個(gè)體的適應(yīng)度值進(jìn)行比較，并選擇一定比例的優(yōu)質(zhì)個(gè)體傳遞到上一層。

4.4 整合新種群

將每一層探索并聚類后的新個(gè)體、加速并聚類后的新個(gè)體、以及傳遞而來(lái)的新個(gè)體整合在一起，按照輪盤賭規(guī)則從中選擇同等數(shù)量的個(gè)體作為該層新個(gè)體。

4.5 算法流程

步驟1 確定參數(shù)，給定K作為彩色圖像的色彩量化級(jí)，確定種群規(guī)模NIND，以及各層種群個(gè)體所占比例divide，迭代的最大次數(shù)MAXGEN;

步驟2 種群初始化，隨機(jī)選取原圖像中的K種不同顏色作為一個(gè)個(gè)體x，構(gòu)造初始種群，記為X（K，3，NIND）;

步驟3 種群分層，按照式（2）計(jì)算每個(gè)個(gè)體的適應(yīng)值，將總的個(gè)體按適應(yīng)值從大到小的排序，并根據(jù)式（5）、（6）、（7）進(jìn)行分層;

步驟4 對(duì)個(gè)體進(jìn)行更新，每層個(gè)體通過(guò)探索、K-means聚類、加速、K-means聚類過(guò)程進(jìn)行更新，并從整合后的群體中按比例選取一定數(shù)量個(gè)體傳遞到上一層;

步驟5 終止條件判斷，如果gen>MAXGEN，則終止，并根據(jù)得到最優(yōu)的色彩結(jié)果對(duì)原彩色圖像Y進(jìn)行量化，畫出量化圖像Y′;否則令gen=gen+1，X=NewX，重新回到步驟3。

4.6 時(shí)間復(fù)雜度分析

設(shè)最大迭代次數(shù)為MAXGEN，種群規(guī)模為NIND，色彩量化級(jí)為K，由4.5節(jié)知，在一個(gè)完整的循環(huán)過(guò)程，第3步、第4步與第5步為并列操作，語(yǔ)句的執(zhí)行頻度均為f（n）=NIND·K，則對(duì)于算法的全部循環(huán)過(guò)程，語(yǔ)句的執(zhí)行頻度為f（n）=

MAXGEN·NIND·K， 因此本文算法的時(shí)間復(fù)雜度可表示為T（n）=O（f（n））=O（MAXGEN·NIND·K），K-means聚類算法與探索等過(guò)程是并列的，并沒有增加PES的時(shí)間復(fù)雜度，因此本文算法的時(shí)間復(fù)雜度與PES算法保持一致。

5 仿真實(shí)驗(yàn)

為驗(yàn)證算法的有效性，實(shí)驗(yàn)對(duì)文獻(xiàn)[10]中的大?。ǚ直媛剩?12×512的4幅標(biāo)準(zhǔn)測(cè)試圖像進(jìn)行量化，如圖2（a）前4幅圖像所示，將本文新算法與K-means算法、PSO算法、DE/best/1算法以及基于PES的算法對(duì)彩色圖像量化結(jié)果進(jìn)行比較。這里用類內(nèi)均方誤差MSE作為對(duì)比量。根據(jù)已有文獻(xiàn)參數(shù)顯示，在PSO算法和DE/best/1算法中，均有以下設(shè)置：種群規(guī)模為100，最大迭代次數(shù)為200，算法均運(yùn)行10次，記錄10次實(shí)驗(yàn)中最小的MSE值。因此本文算法參數(shù)設(shè)置為種群規(guī)模100，最大迭代次數(shù)200，加速步長(zhǎng)為0.3，同樣運(yùn)行10次，記錄10次實(shí)驗(yàn)中的最小MSE值。

以16色彩量化級(jí)的圖像為例，本文展示了5種不同算法的量化圖像，如圖2前4幅圖像中的（b）～（f）所示，同時(shí)以Lenna、Baboon圖像為例展示了部分細(xì)節(jié)效果，如圖2后2幅圖像Detail-L與Detail-B中的（b）～（f）所示。其中每幅圖中的 （b）、（c）、（d）、（e）和（f）分別表示本文算法、PES、DE/best/1、PSO、K-means聚類算法的量化圖像。需要指出的是，DE/best/1、PSO、K-means這三種算法的量化圖像效果來(lái)源于文獻(xiàn)[10]。表1為PES、DE/best/1、PSO、K-means以及本文算法分別對(duì)Pepper、Airplane、Lenna、Baboon這四幅圖像10次量化后的最小MSE值比較。表2為本文算法與其他算法在3個(gè)量化級(jí)、3幅圖像的MSE值的平均差值比。

圖2前4幅圖像分別展示了不同算法在色彩量化級(jí)為16時(shí)的量化圖像;圖2后兩幅圖像分別展示了圖2（a）中Lenna與Baboon兩幅圖像黑框部位不同算法的細(xì)節(jié)效果，通過(guò)圖像對(duì)比可以看出，本文算法得到的量化圖像與原圖像更加貼近。

通過(guò)表1數(shù)據(jù)可以看出：

1） 對(duì)于圖像Pepper、Baboon，無(wú)論色彩量化級(jí)為k=16、k=32或k=64，基于PES的算法的MSE值都低于PSO 算法、DE/best/1算法以及K-means的MSE值，且色彩量化級(jí)越少，兩者差別越大。

2） 對(duì)于圖像Lenna，無(wú)論色彩量化級(jí)為k=16或k=32，基于PES的算法的MSE值都低于PSO 算法、DE/best/1算法以及K-means的MSE值。但當(dāng)k=64時(shí)，K-means算法的MSE值低于PES算法的MSE值。

3） 對(duì)于圖像Airplane，在3個(gè)色彩量化級(jí)，基于PES的算法的MSE值僅低于PSO算法的MSE值。與DE/best/1算法和K-means算法相比，其MSE值都比較大，量化結(jié)果較差。

以上結(jié)果分析表明，基于PES的算法總體比PSO 算法和DE/best/1算法的量化效果好，這也體現(xiàn)了作為智能算法，以往智能算法只把問題的核心放在個(gè)體的競(jìng)爭(zhēng)上，而忽略了種群層間相互協(xié)作的不足，以及PES算法通過(guò)人才培養(yǎng)機(jī)制綜合考慮種群層內(nèi)競(jìng)爭(zhēng)、層間合作的優(yōu)勢(shì)之處。但K-means作為經(jīng)典的聚類算法，具有較強(qiáng)的局部搜索能力，其聚類效果以及收斂速度是極好的。從表1數(shù)據(jù)可以看出，隨著色彩量化級(jí)的增加， K-means量化效果也逐漸增強(qiáng)，當(dāng)k=64時(shí)，其量化效果優(yōu)于PES的量化效果。

本文新算法綜合考慮PES和K-means的優(yōu)缺點(diǎn)，首先通過(guò)具有全局尋優(yōu)能力的PES智能算法避免了K-means聚類算法易陷入局部最優(yōu)的缺點(diǎn)，然后結(jié)合K-means聚類算法聚類效果好的優(yōu)點(diǎn)，最后對(duì)原圖像進(jìn)行量化。從表1可以看出，在k=16、32、64時(shí)，新算法所得MSE值均比其他算法小，這說(shuō)明了該算法在克服了K-means聚類算法對(duì)初始點(diǎn)敏感和易陷入局部最優(yōu)的問題后展現(xiàn)出的優(yōu)越性。從表2可以看出，新算法對(duì)于Pepper、Airplane、Lenna三幅圖像量化后的MSE平均差值比為：比PES低12.25%，比DE/best/1低15.52%，比PSO低58.33%，比K-means低15.06%。以上分析均表明，新算法的量化效果優(yōu)于其他智能算法以及K-means聚類算法。

6 結(jié)語(yǔ)

本文把將PES用于彩色圖像顏色量化中，將K-means聚類算法中的聚類損失函數(shù)作為個(gè)體適應(yīng)度函數(shù)，提出了一種基于K-means的PES彩色圖像量化方法。本方法充分利用了PES的特點(diǎn)，較好地解決了彩色圖像顏色量化中K-means聚類算法對(duì)初值選擇很敏感的問題，同時(shí)考慮了種群個(gè)體在優(yōu)化過(guò)程中層內(nèi)個(gè)體相互競(jìng)爭(zhēng)與層間個(gè)體相互協(xié)作的問題，平衡了算法開采與探索、協(xié)作與競(jìng)爭(zhēng)的矛盾，讓協(xié)作和競(jìng)爭(zhēng)變得高效。仿真實(shí)驗(yàn)表明，新算法對(duì)彩色圖像的量化效果優(yōu)于粒子群等智能算法以及K-means聚類算法的量化效果，并且可以產(chǎn)生較好的視覺效果。

參考文獻(xiàn)

[1]徐速，胡健，周元.基于微粒群優(yōu)化算法的顏色量化[J].數(shù)字通信，2011，38（2）：61-63.（XU S， HU J， ZHOU Y. Color quantization based on particle swarm optimization algorithm[J]. Digital Communication， 2011， 38（2）： 61-63.）

[2]謝江寧，王磊.基于層級(jí)分割的顏色恒常性算法[J].山東大學(xué)學(xué)報(bào) （理學(xué)版），2016，51（1）：101-105.（XIE J N， WANG L. Color constancy using hierarchical segments [J]. Journal of Shandong University （Natural Science）， 2016， 51（1）： 101-105.）

[3]耿國(guó)華，周明全.基于八叉樹結(jié)構(gòu)的色彩量化算法[J].小型微型計(jì)算機(jī)系統(tǒng)，1997，18（1）：24-29.（GENG G H， ZHOU M Q. Color quantization algorithm based on octree structure [J]. Mini-Micro Systems， 1997， 18（1）： 24-29.）

[4]FRACKIEWICZ M， PALUS H. K-means color image quantization with deterministic initialization： new image quality metrics [C]// Proceedings of the 2018 International Conference on Image Analysis and Recognition， LNCS 10882. Berlin：Springer， 2018： 56-61.

[5]ZHANG Y， XU T， GAO W. Image retrieval based on GA integrated color vector quantization and curvelettransform [C]// Proceedings of the 2012 International Conference in Swarm Intelligence， LNCS 7331. Berlin： Springer， 2012： 406-413.

[6]沙秋夫，劉向東，何希勤，等.一種基于粒子群算法的色彩量化方案[J].中國(guó)圖象圖形學(xué)報(bào)，2007，12（9）：1544-1548.（SHA Q F， LIU X D， HE X Q， et al. Color image quantization using particle swarm optimization [J]. Journal of Image and Graphics， 2007， 12（9）： 1544-1548.）

[7]許永峰，姜振益.一種基于粒子群優(yōu)化的K-均值彩色圖像量化算法[J].西北大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，42（3）：351-354.（XU Y F， JIANG Z Y. A K-means color image quantization method based on particle swarm optimization [J]. Journal of Northwest University （Natural Science Edition）， 2012， 42（3）： 351-354.）

[8]ALAMDAR F， BAHMANI Z， HARATIZADEH S. Color quantization with clustering by F-PSO-GA[C]// Proceedings of the 2010 IEEE International Conference on Intelligent Computing and Intelligent Systems. Piscataway， NJ： IEEE， 2010： 233-238.

[9]OMRAN M G， ENGELBRECHT A P， SALMAN A. A color image quantization algorithm based on particle swarm optimization [J]. Informatica， 2005， 29（3）： 261-270.

[10]蘇清華.圖像顏色量化模型優(yōu)化方法及其在裂紋圖像中的應(yīng)用[D].武漢：武漢理工大學(xué)，2013：11-57.（SU Q H. Optimization methods of image color quantization model and its application in crack images [D]. Wuhan： Wuhan University of Technology， 2013： 11-57.）

[11]FREISLEBEN B， SCHRADER A. An evolutionary approach to color image quantization [C]// Proceedings of the 1997 IEEE International Conference on Evolutionary Computation. Piscataway， NJ： IEEE， 1997：459-464.

[12]談慶.基于金字塔結(jié)構(gòu)的群智能演化策略[D].武漢：武漢理工大學(xué)，2018：13-21.（TAN Q. Group intelligence evolution strategy based on pyramid structure [D]. Wuhan： Wuhan University of Technology， 2008： 13-21.）

[13]DURKHEIM . The Division of Labour in Society [M]. London： Macmillan Education UK， 2013： 5-10.

This work is partially supported by the Fundamental Research Funds for the Central Universities （2017IB014），

the Humanities and Social Sciences Research Project of Ministry of Education of the Peoples Republic of China （13YJCZH060）.

LI He， born in 1994， M. S. candidate. Her research interests include applied mathematics， image processing.

JIANG Dengying， born in 1976， Ph. D.， professor. Her research interests include applied mathematics.

HUANG Zhangcan， born in 1960， Ph. D.， professor. His research interests include intelligent computing， image processing.

WANG Zhanzhan， born in 1993， M. S. candidate. His research interests include intelligent computing.