基于差分进化算法的查找表逆半调模板选择

叶德刚，文志强，钟智彦

（湖南工业大学 计算机与通信学院，湖南 株洲 412007）

基于差分进化算法的查找表逆半调模板选择

叶德刚，文志强，钟智彦

（湖南工业大学 计算机与通信学院，湖南 株洲 412007）

为提高图像逆半调技术中传统查找表法的模板对逆半调图像的质量和效果，提出了一种基于差分进化算法求取图像逆半调技术中查找表最优模板选择的方法。实验表明本文方法寻得的模板具有全局最优性，求得的最佳模板与其它算法相同，但是在收敛速度方面优于其它全局搜索算法。

逆半调；差分进化算法；模板选择；查找表

0 引言

数字半调技术是将连续色调图像转变为离散点组成的等观感半色调图像（二值图像）的技术[1]。由于人眼视觉的低通滤波特性，在一定的观察范围内半色调图像与原始连续色调图像相近[2]。从原始连续图像到半调图像是一个多对一的映射过程，半调操作就是把原始连续图像二值化，引入量化噪声的过程，因此半调过程是一种图像的退化过程[3]。而逆半调是半调的逆过程，它将二值半调图像重建为连续色调图像，是一个一对多的映射过程，因而逆半调方法是不可能完全重建出与原图像，而只能尽可能地近似复原原连续图像。目前，图像逆半调技术可分为3类：滤波法、最优估值法以及机器学习法[4]。

查找表（look-up table，LUT）逆半调方法是一种典型的机器学习方法，原理简单通用、不涉及任何的线性滤波器、所占资源少，比其它的逆半调方法运算速度快，并且能得到较好的图像重建效果[5]。从LUT逆半调方法提出到现在，在许多的逆半调方法中与其它方法相结合。在文献[4]中，详细介绍了2008年以前与LUT相结合的逆半调方法，在这些方法中，很少有直接对模板进行改进的方法，只是利用图像的边缘或纹理等信息对LUT逆半调方法进行改进。2008年至今，对于LUT的研究中有与神经网络相结合的查找表法[1]，与改进的模拟退火相结合的查找表法[4]，与贪心算法相结合的LUT方法[5]，与八领域动态均值估值法相结合的LUT逆半调方法[6]，与精英遗传算法相结合的LUT逆半调方法[7]等许多采用LUT逆半调的方法。

以上提出的LUT逆半调方法中，贪心算法是一种局部搜索算法，求得的结果有可能不是全局最优解，而模拟退火算法和遗传算法虽然是全局搜索算法，但是收敛速慢，而且有可能陷入局部最优，因而也有可能不能求得最优解。针对以上问题，本文提出了一种差分进化算法（differential evolution，DE）与LUT逆半调方向相结合的模板选择方法，该算法是一种全局搜索算法，有着良好的全局收敛性和鲁棒性，在收敛速度方面优于其它算法。

1 传统LUT逆半调算法

LUT逆半调方法不涉及任何线性滤波器，也不限于半调图像是采用何种算法形成的。逆半调图像中某个像素点的值是根据半调图中像素的分布及其对应连续图像的该点像素值确定的。传统典型的LUT模板主要有16-rect,16-pels,19-pels。假定模板的尺寸为W×H，模板中有M(M＜W×H)个邻域像素点,并且模板的尺寸以及邻域的个数是固定不变的。本研究的目的是寻找一个模板，使得重建图像的质量最好，而评价图像质量的一个标准是看重建图像与原图像之间的峰值信噪比（peak signal to noise ratio，PSNR），为了体现出一个模板的普适性，本文选择P对连续灰度图像以及对应的半调图像构成样本集图像{(Gk, Hk)|1≤k≤P}进行LUT逆半调，然后计算P对重建图像的峰值信噪比，求平均值。因此，式（1）作为判断模板好坏的评价函数，即

式中：P为半调图及其逆半调图的样本数量；

x1×y1, x2×y2, …, xP×yP为第k(k=1, 2, …, P)幅图像的高和宽；

Gk(i, j)为第k幅连续色调图像在(i, j)处的像素值；

一个大小为5×5，邻域个数为16的模板如图1所示，其中中心点O表示待处理的目标点，在模板中同样是看成邻域像素点，而1表示选中的领域像素点，0表示未选中的领域像素点寻找最佳模板的过程中，邻域像素点1的个数M必须满足式（2），即

这样，模板选择问题将转换成一个在符合式（2）的条件下，寻找出一个模板T使得平均峰值信噪比最大的数学问题。

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

LUT逆半调方法思路如下：设T为一个模板，通过模板T可能产生的所有样本模式及其对应的连续色调灰度值g之间的对应关系，可建立一个LUT表，而逆半调图像可以通过查询此LUT表完成[1]。其思路如图2所示。

