李高平

(西南民族大學(xué)數(shù)學(xué)學(xué)院，四川成都 610041)

圖像作為蘊(yùn)涵信息量最大的媒體，它占有的海量數(shù)據(jù)量給圖像數(shù)據(jù)的儲存與傳輸帶來極大困難，成為圖像技術(shù)應(yīng)用的瓶頸.如何高效、實(shí)時地壓縮圖像，以較少的空間儲存大量圖像是解決數(shù)據(jù)有效儲存與傳輸?shù)年P(guān)鍵問題，是信息化社會所依賴的主要技術(shù)基礎(chǔ)之一.

分形圖像編碼作為一種全新的圖像編碼方法，對信源的先驗(yàn)知識要求極少，更多地利用圖像的自相似性及比例特性.它雖然具有壓縮原理新穎、高壓縮比、解碼效果好、抗干擾能力強(qiáng)等優(yōu)點(diǎn)，但它與主流采用的編碼方法相比還沒有明顯優(yōu)勢，是一種編碼過程特別耗時而其解碼過程快的不對稱編碼技術(shù).目前很多研究工作都是以 Jacquin 提出的分形塊編碼為基礎(chǔ)[1]，在基本理論、編碼方案改進(jìn)、應(yīng)用擴(kuò)展等方面進(jìn)行探索[2-9].

壓縮感知是將壓縮和采樣兩個過程一并進(jìn)行的，若信號在某一個正交空間具有稀疏性，就能在原始信號投影到更低維信號空間時，以遠(yuǎn)低于奈奎斯特采樣頻率來采樣該信號，并可能以高概率重建該信號，但它存在圖像尺寸太大時，因計(jì)算量大而實(shí)時性差的問題.壓縮感知的關(guān)鍵要素包括稀疏表示方法[10-11]、測量矩陣的選擇[12-14]和重構(gòu)算法的設(shè)計(jì)[15-17].

盡管分形圖像編碼、圖像壓縮感等新一代編碼技術(shù)有各自公認(rèn)的顯著優(yōu)點(diǎn)，但純粹基于分形理論的編碼方法存在編碼時間長、實(shí)時性差的問題.同樣，純粹基于圖像壓縮感知理論的編碼方法存在圖像重建時耗時很長，與目前廣泛使用的編碼方法相比，還缺乏競爭力，離完全實(shí)用還有相當(dāng)距離.因此，本文將分形圖像編碼與圖像壓縮感知兩種編碼方法結(jié)合起來，揚(yáng)二者之長，避二者之短(即分形法是編碼過程長、解碼過程快，壓縮感知恰好相反)，研究性能更優(yōu)的混合編碼算法，以全搜索分形圖像編碼算法為基本框架，融入壓縮感知圖像編碼算法中的觀測矩陣.首先將原始圖像分成大小相等的圖像子塊，對每個圖像子塊采用高斯隨機(jī)矩陣來采樣它的觀測值，然后求出其均值與標(biāo)準(zhǔn)差，據(jù)此定義每個子塊的均標(biāo)積特征值，最后在編碼階段的值域R 塊與碼書D 塊的匹配過程中，以該特征值為依據(jù)設(shè)置剔除條件，搜索最佳匹配D 塊的范圍遠(yuǎn)小于全局搜索范圍. 實(shí)驗(yàn)結(jié)果表明，本文提出的混合編碼算法與全搜索分形算法、壓縮感知編碼算法相比，以PSNR 度量的重建圖像質(zhì)量分別降低約0.8 dB、2.58 dB 的情況下，編碼時間平均分別減少了90 %、80 %以上，其主觀質(zhì)量評價指標(biāo)SSIM 值幾乎無變化.

1 分形與壓縮感知結(jié)合的圖像編碼算法

1.1 基本分形圖像編碼流程圖

基本分形圖像編碼[1]過程流程圖如圖1 所示.

圖1 基本分形圖像編碼過程流程圖Fig.1 The basic fractal image coding process flow chart

1.2 壓縮感知圖像編碼流程圖

壓縮感知圖像編碼方法流程圖如圖2 所示.

圖2 壓縮感知圖像編碼流程圖Fig.2 The flow chart of compressive sensing image encoding

1.3 分形與壓縮感知相結(jié)合的圖像編碼算法流程圖

將分形與壓縮感知相結(jié)合的圖像編碼算法流程圖如圖3 所示.

圖3 分形與壓縮感知結(jié)合的圖像編碼算法流程圖Fig.3 The flow chart of image coding algorithm combining fractal andcompressive sensing

具體步驟為:

Step1:將原始圖像分割成n×n大小的待編碼Range 塊，以及 2n×2n大小的 domain 塊(收縮成n×n大小后，用作碼書Ω 中的子塊)；

Step2:用設(shè)計(jì)的觀測矩陣采樣待編碼Range 塊與碼書Ω 中每個子塊的測量值；

