張力戈,秦小林,楊 涌,黃 東
(1.中國(guó)科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所,成都 610041; 2.中國(guó)科學(xué)院大學(xué),北京 100049;3.重慶機(jī)電職業(yè)技術(shù)大學(xué),重慶 400036; 4.貴州大學(xué),貴陽(yáng) 550025)
日常生活中數(shù)字圖像的使用量在互聯(lián)網(wǎng)的飛速發(fā)展下保持爆炸式增長(zhǎng),圖像壓縮是解決數(shù)字圖像高效存儲(chǔ)以及在有限帶寬下高效傳輸?shù)年P(guān)鍵技術(shù)之一.圖像壓縮去除圖像中的冗余信息以較少的比特表示原來(lái)的像素矩陣,分為有損壓縮與無(wú)損壓縮兩類[1].無(wú)損壓縮如游程編碼[2]、霍夫曼編碼[3]等壓縮率較低但不會(huì)造成數(shù)據(jù)失真,適用于醫(yī)療、軍事等領(lǐng)域中使用的特定圖像,要求高保真度與真實(shí)性.有損壓縮如矢量量化[4]、分型圖像壓縮[5]、小波變換編碼[6]、塊截?cái)嗑幋a[7]等,這些算法壓縮率高但會(huì)產(chǎn)生失真效果,適用于日常工作、生活等領(lǐng)域中使用的一般圖像,可接受一定數(shù)據(jù)失真.
塊截?cái)嗑幋a(Block Truncation Coding, BTC)是Mitchel等[7]提出的一種簡(jiǎn)單高效的有損灰度圖像壓縮算法,同時(shí)也廣泛應(yīng)用在圖像檢索[8]、數(shù)據(jù)隱藏[9]、圖像認(rèn)證[10]、數(shù)字水印[11]等領(lǐng)域.BTC將圖像分成不重疊的子塊,每個(gè)子塊壓縮為一個(gè)位圖與兩個(gè)量化值.為進(jìn)一步降低BTC壓縮灰度圖像的失真效果,很多基于BTC的改進(jìn)算法被提出,例如Mitchell等[12]提出的絕對(duì)矩塊截?cái)嗑幋a(Absolute Moment Block Truncation Coding, AMBTC)和L. Hui等[13]提出的自適應(yīng)塊截?cái)嗑幋a等.對(duì)于彩色圖像,直接使用傳統(tǒng)的BTC算法需要對(duì)R,G,B通道平面進(jìn)行處理,將每個(gè)圖像塊壓縮為3個(gè)位圖與6個(gè)量化值,壓縮率偏低.Wu等[14]針對(duì)此問(wèn)題提出了單位圖塊截?cái)嗑幋a(Single Bitmap Block Truncation Coding, SBBTC),將R,G,B通道平面的位圖壓縮成一個(gè)公共位圖,算法有效的提升了BTC的壓縮率,但重構(gòu)圖像失真度較高,權(quán)重平面(Weighted Plane, W-plane)是其中一個(gè)簡(jiǎn)單有效的方法.基于Wu等[14]的工作,Tai等[15]提出基于Hopfield神經(jīng)網(wǎng)絡(luò)的單位圖塊截?cái)嗑幋a,算法通過(guò)Hopfield神經(jīng)網(wǎng)絡(luò)優(yōu)化生成公共位圖,重構(gòu)圖像的失真度低于Wu等[14]的算法.隨后,Tai等[16]又提出基于遺傳算法的單位圖塊截?cái)嗑幋a(GA-AMBTC),通過(guò)遺傳算法優(yōu)化生成公共位圖,該算法重構(gòu)圖像的視覺(jué)質(zhì)量?jī)?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通過(guò)遺傳算法與貓群算法可以得到最優(yōu)值,但需要的算法迭代輪數(shù)較高.
煙花算法是譚營(yíng)等[20]在2010年提出的群體智能優(yōu)化算法,算法通過(guò)煙花的爆炸機(jī)制與變異機(jī)制平衡了局部搜索與全局搜索,具有較好的優(yōu)化性能且應(yīng)用廣泛,如多模態(tài)函數(shù)優(yōu)化[21]、復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)[22]等.為解決一些特殊離散問(wèn)題,如多維背包問(wèn)題[23]等,二進(jìn)制形式煙花算法被提出.本文將煙花算法改進(jìn)為二進(jìn)制形式并結(jié)合W-plane方法,提出了基于二進(jìn)制煙花算法的單位圖塊截?cái)嗑幋a.與文獻(xiàn)[23]中的二進(jìn)制煙花算法不同,本文保留原始煙花算法對(duì)爆炸火花數(shù)目與爆炸半徑的計(jì)算公式,在生成爆炸火花與高斯變異火花時(shí)均作了相應(yīng)改進(jìn)以提高算法的尋優(yōu)效果.
SBBTC是BTC的擴(kuò)展,主要用于彩色圖像的壓縮.W-plane方法是一種傳統(tǒng)的SBBTC方法,主要步驟如下:
(1)
式中wij為權(quán)重平面在位置(i,j)處像素的灰度值;
2)根據(jù)式(2),生成每個(gè)子圖像塊的公共位圖,計(jì)算兩個(gè)量化向量H,L.
(2)
式中xij=(Rij,Gij,Bij),q為公共位圖中值為1元素的個(gè)數(shù);
3)根據(jù)式(3)重構(gòu)每個(gè)子圖像塊,通過(guò)子圖像塊組合成重構(gòu)圖像.
(3)
式中cij為重構(gòu)子圖像塊在位置(i,j)處像素的灰度值向量.
煙花算法有效地平衡了全局搜索與局部搜索,算法主要步驟如下:
1)初始化N個(gè)煙花并評(píng)估每個(gè)煙花ri的適應(yīng)度值,根據(jù)式(4)計(jì)算每個(gè)煙花的爆炸火花數(shù)目Si與爆炸半徑Ai.
(4)
2)根據(jù)Ai為每個(gè)煙花生成Si個(gè)爆炸火花,同時(shí)根據(jù)煙花生成一定數(shù)量高斯變異火花.
3)將煙花、爆炸火花與高斯變異火花作為候選集,從中選擇下一代N個(gè)煙花,候選集中適應(yīng)度值最小的煙花被確定性選擇為下一代煙花,其余N-1個(gè)煙花通過(guò)輪盤賭方法從候選集中選出.
4)重復(fù)步驟1)~4)直到達(dá)到指定迭代輪數(shù)或滿足預(yù)先設(shè)定的停止標(biāo)準(zhǔn).
本文結(jié)合W-plane方法,基于二進(jìn)制煙花算法提出了兩種單位圖塊截?cái)嗑幋a策略.兩種策略的算法過(guò)程相互獨(dú)立,各自得到的壓縮圖像精度不同,整體流程如圖1所示.兩種策略主要區(qū)別在于子圖像塊預(yù)處理部分.策略一在處理子圖像塊時(shí)采用局部?jī)?yōu)化的思想,通過(guò)BTC方法確定公共位圖中待優(yōu)化元素.策略二采用全局優(yōu)化的思想,將整個(gè)公共位圖中的元素作為待優(yōu)化元素.兩種策略在得到待優(yōu)化原素后,通過(guò)相同的優(yōu)化方法與壓縮方法對(duì)圖像進(jìn)行壓縮與重構(gòu).
圖1 兩種策略流程圖
對(duì)于給定大小為M×N×3的彩色圖像,將圖像分成不重疊的子圖像塊,每個(gè)子圖像塊的大小為m×m×3,后續(xù)操作將在每個(gè)子圖像塊上進(jìn)行.
策略一采用局部?jī)?yōu)化思想對(duì)每個(gè)子圖像塊進(jìn)行預(yù)處理.首先對(duì)子圖像塊R,G,B通道平面使用BTC方法得到相應(yīng)的3個(gè)位圖RP,GP,BP,根據(jù)式(5)生成子圖像塊初始公共位圖BM并將其中值為α的元素個(gè)數(shù)記做nα,記錄所有值為α元素的位置并將這些位置標(biāo)記為L(zhǎng),同時(shí)將值為α的元素逐行記做長(zhǎng)度為nα的向量s=(α,α,…,α).得到BM后,需對(duì)其中值為α的元素即s進(jìn)行優(yōu)化以生成最終公共位圖,在進(jìn)行優(yōu)化之前先對(duì)s的值進(jìn)行初始化.
(5)
為保證初始化s不影響B(tài)M中其它元素值,策略一通過(guò)W-plane方法得到子圖像塊的位圖BW,如圖2所示,使用BW中位置與L對(duì)應(yīng)的nα個(gè)元素值初始化s.策略一使用W-plane方法初始化證明如下.
圖2 策略一初始化s示意
(6)
策略二采用全局優(yōu)化思想對(duì)每個(gè)子圖像塊進(jìn)行預(yù)處理.對(duì)子圖像塊使用W-plane方法得到權(quán)重平面的位圖BW,并將其作為初始公共位圖BM.如圖3所示,將BM元素逐行轉(zhuǎn)換為向量s,向量長(zhǎng)度為m2.
圖3 策略二初始化s示意
在子圖像塊預(yù)處理階段得到向量s后,采用二進(jìn)制煙花算法對(duì)s進(jìn)行優(yōu)化并得到其對(duì)應(yīng)的位圖與量化值.算法基于均方誤差(Mean Squared Error, MSE)設(shè)計(jì)評(píng)價(jià)函數(shù)來(lái)計(jì)算每個(gè)煙花的適應(yīng)度值,如式(7)所示.
(7)
式中:Xi為煙花個(gè)體,Tij為Xi對(duì)應(yīng)的位圖TF在位置(i,j)處的值,cRH,cRL,cGH,cGL,cBH,cBL為Xi對(duì)應(yīng)的6個(gè)量化值.
2.3.1 煙花種群初始化
二進(jìn)制煙花算法首先需要對(duì)煙花種群初始化.根據(jù)式(8)初始化N個(gè)煙花,煙花為二進(jìn)制向量,維度為l.在策略一中,l的取值為nα,在策略二中,l的取值為m2.
(8)
式中d()隨機(jī)生成維度為l的二進(jìn)制向量,Xi為煙花個(gè)體.
2.3.2 參數(shù)計(jì)算
煙花種群初始化之后,計(jì)算每個(gè)煙花的適應(yīng)度值與其生成的爆炸火花的數(shù)目、爆炸半徑.
策略一將每個(gè)煙花的元素根據(jù)L記錄的位置替換BM中值為α的元素,形成完整位圖TF,見(jiàn)圖4(a).策略二將每個(gè)煙花按行生成完整位圖TF,見(jiàn)圖4(b).
圖4 完整位圖生成過(guò)程
得到TF后,通過(guò)式(9)計(jì)算每個(gè)煙花對(duì)應(yīng)的6個(gè)量化值cRH,cRL,cGH,cGL,cBH,cBL并根據(jù)式(7)計(jì)算每個(gè)煙花的適應(yīng)度值.
(9)
式中q為TF中值為1元素的個(gè)數(shù),[·]表示四舍五入取整.
得到每個(gè)煙花的適應(yīng)度值后,通過(guò)式(10)計(jì)算每個(gè)煙花生成的爆炸火花數(shù)目Ai、爆炸半徑Si.
(10)
式中:M為固定常數(shù)50,ε是一個(gè)機(jī)器最小量,取值為2.220 4×e-16,ymax,ymin為當(dāng)前煙花種群的最大適應(yīng)度值與最小適應(yīng)度值,l是Xi維度,在策略一中為nα,在策略二中為m2,[·]表示下界取整.
2.3.3 生成爆炸火花、高斯變異火花
爆炸火花的生成見(jiàn)圖5(a),圖中h表示爆炸范圍記錄.對(duì)每個(gè)煙花Xi,根據(jù)其爆炸半徑Si隨機(jī)生成Ai個(gè)爆炸范圍,確定每個(gè)爆炸范圍在Xi中的位置,對(duì)在爆炸范圍內(nèi)的元素通過(guò)式(11)進(jìn)行變異得到Ai個(gè)爆炸火花E1,E2,…,EAi.
(11)
式中:h為生成的爆炸范圍,oi,ei為Xi與Ei在位置i處的元素值,|·|表示取絕對(duì)值.
高斯變異火花的生成如圖5(b)所示.通過(guò)N個(gè)煙花X1,X2,…,XN生成K個(gè)高斯變異火花U1,U2,…,UK,其中U1,U2由煙花中適應(yīng)度值最大和最小的兩個(gè)煙花Xbetter,Xworst根據(jù)隨機(jī)產(chǎn)生的交叉范圍記錄v互換元素后生成,U3,…,UK由N個(gè)煙花中隨機(jī)選取的K-2個(gè)煙花通過(guò)式(12)逐位變異生成.
ui=|oi-1|.
(12)
式中ui為Ui在位置i處的元素值.
2.3.4 生成新一代煙花種群
從煙花、爆炸火花和高斯變異火花中選取N個(gè)煙花作為新一代煙花種群.選出煙花、爆炸火花、高斯變異火花中適應(yīng)度值最小的火花作為第1個(gè)新一代煙花,剩余N-1個(gè)新一代煙花使用輪盤賭方法從煙花、爆炸火花、高斯變異火花中選擇.
2.3.5 輸出優(yōu)化值
算法重復(fù)步驟2)~4),達(dá)到指定的迭代輪數(shù)niter后,將適應(yīng)度值最小的煙花Xbest作為s的優(yōu)化值,并輸出與及與其對(duì)應(yīng)的完整位圖TF和6個(gè)量化值cRH,cRL,cGH,cGL,cBH,cBL.不同的niter會(huì)生成不同質(zhì)量的Xbest,從而生成不同精度的壓縮圖像.如圖9所示,兩種策略生成的壓縮圖像與原圖之間的結(jié)構(gòu)相似性指數(shù)(Structural Similarity Index, SSIM)值初期會(huì)隨著迭代輪數(shù)的增加而提升.當(dāng)算法迭代一定輪數(shù)后,兩種策略生成的壓縮圖像與原圖之間的SSIM會(huì)逐漸收斂,達(dá)到一個(gè)穩(wěn)定值.從圖9(a)可看出,當(dāng)分塊大小為4×4時(shí),策略一與策略二在迭代10輪后均達(dá)到收斂狀態(tài).從圖9(b)可看出,當(dāng)分塊大小為8×8時(shí),策略一在迭代30輪后達(dá)到收斂狀態(tài),策略二在迭代35輪后達(dá)到收斂狀態(tài).由于分塊大小為8×8時(shí)算法對(duì)應(yīng)的搜索空間要大于4×4時(shí)搜索空間,因此在圖9中,策略一與策略二在分塊大小為8×8時(shí),達(dá)到收斂狀態(tài)所需要的迭代輪數(shù)要多于分塊大小為4×4時(shí)的迭代輪數(shù).同時(shí)由于策略二為全局搜索方法,策略一為局部搜索方法,因此策略二中的搜索空間要大于策略一中的搜索空間,即策略二達(dá)到收斂狀態(tài)所需的迭代輪數(shù)要高于策略一.
圖5 爆炸火花與高斯變異火花生成過(guò)程
根據(jù)完整位圖TF和6個(gè)量化值cRH,cRL,cGH,cGL,cBH,cBL,通過(guò)式(13)恢復(fù)子圖像塊.圖6為恢復(fù)子圖像塊的例子,其中cRH,cRL,cGH,cGL,cBH,cBL分別為235,226,182,156,255,250.在恢復(fù)所有子圖像塊后,將所有子圖像塊組合成重構(gòu)圖像.
(13)
圖6 子圖像塊恢復(fù)過(guò)程
本文所提算法與W-plane、GA-AMBTC、GSBTC、BACO-BTC等算法都是對(duì)SBBTC壓縮圖像精度的改進(jìn),該算法在壓縮比方面與SBBTC保持一致,因此本文的實(shí)驗(yàn)分析主要采用多種算法在壓縮圖像精度方面進(jìn)行詳盡對(duì)比分析.
仿真實(shí)驗(yàn)在MATLAB 2016a環(huán)境下完成,實(shí)驗(yàn)平臺(tái)CPU為Inter Core i5 3.0 GHz,16 GB RAM.算法實(shí)驗(yàn)參數(shù)如表1所示,使用測(cè)試圖片如圖7所示,
均為512×512的彩色圖像,所有實(shí)驗(yàn)結(jié)果均取自算法運(yùn)行10次后的均值.
表1 實(shí)驗(yàn)參數(shù)
本文所提算法是在W-plane方法[14]上的改進(jìn),為驗(yàn)證算法有效性,首先將兩種策略與W-plane方法在圖7中測(cè)試圖片上的結(jié)果進(jìn)行比較.表2、表3分別為分塊大小4×4與8×8時(shí)兩種策略與W-plane方法生成壓縮圖像與原圖的MSE,從表中實(shí)驗(yàn)結(jié)果可以看出兩種策略的MSE均小于W-plane方法,表明所提算法的改進(jìn)有效.
圖7 測(cè)試圖片
表2、表3中實(shí)驗(yàn)結(jié)果顯示策略二生成壓縮圖像與原圖之間的MSE小于策略一,為驗(yàn)證兩種策略效果,將兩種策略對(duì)圖Fruits同時(shí)迭代35輪進(jìn)行對(duì)比.圖8(a)為分塊大小4×4時(shí)的MSE對(duì)比圖,可以看出策略二MSE整體優(yōu)于策略一,圖8(b)為分塊大小8×8時(shí)的MSE對(duì)比圖,策略二在最初幾輪迭代中MSE高于策略一,接近第5輪迭代后策略二MSE值逐步小于策略一.
表2 兩種策略與W-plane重構(gòu)圖像MSE比較(4×4)
表3 兩種策略與W-plane重構(gòu)圖像MSE比較(8×8)
圖8 兩種策略MSE對(duì)比
結(jié)構(gòu)相似性指數(shù)(Structural Similarity Index, SSIM)用于衡量?jī)蓮垐D片的相似度.圖9為兩種策略生成壓縮圖與原圖之間的SSIM對(duì)比圖,圖9(a)的分塊大小為4×4,其中策略二SSIM整體高于策略一,圖9(b)分塊大小為8×8,其中策略二初始優(yōu)化時(shí)SSIM略差于策略一,在迭代幾輪后SSIM高于策略一.從對(duì)比結(jié)果可以看出,策略一由于采用局部?jī)?yōu)化的思想,優(yōu)化位數(shù)少于策略二,因此策略一在迭代一定輪數(shù)后陷入局部最優(yōu),效果無(wú)法進(jìn)一步提升,最終優(yōu)化結(jié)果與策略二相比較差.
進(jìn)一步驗(yàn)證文中所提算法有效性,將兩種策略與GA-AMBTC[16]、GSBTC[17]、BACO-BTC[19]這3算法在圖7測(cè)試圖片上的結(jié)果進(jìn)行對(duì)比,其中GA-AMBTC染色體數(shù)目設(shè)為12,迭代輪數(shù)與本文算法相同,均為20輪,其余參數(shù)與文獻(xiàn)[16]中一致.
圖11至圖14為文中所提兩種策略與3種對(duì)比算法的壓縮圖局部區(qū)域?qū)Ρ龋植繀^(qū)域?yàn)镕rymire中分別選取圖的兩塊子圖,即圖10中兩個(gè)白色框選中的部分,圖11與圖12中各類算法的分塊大小為4×4,圖13、14中各類算法的分塊大小為8×8.由圖11可看出GA-AMBTC、BACO-BTC、策略一、策略二的壓縮圖視覺(jué)效果接近原圖,其中策略二的噪點(diǎn)相比其它3種方法更少,圖12中GA-AMBTC、策略一、策略二的壓縮圖視覺(jué)效果與原圖更為接近且3者視覺(jué)效果大致相同.由于圖13、14中實(shí)驗(yàn)選擇的分塊大小為8×8,因此各種方法得到的壓縮圖存在較明顯的塊效應(yīng),從圖13可看出GA-AMBTC、BACO-BTC、策略一、策略二與原圖接近,其中策略二對(duì)于原圖的細(xì)節(jié)保留更多,圖14可見(jiàn)GA-AMBTC、策略一、策略二的壓縮圖視覺(jué)效果優(yōu)于其它兩種,對(duì)原圖的還原度更高.圖11至圖14表明相對(duì)與其它3種方法和策略一,策略二得到的壓縮圖對(duì)原圖的細(xì)節(jié)保留度較好,壓縮圖與原圖間的相似度更高,即本文算法有效,得到的位圖與量化值更優(yōu).
圖9 兩種策略SSIM對(duì)比
圖10 視覺(jué)效果測(cè)試
圖11 細(xì)節(jié)對(duì)比圖一(4×4)
Fig.11 Detail comparison diagram with block size 4×4 on area one
表4~表7為圖7中所示測(cè)試圖與通過(guò)文中所提兩種策略和3種對(duì)比算法進(jìn)行壓縮后的壓縮圖之間的MSE與SSIM值,各類算法的分塊大小在表4、表6中為4×4,在表5、表7中為8×8.
表4中,策略一在測(cè)試圖Pepper和Fruits上的MSE比BACO-BTC略高,平均MSE比3種對(duì)比算法略低,策略二MSE在整體上都低于其它算法.表5中策略一在測(cè)試圖Pepper、Fruits、Tiffany、Lenna上的MSE高于BACO-BTC,在測(cè)試圖Tiffany上的MSE高于GA-AMBTC,平均MSE略低于3種對(duì)比算法,策略二MSE在整體上都低于其它算法.表4與表5結(jié)果表明本文所提策略二在相同迭代輪數(shù)下優(yōu)于GA-AMBTC,同時(shí)優(yōu)于策略一與其它兩種對(duì)比算法.
圖12 細(xì)節(jié)對(duì)比圖二(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中策略一在測(cè)試圖Fruits、Tiffany、Lenna上SSIM低于BACO-BTC,在測(cè)試圖Tiffany上SSIM低于GA-AMBTC,策略二在測(cè)試圖Tiffany上SSIM低于GA-AMBTC,兩種策略在測(cè)試圖上的平均SSIM均高于3種對(duì)比算法.表6、7結(jié)果表明本文所提算法重構(gòu)圖像與原圖的相似度高于其它算法,即本文所提算法有效且重構(gòu)圖像效果要好于3種對(duì)比算法.
本文針對(duì)彩色圖像壓縮需求,提出了一種基于二進(jìn)制煙花算法的單位圖塊截?cái)嗑幋a方法.該方法結(jié)合塊截?cái)嗑幋a特點(diǎn)將煙花算法改為二進(jìn)制形式,以W-plane方法公共位圖中的部分位與全部位作為初始化,采用局部?jī)?yōu)化與全局優(yōu)化的思想進(jìn)行兩種不同的優(yōu)化得到彩色圖像的公共位圖,在保證壓縮比不變下提升重構(gòu)圖像與原圖之間的相似度.實(shí)驗(yàn)結(jié)果表明,該方法可以有效地降低重構(gòu)圖像的失真度,提高重構(gòu)圖像的視覺(jué)質(zhì)量.所提方法屬于有損壓縮,對(duì)不同大小和類型的彩色圖像均可通過(guò)調(diào)整圖像分塊標(biāo)準(zhǔn)與子圖像塊大小來(lái)實(shí)現(xiàn)有效壓縮.未來(lái)可在方法的子圖像塊預(yù)處理方面將兩種策略進(jìn)行融合,同時(shí)在優(yōu)化算法方面進(jìn)行簡(jiǎ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)