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

楊蒙蒙，張愛華

（南京郵電大學理學院，南京 210023）

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

0 引言

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

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

1 基本分形編碼算法

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

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

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

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

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

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

2.1 特征提取和圖像塊檢索

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

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

2）熵（Entropy，Ent）。

3）對比度（Contrast，Con）。

4）相關性（Correlation，Corr）。

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

2.2 SOMP稀疏分解思想

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

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

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

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

在保證重構精度的前提下，求解出盡量稀疏的系數矩陣S。

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

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

2.3.1 確定過完備虛擬碼本

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

2.3.2 正交化分形編碼

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

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

2.3.3 稀疏灰度匹配

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

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

2.4 算法描述

基于以上分析，算法具體實現步驟如下。

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

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

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

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

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

3 實驗結果及分析

為了測試本文算法的有效性，選取了5幅大小為512像素×512 像素的標準灰度圖像進行實驗，分別為Lena、Elain、Peppers、Goldhill 以及Zelda，硬件平臺為Window 10 和CPU Ryzen5-2500操作系統的計算機，所有方法均在Matlab2018a環境中實現，對比參數為編碼時間、峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）和結構相似度（Structural SIMilarity，SSIM）。

3.1 實驗參數設置

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

圖2 特征數量M和PSNR關系Fig.2 Relationship between the number of features M and PSNR

圖3 特征數量M和編碼時間的關系Fig.3 Relationship between the number of features M and encoding time

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

圖4 稀疏度L和PSNR關系Fig.4 Relationship between sparsity L and PSNR

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

3.2 實驗結果與分析

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

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

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

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

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

4 結語

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

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