图2 LUT逆半调方法思想Fig. 2 LUT Inverse halftone algorithm thought

从图中可以看出LUT逆半调过程可以分为建表阶段以及逆半调阶段。建表之前，需要收集P对连续灰度图像以及对应的半调图像构成样本集{(Gk, Hk) |1≤k≤P}，Gk表示第k幅连续灰度图像，Hk为与之对应的半调图像。

LUT逆半调方法建表过程如下。

Step1 建表阶段。根据样本集，从中依次取一副连续图和对应的半调图，然后让模板在2幅图像上依次从左至右，从上到下，移动模板，根据图像中像素的分布，形成一张预先计算好的LUT表，直到样本集中的图像全部处理完，利用已求得的查找表，估计未出现的逆半调值，完善LUT表。

Step2 逆半调阶段。利用完整的LUT表，重建连续图像。至此，已经完成了LUT表的建立与图像的逆半调恢复。

2 基于差分进化算法的模板选择

差分进化算法是一种模拟自然界生物进化机制的一种仿生智能算法，最主要的操作思想是基于种群内个体差异度生成临时个体，然后随机重组实现种群进化[8]。DE算法和其它仿生算法一样，具有良好的全局收敛性和鲁棒性，非常适合求解各种最优化问题。DE算法的主要特点是算法简单、收敛速度快和所需领域知识少，在解决复杂的全局优化问题方面，DE算法被实践证明是一种有效的全局最优解的搜索算法。在进化算法框架里有很多类型的算法，J. Vesterstrom和R. Thomsen将差分进化算法、遗传算法、粒子群算法进行实验分析，指出在解决复杂优化问题方面，差分进化算法的收敛速度更快，稳定性更强[9]。

利用差分进化算法求最佳NM领域LUT模板算法，操作如下。

1）编码。LUT最优模板选择是一种非连续值的问题，所以首先要对DE算法的初始种群T0进行随机编码。课题组采用二进制进行编码，编码方式为：对模板进行扫描，从左上角开始，按照从左至右，从上到下的顺序扫描，构成个体，其中表示个体T0(m)的第j个基因，N表示模板大小，pop表示种群的规模，m表示种群T0中的第m个个体T0(m)。一个LUT模板个体可如图3所示，则个体T0(m)的编码为{I1I2I3I4I5I6I7I8I9I10I11I12I13I14I15I16I17I18I19I20I21I22I23I24I25}，解码是编码的逆过程。

图3 一个LUT模板个体Fig. 3 An individual LUT template

2）变异操作。在对当前种群的评价函数计算之后，需要对种群中的个体进行扰动，使种群进化。具体的扰动操作如下：在种群Ti中随机产生3个互不相同的整数r1, r2, r3{1, 2, …, pop}，且要求r1≠r2≠r3≠m，先将个体Ti(r1), Ti(r2), Ti(r3)转换成实数，然后按照式（3）产生变异个体Vi(m)，之后把变异个体Vi(m)转换成二进制形式，即

式中F表示缩放因子，取值范围为[0, 2]。

3）交叉操作。首先生成一个随机数Rand {0, 1, 2, ..., N×N-1}，然后对Ti(m)和Vi(m)按照式（4）得到试验个体Ui(m)，即

式中：r为分布于0到1之间的随机数；

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

交叉过程如图4所示，图中r为0和1之间的随机数。

图4 交叉过程Fig. 4 Cross process

4）个体约束。在变异和交叉过程中，有可能会遇到个体中领域像素个数不满足约束条件式（2）的，因此需要对个体进行调整。首先，统计模板个体中1的个数为num，如果num大于M，因为需要保证中心点的位置为1，因此把除中心点之外的1的num-M个位置随机变为0；如果num小于M，则把0的M-num个位置随机变为1；确保个体Vi中1的个数刚好为M个。

5）选择操作。根据交叉操作得到的试验种群Ui和种群Ti，按照式（5）得到新的种群Ti+1中的每个个体Ti+1(m)，其中psnr(Ti(m))和psnr(Ui(m))表示模板个体的评价函数，在这里即是由式（1）求得的平均峰值性噪比。

基于差分进化算法求取LUT图像逆半调最优模板算法的流程图如图5所示，具体步骤如下。

Step1 设定进化参数：种群规模pop，交叉因子为CR，缩放因子为F，进化代数为CYC_NUM,随机生成初始种群T0={T0(0), T0(1),…,T0(m)},其中m {1, 2, …, pop}, T0(x)即为一个模板，然后设种群中的最优个体为bestLut和最优个体的评价函数的值为bestpsnr=0，模板大小为N，模板中有效像素点个数为M。使用初始种群对P对半调图像及其对应连续色调图像进行传统的LUT算法的步骤。然后根据公式（2）计算初始种群每个个体评价函数值psnr(T0(m))。