Step3:根據(jù)測量值定義待編碼Range 塊與碼書Ω中每個子塊的均標(biāo)積特征值，并將碼書Ω 中的子塊按其特征值進(jìn)行升序排列；

Step4:對每個待編碼Range 塊，用二分法在碼書Ω 中找到與其均標(biāo)積特征值最接近的子塊，按照剔除條件尋找其最佳匹配塊，并記錄它的分形碼；

Step5:按照Step4 找出的所有待編碼Range 塊的分形碼的集合，就構(gòu)成了原始圖像的分形碼. 重建圖像時，就用該分形碼按照分形編碼的解碼迭代算法來生成.

1.4 算法的理論基礎(chǔ)

本文中測量矩陣Ф 選取的是高斯隨機(jī)矩陣，在依據(jù)子塊測量值定義子塊的特征值時，既要消除對比度因子的影響，又要滿足特征提取簡單可行，且具有代表性.否則，在鄰域內(nèi)找到的局部匹配塊就不是全局匹配塊，導(dǎo)致用局部匹配塊代替全局最優(yōu)匹配塊的數(shù)量太多，造成解碼圖像質(zhì)量下降很大.

式中μ(Y)為圖像子塊X的測量值Y的均值，σ(Y)為圖像子塊X的測量值Y的標(biāo)準(zhǔn)差.

在自仿射變換下，討論R 塊與碼書中D 塊的均標(biāo)積特征滿足什么條件，才有可能成為最優(yōu)匹配塊對.找尋每個待編碼R 塊的最優(yōu)匹配塊時，通過遍歷碼書Ω 來得到自仿射變換w下均方根誤差最小的D塊作為最優(yōu)匹配塊.鑒于均標(biāo)積特征在自仿射變換w下具有不變性，所以，應(yīng)有下式成立:

從上式可以看出，D 塊能成為R 塊的最佳匹配塊，在均標(biāo)積特征意義下，也應(yīng)該是近鄰.

1.5 快速編碼算法方案

圖像分割出的待編碼R 塊數(shù)量、碼書Ω 容量以及搜索最佳匹配塊的方式這三個關(guān)鍵因素是設(shè)計(jì)快速編碼過程方案時需要重點(diǎn)考慮的.前面2 個因素由分割圖像方案決定，在此只討論何種搜索方式才能在碼書Ω 中快速找到待編碼R 塊的最佳匹配D 塊，依據(jù)上式(2)可知，R 塊和D 塊能組成匹配對，要求D塊的T(D)值應(yīng)該與R 塊的T(R)值接近，也就是說在均標(biāo)積特征意義下，R 塊的最優(yōu)匹配Dm塊應(yīng)位于那些D 塊均標(biāo)積特征值與R 塊均標(biāo)積特征值比較接近的D 塊子集中.所以，在設(shè)計(jì)搜索方案時，首先按照碼書Ω 中的全體D 塊的均標(biāo)積特征值進(jìn)行升序排列，即T(Di)≤T(Di＋1)，然后，在升序碼書 Ω 中采用二分法搜索與編碼R 塊均標(biāo)積特征值T(R)相差最小的初始匹配塊D 塊:

如果記R 塊與初始匹配塊Dinit間的誤差Einit為

為常數(shù).

按照上述建立的剔除條件，在碼書Ω 中搜尋與R塊匹配誤差滿足式(3)所對應(yīng)的D 塊后，記錄其位置序號m、自仿射變換中的量化參數(shù)及等距變換的序號t，它們就構(gòu)成該R 塊的分形碼. 待編碼圖像的所有R 塊的分形碼集合就構(gòu)成了該幅圖像的分形碼.

2 仿真實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)的測試對象為4 幅復(fù)雜性各異的圖像Lena、Boat、Peppers 和 polar bear(512 × 512，8bit 量化)，采用固定方塊分割圖像，R 塊、D 塊大小分別為8 ×8、16 ×16，碼書步長為 8. 此時，待編碼 R 塊總數(shù)量為4 096，碼書Ω 的容量為3 969，采樣率p=0.5，仿真實(shí)驗(yàn)平臺為PC 機(jī) (Intel(R) Core(TM) i5-8500 CPU ＠3.00 GHz 3.00 GHz).

2.1 均標(biāo)積特征的有效性驗(yàn)證

本文依據(jù)圖像子塊測量值定義的均標(biāo)積特征，是否刻畫了圖像子塊中的自相似性，下面通過仿真實(shí)驗(yàn)測出編碼R 塊在全搜索中得到的最優(yōu)匹配D 塊，與在均標(biāo)積特征意義下按照剔除條件得到的匹配D 塊，其距離表明了均標(biāo)積特征的有效性.

