張力戈，秦小林，楊 涌，黃 東

(1.中國科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所，成都 610041； 2.中國科學(xué)院大學(xué)，北京 100049；3.重慶機(jī)電職業(yè)技術(shù)大學(xué)，重慶 400036； 4.貴州大學(xué)，貴陽 550025)

日常生活中數(shù)字圖像的使用量在互聯(lián)網(wǎng)的飛速發(fā)展下保持爆炸式增長，圖像壓縮是解決數(shù)字圖像高效存儲以及在有限帶寬下高效傳輸?shù)年P(guān)鍵技術(shù)之一.圖像壓縮去除圖像中的冗余信息以較少的比特表示原來的像素矩陣，分為有損壓縮與無損壓縮兩類[1].無損壓縮如游程編碼[2]、霍夫曼編碼[3]等壓縮率較低但不會造成數(shù)據(jù)失真，適用于醫(yī)療、軍事等領(lǐng)域中使用的特定圖像，要求高保真度與真實(shí)性.有損壓縮如矢量量化[4]、分型圖像壓縮[5]、小波變換編碼[6]、塊截?cái)嗑幋a[7]等，這些算法壓縮率高但會產(chǎn)生失真效果，適用于日常工作、生活等領(lǐng)域中使用的一般圖像，可接受一定數(shù)據(jù)失真.

塊截?cái)嗑幋a(Block Truncation Coding, BTC)是Mitchel等[7]提出的一種簡單高效的有損灰度圖像壓縮算法，同時也廣泛應(yīng)用在圖像檢索[8]、數(shù)據(jù)隱藏[9]、圖像認(rèn)證[10]、數(shù)字水印[11]等領(lǐng)域.BTC將圖像分成不重疊的子塊，每個子塊壓縮為一個位圖與兩個量化值.為進(jìn)一步降低BTC壓縮灰度圖像的失真效果，很多基于BTC的改進(jìn)算法被提出，例如Mitchell等[12]提出的絕對矩塊截?cái)嗑幋a(Absolute Moment Block Truncation Coding, AMBTC)和L. Hui等[13]提出的自適應(yīng)塊截?cái)嗑幋a等.對于彩色圖像，直接使用傳統(tǒng)的BTC算法需要對R,G,B通道平面進(jìn)行處理，將每個圖像塊壓縮為3個位圖與6個量化值，壓縮率偏低.Wu等[14]針對此問題提出了單位圖塊截?cái)嗑幋a(Single Bitmap Block Truncation Coding, SBBTC)，將R,G,B通道平面的位圖壓縮成一個公共位圖，算法有效的提升了BTC的壓縮率，但重構(gòu)圖像失真度較高，權(quán)重平面(Weighted Plane, W-plane)是其中一個簡單有效的方法.基于Wu等[14]的工作，Tai等[15]提出基于Hopfield神經(jīng)網(wǎng)絡(luò)的單位圖塊截?cái)嗑幋a，算法通過Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化生成公共位圖，重構(gòu)圖像的失真度低于Wu等[14]的算法.隨后，Tai等[16]又提出基于遺傳算法的單位圖塊截?cái)嗑幋a(GA-AMBTC)，通過遺傳算法優(yōu)化生成公共位圖，該算法重構(gòu)圖像的視覺質(zhì)量優(yōu)于之前的算法.之后，Chang等[17]提出基于漸進(jìn)搜索的單位圖塊截?cái)嗑幋a(GSBTC)，Cui等[18]提出了基于貓群算法的單位圖塊截?cái)嗑幋a(CSO-BTC).最近，Li等[19]提出基于二進(jìn)制蟻群算法的單位圖塊截?cái)嗑幋a(BACO-BTC)，使用二進(jìn)制蟻群算法優(yōu)化生成公共位圖.GSBTC與BACO-BTC計(jì)算量較低，但生成的公共位圖為近似優(yōu)化值，生成重構(gòu)圖像的質(zhì)量難以達(dá)到最優(yōu)效果，GA-AMBTC與CSO-BTC通過遺傳算法與貓群算法可以得到最優(yōu)值，但需要的算法迭代輪數(shù)較高.

