基于GSOFM的分形圖像壓縮方法

1、基于 GSOFM 的分形圖像壓縮方法郭建威遼寧工程技術大學(125105E-mail :摘 要:本文針對分形圖像壓縮編碼中編碼時間長的特點, 給出了一種結合神經網絡和多尺 度分析的分形編碼方法。通過多尺度的逐次逼近和 KNN 網絡自組織分類,可以極大地縮減 分形編碼的時間。 這種新算法可通過高效的圖像域分類算法來改善對圖像掃描的速度, 減少 計算量,最終達到編碼加速的目的。此外,本文在自組織特征映射網絡(SOFM 基礎上結 合灰關系分析, 使用一種新型網絡 (GSOFM , 并作了計算機仿真實驗。 實驗仿真結果表明, 本文提出的方法與普通的全搜索方法相比, 可大大加速圖像編碼過程, 而壓縮率和

2、圖像質量 僅有微小變化。圖像質量,壓縮時間和壓縮率這三個指標也優(yōu)于 fisher 方法。關鍵詞:圖像壓縮,分形,神經網絡,自組織特征映射網絡1. 引言圖像壓縮技術已經研究了幾十年,并取得了一些成績,但還有許多的不足值得我們進一 步探討, 壓縮速度和質量依然是圖像壓縮中的主要問題和主要矛盾。 為了在不損失或盡可能 少損失圖像質量的前提下提高分形圖像壓縮的速度, 本文在基于分形理論的圖像壓縮算法基 礎上,通過結合多尺度分析和神經網絡的分形編碼方法,以降低圖像復雜度 1-3,利用 GSOFM 4充分發(fā)揮分形壓縮的高壓縮比性能和神經網絡的提高壓縮速度的性能,將分形中 遇到的某些近似相似的圖像塊歸類,

3、以少數有代表性的圖像小塊來代替與其相似的, 減少分 形中的總計算次數,從而減少分形壓縮的時間。在這個過程中,本文也使用了四叉樹 5和多 尺度逼近 6-7的方法, 降低圖像維數, 進一步減少計算負擔, 大大提高分形方法的壓縮速度。 在仿真實驗中,我們用這種方法與全搜索方法及其 Fisher 方法 8相比較,對比這三種方法的 壓縮圖像時間, 所得圖像的質量和壓縮比。 此方法在速度上應該比全搜索方法 5有大的飛躍, 比 Fisher 方法也各個方面也應有一定優(yōu)勢。2. 一種基于神經網絡的分形圖像壓縮的方法2.1神經網絡和塊圖像編碼自組織特征映射 SOFM(Selforganizing feature

4、 map9-11是一種無教師學習的神經網 絡,其中,不同的神經元通過無監(jiān)督學習 12過程匹配不同的輸入信號模式(pattern 或模式 的分類。 自組織過程可視為從高維輸入空間到低維空間的概率密度的映射, 該低維空間通常 是一維、二維或三維空間,相應于臨近模式的輸出節(jié)點是拓撲不變的。 SOFM 的目的是將輸 入數據按照其相似性進行分類。本文中使用 KKN 網和 SOFM 在編碼算法, 將圖像分割成相同尺寸的像素塊分別進行編 碼。對于 256×256像素大小的圖像,塊的大小通常為 4×4, 8×8, 16×16和 32×32。在 SOFM 圖像塊

5、編碼中,視每個塊為一個高維輸入模式(一個 8×8的塊屬于 R64,用 KNN 網的自 組織過程去映射各個圖像類。采用 GSOFM 的映射特性將目標圖像的圖像類映射到一個低維神經元矩陣。 因為輸入空 間(圖像塊的維數遠大于輸出空間(神經元空間的維數,用圖像塊的多尺度逼近來降低 向量空間的維數。自組織過程以后, KNN 網的神經元將會產生關聯(lián)的權向量,其作為圖像塊的逼近或類的代表。 在編碼過程中, 將圖像塊輸入到輸入層, 將具有最高響應的神經元在 輸出空間中的位置作為該塊的編碼。這個編碼與激活神經元的權向量結合,用于表示該塊。2.2 GSOFM的學習算法GSOFM 的訓練屬于無人監(jiān)督競爭

6、學習算法。Kohonen 神經網絡包含一個輸入層和一個通過權矩陣相聯(lián)系的輸出層,也叫 KNN 層。 這個輸出層是競爭的,且通常是一維、二維或三維陣列。這里實用二維 KNN 層應用于圖像 塊編碼算法。 圖 1 SOFM的二維網絡結構神經元 (和 是 KNN 網神經元的序列號可視為一個具有權矩陣 的簡易處 理器,通過它可以把相似的輸入神經元歸類。 輸入的圖像塊向量 (i 和 nm N m n nm w ij b j 為輸入神經元序 列號,即圖像塊編號并行輸入到所有神經元,并且每個神經元具有活躍因子:=Pk m,n i,j m,n k w k b u 12(1其中, P 是 的像素個數, k 為單個

7、輸入結點的分量。當 i,j b k w k b m,n i,j 最小, 也就是 和 距離最近時, u 有極大值,為活躍因子。k b i,j k w m,n m,n 一般學習算法如下:1 用隨機數初始化每個神經元的權值 w mn ,設置鄰域半徑為 NE (0,學習速率為 (0 (0<(0<1及總學習次數為 T2 將塊 映射到輸入層并獲得每個神經元的活躍因子 ,即有極大值i,j b m,n u 3 有極大活躍因子選擇勝出的神經元 j*4 定義輸入模式分量 , , 2, 1(n k b nmk L =,和權值 間的灰關系系數 nmk w nmk 為 maxmax min +=nmk nm

8、k其中, 為輸入塊的序列號, 為其分量, m n , k 10(是判別系數,通常取 =0.5,并且nmk k M m N n p k w b =, , 2, 1, , 2, 1, , 2, 1min min min min L L Lnmk k M m N n p k w b =, , 2, 1, , 2, 1, , 2, 1max max max max L L L nmk k nmk w b =5 更改勝出的神經元及其臨近神經元的權值如下:(*,(, , ( (, , 1, t NE j n m w b t w w t n m ij nmk t n m t nm 鄰域 +=+更新學習速率

9、(t及鄰域半徑為 NE (t , (t是隨次數 t 增加而減小的增益項, 它的值介 于 0和 1之間。/1( (0T t t =1(0(INTt/TNE NE(t=6 轉向 2, 繼續(xù)上述過程,直到 (t=0為止。2.3一種新的分形圖像編碼加速算法下面將闡述基于結合多尺度分析和 GSOFM 網絡的逼近算法,以縮減分形編碼的時間。 這種新算法可通過高效的圖像域分類算法來改善最佳匹配的速度,進而加速編碼過程。當采用四叉樹方法進行圖像分割時,可采用四種值域大小(例如 4×4, 8×8, 16×16,和 32×32,和定義域的大小(例如 8×8, 16

10、×16, 32×32和 64×64,這將導致一個高達 1024維的 KNN 輸入空間,從而引起計算和存儲問題。為了解決這個問題,用該塊的 2j (j=0, -2 -4, -6, -8 尺度上的離散逼近使其大小降低到 4×4。例如,對于 8×8的值域塊,我們采用該 塊在 1/4尺度下的離散逼近;相應地對 16×16的定義域塊,采用在 1/16尺度下的離散逼近, 等等。這里,假設 KNN 網的輸入空間是 R16。結合多尺度分析和 KNN 網的分形圖像編碼的具體算法如下:1 對原始圖像進行降采樣來獲得尺度 1/4 , 1/16, 1/64

11、和 1/256下的圖像。 大小為 (b x , b y 像素的塊在尺度 2j (j=0, -2 -4, -6, -8 下進行離散逼近,所獲得的圖像大小為 (2j b x , 2j b y 像素。這里最低尺度為 1/256.2 建立一個定義域池,用于訓練 KNN 網。注意,用于訓練 KNN 網的定義域池可從另 一個不同于將要編碼的圖像中獲得。 這樣只要通過學習得出分類權重, 便可以在不同圖像上 進行分類,不必對每一幅圖像分別進行學習。我們在尺度 2j (j=-2, -4, -6, -8 下使用大小為 4×4像素的圖像塊來訓練 KNN. 這個過程可總結如下:a 在尺度 2j (j=-2,

12、-4, -6, -8 下選擇每一個大小為 4×4像素的塊。 例如, 對于 256×256的圖像,在尺度 1/256下,塊的數目是(16-4+1 ×(16-4+1 .b 將每個塊 d i 進行規(guī)格化(min (max , ( , (' i i i i i d d d y x d y x d = (1 其中, i d 是定義域塊 d i 的平均像素值, max(d i 和 min(d i 分別是 d i 的最大和最小像素值。c 產生每個規(guī)格化塊 d i 的等距變換。定義域池中的塊可重復出現(xiàn)。3 用在定義域池(即從步驟 2中獲得的訓練集中的規(guī)格化向量建立 KNN

13、 網的碼本。 a 將 KNN 中的所有權值置成隨機數。b 從定義域池中提取向量并用于訓練 KNN 。c 重復 3中(b 步驟直到映射收斂。4 在編碼圖像的定義域池中的向量和 KNN 網中一個神經元間建立聯(lián)系。 每一個神經元 保持一個最接近于在他們權中存儲模式的關聯(lián)向量序列, 每一個向量由定義域塊和等距變換 操作指示產生。5 根據式 (1, 在較低尺度上通過活躍神經元 N kl , 在圖像的定義域塊和值域塊間建立聯(lián) 系。在這個尺度上,定義域塊和值域塊的大小為 4×4。a 在值域塊和關聯(lián)到活躍神經元 Nkl 的類中的塊之間搜索最佳匹配 (滿足誤差限 E 。 如果類中的一個塊匹配上了, 則

14、在較高尺度上, 采用相同的等距變換搜索這個塊, 和它的右 鄰塊、下邊鄰塊和右下方鄰塊(位置關系表明相鄰的塊具有相似的特性。重復本步驟直到 尺度 1。b 如果沒有滿足誤差限 E 的匹配, 我們可搜索臨近神經元 1(±=k m N mn ,關 聯(lián)的類。1±=l n c 如果在臨近神經元 N mn 關聯(lián)的類中也沒有滿足誤差限 E 的匹配,該值域塊將被分解 成四個更小的同大小的塊(采用四叉樹分割,并對每個塊進行編碼(重復步驟 4和 5。d 如果找到達到最小品質標準要求的匹配,我們可對該塊進行編碼。e 重復 5(a到 5(d步驟,直到所有的塊都編碼為止。通過以上步驟,我們便完成了對數

15、字圖像壓縮的加速。應用這種方法,理論上是可以 在分形中減少尋找匹配塊的次數,提高分形壓縮的速度。我們在下面章節(jié)中將給出具體仿 真試驗的結果,來證明此方法的有效性。3. 基于 GSOFM 分形編碼方法仿真實驗測試中采用大小為 8位 256×256像素的 LENNA 灰度圖像。 從多個方面將該算法與無遺 漏最佳匹配搜索方法(全搜索法和 FISHER 方法進行比較:編碼時間,壓縮倍數和圖像質 量(PSNR 。在本文提出的方法中,可使用四種值域塊大小 (4 × 4, 8 × 8, 16× 16及 32 ×32 , 定義域塊大小可采用 ( 8×

16、8, 16×16, 32×3及 64×64。 編碼實現(xiàn)在 2000 MHz 的 Pentium 4處理器上進行。 KNN 的輸入空間是 R16.PSNR 是兩個大小為 m×n的圖像 f 和 g 之間的失 真程度的度量,定義如下:×=MSE PSNR 225510log10 (2式中, n m j i g j i f MSE n j m i ×=10102, ( , (壓縮倍數:壓縮后圖像數據大小 /原始圖像數據大小。在對圖像存儲時,要對編碼信息進行量化后再存儲,這樣可以減小文件的存儲空間。 量化時,對于一個值域塊的編碼信息中的匹配塊位

17、置坐標(x , y 使用 8位,對比度 使用 5s位,亮度 o 使用 6位進行存儲, 3位存儲旋轉變換種類, 2位存儲層次信息。如果一個圖像 在編碼后值域塊的編碼信息的數目為 ,則它所在的存儲空間為:n8/ 236582(+××n 字節(jié)3.1 與無遺漏最佳匹配搜索方法的進行比較與無遺漏最佳匹配搜索方法對比結果如表 3-1所示。實驗結果表明,本文提出的 方法可在很大程度上提高圖像壓縮速度,加速效果十分明顯。表 3-1 比對表圖像 方法 PSNR 時間(秒 壓縮倍數全搜索方法 35.26 8600 8.16Lenna本文方法 35.10 17 8.07在圖 3-1(a和 3-1(b中,我們可以清楚的看出按照本文算法壓縮后的圖像與原始圖像的 對比,效果還是可以讓人滿意的。 圖 3-1(a 本文方法壓縮的 Lenna 圖像 圖 3-1(b 原始的 Lenna 圖像3.2 與 fisher 方法進行