基于差分進(jìn)化算法的查找表逆半調(diào)模板選擇

葉德剛，文志強，鐘智彥

（湖南工業(yè)大學(xué) 計算機與通信學(xué)院，湖南 株洲 412007）

基于差分進(jìn)化算法的查找表逆半調(diào)模板選擇

葉德剛，文志強，鐘智彥

（湖南工業(yè)大學(xué) 計算機與通信學(xué)院，湖南 株洲 412007）

為提高圖像逆半調(diào)技術(shù)中傳統(tǒng)查找表法的模板對逆半調(diào)圖像的質(zhì)量和效果，提出了一種基于差分進(jìn)化算法求取圖像逆半調(diào)技術(shù)中查找表最優(yōu)模板選擇的方法。實驗表明本文方法尋得的模板具有全局最優(yōu)性，求得的最佳模板與其它算法相同，但是在收斂速度方面優(yōu)于其它全局搜索算法。

逆半調(diào)；差分進(jìn)化算法；模板選擇；查找表

0 引言

數(shù)字半調(diào)技術(shù)是將連續(xù)色調(diào)圖像轉(zhuǎn)變?yōu)殡x散點組成的等觀感半色調(diào)圖像（二值圖像）的技術(shù)[1]。由于人眼視覺的低通濾波特性，在一定的觀察范圍內(nèi)半色調(diào)圖像與原始連續(xù)色調(diào)圖像相近[2]。從原始連續(xù)圖像到半調(diào)圖像是一個多對一的映射過程，半調(diào)操作就是把原始連續(xù)圖像二值化，引入量化噪聲的過程，因此半調(diào)過程是一種圖像的退化過程[3]。而逆半調(diào)是半調(diào)的逆過程，它將二值半調(diào)圖像重建為連續(xù)色調(diào)圖像，是一個一對多的映射過程，因而逆半調(diào)方法是不可能完全重建出與原圖像，而只能盡可能地近似復(fù)原原連續(xù)圖像。目前，圖像逆半調(diào)技術(shù)可分為3類：濾波法、最優(yōu)估值法以及機器學(xué)習(xí)法[4]。

查找表（look-up table，LUT）逆半調(diào)方法是一種典型的機器學(xué)習(xí)方法，原理簡單通用、不涉及任何的線性濾波器、所占資源少，比其它的逆半調(diào)方法運算速度快，并且能得到較好的圖像重建效果[5]。從LUT逆半調(diào)方法提出到現(xiàn)在，在許多的逆半調(diào)方法中與其它方法相結(jié)合。在文獻(xiàn)[4]中，詳細(xì)介紹了2008年以前與LUT相結(jié)合的逆半調(diào)方法，在這些方法中，很少有直接對模板進(jìn)行改進(jìn)的方法，只是利用圖像的邊緣或紋理等信息對LUT逆半調(diào)方法進(jìn)行改進(jìn)。2008年至今，對于LUT的研究中有與神經(jīng)網(wǎng)絡(luò)相結(jié)合的查找表法[1]，與改進(jìn)的模擬退火相結(jié)合的查找表法[4]，與貪心算法相結(jié)合的LUT方法[5]，與八領(lǐng)域動態(tài)均值估值法相結(jié)合的LUT逆半調(diào)方法[6]，與精英遺傳算法相結(jié)合的LUT逆半調(diào)方法[7]等許多采用LUT逆半調(diào)的方法。

以上提出的LUT逆半調(diào)方法中，貪心算法是一種局部搜索算法，求得的結(jié)果有可能不是全局最優(yōu)解，而模擬退火算法和遺傳算法雖然是全局搜索算法，但是收斂速慢，而且有可能陷入局部最優(yōu)，因而也有可能不能求得最優(yōu)解。針對以上問題，本文提出了一種差分進(jìn)化算法（differential evolution，DE）與LUT逆半調(diào)方向相結(jié)合的模板選擇方法，該算法是一種全局搜索算法，有著良好的全局收斂性和魯棒性，在收斂速度方面優(yōu)于其它算法。

1 傳統(tǒng)LUT逆半調(diào)算法