煙花算法是譚營等[20]在2010年提出的群體智能優(yōu)化算法，算法通過煙花的爆炸機(jī)制與變異機(jī)制平衡了局部搜索與全局搜索，具有較好的優(yōu)化性能且應(yīng)用廣泛，如多模態(tài)函數(shù)優(yōu)化[21]、復(fù)雜網(wǎng)絡(luò)社區(qū)檢測[22]等.為解決一些特殊離散問題，如多維背包問題[23]等，二進(jìn)制形式煙花算法被提出.本文將煙花算法改進(jìn)為二進(jìn)制形式并結(jié)合W-plane方法，提出了基于二進(jìn)制煙花算法的單位圖塊截?cái)嗑幋a.與文獻(xiàn)[23]中的二進(jìn)制煙花算法不同，本文保留原始煙花算法對爆炸火花數(shù)目與爆炸半徑的計(jì)算公式，在生成爆炸火花與高斯變異火花時均作了相應(yīng)改進(jìn)以提高算法的尋優(yōu)效果.

1 相關(guān)理論

1.1 W-plane方法

SBBTC是BTC的擴(kuò)展，主要用于彩色圖像的壓縮.W-plane方法是一種傳統(tǒng)的SBBTC方法，主要步驟如下：

(1)

式中wij為權(quán)重平面在位置(i,j)處像素的灰度值；

2)根據(jù)式(2)，生成每個子圖像塊的公共位圖，計(jì)算兩個量化向量H，L.

(2)

式中xij=(Rij,Gij,Bij)，q為公共位圖中值為1元素的個數(shù)；

3)根據(jù)式(3)重構(gòu)每個子圖像塊，通過子圖像塊組合成重構(gòu)圖像.

(3)

式中cij為重構(gòu)子圖像塊在位置(i,j)處像素的灰度值向量.

1.2 煙花算法

煙花算法有效地平衡了全局搜索與局部搜索，算法主要步驟如下：

1)初始化N個煙花并評估每個煙花ri的適應(yīng)度值，根據(jù)式(4)計(jì)算每個煙花的爆炸火花數(shù)目Si與爆炸半徑Ai.

(4)

2)根據(jù)Ai為每個煙花生成Si個爆炸火花，同時根據(jù)煙花生成一定數(shù)量高斯變異火花.

3)將煙花、爆炸火花與高斯變異火花作為候選集，從中選擇下一代N個煙花，候選集中適應(yīng)度值最小的煙花被確定性選擇為下一代煙花，其余N-1個煙花通過輪盤賭方法從候選集中選出.

4)重復(fù)步驟1)～4)直到達(dá)到指定迭代輪數(shù)或滿足預(yù)先設(shè)定的停止標(biāo)準(zhǔn).

2 本文算法

本文結(jié)合W-plane方法，基于二進(jìn)制煙花算法提出了兩種單位圖塊截?cái)嗑幋a策略.兩種策略的算法過程相互獨(dú)立，各自得到的壓縮圖像精度不同，整體流程如圖1所示.兩種策略主要區(qū)別在于子圖像塊預(yù)處理部分.策略一在處理子圖像塊時采用局部優(yōu)化的思想，通過BTC方法確定公共位圖中待優(yōu)化元素.策略二采用全局優(yōu)化的思想，將整個公共位圖中的元素作為待優(yōu)化元素.兩種策略在得到待優(yōu)化原素后，通過相同的優(yōu)化方法與壓縮方法對圖像進(jìn)行壓縮與重構(gòu).

圖1 兩種策略流程圖

2.1 圖像分塊

對于給定大小為M×N×3的彩色圖像，將圖像分成不重疊的子圖像塊，每個子圖像塊的大小為m×m×3，后續(xù)操作將在每個子圖像塊上進(jìn)行.

