基于遺傳算法的圖像壓縮
2007-01-01 00:00:00陳玉萍須文波
計算機應用研究 2007年6期
摘 要：用基于圖像像素的遺傳聚類算法分析圖像壓縮問題，要解決的主要問題是找到一種能有效地處理這種聚類的算法。如今用遺傳算法來解決聚類問題正在被研究。用遺傳算法得到一個有序的圖像像素序列，然后進行聚類獲得壓縮。結果表明在圖像壓縮問題中，遺傳算法是一種有效的、可靠的優化算法，具有一定的實用價值。
關鍵詞：遺傳算法； 圖像壓縮； 聚類
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2007)06-0167-03
0 引言
聚類算法可分成兩類，即建設性算法和迭代算法。在建設性算法中，由局部解發展成一個完整的可行解決定了到各個不同類的目標。在迭代算法中，初始化一個完整的可行解總是可能的，并且從一次次迭代中，通過不同方法對可行解改進。常見的Kmeans聚類就屬于這個類型。
近來，Ismail 和Kamel［1］已經通過深度優先和廣度優先交替使用方法進行目標函數最小化來改進Kmeans算法［2］。在這個算法中，目標元素在每次迭代時被移動到不同的類中，通過不斷地調整目標元素來減小目標函數值，同時該算法的貪婪本性能使目標函數值達到局部最小。在調整局部最小問題上， Klein和Dubes［3］已經應用了模擬退火算法解決此問題，但是模擬退火算法的缺點是運行時間長且模擬退火算法的有效進化過程是很難得到的。
本文主要是基于Bhuyan的文章［4］，首先用遺傳算法來獲取一個適當的目標序列N，然后把N個目標分成M個不相關的類。而本文用遺傳算法來找到聚類中的可能解，并同步地通過該算法來搜索最優解，并對最優解進行聚類。它形成一種與經典遺傳算法相對應的可選方案：先定義了適應性函數，用它來使所要排序的元素的無序性達到最小化。在這種方法中，適應性值的計算和聚類過程是不相關的。當獲得有序的元素序列后，就對其進行聚類，把聚類看做是算法的最后一步。根據在實驗中獲得的結果，筆者認為用遺傳算法來解決聚類問題是非常有前景的。
1 遺傳算法的描述［5］
把基于文獻[1]中的遺傳算法應用于獲取有序元素。
1.1 目標函數
本文在目標函數中沒有考慮聚類，只設定用遺傳算法去獲得一有序元素序列，目的是縮小元素的無序性。因此假設：
給出一個有序元素序列：X=[Xi]N個有序元素，每一個元素向量又是一個包含P個字節的向量。
目標函數定義如下：
現在問題是最小化F。F表示序列中每一個元素與它的下一個元素之間的距離之和。
1.2 聚類方案：有序序列
用有序序列的元素來表示所求的目標，在這些有序元素中，每一部分是由目標函數轉換來的。這種有序元素之間表現出較大的相似性，而在最優聚類中并沒有直接表示出來。
例如，假設1－6的目標染色體其序列為（2 3 5 1 6 4）。假定在一個導致最優解的序列中相似的對象被放在彼此靠近的地方。基于這個假設，序列（2 3 5 1 6 4）顯示2和3 比2和5更相似，5不能包含在含有2而沒有3的類中。在具體把N個目標分割成M個類的特殊情況下，假設（O1，O2，…，ON）是N個目標的特殊序列。那么每一類構成一目標間距（Oi+1，Oi+2，…，Oj），(1≤i≤j≤N)。
根據這種約束條件，其不同類的個數為1/2×N×(N+1)。
1.3 初始化種群構造器
下面給出了基于遺傳算法的三種不同初始化種群構造器：
(1)構造器A：隨機設置一個有序的目標。這種策略的目的是獲得一個初始化種群。它可在最壞的情況下測試遺傳算法。在整個搜索空間，遺傳算法可完全忽視一些最佳的區域。
(2)構造器B：使用啟發式算法來計算兩目標間的最小距離。它隨機地產生一目標標志并且把它放置在有序序列的第一個位置。然后在所有的對象中搜索有序序列中不存在的目標，目的是找到與最近加入到有序序列的對象最接近的目標。它重復這種操作直到所有的目標均包含在有序序列中。此構造器的復雜度為θ(N2)。
(3)構造器C：使用一個貪婪的啟發式算法去構造一個初始化種群，其主要目的是平衡隨機性問題。與構造器B不同之處是尋找與最近添加到有序序列中的對象最接近的目標，本構造器搜索包含在序列中的目標，不是全部只在K個目標中搜索，K是一個常量。在這種情況下，時間復雜度可大大減少。
文采用構造器C，在此構造器中允許參數K可由用戶輸入。
1.4 雙親選擇操作
這里所面臨的問題是函數的最小化問題。因此目標函數f(x)必須與適應性函數f(x)相映射。在這個適應性函數中，選擇xi作為父代（用于交叉）的概率由下式確定：
f(xi)/∑pi=1f(xi)（3）
其中，P是種群的大小，如果把f(x)當做F(x)的轉換，那么目標函數值最大的和最小的序列之間沒有太大的區別。因此通過下面這種方法來變換解決：
這里遇到的問題歸結為適應函數中最大常量的計算和種群中所有染色體的適應性值彼此太接近。用這種方法產生一代的進化幾乎是基于等概率的，而不是基于選擇上一代最佳部分。為了解決這個問題，在下列方法中測量適應性函數值：
1.5 交叉操作
在這個交叉操作中子代第一個目標相對應于任何父代的第一個位置。那么就定義在雙親中最近被包含的距離。最短距離的目標被加到子代最左邊的空的位置上。如果計算得到的距離是相等的，那么目標是可隨機選擇的，這樣處理一直到所有的子代位置被填滿。
因此隨機地從4、5、7中選擇。假定選擇7，把7放在子代的第二個位置上。在P1 中最接近的是{2，6}和在P2中最接近的是{4，8}，由于6已經包含在里面了，再隨機地從2、4、8中選出子代的第三個目標。假定選定2，在剩余的位置用相同的方法把它填滿。染色體的結果為（6，7，2，4，8，1，5，3）。
1.6 取代操作
這步操作是從父代P(old)和子代P(offspring)中選擇一個固定大小的種群。由用戶給定一個參數X，確定新的種群P(new)是由父代P(old)和子代P(offspring)組合成最優的序列而來的。P(new)的剩余部分是隨機地從子代P(offspring)選擇出來的。當參數X為零時，P(new)全部從P(offspring)里選擇；否則，如果參數X等于種群的大小，那么P(new)是由P(old)和P(offspring)共同形成。
1.7 變異操作
這個操作主要是解決遺傳算法中有關局部最小化問題。這些問題似乎由于遺傳算法考慮到了種群作為一個整體而不是尋找最好的個體。事實上，遺傳算法在組合優化上是非常實用的，特別在局部搜索中優化最后的種群目標。
變異操作函數是隨機選擇兩個目標序列并改變其位置。
2 聚類算法的應用
一旦通過遺傳算法獲得有序元素序列后，就可以處理聚類問題。下面介紹四種不同的聚類算法來解釋這問題。
2.1 固定聚類
在該算法中聚類的數目是固定的，每個類中含有相同個數的數據向量。當獲得最終的有序序列時可依據數據向量劃分相應的類，如下公式：E=N/M。其中，N表示元素的數目，M表示類的數目，E表示每類所含元素。
2.2 固定類的動態聚類
在這個算法中聚類的數目是固定的，但每個類中含有的數據向量個數不同，與第一種聚類不同。當獲得最終有序元素序列后，計算相鄰兩個元素間的歐氏距離，最后選擇M-1較大距離作為聚類中心。這種方法的思路是這些較大距離的元素必須來自不同的聚類。
2.3 不固定類的動態聚類
這種方法相似于上面的方法，不同之處在于聚類的數目是不固定的，相反它是由用戶輸入參數算法來決定：壓縮比例。
使用這個參數后，用該算法計算所需群的數量然后用它們來執行聚類過程。
類的計算如下：
C=trunc[(100-p)×N/100]
其中，C表示要用到的類的數目，P表示用戶輸入的壓縮比例，N表示聚類的所有元素。
2.4 基于量子的微粒群優化聚類（QPSO聚類）［5，6]
QPSO是一種微粒群進化算法。在該算法中，聚類的數目是固定的，但指定到每一個類里元素數目是不固定的。它用“群體”和“進化”的概念，依據個體（微粒）的適應值大小進行操作。QPSO將每個個體看做是Nd維搜索空間中的一個沒有重量和體積的微粒，并在搜索空間動態調整粒子i的最佳適應性值pbest， 及粒子群的最佳適應性值gbest。
聚類的標準是根據樣本之間的歐幾里得幾何距離（Euclidean），即計算樣本和每一個聚類中心的距離，把這個樣本分配到距離最小的中心向量中。樣本到聚類中心的距離計算如下：
3 實驗結果
測試結果如表1所示（誤差：平方偏差的總和）。
表1 測試結果
4 結束語
所有的測試在同一幅圖像中，但所有的各步操作在本文中是有效的。對于固定聚類方法，盡管算法簡單，結果可接受，但不推薦，原因是在計算時間差不多的情況下QPSO聚類能達到更好的效果。固定動態聚類沒有達到很好的效果，在很多情況下，其結果比固定聚類方法更糟糕，用這種方法來進行圖像壓縮，所聚的類有的非常大，里面有很多均值點。雖然誤差很大，但它在處理圖像顏色和定義邊界時有很好的效果。不固定類的動態聚類經其結果分析發現能達到一定的效果。通過QPSO聚類方法的實現和數據的測驗分析，能達到很好的壓縮效果。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
