交互式差分演化卡通人脸生成*

喻 飞，魏 波

1.闽南师范大学 物理与信息工程学院，福建 漳州 363000

2.华东交通大学 软件学院，南昌 330013

交互式差分演化卡通人脸生成*

喻 飞1+，魏 波2

1.闽南师范大学 物理与信息工程学院，福建 漳州 363000

2.华东交通大学 软件学院，南昌 330013

基于组件的卡通人脸生成分为构件的组合及特征调整两阶段完成，可分别视为组合优化和连续优化问题解决。然而，人脸特征参数优化过程中很难用函数显性表示其优化目标，是典型的隐性目标优化问题。针对此问题，提出基于反向学习策略的交互式差分演化算法（interactive differential evolution algorithm based on opposition-based learning strategy，IDE-OBL），将传统交互式演化算法中人为提供适应值的交互方式转化为成对比较的方式，采用反向学习策略加快算法收敛，在一定程度上减少了用户评价次数。实验结果表明，在基于组件的卡通人脸生成问题中，IDE-OBL比未使用反向学习策略的IGA和IDE要好，减少了演化迭代次数，有利于用户疲劳程度的缓解。

交互式演化算法；差分演化；卡通人脸；反向学习

1 引言

卡通人脸图像是指创作具有卡通风格的人脸肖像，其实现方法得到了不少研究人员的关注。研究成果在影视制作、网络媒介、动画片创作、互联网隐私保护等方面有着广泛的应用。

Winnemöller等人[1]提出了一种图像抽象化框架，通过改变图像的亮度和颜色对比特性来实现人脸图像卡通画效果。宋阳等人[2]通过提取人脸边缘轮廓生成线条画，与可调整的光照图像进行合成。这类方法能最大限度地保留原始人脸照片的特点，但用户在图像生成中干预程度有限，较难完成夸张卡通效果。基于组件库的卡通人脸图像生成方法可以克服此缺点。Liu等人[3]提出的NatureFace基于统计数据建立人脸特征模型，与组件库结合生成人脸卡通图像。Nejad等人[4]采用边缘检测、模板匹配和Hermit插值建立局部组件的轮廓，并将阴影、光照等信息融入其中，通过样本的特征参数调整最终合成图像。Zhang等人[5]在大量数据样例基础上对人脸建模并生成组件库，然后通过组件合成完整的人脸图像。基于组件库可以生成标准的人脸模型，通过特征优化得到符合要求的卡通图像，需要定义大量不同的人脸组件[6]，模型参数的确定来自于统计数据，用户也可以进行参数调整，但此过程依赖于经验，不利于用户创作中的灵感发现。

另外，卡通人脸图像的设计具有主观性，人脸特征随不同用户的需要而变化。现有解决方案中，用户通过交互界面进行特征调整。但是，多数用户适合作图像的评价者而非设计者。换言之，用户能轻易地从整体上评价生成的图像是否符合要求，但很难进行局部特征修改。

针对此问题，本文将交互式差分演化算法用于人脸图像生成，建立一种人机协同工作模式。算法负责生成人脸组件，并合成整体图像，用户负责在线评价，其评价信息反馈至算法中，再次生成可供评价的人脸组件，如此迭代下去，最终获得满足需求的图像，为用户提供创作原型。

2 卡通人脸图像生成

2.1 组件模型设计

人脸组件是指人脸的整体轮廓及各个组成部分，本文用三阶贝塞尔曲线描述，其数学表示形式如式（1）所示。

调节控制点P0、P1、P2和P3的位置就可以控制曲线的形状。如图1所示，用6条首尾相连的曲线描述人脸轮廓，调整控制点的位置就能获得不同的人脸形状。控件可独立进行调整，如放大、缩小、平移等。此外，通过设置关键点可获得更多特征信息，本文在文献[7]的基础上定义了组件的关键点，图2给出了部分关键点的位置。

表1列出了部分关键点及相关特征参数的计算方法，其中x和y分别表示关键点在二维绘图空间上x轴和y轴上的取值。