2.2 子圖像塊預(yù)處理

策略一采用局部優(yōu)化思想對每個子圖像塊進(jìn)行預(yù)處理.首先對子圖像塊R,G,B通道平面使用BTC方法得到相應(yīng)的3個位圖RP,GP,BP，根據(jù)式(5)生成子圖像塊初始公共位圖BM并將其中值為α的元素個數(shù)記做nα，記錄所有值為α元素的位置并將這些位置標(biāo)記為L，同時將值為α的元素逐行記做長度為nα的向量s=(α,α,…,α).得到BM后，需對其中值為α的元素即s進(jìn)行優(yōu)化以生成最終公共位圖，在進(jìn)行優(yōu)化之前先對s的值進(jìn)行初始化.

(5)

為保證初始化s不影響B(tài)M中其它元素值，策略一通過W-plane方法得到子圖像塊的位圖BW，如圖2所示，使用BW中位置與L對應(yīng)的nα個元素值初始化s.策略一使用W-plane方法初始化證明如下.

圖2 策略一初始化s示意

(6)

策略二采用全局優(yōu)化思想對每個子圖像塊進(jìn)行預(yù)處理.對子圖像塊使用W-plane方法得到權(quán)重平面的位圖BW，并將其作為初始公共位圖BM.如圖3所示，將BM元素逐行轉(zhuǎn)換為向量s，向量長度為m2.

圖3 策略二初始化s示意

2.3 二進(jìn)制煙花算法優(yōu)化

在子圖像塊預(yù)處理階段得到向量s后，采用二進(jìn)制煙花算法對s進(jìn)行優(yōu)化并得到其對應(yīng)的位圖與量化值.算法基于均方誤差(Mean Squared Error, MSE)設(shè)計(jì)評價函數(shù)來計(jì)算每個煙花的適應(yīng)度值，如式(7)所示.

(7)

式中：Xi為煙花個體，Tij為Xi對應(yīng)的位圖TF在位置(i,j)處的值，cRH,cRL,cGH,cGL,cBH,cBL為Xi對應(yīng)的6個量化值.

2.3.1 煙花種群初始化

二進(jìn)制煙花算法首先需要對煙花種群初始化.根據(jù)式(8)初始化N個煙花，煙花為二進(jìn)制向量，維度為l.在策略一中，l的取值為nα，在策略二中，l的取值為m2.

(8)

式中d()隨機(jī)生成維度為l的二進(jìn)制向量，Xi為煙花個體.

2.3.2 參數(shù)計(jì)算

煙花種群初始化之后，計(jì)算每個煙花的適應(yīng)度值與其生成的爆炸火花的數(shù)目、爆炸半徑.

策略一將每個煙花的元素根據(jù)L記錄的位置替換BM中值為α的元素，形成完整位圖TF，見圖4(a).策略二將每個煙花按行生成完整位圖TF,見圖4(b).

圖4 完整位圖生成過程

得到TF后，通過式(9)計(jì)算每個煙花對應(yīng)的6個量化值cRH,cRL,cGH,cGL,cBH,cBL并根據(jù)式(7)計(jì)算每個煙花的適應(yīng)度值.

(9)

式中q為TF中值為1元素的個數(shù)，[·]表示四舍五入取整.

得到每個煙花的適應(yīng)度值后，通過式(10)計(jì)算每個煙花生成的爆炸火花數(shù)目Ai、爆炸半徑Si.

(10)

式中：M為固定常數(shù)50，ε是一個機(jī)器最小量，取值為2.220 4×e-16，ymax,ymin為當(dāng)前煙花種群的最大適應(yīng)度值與最小適應(yīng)度值，l是Xi維度，在策略一中為nα，在策略二中為m2，[·]表示下界取整.

2.3.3 生成爆炸火花、高斯變異火花