Step2 对当前的种群Ti按照式（3）进行变异操作,得到变异种群Vi(m)。

Step3 根据原始种群Ti和变异种群Vi(m)按照式（4）得到试验种群Ui(m)，并且按照传统LUT算法的步骤计算试验种群Ui(m)的个体评价函数的值psnr(Ui(m))。

Step4 根据Ti和试验种群Ui(m)按照式（5），得到新的种群Ti+1。同时计算其psnr(Ti+1(x))。把新种群中个体评价函数值最高的并赋值给bestpsnr，同时找到对应的个体存储到bestLut中。

Step5 循环执行Step2～Step4，直到达到最大进化代数CYC_NUM。

图5 基于DE算法的LUT模板选择算法流程图Fig. 5 LUT template selection algorithm flowchart based on DE algorithm

3 实验分析

实验的操作系统为Windows 7，实验平台为Visual Studio 2010以及Opencv 2.4.9。为消除训练样本以及空值估计对模板选择的影响，实验均采用样本大小为50幅256×256的连续图像，以及采用由3种图像半调算法产生的对应的半调图像。这3种方法分别为Floyd-Steinberg、Jarvis和Stucki[1]。求取最佳模板的算法为：DE算法、精英遗传算（elitist genetic algorithm，EGA）、贪心算法（greedy algorithm，GA）以及模拟退火算法（simulated annealing，SA）。4种算法的循环终止条件设置为5代内种群个体没有发生改变或者到达设置的最大迭代次数，求取最佳模板以及对应的训练样本的平均峰值信噪比。

其中，DE算法中设定种群规模pop=20，最大进化代数CYC_NUM=150，缩放因子F=0.5，模板大小N=5，交叉因子CR=0.4；EGA算法实验中的参数设定为：种群规模、最大进化代数及模板大小与DE算法的相同，变异概率设定为0.4。有效像素点个数M=16和M=19的情况下，4种算法求得的最佳模板的平均峰值信噪比如表1中所示，从表中可以看出DE、EGA、GA 3种算法求得的最好的峰值信噪比是一样的，而用SA求得的明显不如其它3种算法，在图6中列出了4中算法求得的最佳模板。

表2中列出4种算法求最佳模板所消耗的时间，GA是一种局部搜索算法，其它3种是全局搜索算法，为了使条件尽可能的相似，实验中将不考虑GA。DE和SA的耗时大约是EGA的2倍，而SA求得的模板结果相对而言也比较差。在实验中发现，虽然DE, EGA 2种算法相同，但是在求解过程中DE算法的收敛速度比EGA速度快，这与文献[9]中的研究相同。对此进行实验验证，2种算法均采用种群大小为20，根据表1设置了表3的循环终止条件，或者是循环次数达到设定的最大循环次数。

表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 循环终止条件（N=5）Table 3 Loop termination conditions （N = 5）

实验结果如图7和图8所示。

图7 DE，EGA循环次数比较（N=5, M=16）Fig.7 The cycle comparison of DE and EGA （N=5, M=16）

图8 DE, EGA循环次数比较（N=5, M=19）Fig. 8 The cycle comparison of DE and EGA（N=5, M=19）

从图中可以看出，在相同条件下达到循环终止条件时，DE算法的收敛次数明显比EGA的收敛次数少。因此，在求最佳模板中，DE算法虽然比EGA算法所消耗的时间多，但是在收敛速度方便，比EGA算法快，同时，从DE算法的流程来看，DE算法十分简单，而且也比EGA收敛速度快，所需领域知识少，只要根据DE算法的步骤，设定好初始值，按照步骤进行设计即可完成对问题的求解。

4 结语

本文提出了一种基于差分进化算法的查找表逆半调模板选择方法，通过与精英遗传算法、贪心算法、模拟退火算法之间进行比较，进行了大量的实验验证，最后得出本文算法在收敛性方便取得了较好的成绩。同时，求得的最佳模板与精英遗传算法、贪心算法的结果相同，比模拟退火算法的结果要好。

[1]孔月萍. 图像逆半调及其质量评价技术研究[D]. 西安：西安电子科技大学，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的图像逆半调改进算法[J]. 计算机技术与发展，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]郑海红，孔月萍，曾 平，等. 误差分散类逆半调技术综述[J]. 中国图象图形学报，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]. 湖南工业大学学报，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的逆半调改进算法[J]. 湖南工业大学学报，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]. 黑龙江大学自然科学学报，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.

（责任编辑：申 剑）

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

国家自然科学基金资助项目（61170102），湖南省研究生科研创新基金资助项目（CX2015B566），湖南省自然科学基金资助项目（2014JJ2115, 2015JJ2046），湖南省教育厅科研基金资助项目（15A049）

叶德刚（1992-），男，湖南岳阳人，湖南工业大学硕士生，主要研究方向为图像处理，E-mail：ye211112@126.com