圖像塊自相似特征的快速分形編碼算法

李高平，宋建成

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

圖像塊自相似特征的快速分形編碼算法

李高平，宋建成

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

為了解決全搜索分形圖像編碼算法在編碼過程中range塊和domain塊匹配特別耗時(shí)問題，定義了每個(gè)range塊和domain塊的自相似特征，由于在自仿射變換下最優(yōu)匹配塊間的自相似特征應(yīng)該接近，因此，每個(gè)range塊的最優(yōu)匹配塊搜索范圍僅限在與其自相似特征接近的domain塊鄰域內(nèi)，變?nèi)炙阉鳛榫植克阉?六幅圖像的仿真結(jié)果表明，它確實(shí)能夠在PSNR降低0.48dB(其結(jié)構(gòu)相似性SSIM值僅下降0.0015)的情況下，平均耗時(shí)僅為全搜索分形編碼算法的18.65%左右，而且也優(yōu)于其他特征算法，所提算法達(dá)到了加快編碼過程速度的目標(biāo).

圖像壓縮；分形圖像編碼；四鄰域像素值平均；自相似特征

分形圖像壓縮編碼算法是一種基于圖像具有的自相似性來實(shí)現(xiàn)圖像數(shù)據(jù)壓縮的新一代有損編碼方法，用壓縮映射集來表達(dá)圖像信息，并用迭代的方式來恢復(fù)原圖像.但它有一個(gè)明顯的缺點(diǎn)，編碼過程需要花費(fèi)大量時(shí)間才能完成在一個(gè)數(shù)量龐大的碼書中找尋出每個(gè)與編碼range塊相匹配的domain塊，使其計(jì)算復(fù)雜性很高，進(jìn)而限制了它在圖像壓縮領(lǐng)域的運(yùn)用.近年來，在盡量不降低圖像質(zhì)量的情況下來加快分形編碼速度，成為許多學(xué)者研究的重要內(nèi)容，通過提出的措施也取得了較好的加速效果[1-16].其采用的措施主要有分類法和特征向量法，目的是減少搜尋待編碼range塊的最優(yōu)匹配domain塊的范圍，變?nèi)炙阉鳛榫植克阉?措施的有效性取決于局部搜索得到的domain塊有多少是它的最優(yōu)匹配塊.本文繼續(xù)研究特征向量法來加快編碼過程，在構(gòu)造圖像塊的特征向量時(shí)，既要便于提取又要注意其維數(shù)不能太大，以避免加重存儲(chǔ)負(fù)擔(dān).鑒于待編碼圖像本身的復(fù)雜性各異，就選用蘊(yùn)含在圖像塊中的自相似特征來刻畫其信息.具體地說，首先把n×n大小的圖像塊通過四鄰域像素值平均收縮為n/2×n/2大小的圖像塊，然后將收縮前后的兩個(gè)圖像塊上像素點(diǎn)灰度值按某種方式向量化為向量X和，最后把它們?nèi)ゾ岛蟮玫降膬蓚€(gè)向量2-范數(shù)比值作為圖像塊的自相似特征.實(shí)驗(yàn)結(jié)果表明，在編碼階段的匹配過程中，以自相似特征為依據(jù)所做局部搜索來取代全局搜索，可以獲取大部分待編碼range塊的最優(yōu)匹配塊.它優(yōu)于相似比特征[10]和可選特征[15]，據(jù)此特征提出的快速算法在解碼圖像質(zhì)量降低約0.48dB(其結(jié)構(gòu)相似性SSIM值僅下降約0.0015)的情況下，編碼時(shí)間明顯減少，僅僅為全搜索算法的18.65%.

1 全搜索分形圖像編碼算法

全搜索分形圖像編碼過程流程圖如圖1所示.

圖1 全搜索分形圖像編碼過程流程圖Fig.1 The flow chart of the full search fractal image encoding

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

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

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