Table 1 Key points and features in face(parts)表1 人脸关键点及其特征计算（部分）

2.2 模型参数设置

人脸组件在生成图像时需要满足一定的比例约束关系，文献[7]采用固定约束关系生成初始人脸图形。但是这种比例关系并非绝对，只能按照常见人脸比例来确定。实际应用中，卡通人脸本身是抽象的，有些场合可能需要夸张的人物造型。因此，人脸模型参数设置在一定范围以内，并允许可调才更加合理。本文采用与文献[7]中相同的特征参数设置，允许参数在更广的范围内取值，所有的数值归一化至[0,1]区间。表2给出了模型部分参数取值情况，FW和FL分别表示脸宽和脸长，EW指眼睛宽度。

Table 2 Parameters setting of face model(parts)表2 人脸模型参数设置（部分）

卡通人脸模型的参数只能在一定范围内调整，大部分生成系统按照常见审美标准约定优化目标进行参数寻优，或者直接将模型参数的调整设计成交互式界面，由用户去完成调整。前者的问题在于优化目标函数很难确定，后者的缺陷在于交互过程时间开销太大。大部分用户并不具备专业绘画人员的素质，对参数的调节是盲目的。本文所用算法中，差分演化算法用于搜索人脸特征空间，而用户则充当目标函数的功能，是目标的评价者而非设计者，从而加快参数优化过程。

3 交互式演化算法

人脸卡通图像的生成被看成参数优化问题后，演化算法均可完成此项工作。然而，用户需求具有主观性，很难用明确的数学函数描述，是典型的隐性优化问题。作为解决隐性优化问题的代表性方法，交互式演化算法（interactive evolution algorithm，IEA）得到了很多学者的关注。

3.1 交互式遗传算法

早期的IEA应用多采用交互式遗传算法（interactive genetic algorithm，IGA）实现[8-10]，用户与算法的交互表现为提供评价分数作为个体的适应值[11]。IGA种群的一次迭代过程如图3所示，可以看出用户对演化种群中的每个个体均提供适应值。演化个体通过交互界面以显性的形式提供给用户进行评分，采用纯数字评分或者等级制[12]。这种评价方式存在的缺陷是用户给出的评分只能是相对结果，需要向绝对适应值进行映射，增加了算法的复杂性。

Fig.3 An iteration of IGA图3 IGA算法的一次迭代过程

3.2 交互式差分演化算法

不同于IGA，交互式差分演化算法（interactive differential evolution，IDE）不需要用户直接提供演化个体的适应值，而是通过成对比较的方式评价演化种群，这减轻了用户在评价过程中的疲劳程度。近年来，交互式差分演化算法在图像检索[13]、图像增强[14]、图像滤波器[15]等方面均有应用。

IDE基于差分演化算法（differential evolution，DE）实现。DE是一种基于种群差异的启发式随机搜索算法，使用实数编码表示[16]，广泛应用于函数优化问题中。t时刻种群中的第i个个体表示成d维的向量，如式（2）描述：

为了产生下一代种群，对于当前种群中的每一个个体向量Zk(t)，随机选择另外的3个个体，例如Zi(t)、Zj(t)和Zm(t)。计算Zi(t)和Zj(t)两个个体向量的差，并通过缩放因子F（通常的取值区间为[0,1]）进行缩放，其结果加上Zm(t)从而产生一个实验向量Ui(t+1)。那么，对于实验向量Ui(t+1)的第n维分量可以用式（3）表示：

其中，Cr∈[0,1]被称为DE算法的交叉概率。如果新产生的实验向量Ui(t+1)的适应值好于Zm(t)，则在t+1代将其替换，否则保持当前值不变。可以描述如式（4）：

对于式（4），在IDE算法中并不需要计算适应值f(Zi(t))和f(Ui(t+1))，而是将DE算法中这两者的比较直接交由用户去完成。显然，这种一对一的比较评价方式相比IGA中的评分方法，用户疲劳程度会大大减轻。IDE算法中种群的一次迭代过程如图4所示。

