基于遺傳算法的圖像壓縮

摘 要：用基于圖像像素的遺傳聚類算法分析圖像壓縮問題，要解決的主要問題是找到一種能有效地處理這種聚類的算法。如今用遺傳算法來解決聚類問題正在被研究。用遺傳算法得到一個有序的圖像像素序列，然后進(jìn)行聚類獲得壓縮。結(jié)果表明在圖像壓縮問題中，遺傳算法是一種有效的、可靠的優(yōu)化算法，具有一定的實用價值。

關(guān)鍵詞：遺傳算法； 圖像壓縮； 聚類

中圖分類號：TP391文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2007)06-0167-03

0 引言

聚類算法可分成兩類，即建設(shè)性算法和迭代算法。在建設(shè)性算法中，由局部解發(fā)展成一個完整的可行解決定了到各個不同類的目標(biāo)。在迭代算法中，初始化一個完整的可行解總是可能的，并且從一次次迭代中，通過不同方法對可行解改進(jìn)。常見的Kmeans聚類就屬于這個類型。

近來，Ismail 和Kamel［1］已經(jīng)通過深度優(yōu)先和廣度優(yōu)先交替使用方法進(jìn)行目標(biāo)函數(shù)最小化來改進(jìn)Kmeans算法［2］。在這個算法中，目標(biāo)元素在每次迭代時被移動到不同的類中，通過不斷地調(diào)整目標(biāo)元素來減小目標(biāo)函數(shù)值，同時該算法的貪婪本性能使目標(biāo)函數(shù)值達(dá)到局部最小。在調(diào)整局部最小問題上， Klein和Dubes［3］已經(jīng)應(yīng)用了模擬退火算法解決此問題，但是模擬退火算法的缺點是運行時間長且模擬退火算法的有效進(jìn)化過程是很難得到的。

本文主要是基于Bhuyan的文章［4］，首先用遺傳算法來獲取一個適當(dāng)?shù)哪繕?biāo)序列N，然后把N個目標(biāo)分成M個不相關(guān)的類。而本文用遺傳算法來找到聚類中的可能解，并同步地通過該算法來搜索最優(yōu)解，并對最優(yōu)解進(jìn)行聚類。它形成一種與經(jīng)典遺傳算法相對應(yīng)的可選方案：先定義了適應(yīng)性函數(shù)，用它來使所要排序的元素的無序性達(dá)到最小化。在這種方法中，適應(yīng)性值的計算和聚類過程是不相關(guān)的。當(dāng)獲得有序的元素序列后，就對其進(jìn)行聚類，把聚類看做是算法的最后一步。根據(jù)在實驗中獲得的結(jié)果，筆者認(rèn)為用遺傳算法來解決聚類問題是非常有前景的。

1 遺傳算法的描述［5］

把基于文獻(xiàn)[1]中的遺傳算法應(yīng)用于獲取有序元素。

1.1 目標(biāo)函數(shù)

本文在目標(biāo)函數(shù)中沒有考慮聚類，只設(shè)定用遺傳算法去獲得一有序元素序列，目的是縮小元素的無序性。因此假設(shè)：

給出一個有序元素序列：X=[Xi]N個有序元素，每一個元素向量又是一個包含P個字節(jié)的向量。

目標(biāo)函數(shù)定義如下：

現(xiàn)在問題是最小化F。F表示序列中每一個元素與它的下一個元素之間的距離之和。

1.2 聚類方案：有序序列

用有序序列的元素來表示所求的目標(biāo)，在這些有序元素中，每一部分是由目標(biāo)函數(shù)轉(zhuǎn)換來的。這種有序元素之間表現(xiàn)出較大的相似性，而在最優(yōu)聚類中并沒有直接表示出來。

例如，假設(shè)1－6的目標(biāo)染色體其序列為（2 3 5 1 6 4）。假定在一個導(dǎo)致最優(yōu)解的序列中相似的對象被放在彼此靠近的地方。基于這個假設(shè)，序列（2 3 5 1 6 4）顯示2和3 比2和5更相似，5不能包含在含有2而沒有3的類中。在具體把N個目標(biāo)分割成M個類的特殊情況下，假設(shè)（O1，O2，…，ON）是N個目標(biāo)的特殊序列。那么每一類構(gòu)成一目標(biāo)間距（Oi+1，Oi+2，…，Oj），(1≤i≤j≤N)。