然后對(duì)不滿足｜s｜＜1的對(duì)比度因子s以截?cái)喾绞教幚?式(1)的外層極小化問題用全搜索法求解:

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

2 自相似特征的快速分形編碼算法

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

對(duì)于一個(gè)N×N大小的圖像I，編碼R塊大小設(shè)為n×n，需要編碼的R塊數(shù)量，碼書Ω(以符號(hào)表示碼書容量)中D塊大小設(shè)置為2n×2n，取生成碼書步長為δ，其碼書容量大小，若按全搜索方式尋找每個(gè)range塊的最優(yōu)匹配domain塊，由式(3)可知，它需要搜尋完整個(gè)碼書Ω中的D塊，那編碼過程需要次匹配，會(huì)因碼書Ω容量龐大而消費(fèi)很多時(shí)間，縮減搜索空間是勢在必行.下面通過定義圖像塊的特征，并依據(jù)該特征把匹配過程的全搜索轉(zhuǎn)換為鄰域搜索.

圖2 四鄰域像素值平均示意圖Fig.2 Four neighbour pixel values average diagram

下面來討論在自仿射變換下，R塊能與D塊組成最優(yōu)匹配塊時(shí)，它們的自相似特征間的關(guān)系.

全搜索方式中，每個(gè)待編碼R塊通過自仿射變換w在碼書Ω中尋找均方根誤差最小的D塊為最優(yōu)匹配塊，即

用最小二乘法求得式(2)中亮度偏移o的解為

將(5)式中o代入(4)式，有

將(6)(7)式兩邊同時(shí)2-范數(shù)并做比，有

從(8)式可以看出，若R塊和D塊能組成匹配對(duì)，那它們的自相似比也應(yīng)該比較接近.

2.2 快速編碼算法方案

設(shè)計(jì)加快編碼過程方案時(shí)，涉及3個(gè)關(guān)鍵因素:編碼R塊集的數(shù)量、碼書Ω容量以及采取的搜索法.前面2個(gè)因素由分割方案決定，在此討論待編碼的R塊在碼書Ω中的搜索方式.由(8)式可知，R塊和D塊能組成匹配對(duì)，要求S(D)應(yīng)該與S(R)接近，也就是說R塊的最優(yōu)匹配Dm塊在自相似特征意義下位于與R塊自相似特征接近的D塊鄰域內(nèi).所以，在設(shè)計(jì)搜索法時(shí)，首先根據(jù)自相似特征值升序排列碼書中的全體D塊，即，然后，在升序碼書Ω中采用二分法搜索與編碼R塊自相似特征值S(R)相差最小的初始匹配塊D塊:

其后，編碼搜索過程在Dinit的k鄰域內(nèi)進(jìn)行.對(duì)每個(gè)編碼的R塊，它的搜索碼書Ωs為

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

選擇6幅復(fù)雜性各異的圖像Lena、Peppers、Boat、Baboon、Goldhill和bridge(512×512，8bit量化)來作為實(shí)驗(yàn)的測試對(duì)象，方塊分割圖像，R塊、D塊及碼書步長分別取為4×4、8×8和8，此時(shí)，編碼R塊集數(shù)量為16384，碼書Ω容量為32768，仿真實(shí)驗(yàn)平臺(tái)為PC機(jī)(AMD Athlon，3.01GH CPU/2G內(nèi)存)，算法用C＋＋編寫的程序?qū)崿F(xiàn).

3.1 自相似特征的有效性驗(yàn)證

本文定義的圖像塊自相似特征，是用蘊(yùn)含在圖像塊中的自相似性來刻畫其信息.為了表明圖像塊自相似特征優(yōu)于相似比特征[10]和可選特征[15]，下面通過仿真實(shí)驗(yàn)測出編碼R塊在全搜索中得到的最優(yōu)匹配塊，有多少落在上述特征意義下的初始匹配塊Dinit的k鄰域內(nèi).對(duì)每個(gè)編碼R塊在該鄰域中找到的次優(yōu)匹配塊就是最優(yōu)匹配塊的R塊總數(shù)量隨鄰域半徑k的變化情況見圖3(圖中數(shù)據(jù)取的是6幅512×512測試圖像的平均值).