LUT逆半調(diào)方法不涉及任何線性濾波器，也不限于半調(diào)圖像是采用何種算法形成的。逆半調(diào)圖像中某個像素點的值是根據(jù)半調(diào)圖中像素的分布及其對應(yīng)連續(xù)圖像的該點像素值確定的。傳統(tǒng)典型的LUT模板主要有16-rect,16-pels,19-pels。假定模板的尺寸為W×H，模板中有M(M＜W×H)個鄰域像素點,并且模板的尺寸以及鄰域的個數(shù)是固定不變的。本研究的目的是尋找一個模板，使得重建圖像的質(zhì)量最好，而評價圖像質(zhì)量的一個標(biāo)準(zhǔn)是看重建圖像與原圖像之間的峰值信噪比（peak signal to noise ratio，PSNR），為了體現(xiàn)出一個模板的普適性，本文選擇P對連續(xù)灰度圖像以及對應(yīng)的半調(diào)圖像構(gòu)成樣本集圖像{(Gk, Hk)|1≤k≤P}進(jìn)行LUT逆半調(diào)，然后計算P對重建圖像的峰值信噪比，求平均值。因此，式（1）作為判斷模板好壞的評價函數(shù)，即

式中：P為半調(diào)圖及其逆半調(diào)圖的樣本數(shù)量；

x1×y1, x2×y2, …, xP×yP為第k(k=1, 2, …, P)幅圖像的高和寬；

Gk(i, j)為第k幅連續(xù)色調(diào)圖像在(i, j)處的像素值；

一個大小為5×5，鄰域個數(shù)為16的模板如圖1所示，其中中心點O表示待處理的目標(biāo)點，在模板中同樣是看成鄰域像素點，而1表示選中的領(lǐng)域像素點，0表示未選中的領(lǐng)域像素點尋找最佳模板的過程中，鄰域像素點1的個數(shù)M必須滿足式（2），即

這樣，模板選擇問題將轉(zhuǎn)換成一個在符合式（2）的條件下，尋找出一個模板T使得平均峰值信噪比最大的數(shù)學(xué)問題。

圖1 一個包含16個域像素，大小為5×5的模板Fig. 1 A template containing 16 pixels with size of 5×5

LUT逆半調(diào)方法思路如下：設(shè)T為一個模板，通過模板T可能產(chǎn)生的所有樣本模式及其對應(yīng)的連續(xù)色調(diào)灰度值g之間的對應(yīng)關(guān)系，可建立一個LUT表，而逆半調(diào)圖像可以通過查詢此LUT表完成[1]。其思路如圖2所示。

圖2 LUT逆半調(diào)方法思想Fig. 2 LUT Inverse halftone algorithm thought

從圖中可以看出LUT逆半調(diào)過程可以分為建表階段以及逆半調(diào)階段。建表之前，需要收集P對連續(xù)灰度圖像以及對應(yīng)的半調(diào)圖像構(gòu)成樣本集{(Gk, Hk) |1≤k≤P}，Gk表示第k幅連續(xù)灰度圖像，Hk為與之對應(yīng)的半調(diào)圖像。

LUT逆半調(diào)方法建表過程如下。

Step1 建表階段。根據(jù)樣本集，從中依次取一副連續(xù)圖和對應(yīng)的半調(diào)圖，然后讓模板在2幅圖像上依次從左至右，從上到下，移動模板，根據(jù)圖像中像素的分布，形成一張預(yù)先計算好的LUT表，直到樣本集中的圖像全部處理完，利用已求得的查找表，估計未出現(xiàn)的逆半調(diào)值，完善LUT表。

Step2 逆半調(diào)階段。利用完整的LUT表，重建連續(xù)圖像。至此，已經(jīng)完成了LUT表的建立與圖像的逆半調(diào)恢復(fù)。

2 基于差分進(jìn)化算法的模板選擇

差分進(jìn)化算法是一種模擬自然界生物進(jìn)化機制的一種仿生智能算法，最主要的操作思想是基于種群內(nèi)個體差異度生成臨時個體，然后隨機重組實現(xiàn)種群進(jìn)化[8]。DE算法和其它仿生算法一樣，具有良好的全局收斂性和魯棒性，非常適合求解各種最優(yōu)化問題。DE算法的主要特點是算法簡單、收斂速度快和所需領(lǐng)域知識少，在解決復(fù)雜的全局優(yōu)化問題方面，DE算法被實踐證明是一種有效的全局最優(yōu)解的搜索算法。在進(jìn)化算法框架里有很多類型的算法，J. Vesterstrom和R. Thomsen將差分進(jìn)化算法、遺傳算法、粒子群算法進(jìn)行實驗分析，指出在解決復(fù)雜優(yōu)化問題方面，差分進(jìn)化算法的收斂速度更快，穩(wěn)定性更強[9]。

利用差分進(jìn)化算法求最佳NM領(lǐng)域LUT模板算法，操作如下。