爆炸火花的生成見圖5(a)，圖中h表示爆炸范圍記錄.對每個煙花Xi，根據(jù)其爆炸半徑Si隨機(jī)生成Ai個爆炸范圍，確定每個爆炸范圍在Xi中的位置，對在爆炸范圍內(nèi)的元素通過式(11)進(jìn)行變異得到Ai個爆炸火花E1,E2,…,EAi.

(11)

式中：h為生成的爆炸范圍，oi,ei為Xi與Ei在位置i處的元素值，|·|表示取絕對值.

高斯變異火花的生成如圖5(b)所示.通過N個煙花X1,X2,…,XN生成K個高斯變異火花U1,U2,…,UK，其中U1,U2由煙花中適應(yīng)度值最大和最小的兩個煙花Xbetter,Xworst根據(jù)隨機(jī)產(chǎn)生的交叉范圍記錄v互換元素后生成，U3,…,UK由N個煙花中隨機(jī)選取的K-2個煙花通過式(12)逐位變異生成.

ui=|oi-1|.

(12)

式中ui為Ui在位置i處的元素值.

2.3.4 生成新一代煙花種群

從煙花、爆炸火花和高斯變異火花中選取N個煙花作為新一代煙花種群.選出煙花、爆炸火花、高斯變異火花中適應(yīng)度值最小的火花作為第1個新一代煙花，剩余N-1個新一代煙花使用輪盤賭方法從煙花、爆炸火花、高斯變異火花中選擇.

2.3.5 輸出優(yōu)化值

算法重復(fù)步驟2)～4)，達(dá)到指定的迭代輪數(shù)niter后，將適應(yīng)度值最小的煙花Xbest作為s的優(yōu)化值，并輸出與及與其對應(yīng)的完整位圖TF和6個量化值cRH,cRL,cGH,cGL,cBH,cBL.不同的niter會生成不同質(zhì)量的Xbest，從而生成不同精度的壓縮圖像.如圖9所示，兩種策略生成的壓縮圖像與原圖之間的結(jié)構(gòu)相似性指數(shù)(Structural Similarity Index, SSIM)值初期會隨著迭代輪數(shù)的增加而提升.當(dāng)算法迭代一定輪數(shù)后，兩種策略生成的壓縮圖像與原圖之間的SSIM會逐漸收斂，達(dá)到一個穩(wěn)定值.從圖9(a)可看出，當(dāng)分塊大小為4×4時，策略一與策略二在迭代10輪后均達(dá)到收斂狀態(tài).從圖9(b)可看出，當(dāng)分塊大小為8×8時，策略一在迭代30輪后達(dá)到收斂狀態(tài)，策略二在迭代35輪后達(dá)到收斂狀態(tài).由于分塊大小為8×8時算法對應(yīng)的搜索空間要大于4×4時搜索空間，因此在圖9中，策略一與策略二在分塊大小為8×8時，達(dá)到收斂狀態(tài)所需要的迭代輪數(shù)要多于分塊大小為4×4時的迭代輪數(shù).同時由于策略二為全局搜索方法，策略一為局部搜索方法，因此策略二中的搜索空間要大于策略一中的搜索空間，即策略二達(dá)到收斂狀態(tài)所需的迭代輪數(shù)要高于策略一.

圖5 爆炸火花與高斯變異火花生成過程

2.4 重構(gòu)圖像

根據(jù)完整位圖TF和6個量化值cRH,cRL,cGH,cGL,cBH,cBL，通過式(13)恢復(fù)子圖像塊.圖6為恢復(fù)子圖像塊的例子，其中cRH,cRL,cGH,cGL,cBH,cBL分別為235,226,182,156,255,250.在恢復(fù)所有子圖像塊后，將所有子圖像塊組合成重構(gòu)圖像.

(13)

圖6 子圖像塊恢復(fù)過程

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

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

本文所提算法與W-plane、GA-AMBTC、GSBTC、BACO-BTC等算法都是對SBBTC壓縮圖像精度的改進(jìn)，該算法在壓縮比方面與SBBTC保持一致，因此本文的實(shí)驗(yàn)分析主要采用多種算法在壓縮圖像精度方面進(jìn)行詳盡對比分析.

