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

喻 飛，魏 波

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年于武漢大學獲得博士學位，現為華東交通大學講師，主要研究領域為機器學習，數據挖掘等。