基于灰度共生矩陣和同步正交匹配追蹤的分形圖像壓縮

楊蒙蒙，張愛華

（南京郵電大學(xué)理學(xué)院，南京 210023）

（*通信作者電子郵箱zhangah@njupt.edu.cn）

0 引言

隨著多媒體信息以及計算機(jī)工業(yè)技術(shù)的高速發(fā)展，分形圖像壓縮編碼算法作為一種與時俱進(jìn)、功能強(qiáng)大的圖像壓縮技術(shù)，利用圖像內(nèi)部的自相似性以及各個區(qū)域之間可以相互表達(dá)的特性，成為有損壓縮圖像技術(shù)的代表。它由Barnsley［1］于1988 年提出最初的思想，Jacquin［2］在原有的基礎(chǔ)上進(jìn)行改進(jìn)從而發(fā)展起來，基于分形的圖像壓縮編碼其壓縮方法簡單，可在任意尺度下重構(gòu)且壓縮比高具有獨(dú)特優(yōu)勢，但是與傳統(tǒng)的圖像編碼技術(shù)相比，在灰度匹配過程中由于需要大量的相似性計算，因此非常耗時［3］。在過去的時間里，為了降低計算成本，研究者們進(jìn)行了許多有效的研究［4-21］，從空間關(guān)系［4-6］的角度出發(fā)、采用鄰域方法、縮小匹配圖像塊大部分相鄰的搜索空間。從平面擬合的角度出發(fā)，Lu 等［7］提出了一種新的基于Huber 擬合平面魯棒分形圖像編碼，與Shen 等［8］的無搜索方法相比，在穩(wěn)健回歸模型中建立新的灰度匹配，引入一種新的匹配誤差函數(shù)，降低了計算量；對于典型的優(yōu)化算法，Wang等［9］提出了一種將粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法和混合四叉樹劃分相結(jié)合的分形圖像編碼算法，采用基于范圍塊分類的PSO 搜索策略，在縮短編碼時間的同時改善了重建圖像質(zhì)量。從參數(shù)變換和相關(guān)系數(shù)出發(fā)，利用相鄰像素間的相關(guān)性，將問題由圖像域轉(zhuǎn)換到向量域，降低了合適域搜索的復(fù)雜性［10-12］，例如Maydaniuk 等［12］提出了一種基于二維線性近似系數(shù)表示范圍塊和域塊的方法，允許每個范圍塊通過三個近似系數(shù)對塊進(jìn)行快速預(yù)選來縮短編碼時間。此外，基于特征向量法，何傳江等［13］提出的改進(jìn)分形叉跡算法以及張璟等［14］提出的雙交叉和特征算法都在一定程度上縮短了編碼時間。

為了更進(jìn)一步平衡編碼時間和圖像重構(gòu)質(zhì)量的關(guān)系，本文將提取圖像的灰度共生矩陣作為特征向量，進(jìn)行相似性計算來縮減碼本，通過灰度稀疏匹配追蹤變換和特征提取之間建立密切的關(guān)系，獲得了更好的解碼質(zhì)量和更快的編碼速度。

1 基本分形編碼算法

在分形壓縮編碼算法中，原始圖像被劃分成大小為r×r的不重疊范圍塊Ri(i=1，2，…，N)，以及可以重疊且大小為d×d的域塊Dj(j=1，2，…，M)，其中，域塊的大小一般取范圍塊大小的兩倍，即d=2r。在編碼過程中，通過空間壓縮［2］將定義域塊D的大小降至范圍塊R的相同大?。?5］，所有收縮后的D塊經(jīng)過8 個等距變換后形成虛擬碼本，因此變換后的域塊D和范圍塊R之間的灰度變換可以表示為：

同時在編碼過程中，為了尋求R塊的最佳匹配塊，需滿足匹配誤差最?。?］，即：

其中：‖‖· 表示l2范數(shù)，I是亮度值均為1 的常值塊，s和o分別起調(diào)整Dj的對比度和亮度的作用，通過最小二乘法求解式（2），得到最小平方問題的解：