根據(jù)這種約束條件，其不同類的個數(shù)為1/2×N×(N+1)。

1.3 初始化種群構(gòu)造器

下面給出了基于遺傳算法的三種不同初始化種群構(gòu)造器：

(1)構(gòu)造器A：隨機(jī)設(shè)置一個有序的目標(biāo)。這種策略的目的是獲得一個初始化種群。它可在最壞的情況下測試遺傳算法。在整個搜索空間，遺傳算法可完全忽視一些最佳的區(qū)域。

(2)構(gòu)造器B：使用啟發(fā)式算法來計算兩目標(biāo)間的最小距離。它隨機(jī)地產(chǎn)生一目標(biāo)標(biāo)志并且把它放置在有序序列的第一個位置。然后在所有的對象中搜索有序序列中不存在的目標(biāo)，目的是找到與最近加入到有序序列的對象最接近的目標(biāo)。它重復(fù)這種操作直到所有的目標(biāo)均包含在有序序列中。此構(gòu)造器的復(fù)雜度為θ(N2)。

(3)構(gòu)造器C：使用一個貪婪的啟發(fā)式算法去構(gòu)造一個初始化種群，其主要目的是平衡隨機(jī)性問題。與構(gòu)造器B不同之處是尋找與最近添加到有序序列中的對象最接近的目標(biāo)，本構(gòu)造器搜索包含在序列中的目標(biāo)，不是全部只在K個目標(biāo)中搜索，K是一個常量。在這種情況下，時間復(fù)雜度可大大減少。

文采用構(gòu)造器C，在此構(gòu)造器中允許參數(shù)K可由用戶輸入。

1.4 雙親選擇操作

這里所面臨的問題是函數(shù)的最小化問題。因此目標(biāo)函數(shù)f(x)必須與適應(yīng)性函數(shù)f(x)相映射。在這個適應(yīng)性函數(shù)中，選擇xi作為父代（用于交叉）的概率由下式確定：

f(xi)/∑pi=1f(xi)（3）

其中，P是種群的大小，如果把f(x)當(dāng)做F(x)的轉(zhuǎn)換，那么目標(biāo)函數(shù)值最大的和最小的序列之間沒有太大的區(qū)別。因此通過下面這種方法來變換解決：

這里遇到的問題歸結(jié)為適應(yīng)函數(shù)中最大常量的計算和種群中所有染色體的適應(yīng)性值彼此太接近。用這種方法產(chǎn)生一代的進(jìn)化幾乎是基于等概率的，而不是基于選擇上一代最佳部分。為了解決這個問題，在下列方法中測量適應(yīng)性函數(shù)值：

1.5 交叉操作

在這個交叉操作中子代第一個目標(biāo)相對應(yīng)于任何父代的第一個位置。那么就定義在雙親中最近被包含的距離。最短距離的目標(biāo)被加到子代最左邊的空的位置上。如果計算得到的距離是相等的，那么目標(biāo)是可隨機(jī)選擇的，這樣處理一直到所有的子代位置被填滿。

因此隨機(jī)地從4、5、7中選擇。假定選擇7，把7放在子代的第二個位置上。在P1 中最接近的是{2，6}和在P2中最接近的是{4，8}，由于6已經(jīng)包含在里面了，再隨機(jī)地從2、4、8中選出子代的第三個目標(biāo)。假定選定2，在剩余的位置用相同的方法把它填滿。染色體的結(jié)果為（6，7，2，4，8，1，5，3）。

1.6 取代操作

這步操作是從父代P(old)和子代P(offspring)中選擇一個固定大小的種群。由用戶給定一個參數(shù)X，確定新的種群P(new)是由父代P(old)和子代P(offspring)組合成最優(yōu)的序列而來的。P(new)的剩余部分是隨機(jī)地從子代P(offspring)選擇出來的。當(dāng)參數(shù)X為零時，P(new)全部從P(offspring)里選擇；否則，如果參數(shù)X等于種群的大小，那么P(new)是由P(old)和P(offspring)共同形成。

