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

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

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

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

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

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

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

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

8、k其中, 為輸入塊的序列號(hào), 為其分量, m n , k 10(是判別系數(shù),通常取 =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 更改勝出的神經(jīng)元及其臨近神經(jīng)元的權(quán)值如下:(*,(, , ( (, , 1, t NE j n m w b t w w t n m ij nmk t n m t nm 鄰域 +=+更新學(xué)習(xí)速率

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

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

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

12、-4, -6, -8 下選擇每一個(gè)大小為 4×4像素的塊。 例如, 對(duì)于 256×256的圖像,在尺度 1/256下,塊的數(shù)目是(16-4+1 ×(16-4+1 .b 將每個(gè)塊 d i 進(jìn)行規(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 產(chǎn)生每個(gè)規(guī)格化塊 d i 的等距變換。定義域池中的塊可重復(fù)出現(xiàn)。3 用在定義域池(即從步驟 2中獲得的訓(xùn)練集中的規(guī)格化向量建立 KNN

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

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

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

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

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