R、、D和分別表示為圖像塊R和D的像素灰度值用某種掃描方式所構(gòu)成的向量及其均值。經(jīng)過上述求解后，得到R的分形碼，即域塊D的位置、等距變換t、對比度參數(shù)s和亮度偏移參數(shù)o。詳細(xì)的塊匹配過程如圖1 所示，全體R塊分形碼構(gòu)成了原始圖像的分形碼，描述了一個使原圖像近似不變的壓縮變換；解碼過程是一個相對簡單的迭代過程，基于壓縮不動點(diǎn)定理和分形編碼，解碼過程從任意圖像開始，最后，迭代吸引子［2］便是原始圖像的一個近似圖像。

圖1 范圍塊和域塊之間的收縮仿射變換過程Fig.1 Process of compressive affine transformation between range block and domain block

2 基于灰度共生矩陣的正交化稀疏編碼

2.1 特征提取和圖像塊檢索

灰度共生矩陣是1973年由Haralick等［16］提出的一種通過研究灰度的空間相關(guān)特性來描述紋理的常用方法。作為一種成熟的統(tǒng)計圖像分析方法，灰度共生矩陣［17］具有較強(qiáng)的適應(yīng)性與魯棒性，且方法簡單，在統(tǒng)計分析領(lǐng)域應(yīng)用較廣。通過計算灰度圖像得到它的共生矩陣，然后通過計算該共生矩陣得到矩陣的部分特征值來分別代表圖像的某些紋理特征［18］。在本文中，使用對比度、能量、熵、相關(guān)性4 個特征來進(jìn)行圖像塊的檢索，公式如下：

1）能量（Angular second moment，Asm）。

2）熵（Entropy，Ent）。

3）對比度（Contrast，Con）。

4）相關(guān)性（Correlation，Corr）。

分別對R塊和D塊提取以上4 個特征，為了方便計算，本文將能量、熵、對比度和相關(guān)性的均值作為最終的紋理特征，且均值特征向量使用T=[T1T2T3T4]來表示，對于每個R塊和所有D塊之間的相似性匹配d(TRi，TDj)，根據(jù)實(shí)驗(yàn)效果采用切比雪夫距離進(jìn)行衡量，即dist(Ri，Dj)=，當(dāng)檢索碼本中的D塊時，較短的距離表示紋理相似度較高，d(TR，TD)之間的距離越小，則證明R塊和D塊越匹配，因此將R塊和所有D塊之間的切比雪夫距離由小及大排序，得到關(guān)于塊R的相似度量矩陣Δ(Ri，Dj)=這種方法可以快速提取圖像塊之間的相似度信息，降低計算的復(fù)雜度，在改善重建圖像質(zhì)量的基礎(chǔ)上加快編碼速度。

2.2 SOMP稀疏分解思想

基于正交匹配追蹤（Orthogonal Matching Pursuit，OMP）算法，同步正交匹配追蹤（Simultaneous Orthogonal Matching Pursuit，SOMP）算法［19］同樣也是一種貪婪追蹤類算法，顧名思義，SOMP 能夠同時進(jìn)行稀疏逼近。一般來說，信號在其稀疏域越稀疏，其信號重建就越準(zhǔn)確，對于圖像而言，本身具有較復(fù)雜的特征，由此學(xué)者們提出了使用超完備冗余字典［20］來對信號進(jìn)行稀疏表示。

從理論上講，字典Q中的每一列是一個訓(xùn)練樣本，測試樣本x∈Rd為一個列向量，它們的關(guān)系表達(dá)如下：

其中Si∈Rn為qi的表示系數(shù)，方便敘述，式（10）簡化為：

其中矩陣Q=[q1，q2，…，qn] ∈Rd×n是一個基矩陣，但式（11）是欠定線性組，因此它的解答可以等價為求解l1范數(shù)的稀疏最優(yōu)解過程，如下：

在保證重構(gòu)精度的前提下，求解出盡量稀疏的系數(shù)矩陣S。

2.3 正交化稀疏灰度匹配變換

在基本分形編碼過程中，范圍塊R作為待編碼的塊，域塊D作為碼字。對于每個范圍塊，在域池中搜索匹配一對一的域塊。通過實(shí)驗(yàn)發(fā)現(xiàn)對于一些結(jié)構(gòu)相似度低的圖像，如果圖像的域塊不能很好地逼近距離塊，這種方法不僅耗時而且重構(gòu)圖像質(zhì)量較低［21］，無法滿足實(shí)際需求。在本文中，為了使R塊盡可能匹配更多的域塊D，此次將SOMP算法應(yīng)用到塊的匹配過程，通過生成相應(yīng)的稀疏系數(shù)矩陣S，實(shí)現(xiàn)了一個范圍塊和多個域塊之間的匹配關(guān)系。

