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

楊蒙蒙，張愛(ài)華

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

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

0 引言

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

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

1 基本分形編碼算法

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

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

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

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

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

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

2.1 特征提取和圖像塊檢索

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

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

2）熵（Entropy，Ent）。

3）對(duì)比度（Contrast，Con）。

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

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

2.2 SOMP稀疏分解思想

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

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

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

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

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

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

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

2.3.1 確定過(guò)完備虛擬碼本

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

2.3.2 正交化分形編碼

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

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

2.3.3 稀疏灰度匹配

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

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

2.4 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 稀疏度L和編碼時(shí)間關(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 為幾種算法編碼的解碼圖像對(duì)比。與BFIC 算法、改進(jìn)叉跡分形算法以及雙交叉和特征算法相比，從Lena放大的局部圖像來(lái)看，前三種算法的重構(gòu)圖像都出現(xiàn)了明顯的塊效應(yīng)，而在Goldhill 解碼圖像中，這三種算法在關(guān)于天空的細(xì)節(jié)上也有缺陷，本該灰色天空的地方出現(xiàn)了泛白的跡象，本文算法在視覺(jué)效果上幾乎與原圖沒(méi)有差別，獲得了高質(zhì)量重建圖像的同時(shí)編碼速度也得到了較大的提升。根據(jù)表1 可知，實(shí)驗(yàn)數(shù)據(jù)變化最大的是圖像Peppers，在雙交叉和特征算法中，PSNR 僅為9.33，在本文算法中，獲得了較好編碼質(zhì)量的同時(shí)編碼時(shí)間也大大縮短，雖然和SFIC 算法相比，圖像Lena 和Goldhill 的PSNR 稍低了一點(diǎn)，但在保證一定圖像質(zhì)量和結(jié)構(gòu)相似度（SSIM）的前提下，編碼耗時(shí)縮短了至少89%。

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

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

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

圖7 測(cè)試圖像在不同算法下的編碼時(shí)間對(duì)比Fig.7 Comparison of encoding time of test images under different algorithms

4 結(jié)語(yǔ)

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

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