4 交互式差分演化算法下的参数优化

4.1 反向策略

Tizhoosh提出了反向学习方法（opposition-based learning，OBL）[17]。OBL通过比较个体及其反向个体的适应值，从而在种群中保证拥有较好适应值的个体在演化过程中生存下来，加速演化算法收敛。此方法被分别应用到差分演化算法[18]和粒子群算法[19]中，在高维问题中获得了较好的实验效果。

反向学习策略的基本思想源于反向数的概念。对于实数x∈[a,b]，其反向数表示如下：

同理，N维空间中的反向数可以这样来定义。假设X=(x1,x2,…,xN)为N维空间中的一点，其中x1,x2,…,xN∈R，xi∈[ai,bi]，∀i∈{1,2,…,N}。反向点中第i个坐标为：

Fig.4 An iteration of IDE图4 IDE算法的一次迭代过程

基于反向点的概念，反向优化方法这样定义。假设学习X=(x1,x2,…,xN)是N维空间中的一点（即问题的一个候选解），f(·)为适应值函数，即计算候选解的适应值。根据反向点的概念可得到X=(x1,x2,…,xN)的反向点为。如果存在f(X)≥，也就是比X有更好的适应值，用代替X，否则种群中X保持不变。

4.2 反向交互式差分演化算法

基于反向学习的交互式差分演化算法的伪代码见算法1，在DE算法中OBL一般用在两个阶段，即基于反向的种群初始化和演化群体跳跃[18,20]。其中，加粗部分即第7、12、24行需设计成人机交互界面形式，即涉及到适应值比较则由个人用户参与评价。具体实现时，只需将演化个体比较选择的过程由用户代替即可。

算法1反向交互式差分演化算法

输入：初始种群P0，初始反向种群OP0，当前种群P，当前反向种群OP，问题维度D，j维变量取值范围[aj,bj]，跳转概率Jr，j维变量在当前种群中的最大值和最小值分别为，种群大小用Np表示。

以上人为干预的3个场合可以使用相同的评价界面。文献[21]提出在交互式差分演化算法中使用OBL，使用户评价的个体变为3个，在模拟实验用户上验证了其效果。本文中，OBL应用在种群的初始化阶段和新种群产生结束后。

基于IDE的卡通人脸生成的人机交互界面如图5所示，每一次演化均需要用户对所有个体进行评价。用户成对评价的可以是个体及其反向个体（算法1第12行），或者是个体及其交叉变异对应的实验解（算法第7行和第24行），其显性表示对应于图5中的标签“T0”和“T1”。用户可以通过图中的单选框“No.0”和“No.1”来选择较好的解。

5 实验结果及分析

本文使用Java实现了算法，并使用SWT设计人机交互界面。为了验证交互式差分演化算法在卡通人脸生成中的效果及其在不同维度数据中的表现，使用了两个不同特征维度的人脸模板，分别为男孩人脸（特征维度Nf=10）和女孩人脸（特征维度Nf=20），其特征值如表3所示，取值归一化至（0,1）范围。为避免用户疲劳且受交互界面的限制，迭代中每次评价的个体不宜过多。本文设置为20个，即演化种群大小Np=20。

Fig.5 Interface for generation of cartoon face图5 人脸卡通图像生成交互界面

Table 3 Face templates and their feature values表3 人脸模板及特征取值

本文提出的算法命名为IDE-OBL，将文献[8]提出的IGA算法作为对比算法，同时也对比了未使用反向学习策略的IDE。算法相关参数设置为：交叉概率Cr=0.6，OBL跳跃概率Jr=0.4，演化迭代终止条件为用户找到满意解。

为了验证反向交互式差分演化算法在卡通人脸图像生成中的使用效果，本文在模拟环境和真实人机交互环境上分别进行了实验。

5.1 模拟评价环境下实验

