基于相似比的變鄰域搜索的快速分形編碼算法

汪明華，李高平

(西南民族大學(xué)計算機科學(xué)與技術(shù)學(xué)院，四川 成都 610041)

基于相似比的變鄰域搜索的快速分形編碼算法

汪明華，李高平

(西南民族大學(xué)計算機科學(xué)與技術(shù)學(xué)院，四川 成都 610041)

為了解決基本分形圖像編碼算法中的編碼過程特別耗時問題，通過定義每個range塊和domain塊的相似比，建立它與匹配均方根誤差間的關(guān)系不等式，可把尋找range塊的最佳匹配domain塊的全局搜索變?yōu)榻徦阉?鑒于在自仿射變換下最優(yōu)匹配塊間的相似比值應(yīng)該接近，但它們間的遠近程度不一致，因此，每個range塊的最優(yōu)匹配塊搜索范圍應(yīng)限制在與其相似比值接近的domain塊變鄰域內(nèi).四幅圖像的仿真結(jié)果表明，它確實能夠在PSNR降低0.103dB(其結(jié)構(gòu)相似性SSIM值僅下降0.0004)的情況下，平均耗時僅為基本分形編碼算法的38.97%左右，而且也優(yōu)于可選特征算法，實現(xiàn)了加快編碼過程速度的目標.

圖像壓縮；分形圖像編碼；變鄰域搜索；相似比

隨著信息技術(shù)和媒體技術(shù)的飛速發(fā)展，如何有效處理海量信息中的圖像數(shù)據(jù)，已經(jīng)成為人們關(guān)注的熱點問題，各種圖像壓縮編碼方法應(yīng)運而生.基于圖像內(nèi)部的自相似性來實現(xiàn)圖像數(shù)據(jù)壓縮的分形編碼方法被認為是目前最有前途的編碼技術(shù)之一，但是因其編碼時間長、計算復(fù)雜性高等問題使其應(yīng)用性受到了限制.近年來，在如何保證圖像質(zhì)量的前提下來加快分形編碼過程的速度，已成為許多學(xué)者研究的關(guān)鍵問題，通過提出的措施也取得了較好的加速效果[1-17].在文獻[10]中提出了一種基于相似比的分形編碼算法并給出了可行性分析，在編碼過程中，每個range塊只搜索與range塊相似比相差較近的碼書中的domain塊，通過減少搜索對象來達到縮減最佳匹配過程的過度耗時問題.本文對此做了進一步研究，不僅從理論上證明匹配均方誤差與匹配塊相似比間的關(guān)系不等式，而且據(jù)此提出了變鄰域搜索的快速分形編碼算法.仿真實驗結(jié)果表明，在編碼過程的匹配階段，基于相似比為依據(jù)所做的近鄰搜索來取代全局搜索，可以獲取大部分待編碼range塊的最優(yōu)匹配塊，且它優(yōu)于可選特征[16]，據(jù)此提出的變鄰域搜索快速算法，在解碼圖像質(zhì)量降低約0.103dB(其結(jié)構(gòu)相似性SSIM值僅下降約0.0004)的情況下，編碼過程耗時僅為基本分形圖像編碼算法的38.97%，減少編碼時間約61%.

1 基本分形圖像編碼算法

首先選取一種分割方式，將圖像分成兩類子塊集:編碼range塊(簡稱R塊，大小為n×n，互不重疊)集和domain塊集(簡稱D塊，大小為2n×2n，允許重疊).搜索所用碼書Ω，是將domain塊集中每個D塊采用4－鄰域像素值平均收縮成n×n的子塊，再經(jīng)過8個等距變換而得到.

對每個待編碼R塊，需要求解下面的極小化問題(1)尋找其最優(yōu)匹配D塊的位置和自仿射變換w.

其中，m表示R塊的最優(yōu)匹配塊序號，I∈Rn×n是所有元素均為1的常值塊，R＝(r1，…，rk，…，rM)、D＝(d1，…，dk，…，dM)(M＝n×n)分別表示R塊、D塊像素點灰度值按某種方式向量化后的向量.