1）編碼。LUT最優(yōu)模板選擇是一種非連續(xù)值的問題，所以首先要對DE算法的初始種群T0進(jìn)行隨機編碼。課題組采用二進(jìn)制進(jìn)行編碼，編碼方式為：對模板進(jìn)行掃描，從左上角開始，按照從左至右，從上到下的順序掃描，構(gòu)成個體，其中表示個體T0(m)的第j個基因，N表示模板大小，pop表示種群的規(guī)模，m表示種群T0中的第m個個體T0(m)。一個LUT模板個體可如圖3所示，則個體T0(m)的編碼為{I1I2I3I4I5I6I7I8I9I10I11I12I13I14I15I16I17I18I19I20I21I22I23I24I25}，解碼是編碼的逆過程。

圖3 一個LUT模板個體Fig. 3 An individual LUT template

2）變異操作。在對當(dāng)前種群的評價函數(shù)計算之后，需要對種群中的個體進(jìn)行擾動，使種群進(jìn)化。具體的擾動操作如下：在種群Ti中隨機產(chǎn)生3個互不相同的整數(shù)r1, r2, r3{1, 2, …, pop}，且要求r1≠r2≠r3≠m，先將個體Ti(r1), Ti(r2), Ti(r3)轉(zhuǎn)換成實數(shù)，然后按照式（3）產(chǎn)生變異個體Vi(m)，之后把變異個體Vi(m)轉(zhuǎn)換成二進(jìn)制形式，即

式中F表示縮放因子，取值范圍為[0, 2]。

3）交叉操作。首先生成一個隨機數(shù)Rand {0, 1, 2, ..., N×N-1}，然后對Ti(m)和Vi(m)按照式（4）得到試驗個體Ui(m)，即

式中：r為分布于0到1之間的隨機數(shù)；

CR[0, 1]為交叉因子。

交叉過程如圖4所示，圖中r為0和1之間的隨機數(shù)。

圖4 交叉過程Fig. 4 Cross process

4）個體約束。在變異和交叉過程中，有可能會遇到個體中領(lǐng)域像素個數(shù)不滿足約束條件式（2）的，因此需要對個體進(jìn)行調(diào)整。首先，統(tǒng)計模板個體中1的個數(shù)為num，如果num大于M，因為需要保證中心點的位置為1，因此把除中心點之外的1的num-M個位置隨機變?yōu)?；如果num小于M，則把0的M-num個位置隨機變?yōu)?；確保個體Vi中1的個數(shù)剛好為M個。

5）選擇操作。根據(jù)交叉操作得到的試驗種群Ui和種群Ti，按照式（5）得到新的種群Ti+1中的每個個體Ti+1(m)，其中psnr(Ti(m))和psnr(Ui(m))表示模板個體的評價函數(shù)，在這里即是由式（1）求得的平均峰值性噪比。

基于差分進(jìn)化算法求取LUT圖像逆半調(diào)最優(yōu)模板算法的流程圖如圖5所示，具體步驟如下。

Step1 設(shè)定進(jìn)化參數(shù)：種群規(guī)模pop，交叉因子為CR，縮放因子為F，進(jìn)化代數(shù)為CYC_NUM,隨機生成初始種群T0={T0(0), T0(1),…,T0(m)},其中m {1, 2, …, pop}, T0(x)即為一個模板，然后設(shè)種群中的最優(yōu)個體為bestLut和最優(yōu)個體的評價函數(shù)的值為bestpsnr=0，模板大小為N，模板中有效像素點個數(shù)為M。使用初始種群對P對半調(diào)圖像及其對應(yīng)連續(xù)色調(diào)圖像進(jìn)行傳統(tǒng)的LUT算法的步驟。然后根據(jù)公式（2）計算初始種群每個個體評價函數(shù)值psnr(T0(m))。

Step2 對當(dāng)前的種群Ti按照式（3）進(jìn)行變異操作,得到變異種群Vi(m)。

Step3 根據(jù)原始種群Ti和變異種群Vi(m)按照式（4）得到試驗種群Ui(m)，并且按照傳統(tǒng)LUT算法的步驟計算試驗種群Ui(m)的個體評價函數(shù)的值psnr(Ui(m))。

Step4 根據(jù)Ti和試驗種群Ui(m)按照式（5），得到新的種群Ti+1。同時計算其psnr(Ti+1(x))。把新種群中個體評價函數(shù)值最高的并賦值給bestpsnr，同時找到對應(yīng)的個體存儲到bestLut中。