圖3 R塊總數(shù)量隨鄰域半徑k的變化情況Fig.3 The range block quantity vs.radius of neighbour k

圖3顯示，在相同的搜索鄰域半徑，在本文特征意義下，能找到最優(yōu)匹配塊的R塊的總數(shù)量明顯高于其它兩種特征.在初始匹配塊Dinit的鄰域內(nèi)找到的次優(yōu)匹配塊就是最優(yōu)匹配塊的R塊數(shù)量占總編碼R塊數(shù)的比例分別記為P10、P50和P100，用百分?jǐn)?shù)表示.本文特征、相似比特征[10]和可選特征[15]的這三項(xiàng)指標(biāo)均列于表1(表中數(shù)據(jù)取的是測試圖像的平均值).

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

表1中數(shù)據(jù)表明，本文特征的三項(xiàng)指標(biāo)也好于其他兩種特征.上述圖表均例證了本文定義的圖像塊自相似特征是占優(yōu)的.圖表數(shù)據(jù)也顯示，對(duì)本文定義的特征，只需搜索碼書的10%空間，就有大約30.9%的R塊找到了最優(yōu)匹配塊，搜索50%空間就有84.4%，R塊需要搜索完整個(gè)碼書才能找到最優(yōu)匹配塊的比例僅為1.3%.這說明絕大多數(shù)的待編碼R塊的最優(yōu)匹配塊就在圖像塊自相似特征意義下的初始匹配塊附近，驗(yàn)證了它的合理性.

3.2 自相似特征快速算法的有效性驗(yàn)證

先通過實(shí)驗(yàn)確定圖像塊自相似特征意義下的初始匹配塊Dinit的k鄰域半徑k值，以確定搜索碼書Ωs的容量.圖4是6幅測試圖像的解碼質(zhì)量(以PSNR度量)在不同鄰域半徑k值下的變化情況.

圖4 解碼圖像質(zhì)量隨鄰域半徑k的變化情況Fig.4 The quality of the decoded image vs.radius of neighbour k

選編碼時(shí)間(秒)、峰值信噪比PSNR(dB)和結(jié)構(gòu)相似性SSIM(structural similarity)為測試性能參數(shù)，來驗(yàn)證本文所提快速算法的有效性.本文算法(k＝0.5)與全搜索算法的對(duì)比實(shí)驗(yàn)結(jié)果列于表2.

表2數(shù)據(jù)表明，對(duì)所給測試對(duì)象，本文所提算法加快全搜索算法的編碼過程的速度相差不是很大，但解碼圖像質(zhì)量相差還是比較大的.取平均值來看，在解碼圖像質(zhì)量(以PSNR度量)降低約0.48dB的情況下，編碼過程耗時(shí)僅為全搜索算法所需時(shí)間的18.65%左右.眾所周知，作為圖像質(zhì)量評(píng)價(jià)的客觀指標(biāo)PSNR，沒有考慮到人眼的視覺特性，易造成評(píng)價(jià)結(jié)果與人的主觀感覺不吻合.為此，引入衡量兩幅圖像相似度的新指標(biāo)SSIM來評(píng)價(jià)圖像感知質(zhì)量，它們的SSIM值僅平均下降約0.0015，這充分說明所提算法的解碼圖像的主觀質(zhì)量是很不錯(cuò)的.

表2 本文算法與全搜索分形算法對(duì)比結(jié)果Table 2 The comparison between the proposed algorithm and the full search algorithm

4 結(jié)論