鑒于式(1)是NP難問題，故只能求次優(yōu)解.首先忽略式(1)中約束｜s｜＜1，將(1)的內(nèi)層約束極小化轉(zhuǎn)化為(2)式的極小值問題來求解:

然后對不滿足｜s｜＜1的對比度因子s以截斷方式處理.式(1)的外層極小化問題用全搜索法求解:

解碼圖像用分形碼按迭代方式重構(gòu).

2 變鄰域搜索的快速分形編碼算法

2.1 算法的理論分析

在基本分形算法的匹配搜索階段，每個range塊都以全搜索方式在整個碼書Ω(其容量龐大)中尋找它的最優(yōu)匹配domain塊，而導(dǎo)致匹配搜索需要特別多的時間.下面首先定義圖像塊的相似比，從理論上證明匹配均方誤差與匹配塊相似比間的關(guān)系不等式，然后據(jù)此提出變鄰域搜索的快速分形編碼算法，以縮減匹配搜索所需時間.

定義 圖像塊上像素灰度值按行向量后記為X＝(x1，…，xi，…，xM)∈RM(RM代表n×n＝M灰度圖像塊空間)，相應(yīng)地，它的上半部分子塊記為X*＝，定義圖像塊的相似比為去均值后的2-范數(shù)‖X*－·I‖，與X去均值后的2-范數(shù)‖X－·I‖之比[10]，即

在自仿射變換下，R塊能與D塊組成最優(yōu)匹配塊時，它們間的相似比應(yīng)該比較接近[10]，即

下面的定理進一步給出R塊與D塊的匹配誤差與其相似比間的關(guān)系，它們共同構(gòu)成本文算法的理論基礎(chǔ).

定理 若圖像塊大小為n×n，其上的像素灰度值按升序向量化為R，D∈RM(M＝n×n)，則有下面的不等式:

由2-范數(shù)、內(nèi)積以及式(4)有

由Cauchy-Schwarz不等式和式(7)有

又問題(2)的解為

故匹配均方誤差為

定理得證.

2.2 快速編碼算法設(shè)計

基本分形編碼算法中匹配搜索階段的耗時主要取決于需要編碼的R塊數(shù)量、碼書Ω容量.比如說，對于一個N×N大小的圖像I，若編碼R塊和D塊大小分別設(shè)為n×n和2n×2n，則需要編碼的R塊數(shù)量為NR＝(N/n)2，碼書Ω容量為((N－2n)/δ＋1)2(δ為碼書步長)，以全搜索方式尋找每個R塊的最優(yōu)匹配D塊，那就需要NRD＝次匹配.問題在于，是不是每個R塊都需要NRD次匹配搜索才能找到它的最優(yōu)匹配D塊?在式(4)定義的相似比下，從自仿射變換角度看，R塊能與D塊組成最優(yōu)匹配對的條件是它們間的相似比應(yīng)該比較接近；從R塊與D塊的匹配誤差角度看，式(6)表明，R塊和D塊能組成匹配對的必要條件是R塊的相似比S(R)應(yīng)要求與D塊相似比S(D)接近.這些都說明在相似比意義下應(yīng)該是近鄰，也就是說，每個編碼不一定需要搜索完整個碼書Ω來找它的最優(yōu)匹配D塊.下一個問題是，如何確定每個R塊的搜索碼書Ωs?并要求這個碼書的容量盡可能小，且包含R塊的最優(yōu)匹配D塊.根據(jù)上面分析得出的近鄰結(jié)論，在設(shè)計快速算法時，首先確定鄰域中心碼本塊D0，將碼書中的全體D塊按相似比值大小進行升序排列，即S(Di)≤S(Di＋1)，然后，在升序碼書Ω中采用二分法搜索與編碼R塊相似比值S(R)相差最小的D塊為D0，即

然后，對每個編碼的R塊，它的搜索碼書Ωs就在D0的k鄰域內(nèi)進行，即