2.3.1 確定過完備虛擬碼本

作為一個虛擬碼本，域池中通常包含大量的域塊，這些塊D={dj}Ω可以作為稀疏編碼的過完備基集，做規(guī)范化處理后，R塊和D塊的匹配過程是在域池中為每個R塊搜索相應(yīng)的基，因此可以直接將稀疏編碼的搜索策略應(yīng)用到分形中［22］。

2.3.2 正交化分形編碼

由BFIC（Baseline Fractal Image Compression）的具體流程可知，對比度參數(shù)s和亮度偏移參數(shù)o的值依賴于塊Di，相關(guān)的編碼參數(shù)在具體的迭代過程會發(fā)生變化，這種變化帶來的不確定性不利于分形編碼參數(shù)進(jìn)行塊與塊之間的匹配，本文采用正交分形編碼算法［23］保證參數(shù)在迭代過程的穩(wěn)定性。因此由=0，則有：

由于從D塊到R塊的仿射變換是由參數(shù)s和Rˉ決定的，因此這兩種參數(shù)的聯(lián)合統(tǒng)計特征能有效表征仿射變換的統(tǒng)計特征［24］。

2.3.3 稀疏灰度匹配

基于構(gòu)造的過完備虛擬碼本，由稀疏分解的思想，所謂的匹配即為求解相應(yīng)的稀疏系數(shù)矩陣的過程，假設(shè)為每個R塊匹配域池中的k個塊Di(i=1，2，…，k)，每個域塊的線性系數(shù)分別為s1，s2，…，sk，根據(jù)稀疏分解，定義一種新的灰度變換為：

其中：R和為圖像塊R的像素值和均值，si(i=1，2，…，k)為對比度參數(shù)，且，根據(jù)上述灰度變換，在對每一個塊R編碼的情況下，由式（13）表示的結(jié)構(gòu)存儲分形碼表示如下：

2.4 算法描述

基于以上分析，算法具體實(shí)現(xiàn)步驟如下。

1）圖像分割。將大小為N×N的原始圖像μorg分割成互不重疊的大小為8× 8 的R塊集合，以縱橫方向步長δ=8 生成可重疊且大小為16 × 16的D塊集合。

2）特征提取。分別對R塊和等距變換后的D塊進(jìn)行灰度共生矩陣的紋理特征提取。

3）碼本構(gòu)成。根據(jù)提出的相似性度量矩陣，計算同等條件下R塊和D塊的切比雪夫距離，由小及大排序記為Δ(R，D)。

4）虛擬碼本。取前M個距離較小的D塊，進(jìn)行規(guī)范化處理后引入8種等距變換，構(gòu)成縮減后的過完備虛擬碼本

5）使用SOMP正交化分形算法灰度匹配：

3 實(shí)驗(yàn)結(jié)果及分析

為了測試本文算法的有效性，選取了5幅大小為512像素×512 像素的標(biāo)準(zhǔn)灰度圖像進(jìn)行實(shí)驗(yàn)，分別為Lena、Elain、Peppers、Goldhill 以及Zelda，硬件平臺為Window 10 和CPU Ryzen5-2500操作系統(tǒng)的計算機(jī)，所有方法均在Matlab2018a環(huán)境中實(shí)現(xiàn)，對比參數(shù)為編碼時間、峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）和結(jié)構(gòu)相似度（Structural SIMilarity，SSIM）。

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

在本文算法中，編碼時間和圖像重構(gòu)質(zhì)量依賴于兩個控制參數(shù)：稀疏度L和所提取的特征數(shù)量M，由2.1 節(jié)的分析可知，M的大小決定了過完備虛擬碼本的大小，M值越大，匹配塊的空間大，圖像重建質(zhì)量較好，但也伴隨著一定數(shù)量的數(shù)據(jù)冗余，因此，設(shè)置合理的碼本數(shù)量對編碼的質(zhì)量和速度至關(guān)重要，如圖2～3 所示，當(dāng)M的值為250 時，PSNR 的增長趨于平緩且編碼時間急劇增長，因此M的取值范圍控制在M∈（0，250）比較合適，經(jīng)過實(shí)驗(yàn)對比分析，在保持實(shí)驗(yàn)效果和時間平衡關(guān)系的前提下，本文取M=250。