模拟环境的建立基于这样一种假设：用户对于拟生成的图像有清晰的认识，但无法手动进行特征调节。对于这种情况，用户在评价个体时不存在误评价的可能，能准确无误地选择一对个体中哪一个更符合心理期望。因此，可以事先假定生成目标O(o1,o2,…,oD)已经存在，实验使用表3所示的男孩和女孩头像。用户评价则通过计算演化个体X(x1,x2,…,xD)与目标特征向量的欧式距离来模拟，则演化个体的适应值计算公式为：

IGA算法中，为了解决轮盘赌选择中概率非负的要求，适应值计算公式修订为：

图6和图7分别给出了3种算法在不同维度的卡通人脸特征空间中寻找目标值的收敛曲线变化情况。在D=10时，3种算法在迭代初始阶段表现并无明显差异，在迭代后期，IGA早熟，IDE和IDE-OBL效果较好。在D=20时，IDE-OBL收敛速度和收敛精度明显好于另外两种算法。为获得准确的对比结果，模拟实验中迭代次数t=150，而在真实人机交互环境中，为避免用户疲劳，一般取t≤30为宜。

Fig.6 Evaluation result for cartoon face of 10 dimensions图6 10维卡通人脸模拟评价结果

Fig.7 Evaluattion result for cartoon face of 20 dimensions图7 20维卡通人脸模拟评价结果

Table 4 Experiment result for different users on different feature dimensions表4 不同用户在不同特征维度下的实验结果

5.2 人机交互环境下的实验

为了减少用户个体差异造成的噪声，实验中选择5个用户参与实验，要求每个用户进行10次操作，且每个完整的交互周期内，特征可调次数不超过5次。实验前将人脸生成系统的基本原理告知用户，最终统计实验结果的平均情况。

表4给出了5个用户使用IDE-OBL生成卡通人脸图像的一次结果。不难看出，本文算法能在用户可接受的迭代次数内找到满意解。在不限定生成解的条件下，不同用户期望生成的人脸图像是不一样的，因此其获得的卡通人脸图像也形态各异，但均能在30次迭代内找到满意解。

图8、图9和图10分别给出了用户user3使用3种算法IGA、IDE、和IDE-OBL分别生成如表3所示女孩头像时，在演化迭代次数分别为t=5，t=15和t=25时的实验结果（篇幅原因，只取最好4个解）。可以发现，3种算法均能使种群收敛到用户满意的区域，IDE-OBL效果最好。

表5给出了3种交互式演化算法在卡通人脸生成中找到满意解所需要的演化迭代次数。5位参与者要求操作10次，取其中最好5次结果的平均值。不难看出，IDE相比IGA并无明显优势，但是在特征维度较大时，IDE-OBL效果明显。

Table 5 Evaluation times of obtaining satisfactory solution on different feature dimensions表5 不同维度下获得满意解的评价迭代次数对比

Fig.8 Results of IGA图8 IGA算法生成结果

Fig.9 Results of IDE图9 IDE算法生成结果

Fig.10 Results of IDE-OBL图10 IDE-OBL算法生成结果

当然，交互式差分演化算法在每次迭代过程中需要更多的评估时间，但总迭代次数有一定程度的减少，说明OBL策略起了作用。不难理解，OBL在每次种群产生后又重新对解空间进行了一次采样，采样结果被用户进行评价。从而在下次迭代时，用户的选择评价结果被反映在保留下来的个体的基因中。因此，下次迭代的种群中接近满意解的个体会更多一些，加速了算法收敛。

6 结束语

本文使用交互式差分演化算法实现了卡通人脸模型参数的优化，OBL策略加速了算法收敛，能在合理的迭代次数内获得满意解。然而，由于用户参与解的评价，演化种群不宜过大，这限制了搜索空间的大小。另外，因为用户评价时间不能过长，所以演化迭代次数不能过多，否则会造成用户疲劳，形成误判，从而影响最终求解结果。由于反向策略的使用，算法收敛速度加快，较少演化迭代次数也有减轻用户疲劳的趋势，但是反向策略的使用增加了用户评价个体的数量。因此，后续研究中应设计一种筛选机制，从演化种群中选择代表性的解提供给用户进行评价，从而减轻用户评价疲劳。如何在获得更大的搜索空间和减轻用户疲劳之间寻找一种平衡将是后续研究中需要进一步探讨的问题。