值得說明的是，要使Ωs中包含R塊的最優(yōu)匹配D塊，每個編碼R塊的鄰域半徑k的大小是不同的(仿真實驗給予驗證).顯然，將k設(shè)定為一個較小的固定值，那在Ωs中找不到它的最優(yōu)匹配D塊的可能性就會很大，解碼圖像質(zhì)量會變得很差，若k設(shè)定為一個較大的固定值，就不能達到縮減匹配搜索耗時目的.為了解決這個難題，設(shè)計一個變鄰域搜索方案:根據(jù)解碼圖像質(zhì)量要求高低，設(shè)定匹配誤差E(R，D)閾值為λ，先取k＝K0(K0為初始鄰域半徑)，看編碼R塊能否在鄰域N(D0，k)中找到E(R，D)≤λ的D塊，若不能，就取k＝K0＋K(K為擴域步長)，再在鄰域N(D0，k)中找能否滿足E(R，D)≤λ的D塊，若還不能，就再取k＝K0＋2K，…，k＝K0＋nK(n為擴域次數(shù))，直至在鄰域N(D0，k)中找到滿足要求的D塊為止.然后將其位置序號m、所得量化參數(shù)，及等距變換的序號t作為該R塊的分形碼(m，，，t).所有編碼R塊的分形碼集合就構(gòu)成編碼圖像的分形碼.

3 仿真實驗結(jié)果

本節(jié)的仿真實驗驗證兩個主要問題:一是在相似比意義下，編碼R塊與它的最優(yōu)匹配D塊是否為近鄰?二是變鄰域搜索快速編碼算法的有效性.為此，選擇4幅復(fù)雜性各異的圖像Lena、Peppers、Boat、Baboon(512×512，8bit量化)為測試對象，方塊分割圖像，R塊、D塊及碼書步長分別取為4×4、8×8和8，此時，編碼R塊集數(shù)量為16384，碼書Ω容量為32768，仿真實驗平臺為PC機(AMD Athlon，3.01GH CPU/2G內(nèi)存)，算法用C＋＋編寫的程序?qū)崿F(xiàn).

3.1 相似比意義下的近鄰驗證

本文通過定義圖像塊的相似比來刻畫蘊含在圖像塊中的信息.下面通過仿真實驗測出編碼R塊在全搜索中得到的最優(yōu)匹配塊，在相似比意義下的鄰域中心碼本塊D0的k鄰域N(D0，k)內(nèi)的分布情況，4幅測試圖像的結(jié)果列于表1，表中標識“M-N”表示鄰域半徑k的取值區(qū)間為

表1 最優(yōu)匹配塊落入鄰域N(D0，k)內(nèi)的R塊數(shù)量Table 1 Quantity of the range block of the best-matched domain block fall into neighbor N(D0，k)

表1數(shù)據(jù)顯示，從4幅測試圖像的平均值看，只需搜索碼書的10%空間，就有大約22%的編碼R塊能找到它的最優(yōu)匹配塊，搜索50%空間能找到的比例為70%多，編碼R塊要搜索完整個碼書才能找到最佳匹配塊的比例僅為5%.這表明大多數(shù)的編碼R塊的最優(yōu)匹配D塊就在圖像塊相似比意義下，位于鄰域中心碼本塊D0附近，當(dāng)然遠近是不一樣的，佐證了快速算法的理論基礎(chǔ).

下面來比較圖像塊的相似比與可選特征[16]，誰能更好刻畫圖像塊的信息?取4幅測試圖像分別在相似比意義和可選特征意義下，在鄰域N(D0，k)中能找到最優(yōu)匹配塊的編碼R塊數(shù)量比例來進行比較，結(jié)果列于表2(數(shù)據(jù)是4幅測試圖像的平均值)，表中記號P10、P50和P100分別表示能在鄰域半徑k≤100%時，找到的最優(yōu)匹配塊的編碼R塊數(shù)量占總編碼R塊數(shù)的比例(用百分數(shù)表示).

表2 最優(yōu)匹配塊落入鄰域N(D0，k)內(nèi)的R塊比例Table 2 Proportion of the range block of the best-matched domain block fall into neighbor N(D0，k)

表2中數(shù)據(jù)表明，從所給三項指標看，圖像塊的相似比優(yōu)于可選特征，能更好刻畫圖像塊的信息.