只有圖像中具有自相似性及比例特性，采用分形圖像編碼才有效，通過去除圖像的幾何冗余度來實(shí)現(xiàn)圖像數(shù)據(jù)壓縮.本文定義的圖像塊自相似特征用到了蘊(yùn)含在圖像塊中的自相似性，在編碼過程中，能組成匹配對(duì)的R塊與D塊，它們的自相似特征應(yīng)該是接近的，這樣就把消費(fèi)時(shí)間最多的R塊與碼書Ω中D塊的匹配全搜索問題轉(zhuǎn)化為初始匹配塊Dinit(其自相似特征值與S(R)最接近)的鄰域搜索問題，算法復(fù)雜度大大降低.仿真實(shí)驗(yàn)中所用6幅測試圖像，驗(yàn)證了在Dinit的k鄰域內(nèi)(搜索碼書Ωs)搜尋到的次優(yōu)匹配塊，對(duì)絕大多數(shù)的待編碼R塊來說，就是它要找尋的最優(yōu)匹配塊，表明了全搜索被鄰域搜索取代是可行的.本文據(jù)此所提快速分形編碼算法，在解碼圖像質(zhì)量(以PSNR度量)降低0.48dB(以SSIM值度量僅下降約0.0015)的情況下，編碼過程所需時(shí)間僅為全搜索耗時(shí)的18.65%左右.且自相似特征相較于相似比特征和可選特征，更能表述出圖像塊的信息.該算法既有理論分析，又有仿真實(shí)驗(yàn)結(jié)果的佐證，且在全搜索算法基礎(chǔ)上實(shí)現(xiàn)比較容易，它無疑為加快分形圖像編碼過程提供了一個(gè)好的算法.

[1]ZHANG AIHUA，YANG PEI.An improved algorithm for fractal image encoding based on relative error[C]//5th International Congress on Image and Signal Processing，IEEE，2012:254-25.

[2]TANG GUOWEI，WU SHUANG，ZHANG YAN.An improved fast fractal image coding algorithm[C]//2th International Conference on Computer Science and Network Technology，IEEE，2012:730-732.

[3]YANG FENGXIA.Study on the effective measures of enhancing the fractal image coding[C]//International Conference on Computational and Information Sciences，CPS，2013:160-162.

[4]WANG JIANJI，LAN XUGUANG，LIU YUEHU 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].SAI Intelligent Systems Conference，IEEE，2015:761-764.

[6]WANG XINGYUAN，ZHANG DOUDOU，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é)報(bào)，2011，16(1):1-7.

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

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

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

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

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

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

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

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

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

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

Fast fractal encoding algorithm based on image block self-similar feature

LI Gao-ping，SONG Jian-cheng
(School of Computer Science＆Technology，Southwest University for Nationalities，Chengdu 610041，P.R.C.)

The full search fractal image algorithm requires a very long encoding time，which is essentially spent on searching for the best-matched block to an input range block in a large domain pool.In order to solve this problem，defining the self-similar features of each range block and domain block，on account of the self-similar feature for an input range block and its bestmatched domain block should be approximate based on the self affine transformation，so the self-similar feature is utilized to confine efficiently the search scope to the vicinity of the domain block having the closest self-similar feature to the input range block being encoded，it can exactly avoid the excessive search.Simulation results of six test images showed that the average time of the proposed scheme is only about 18.65%while there is averagely the PSNR decrease of 0.48dB(its the structural similarity decrease of 0.0015)，in comparison with the full search fractal algorithm.Moreover，it is better than the other feature algorithm，the proposed algorithm to speed up the encoding process.

image compression；fractal image coding；average of four neighbor pixel values；self-similar feature

TN919.81

A

2095-4271(2016)05-0544-06

10.11920/xnmdzk.2016.05.013

2016-07-04

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

四川省應(yīng)用基礎(chǔ)項(xiàng)目(No.2013JY0180)；四川省教育廳科研項(xiàng)目(No.15ZA0384)