仿真實(shí)驗(yàn)在MATLAB 2016a環(huán)境下完成，實(shí)驗(yàn)平臺CPU為Inter Core i5 3.0 GHz，16 GB RAM.算法實(shí)驗(yàn)參數(shù)如表1所示，使用測試圖片如圖7所示，

均為512×512的彩色圖像，所有實(shí)驗(yàn)結(jié)果均取自算法運(yùn)行10次后的均值.

表1 實(shí)驗(yàn)參數(shù)

3.2 結(jié)果分析

本文所提算法是在W-plane方法[14]上的改進(jìn)，為驗(yàn)證算法有效性，首先將兩種策略與W-plane方法在圖7中測試圖片上的結(jié)果進(jìn)行比較.表2、表3分別為分塊大小4×4與8×8時兩種策略與W-plane方法生成壓縮圖像與原圖的MSE，從表中實(shí)驗(yàn)結(jié)果可以看出兩種策略的MSE均小于W-plane方法，表明所提算法的改進(jìn)有效.

圖7 測試圖片

表2、表3中實(shí)驗(yàn)結(jié)果顯示策略二生成壓縮圖像與原圖之間的MSE小于策略一，為驗(yàn)證兩種策略效果，將兩種策略對圖Fruits同時迭代35輪進(jìn)行對比.圖8(a)為分塊大小4×4時的MSE對比圖，可以看出策略二MSE整體優(yōu)于策略一，圖8(b)為分塊大小8×8時的MSE對比圖，策略二在最初幾輪迭代中MSE高于策略一，接近第5輪迭代后策略二MSE值逐步小于策略一.

表2 兩種策略與W-plane重構(gòu)圖像MSE比較(4×4)

表3 兩種策略與W-plane重構(gòu)圖像MSE比較(8×8)

圖8 兩種策略MSE對比

結(jié)構(gòu)相似性指數(shù)(Structural Similarity Index, SSIM)用于衡量兩張圖片的相似度.圖9為兩種策略生成壓縮圖與原圖之間的SSIM對比圖，圖9(a)的分塊大小為4×4，其中策略二SSIM整體高于策略一，圖9(b)分塊大小為8×8，其中策略二初始優(yōu)化時SSIM略差于策略一，在迭代幾輪后SSIM高于策略一.從對比結(jié)果可以看出，策略一由于采用局部優(yōu)化的思想，優(yōu)化位數(shù)少于策略二，因此策略一在迭代一定輪數(shù)后陷入局部最優(yōu)，效果無法進(jìn)一步提升，最終優(yōu)化結(jié)果與策略二相比較差.

進(jìn)一步驗(yàn)證文中所提算法有效性，將兩種策略與GA-AMBTC[16]、GSBTC[17]、BACO-BTC[19]這3算法在圖7測試圖片上的結(jié)果進(jìn)行對比，其中GA-AMBTC染色體數(shù)目設(shè)為12，迭代輪數(shù)與本文算法相同，均為20輪，其余參數(shù)與文獻(xiàn)[16]中一致.

圖11至圖14為文中所提兩種策略與3種對比算法的壓縮圖局部區(qū)域?qū)Ρ龋植繀^(qū)域?yàn)镕rymire中分別選取圖的兩塊子圖，即圖10中兩個白色框選中的部分，圖11與圖12中各類算法的分塊大小為4×4，圖13、14中各類算法的分塊大小為8×8.由圖11可看出GA-AMBTC、BACO-BTC、策略一、策略二的壓縮圖視覺效果接近原圖，其中策略二的噪點(diǎn)相比其它3種方法更少，圖12中GA-AMBTC、策略一、策略二的壓縮圖視覺效果與原圖更為接近且3者視覺效果大致相同.由于圖13、14中實(shí)驗(yàn)選擇的分塊大小為8×8，因此各種方法得到的壓縮圖存在較明顯的塊效應(yīng)，從圖13可看出GA-AMBTC、BACO-BTC、策略一、策略二與原圖接近，其中策略二對于原圖的細(xì)節(jié)保留更多，圖14可見GA-AMBTC、策略一、策略二的壓縮圖視覺效果優(yōu)于其它兩種，對原圖的還原度更高.圖11至圖14表明相對與其它3種方法和策略一，策略二得到的壓縮圖對原圖的細(xì)節(jié)保留度較好，壓縮圖與原圖間的相似度更高，即本文算法有效，得到的位圖與量化值更優(yōu).