3.2 變鄰域搜索快速編碼算法的有效性驗證

在3.2節(jié)設(shè)計的變鄰域搜索快速編碼算法，涉及匹配誤差E(R，D)閾值λ，初始鄰域半徑K0，擴域步長K.經(jīng)實驗驗證，初始鄰域半徑K0和擴域步長K對算法結(jié)果影響很小，取K0＝1，K＝2，在此主要來確定對算法結(jié)果影響很大的閾值λ，4幅測試圖像的解碼圖像質(zhì)量隨λ的變化情況如圖1所示.

從圖1可以看出，隨著匹配誤差閾值λ的增大，測試圖像的解碼圖像質(zhì)量(以PSNR度量)是在降低，降低速率大小取決于需編碼圖像中所含細節(jié)多少，所以，匹配誤差閾值λ最好根據(jù)實際情況對解碼圖像質(zhì)量要求高低進行選取.對所給4幅測試圖像的情況，當(dāng)λ≤10時，以PSNR度量的解碼圖像質(zhì)量降低很少，故取λ＝10.

圖1 解碼圖像質(zhì)量隨匹配誤差閾值λ的變化情況Fig.1 The quality of the decoded image vs.matching error threshold λ

為驗證變鄰域搜索快速編碼算法的有效性.選編碼時間(秒)、峰值信噪比PSNR(dB)和結(jié)構(gòu)相似性SSIM(structural similarity)為測試性能參數(shù)，本文算法(K0＝1，K＝2，λ＝10)與基本算法的對比實驗結(jié)果列于表3.

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

分析表3數(shù)據(jù)，取4幅測試圖像的平均值，本文所提算法在編碼過程中所耗時間僅為基本算法的38.97%，減少了約61%的時間，以PSNR度量的解碼圖像質(zhì)量降低約0.103dB，以SSIM度量的解碼圖像質(zhì)量降低約0.0004(表明解碼圖像與其編碼前的圖像相比，圖像中的對象結(jié)構(gòu)屬性幾乎沒有變化，也說明它的主觀質(zhì)量是很不錯的).這充分例證了變鄰域搜索快速編碼算法是有效的.在此需要說明的是，表3顯示有些圖像在本文算法下的解碼圖像質(zhì)量高于基本算法，原因在于兩種算法都是有損算法，解碼圖像質(zhì)量依賴于對不滿足約束｜s｜＜1的對比度因子s作截斷處理的數(shù)目.

4 結(jié)論

本文運用圖像塊的相似比，從理論上證明了能組成匹配對的R塊與D塊，它們的相似比應(yīng)該是接近的，并給予了實驗佐證.在此基礎(chǔ)上，把消費時間最多的R塊與碼書Ω中D塊的匹配全搜索問題轉(zhuǎn)化為鄰域中心碼本塊D0(其相似比值與S(R)最接近)的鄰域搜索問題，以縮減搜索空間.考慮到不同編碼R塊需要搜索的鄰域半徑k是不一樣的，本文提出了變鄰域搜索的快速分形編碼算法，在解碼圖像質(zhì)量(以PSNR度量)降低0.103dB(以SSIM值度量僅下降約0.0004)的情況下，編碼過程所需時間僅為基本算法耗時的38.97%左右，達到了保質(zhì)(或少降質(zhì))提速目的，它無疑為加快基本分形圖像編碼過程提供了一個候選算法.

[1]AIHUA ZHANG，PEIYANG.An Improved Algorithm for Fractal Image Encoding Based on Relative Error[C].IEEE:5th International Congress on Image and Signal Processing，2012:254-25.

[2]TANG GUOWEI，WU SHUANG ZHANG YAN.An Improved Fast Fractal Image Coding Algorithm[C].IEEE:2th International Conference on Computer Science and Network Technology，2012:730-732.

[3]FENGXIA YANG.Study on the Effective Measures of Enhancing the Fractal Image Coding[C].International Conference on Computational and Information Sciences，CPS，2013:160-162.