1.7 變異操作

這個操作主要是解決遺傳算法中有關(guān)局部最小化問題。這些問題似乎由于遺傳算法考慮到了種群作為一個整體而不是尋找最好的個體。事實上，遺傳算法在組合優(yōu)化上是非常實用的，特別在局部搜索中優(yōu)化最后的種群目標(biāo)。

變異操作函數(shù)是隨機(jī)選擇兩個目標(biāo)序列并改變其位置。

2 聚類算法的應(yīng)用

一旦通過遺傳算法獲得有序元素序列后，就可以處理聚類問題。下面介紹四種不同的聚類算法來解釋這問題。

2.1 固定聚類

在該算法中聚類的數(shù)目是固定的，每個類中含有相同個數(shù)的數(shù)據(jù)向量。當(dāng)獲得最終的有序序列時可依據(jù)數(shù)據(jù)向量劃分相應(yīng)的類，如下公式：E=N/M。其中，N表示元素的數(shù)目，M表示類的數(shù)目，E表示每類所含元素。

2.2 固定類的動態(tài)聚類

在這個算法中聚類的數(shù)目是固定的，但每個類中含有的數(shù)據(jù)向量個數(shù)不同，與第一種聚類不同。當(dāng)獲得最終有序元素序列后，計算相鄰兩個元素間的歐氏距離，最后選擇M-1較大距離作為聚類中心。這種方法的思路是這些較大距離的元素必須來自不同的聚類。

2.3 不固定類的動態(tài)聚類

這種方法相似于上面的方法，不同之處在于聚類的數(shù)目是不固定的，相反它是由用戶輸入?yún)?shù)算法來決定：壓縮比例。

使用這個參數(shù)后，用該算法計算所需群的數(shù)量然后用它們來執(zhí)行聚類過程。

類的計算如下：

C=trunc[(100-p)×N/100]

其中，C表示要用到的類的數(shù)目，P表示用戶輸入的壓縮比例，N表示聚類的所有元素。

2.4 基于量子的微粒群優(yōu)化聚類（QPSO聚類）［5，6] 

QPSO是一種微粒群進(jìn)化算法。在該算法中，聚類的數(shù)目是固定的，但指定到每一個類里元素數(shù)目是不固定的。它用“群體”和“進(jìn)化”的概念，依據(jù)個體（微粒）的適應(yīng)值大小進(jìn)行操作。QPSO將每個個體看做是Nd維搜索空間中的一個沒有重量和體積的微粒，并在搜索空間動態(tài)調(diào)整粒子i的最佳適應(yīng)性值pbest， 及粒子群的最佳適應(yīng)性值gbest。

聚類的標(biāo)準(zhǔn)是根據(jù)樣本之間的歐幾里得幾何距離（Euclidean），即計算樣本和每一個聚類中心的距離，把這個樣本分配到距離最小的中心向量中。樣本到聚類中心的距離計算如下：

3 實驗結(jié)果

測試結(jié)果如表1所示（誤差：平方偏差的總和）。

表1 測試結(jié)果

4 結(jié)束語

所有的測試在同一幅圖像中，但所有的各步操作在本文中是有效的。對于固定聚類方法，盡管算法簡單，結(jié)果可接受，但不推薦，原因是在計算時間差不多的情況下QPSO聚類能達(dá)到更好的效果。固定動態(tài)聚類沒有達(dá)到很好的效果，在很多情況下，其結(jié)果比固定聚類方法更糟糕，用這種方法來進(jìn)行圖像壓縮，所聚的類有的非常大，里面有很多均值點。雖然誤差很大，但它在處理圖像顏色和定義邊界時有很好的效果。不固定類的動態(tài)聚類經(jīng)其結(jié)果分析發(fā)現(xiàn)能達(dá)到一定的效果。通過QPSO聚類方法的實現(xiàn)和數(shù)據(jù)的測驗分析，能達(dá)到很好的壓縮效果。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。