結合二進制煙花算法的單位圖塊截斷編碼

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

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

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

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

煙花算法是譚營等[20]在2010年提出的群體智能優化算法，算法通過煙花的爆炸機制與變異機制平衡了局部搜索與全局搜索，具有較好的優化性能且應用廣泛，如多模態函數優化[21]、復雜網絡社區檢測[22]等.為解決一些特殊離散問題，如多維背包問題[23]等，二進制形式煙花算法被提出.本文將煙花算法改進為二進制形式并結合W-plane方法，提出了基于二進制煙花算法的單位圖塊截斷編碼.與文獻[23]中的二進制煙花算法不同，本文保留原始煙花算法對爆炸火花數目與爆炸半徑的計算公式，在生成爆炸火花與高斯變異火花時均作了相應改進以提高算法的尋優效果.

1 相關理論

1.1 W-plane方法

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

(1)

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

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

(2)

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

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

(3)

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

1.2 煙花算法

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

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

(4)

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

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

4)重復步驟1)～4)直到達到指定迭代輪數或滿足預先設定的停止標準.

2 本文算法

本文結合W-plane方法，基于二進制煙花算法提出了兩種單位圖塊截斷編碼策略.兩種策略的算法過程相互獨立，各自得到的壓縮圖像精度不同，整體流程如圖1所示.兩種策略主要區別在于子圖像塊預處理部分.策略一在處理子圖像塊時采用局部優化的思想，通過BTC方法確定公共位圖中待優化元素.策略二采用全局優化的思想，將整個公共位圖中的元素作為待優化元素.兩種策略在得到待優化原素后，通過相同的優化方法與壓縮方法對圖像進行壓縮與重構.

圖1 兩種策略流程圖

2.1 圖像分塊

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

2.2 子圖像塊預處理

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

(5)

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

圖2 策略一初始化s示意

(6)

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

圖3 策略二初始化s示意

2.3 二進制煙花算法優化

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

(7)

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

2.3.1 煙花種群初始化

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

(8)

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

2.3.2 參數計算

煙花種群初始化之后，計算每個煙花的適應度值與其生成的爆炸火花的數目、爆炸半徑.

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

圖4 完整位圖生成過程

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

(9)

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

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

(10)

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

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

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

(11)

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

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

ui=|oi-1|.

(12)

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

2.3.4 生成新一代煙花種群

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

2.3.5 輸出優化值

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

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

2.4 重構圖像

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

(13)

圖6 子圖像塊恢復過程

3 實驗結果與分析

3.1 實驗環境設置

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

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

均為512×512的彩色圖像，所有實驗結果均取自算法運行10次后的均值.

表1 實驗參數

3.2 結果分析

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

圖7 測試圖片

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

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

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

圖8 兩種策略MSE對比

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

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

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

圖9 兩種策略SSIM對比

圖10 視覺效果測試

圖11 細節對比圖一(4×4)

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

表4～表7為圖7中所示測試圖與通過文中所提兩種策略和3種對比算法進行壓縮后的壓縮圖之間的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結果表明本文所提策略二在相同迭代輪數下優于GA-AMBTC，同時優于策略一與其它兩種對比算法.

圖12 細節對比圖二(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值整體上都優于其它算法，表7中策略一在測試圖Fruits、Tiffany、Lenna上SSIM低于BACO-BTC，在測試圖Tiffany上SSIM低于GA-AMBTC，策略二在測試圖Tiffany上SSIM低于GA-AMBTC，兩種策略在測試圖上的平均SSIM均高于3種對比算法.表6、7結果表明本文所提算法重構圖像與原圖的相似度高于其它算法，即本文所提算法有效且重構圖像效果要好于3種對比算法.

4 結 論

本文針對彩色圖像壓縮需求，提出了一種基于二進制煙花算法的單位圖塊截斷編碼方法.該方法結合塊截斷編碼特點將煙花算法改為二進制形式，以W-plane方法公共位圖中的部分位與全部位作為初始化，采用局部優化與全局優化的思想進行兩種不同的優化得到彩色圖像的公共位圖，在保證壓縮比不變下提升重構圖像與原圖之間的相似度.實驗結果表明，該方法可以有效地降低重構圖像的失真度，提高重構圖像的視覺質量.所提方法屬于有損壓縮，對不同大小和類型的彩色圖像均可通過調整圖像分塊標準與子圖像塊大小來實現有效壓縮.未來可在方法的子圖像塊預處理方面將兩種策略進行融合，同時在優化算法方面進行簡化改進，以提升算法整體效率.

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

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

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

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