[4]JIANJI WANG，XUGUANG LAN，YUEHU LIU et al.Fractal image encoding with flexible classification sets[J].Chin Sci Bull，2014，59 (14):1597-1606.

[5]LI LOU，YONG LI.Research of Neighborhood Searching Fractal Image Coding Algorithm based on Ant Colony Optimization[C].IEEE:SAI Intelligent Systems Conference，2015:761-764.

[6]WANG XING YUAN，ZHANG DOU DOU，WEI NA.Fractal image coding algorithm using particle swarm optimisation and hybrid quadtree [J].IET Image process，2015，9(2):153-161.

[7]李高平.三均值特征的快速分形圖像編碼算法[J].中國圖象圖形學(xué)報，2011，16(1):1-7.

[8]李高平，向慧芬，趙正武.四分位數(shù)特征的快速分形圖像編碼算法[J].計算機工程與應(yīng)用，2011，47(22):145-148.

[9]寧培興，黃仁.數(shù)理統(tǒng)計特征的快速圖像分形壓縮算法研究[J].計算機工程與應(yīng)用，2012，48(31):161-165.

[10]張愛華，盛飛，楊培，等.基于相似比的快速分形編碼算法[J].計算機技術(shù)與發(fā)展，2012，22(11):176-178.

[11]錢雅儒，郭中華，雍慧.一種改進的規(guī)范塊半范數(shù)算法[J].計算機工程，2012，38(2):221-223.

[12]蘇兆寶，周敏，鄭紅嬋，等.基于像素采樣的分形圖像編碼算法[J].計算機系統(tǒng)應(yīng)用，2013，22(12):136-139，167.

[13]楊培.基于分形圖像編碼的快速搜索方法研究[D].南京:南京郵電大學(xué)，2013.

[14]孫媛媛，孔瑞卿.一種基于字典的快速分形圖像編碼方法[J].計算機工程，2013，39(1):230-233.

[15]劉樹群，潘章容.基于Fisher分類和空間映射的分形圖像編碼方法[J].計算機應(yīng)用，2013，33(12):3552-3554，3558.

[16]袁宗文，魯業(yè)頻，楊漢生.可選特征的快速分形圖像編碼[J].中國圖象圖形學(xué)報，2015，20(2):0177-0182.

[17]裔傳俊，劉亮.采用邊緣分類和平均偏差比較的分形圖像編碼[J].計算機應(yīng)用與軟件，2015，32(2):211-214.

(責(zé)任編輯:張陽，付強，李建忠，羅敏；英文編輯:周序林)

Fast fractal encoding algorithm based on similarity ratio and variable neighborhood search

WANG Ming-hua，LI Gao-ping
(School of Computer Science＆Technology，Southwest University for Nationalities，Chengdu 610041，P.R.C.)

This research is to shorten the exhaustive encoding time of the basic fractal image encoding algorithm.The search scope of best-matched block for an input range block is local against full on the basis of an inequality linking the root-meansquare and defining the similarity ratio.In detail，its search space should be the vicinity of the initial-matched block(i.e.，the domain block having the closet similarity ratio to the input range block being encoded)by the self-affine transformation，but the size of search neighborhood is inconsistent.Therefore，the optimal matching search scope of the input range block being encoded should be the variable neighborhood of initial-matched block.Simulation results of four test images show that average time of the proposed scheme is only about 38.97%while there is averagely the PSNR decrease of 0.103dB(its the structural similarity decrease of 0.0004)，in comparison with the basic fractal algorithm.Moreover，it is better than the optional feature algorithm，the proposed algorithm achieves an objective of speeding up the encoding process.

image compression；fractal image coding；variable neighborhood search；similarity ratio

TP391.41

A

2095-4271(2016)06-0682-06

10.11920/xnmdzk.2016.06.015

2016-08-11

李高平(1966－)，男，教授.研究方向:分形理論及其在圖像處理中的應(yīng)用研究.E-mail:pinggaoli＠163.com

四川省應(yīng)用基礎(chǔ)項目(2013JY0180)；2016年度中央高?；究蒲袠I(yè)務(wù)費專項資金項目(2016ZYXS14)