圖9 兩種策略SSIM對比

圖10 視覺效果測試

圖11 細(xì)節(jié)對比圖一(4×4)

Fig.11 Detail comparison diagram with block size 4×4 on area one

表4～表7為圖7中所示測試圖與通過文中所提兩種策略和3種對比算法進(jìn)行壓縮后的壓縮圖之間的MSE與SSIM值，各類算法的分塊大小在表4、表6中為4×4，在表5、表7中為8×8.

表4中，策略一在測試圖Pepper和Fruits上的MSE比BACO-BTC略高，平均MSE比3種對比算法略低，策略二MSE在整體上都低于其它算法.表5中策略一在測試圖Pepper、Fruits、Tiffany、Lenna上的MSE高于BACO-BTC，在測試圖Tiffany上的MSE高于GA-AMBTC，平均MSE略低于3種對比算法，策略二MSE在整體上都低于其它算法.表4與表5結(jié)果表明本文所提策略二在相同迭代輪數(shù)下優(yōu)于GA-AMBTC，同時優(yōu)于策略一與其它兩種對比算法.

圖12 細(xì)節(jié)對比圖二(4×4)

Fig.12 Detail comparison diagram with block size 4×4 on area two

Fig.13 Detail comparison diagram with block size 8×8 on area one

Fig.14 Detail comparison diagram with block size 8×8 on area two

表6中策略一與策略二的SSIM值整體上都優(yōu)于其它算法，表7中策略一在測試圖Fruits、Tiffany、Lenna上SSIM低于BACO-BTC，在測試圖Tiffany上SSIM低于GA-AMBTC，策略二在測試圖Tiffany上SSIM低于GA-AMBTC，兩種策略在測試圖上的平均SSIM均高于3種對比算法.表6、7結(jié)果表明本文所提算法重構(gòu)圖像與原圖的相似度高于其它算法，即本文所提算法有效且重構(gòu)圖像效果要好于3種對比算法.

4 結(jié) 論

本文針對彩色圖像壓縮需求，提出了一種基于二進(jìn)制煙花算法的單位圖塊截?cái)嗑幋a方法.該方法結(jié)合塊截?cái)嗑幋a特點(diǎn)將煙花算法改為二進(jìn)制形式，以W-plane方法公共位圖中的部分位與全部位作為初始化，采用局部優(yōu)化與全局優(yōu)化的思想進(jìn)行兩種不同的優(yōu)化得到彩色圖像的公共位圖，在保證壓縮比不變下提升重構(gòu)圖像與原圖之間的相似度.實(shí)驗(yàn)結(jié)果表明，該方法可以有效地降低重構(gòu)圖像的失真度，提高重構(gòu)圖像的視覺質(zhì)量.所提方法屬于有損壓縮，對不同大小和類型的彩色圖像均可通過調(diào)整圖像分塊標(biāo)準(zhǔn)與子圖像塊大小來實(shí)現(xiàn)有效壓縮.未來可在方法的子圖像塊預(yù)處理方面將兩種策略進(jìn)行融合，同時在優(yōu)化算法方面進(jìn)行簡化改進(jìn)，以提升算法整體效率.

表4 5種方法重構(gòu)圖像MSE比較(4×4)

表5 5種方法重構(gòu)圖像MSE比較(8×8)

表6 5種方法重構(gòu)圖像SSIM比較(4×4)

表7 5種方法重構(gòu)圖像SSIM比較(8×8)