表1 中數(shù)據(jù)表明，4 幅測試圖像在均標(biāo)積特征意義下所做的鄰域搜索得到的匹配塊的位置與全搜索中得到的最優(yōu)匹配塊所在位置完全一樣的比例平均為8.5 %、相距10 的比例平均為17.6 %、相距50 的比例平均為87.2 %.這說明在均標(biāo)積特征意義下，大多數(shù)的待編碼R 塊的最優(yōu)匹配塊就在較小鄰域半徑的鄰域內(nèi)，驗(yàn)證了它的有效性.

表1 鄰域搜索得到的匹配塊距離最優(yōu)匹配塊的距離統(tǒng)計(jì)Table 1 The distance statistics of the optimal matching block vs.the matching block by neighborhood search

2.2 混合編碼算法的有效性驗(yàn)證

為了驗(yàn)證分形與壓縮感知相結(jié)合的圖像混合編碼算法的有效性，選編碼時間(秒)、峰值信噪比PSNR(dB)和結(jié)構(gòu)相似性SSIM(structural similarity)為測試性能參數(shù)來做仿真對比實(shí)驗(yàn).本文算法(p=0.5，觀測矩陣采用高斯隨機(jī)矩陣)與基本分形編碼算法的對比實(shí)驗(yàn)結(jié)果見表2.

表2 本文算法與基本分形算法對比結(jié)果Table 2 The comparison between the proposed algorithm and the basic fractal algorithm

從表2 數(shù)據(jù)可知，本文所提混合算法加快編碼過程的速度是相當(dāng)明顯的，若降低重建圖像質(zhì)量約0.8 dB，則編碼過程平均耗時僅為基本分形算法所需時間的9.36 %左右.若考慮到人眼的視覺特性，采用衡量兩幅圖像相似度的SSIM 指標(biāo)來評價圖像感知質(zhì)量，該指標(biāo)值僅平均下降約0.002 1，表明本文算法的重建圖像的主觀質(zhì)量幾乎無變化，但編碼時間比基本分形算法平均減少了90 %以上.

本文算法與壓縮感知圖像編碼算法(圖像分塊大小為16 ×16，p=0.5，稀疏矩陣采用離散余弦變換矩陣，觀測矩陣采用高斯隨機(jī)矩陣，重構(gòu)算法采用正交匹配追蹤算法)的對比實(shí)驗(yàn)結(jié)果列于表3.

表3 本文算法與壓縮感知圖像編碼算法對比結(jié)果Table 3 The comparison between the proposed algorithm and the compressive sensing image encoding algorithm

同樣從表3 數(shù)據(jù)可以看出，對所給4 幅測試對象，本文所提算法與壓縮感知圖像編碼算法從時間指標(biāo)上看，提速效果也是相當(dāng)明顯的，在重建圖像質(zhì)量降低約2.58 dB 的情況下，編碼過程耗時僅為全搜索算法所需時間的19.83 %左右，且它們的主觀質(zhì)量指標(biāo)SSIM 值平均增加約0.002. 這充分說明本文所提混合編碼算法的重建圖像在主觀質(zhì)量不降低的情況下，編碼時間平均減少了80 %以上.

仿真實(shí)驗(yàn)所用的4 幅測試圖像在基本分形算法、壓縮感知圖像編碼算法與本文所提出的分形與傳感壓縮相結(jié)合的圖像混合編碼算法的重建圖像分列于 下圖4，從主觀質(zhì)量上看幾乎無差別.

圖4 三種圖像編碼算法的重建圖像對比Fig.4 Thereconstruction image comparison of three image coding algorithms

3 結(jié)論

把壓縮感知理論中的測量矩陣引入到分形圖像編碼算法中，提取圖像子塊的有效信息，去除冗余信息還是有效的.在編碼過程中，依據(jù)圖像子塊測量值定義的均標(biāo)積特征來設(shè)置剔除條件，把與R 塊不太可能組成匹配對的D 塊排除，就把消費(fèi)時間最多的R塊與碼書Ω 中D 塊的匹配全搜索過程轉(zhuǎn)化為鄰域搜索過程，搜索范圍大大降低，節(jié)約了編碼時間.通過4幅測試圖像的仿真實(shí)驗(yàn)數(shù)據(jù)，驗(yàn)證了大多數(shù)的待編碼R 塊的最優(yōu)匹配D 塊位于較小鄰域半徑的鄰域內(nèi)，表明了編碼過程的全搜索被鄰域搜索取代是可行的.本文據(jù)此所提混合分形編碼算法與基本分形算法、壓縮感知圖像編碼算法相比，在主觀質(zhì)量評價指標(biāo)SSIM值幾乎沒有變化、以PSNR 度量的重建圖像質(zhì)量分別降低約0.8 dB、2.58 dB 的情況下，所需時間平均分別為相應(yīng)算法的9.36 %與19.83 %，提高速度的效果非常明顯，為分形圖像編碼算法提供了一個好的候選算法.