[1]Winnemöller H,Olsen S C,Gooch B.Real-time video abstraction[J].ACM Transactions on Graphics,2006,25(3):1221-1226.

[2]Song Yang,Liu Yanli.An algorithm generating human face cartoon portrait including light editing based on photo[J].Journal of Graphics,2015,36(1):83-89.

[3]Liu Yuehu,Su Yuanqi,Shao Yu,et al.A face cartoon producer for digital content service[M]//LNCS 5960:Mobile Multimedia Processing.Berlin,Heidelberg:Springer,2010:188-202.

[4]Nejad S S,Balafar M.Component-based cartoon face generation[J].Electronics,2016,5(4):76.

[5]Zhang Yong,Dong Weiming,Deussen O,et al.Data-driven face cartoon stylization[C]//Proceedings of the SIGGRAPH Asia 2014 Technical Briefs,Shenzhen,China,Dec 3-6,2014.New York:ACM,2014:1-4.

[6]Zhang Yong,Dong Weiming,Ma Chongyang,et al.Datadriven synthesis of cartoon faces using different styles[J].IEEE Transactions on Image Processing,2017,26(1):464-478.

[7]Liu Zhen'an,Liu Xuan.Automatic cartoon face generation based on SVG[J].Measurement&Control Technology,2006,25(5):24-26.

[8]Garcia-Hernandez L,Pierreval H,Salas-Morera L,et al.Handling qualitative aspects in unequal area facility layout problem:an interactive genetic algorithm[J].Applied Soft Computing,2013,13(4):1718-1727.

[9]Koga S,Fukumoto M.A creation of music-like melody by interactive genetic algorithm with user's intervention[C]//Proceedings of the 2014 International Conference on Human-Computer Interaction,Heraklion,Crete,Greece,Jun 22-27,2014.Berlin,Heidelberg:Springer,2014:523-527.

[10]García-Hernández L,Arauzo-Azofra A,Salas-Morera L,et al.Facility layout design using a multi-objective interactive genetic algorithm to support the DM[J].Expert Systems,2015,32(1):94-107.

[11]Lai C C,Chen Yingchuan.A user-oriented image retrieval system based on interactive genetic algorithm[J].IEEE Transactions on Instrumentation and Measurement,2011,60(10):3318-3325.

[12]Sun Xiaoyan,Gong Dunwei,JinYaochu,et al.Anew surrogateassisted interactive genetic algorithm with weighted semisupervised learning[J].IEEE Transactions on Cybernetics,2013,43(2):685-698.

[13]Yu Fei,Li Yuanxiang,Wei Bo,et al.Interactive differential evolution for user-oriented image retrieval system[J].Soft Computing,2016,20(2):449-463.

[14]Lee M C,Cho S B.Interactive differential evolution for image enhancement application in smart phone[C]//Proceedings of the 2012 IEEE Congress on Evolutionary Computation,Brisbane,Australia,Jun 10-15,2012.Piscataway,USA:IEEE,2012:1-6.

[15]Liu Gang,Peng Junzhe,Chen Jie,et al.Image spatial filtering method based on interactive differential evolution strategy[J].Journal of Chinese Computer Systems,2015,36(9):2090-2095.

[16]Storn R,Price K.Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.

[17]Tizhoosh H R.Opposition-based learning:a new scheme for machine intelligence[C]//Proceedings of the 2005 International Conference on Computational Intelligence for Modelling Control and Automation,International Conference on Intelligent Agents,Web Technologies and Internet Commerce,Vienna,Austria,Nov 28-30,2005.Washington:IEEE Computer Society,2006:695-701.

[18]Rahnamayan S,Tizhoosh H R,Salama M M.Oppositionbased differential evolution[J].IEEE Transactions on Evolutionary Computation,2008,12(1):64-79.