圖2 特征數(shù)量M和PSNR關(guān)系Fig.2 Relationship between the number of features M and PSNR

圖3 特征數(shù)量M和編碼時間的關(guān)系Fig.3 Relationship between the number of features M and encoding time

稀疏度L作用于迭代過程的終止以及相應(yīng)的重建效果，如圖4 和圖5 所示，L值越大，圖像的PSNR 越高，但同時也伴隨著較長的編碼時間。當(dāng)L在8～10 時，曲線增長較為平緩且PSNR 也在可接受范圍內(nèi)，綜合考慮這兩個因素，根據(jù)算法的時效性，本文中稀疏度L取9比較合適。

圖4 稀疏度L和PSNR關(guān)系Fig.4 Relationship between sparsity L and PSNR

圖5 稀疏度L和編碼時間關(guān)系Fig.5 Relationship between sparsity L and encoding time

3.2 實(shí)驗(yàn)結(jié)果與分析

本文選取基本分形算法（BFIC）、改進(jìn)分形編碼的叉跡算法［13］、雙交叉和特征算法［14］和稀疏分形圖像壓縮（Sparse Fractal Image Compression，SFIC）算法［22］與本文算法進(jìn)行比較，為了保證算法的公平性，取相同尺度參數(shù)，重構(gòu)誤差閾值設(shè)置為20，圖6 為幾種算法編碼的解碼圖像對比。與BFIC 算法、改進(jìn)叉跡分形算法以及雙交叉和特征算法相比，從Lena放大的局部圖像來看，前三種算法的重構(gòu)圖像都出現(xiàn)了明顯的塊效應(yīng)，而在Goldhill 解碼圖像中，這三種算法在關(guān)于天空的細(xì)節(jié)上也有缺陷，本該灰色天空的地方出現(xiàn)了泛白的跡象，本文算法在視覺效果上幾乎與原圖沒有差別，獲得了高質(zhì)量重建圖像的同時編碼速度也得到了較大的提升。根據(jù)表1 可知，實(shí)驗(yàn)數(shù)據(jù)變化最大的是圖像Peppers，在雙交叉和特征算法中，PSNR 僅為9.33，在本文算法中，獲得了較好編碼質(zhì)量的同時編碼時間也大大縮短，雖然和SFIC 算法相比，圖像Lena 和Goldhill 的PSNR 稍低了一點(diǎn)，但在保證一定圖像質(zhì)量和結(jié)構(gòu)相似度（SSIM）的前提下，編碼耗時縮短了至少89%。

圖6 不同算法的解碼效果Fig.6 Imag decoding effects of different algorithms

表1 測試圖像在不同算法下的性能Tab.1 Test image performance under different algorithms

圖7 進(jìn)一步表明本文算法在編碼效率上的優(yōu)化，因此綜合比較得知，本文的算法可以獲得較好的重建質(zhì)量同時保持更快的編碼速度，較相應(yīng)的對比算法更有效。

圖7 測試圖像在不同算法下的編碼時間對比Fig.7 Comparison of encoding time of test images under different algorithms

4 結(jié)語

針對傳統(tǒng)分形圖像壓縮中存在的計算復(fù)雜度高問題，本文提出了一種基于灰度共生矩陣紋理特征的正交化分形編碼算法，將相似性度量矩陣關(guān)于圖像檢索的概念引入分形圖像壓縮，有效減少了搜索空間，和SOMP 算法相結(jié)合的灰度匹配更是提高了重建的圖像質(zhì)量，編碼速度也得到了較好的提升，通過實(shí)驗(yàn)證明了本文算法的有效性。

圖像壓縮編碼作為人工智能時代通信技術(shù)的一個重要應(yīng)用，減少圖像數(shù)據(jù)中的冗余信息，使用更加高效的格式存儲以及傳輸數(shù)據(jù)是十分必要的。本文算法在時間效能上還有待提高，因此接下來將嘗試使用智能優(yōu)化的算法來加快圖像塊之間的匹配搜索，從而把構(gòu)造效果更佳的混和編碼算法作為接下來的重點(diǎn)研究方向。