Step5 循環(huán)執(zhí)行Step2～Step4，直到達(dá)到最大進(jìn)化代數(shù)CYC_NUM。

圖5 基于DE算法的LUT模板選擇算法流程圖Fig. 5 LUT template selection algorithm flowchart based on DE algorithm

3 實驗分析

實驗的操作系統(tǒng)為Windows 7，實驗平臺為Visual Studio 2010以及Opencv 2.4.9。為消除訓(xùn)練樣本以及空值估計對模板選擇的影響，實驗均采用樣本大小為50幅256×256的連續(xù)圖像，以及采用由3種圖像半調(diào)算法產(chǎn)生的對應(yīng)的半調(diào)圖像。這3種方法分別為Floyd-Steinberg、Jarvis和Stucki[1]。求取最佳模板的算法為：DE算法、精英遺傳算（elitist genetic algorithm，EGA）、貪心算法（greedy algorithm，GA）以及模擬退火算法（simulated annealing，SA）。4種算法的循環(huán)終止條件設(shè)置為5代內(nèi)種群個體沒有發(fā)生改變或者到達(dá)設(shè)置的最大迭代次數(shù)，求取最佳模板以及對應(yīng)的訓(xùn)練樣本的平均峰值信噪比。

其中，DE算法中設(shè)定種群規(guī)模pop=20，最大進(jìn)化代數(shù)CYC_NUM=150，縮放因子F=0.5，模板大小N=5，交叉因子CR=0.4；EGA算法實驗中的參數(shù)設(shè)定為：種群規(guī)模、最大進(jìn)化代數(shù)及模板大小與DE算法的相同，變異概率設(shè)定為0.4。有效像素點個數(shù)M=16和M=19的情況下，4種算法求得的最佳模板的平均峰值信噪比如表1中所示，從表中可以看出DE、EGA、GA 3種算法求得的最好的峰值信噪比是一樣的，而用SA求得的明顯不如其它3種算法，在圖6中列出了4中算法求得的最佳模板。

表2中列出4種算法求最佳模板所消耗的時間，GA是一種局部搜索算法，其它3種是全局搜索算法，為了使條件盡可能的相似，實驗中將不考慮GA。DE和SA的耗時大約是EGA的2倍，而SA求得的模板結(jié)果相對而言也比較差。在實驗中發(fā)現(xiàn)，雖然DE, EGA 2種算法相同，但是在求解過程中DE算法的收斂速度比EGA速度快，這與文獻(xiàn)[9]中的研究相同。對此進(jìn)行實驗驗證，2種算法均采用種群大小為20，根據(jù)表1設(shè)置了表3的循環(huán)終止條件，或者是循環(huán)次數(shù)達(dá)到設(shè)定的最大循環(huán)次數(shù)。

表1 各種算法求得的最佳模板的PSNR（N=5）Table 1 The best template PSNR of all algorithm（N =5）

圖6 N=5時，各算法求得的最佳模板Fig. 6 The best template of all algorithms at N = 5

表2 各算法求最佳模板耗時（N=5, 單位為 h）Table 2 The time-consuming for the best template of all algorithms （N=5, the unit is h） h

表3 循環(huán)終止條件（N=5）Table 3 Loop termination conditions （N = 5）

實驗結(jié)果如圖7和圖8所示。

圖7 DE，EGA循環(huán)次數(shù)比較（N=5, M=16）Fig.7 The cycle comparison of DE and EGA （N=5, M=16）

圖8 DE, EGA循環(huán)次數(shù)比較（N=5, M=19）Fig. 8 The cycle comparison of DE and EGA（N=5, M=19）

從圖中可以看出，在相同條件下達(dá)到循環(huán)終止條件時，DE算法的收斂次數(shù)明顯比EGA的收斂次數(shù)少。因此，在求最佳模板中，DE算法雖然比EGA算法所消耗的時間多，但是在收斂速度方便，比EGA算法快，同時，從DE算法的流程來看，DE算法十分簡單，而且也比EGA收斂速度快，所需領(lǐng)域知識少，只要根據(jù)DE算法的步驟，設(shè)定好初始值，按照步驟進(jìn)行設(shè)計即可完成對問題的求解。

4 結(jié)語

本文提出了一種基于差分進(jìn)化算法的查找表逆半調(diào)模板選擇方法，通過與精英遺傳算法、貪心算法、模擬退火算法之間進(jìn)行比較，進(jìn)行了大量的實驗驗證，最后得出本文算法在收斂性方便取得了較好的成績。同時，求得的最佳模板與精英遺傳算法、貪心算法的結(jié)果相同，比模擬退火算法的結(jié)果要好。