[19]Wang Hui,Wu Zhijian,Rahnamayan S,et al.Enhancing particle swarm optimization using generalized oppositionbased learning[J].Information Sciences,2011,181(20):4699-4714.

[20]Ahandani M A,Alavi-Rad H.Opposition-based learning in the shuffled differential evolution algorithm[J].Soft Computing,2012,16(8):1303-1337.

[21]Pei Yan,Takagi H.Triple and quadruple comparison-based interactive differential evolution and differential evolution[C]//Proceedings of the 12th Workshop on Foundations of Genetic Algorithms XII,Adelaide,Australia,Jan 16-20,2013.New York:ACM,2013:173-182.

附中文参考文献:

[2]宋阳,刘艳丽.基于照片的可编辑光照效果卡通人脸生成算法[J].图学学报,2015,36(1):83-89.

[7]刘振安,刘瑄.基于SVG的卡通人脸图形自动生成法[J].测控技术,2006,25(5):24-26.

[15]刘罡,彭浚哲,陈颉,等.交互式差分演化策略图像空间滤波方法[J].小型微型计算机系统,2015,36(9):2090-2095.

Cartoon Face Generation Based on Interactive Differential Evolution*

YU Fei1+,WEI Bo2

1.School of Physics and Information Engineering,Minnan Normal University,Zhangzhou,Fujian 363000,China
2.School of Software,East China Jiaotong University,Nanchang 330013,China

2017-03,Accepted 2017-06.

Components-based cartoon face generation is composed of components combination and features adjustment.These two stages can be solved through combination optimization and continuous optimization respectively.However,when cartoon face feature parameters are optimized,it is difficult to use functions to explicitly express the optimization objectives,which is a typical problem of implicit objective optimization.To solve this problem,this paper proposes the interactive differential evolution algorithm based on opposition-based learning strategy(IDE-OBL),which transforms the interaction method of artificially providing adaptive values by human beings in conventional interactive evolutionary algorithm to the method of pairwise comparison.In this new evolutionary algorithm,oppositionbased learning strategies are applied to accelerate algorithm convergence,which will reduce the user evaluation times to some extent.The experimental results show that in cartoon face generation IDE-OBL is better than conventional IGA and IDE which do not use OBL,IDE-OBL reduces evolution iteration numbers and is beneficial for the ease of user fatigue.

interactive evolutionary algorithm;differential evolution;cartoon face;opposition-based learning

+Corresponding author:E-mail:yufei@whu.edu.cn

10.3778/j.issn.1673-9418.1703020

*The Natural Science Foundation of Fujian Province under Grant No.2015J01270(福建省自然科学基金);the Education and Scientific Research Foundation for Middle-Aged and Young Teachers of Education Department of Fujian Province under Grant No.JAT170352(福建省教育厅中青年教师教育科研项目);the Open Foundation of Key Laboratory of Digital Signal and Image Processing of Guangdong Province under Grant No.2017GDDSIPL-01(广东省数字信号与图像处理技术重点实验室开放课题).

CNKI网络优先出版:2017-06-27,http://kns.cnki.net/kcms/detail/11.5602.TP.20170627.1246.002.html

YU Fei,WEI Bo.Cartoon face generation based on interactive differential evolution.Journal of Frontiers of Computer Science and Technology,2017,11(12)：2023-2032.

A

TP391

YU Fei was born in 1981.He received the Ph.D.degree from Wuhan University in 2015.Now he is an associate professor at Minnan Normal University,and the member of CCF.His research interests include intelligent computing and machine learning,etc.

喻飞（1981—），男，湖北钟祥人，2015年于武汉大学获得博士学位，现为闽南师范大学副教授，CCF会员，主要研究领域为智能计算，机器学习等。

WEI Bo was born in 1983.He received the Ph.D.degree from Wuhan University in 2013.Now he is a lecturer at East China Jiaotong University.His research interests include machine learning and data mining,etc.

魏波（1983—），男，湖北天门人，2013年于武汉大学获得博士学位，现为华东交通大学讲师，主要研究领域为机器学习，数据挖掘等。