[1]孔月萍. 圖像逆半調(diào)及其質(zhì)量評價技術(shù)研究[D]. 西安：西安電子科技大學(xué)，2008. Kong Yueping. A Study of Inverse Halftoning and Quality Assessment Schemes[D]. Xi’an：Xidian University，2008.

[2]Liu Y F，Guo J M，Lee J D. Inverse Halftoning Based on the Bayesian Theorem[J]. IEEE Transactions on Image Processing，2011，20(4)：1077-1084.

[3]黃麗君，文志強，胡 柳. 一種基于LUT的圖像逆半調(diào)改進(jìn)算法[J]. 計算機技術(shù)與發(fā)展，2013，23(6)：35-37. Huang Lijun，Wen Zhiqiang，Hu Liu. An Improved Image Inverse Halftoning Algorithm Based on LUT[J]. Computer Technology and Development，2013，23(6)：35-37.

[4]鄭海紅，孔月萍，曾 平，等. 誤差分散類逆半調(diào)技術(shù)綜述[J]. 中國圖象圖形學(xué)報，2008，13(1)：1-6. Zheng Haihong，Kong Yueping，Zeng Ping，et al. A Review of Inverse Halftoning Algorithms for Error Diffusion [J]. Journal of Image and Graphics，2008，13(1)：1-6.

[5]盧永樂，文志強，李建飛. 基于改進(jìn)模擬退火算法的查找表逆半調(diào)模板選擇[J]. 湖南工業(yè)大學(xué)學(xué)報，2015，29 (1)：76-82. Lu Yongle，Wen Zhiqiang，Li Jianfei. Template Selection for LUT Inverse Halftoning Based on Improved Simulated Annealing[J]. Journal of Hunan University of Technology，2015，29(1)：76-82.

[6]盧永樂，文志強，黃麗君，等. 基于LUT的逆半調(diào)改進(jìn)算法[J]. 湖南工業(yè)大學(xué)學(xué)報，2013，27(6)：57-61. Lu Yongle，Wen Zhiqiang，Huang Lijun，et al. AnImproved Inverse Halftoning Algorithm Based on LUT[J]. Journal of Hunan University of Technology，2013，27(6)：57-61.

[7]Wen Zhiqiang，Lu Yongle，Zeng Zhigao，et al. Optimizing Template for Lookup-Table Inverse Halftoning Using Elitist Genetic Algorithm[J]. IEEE Signal Processing Letters，2015，22(1)：71-75.

[8]高岳林，劉軍民. 差分進(jìn)化算法的參數(shù)研究[J]. 黑龍江大學(xué)自然科學(xué)學(xué)報，2009，26(1)：81-85. Gao Yuelin，Liu Junmin. Parameter Study of Differential Evolution Algorithm[J]. Journal of Natural Science of Heilongjiang University，2009，26(1)：81-85.

[9]Vesterstrom J，Thomsen R. A Comparative Study of Differential Evolution，Particle Swarn Optimization and Evolutionary Algorithms on Numerical Benchmark Problems [C]// Proceedings of Congress on Evolutionary Computation (CEC 2004). [S. l]：IEEE， 2004：1980-1987.

（責(zé)任編輯：申 劍）

LUT Inverse Halftoning Template Selection Based on Differential Evolution Algorithm

Ye Degang，Wen Zhiqiang，Zhong Zhiyan
（School of Computer and Communicatiom，Hunan University of Technology，Zhuzhou Hunan 412007，China）

To improve the inverse halftoning image quality and effect of traditional LUT template, proposed optimal LUT template selection based on differential evolution algorithm. Experimental results show that the template prepared by the method has global optimality, the best template is same with the template of other algorithms, and it is superior to other global search algorithms in the convergence speed.

inverse halftoning；differential evolution；template selection；look up table

TP391.4

A

1673-9833(2015)05-0082-06

10.3969/j.issn.1673-9833.2015.05.017

2015-08-19

國家自然科學(xué)基金資助項目（61170102），湖南省研究生科研創(chuàng)新基金資助項目（CX2015B566），湖南省自然科學(xué)基金資助項目（2014JJ2115, 2015JJ2046），湖南省教育廳科研基金資助項目（15A049）

葉德剛（1992-），男，湖南岳陽人，湖南工業(yè)大學(xué)碩士生，主要研究方向為圖像處理，E-mail：ye211112@126.com