基于模擬退火算法的三維人臉匹配方法

王曉斌，馮魯橋，楊媛靜

(電子科技大學計算機科學與工程學院 成都 611731)

基于模擬退火算法的三維人臉匹配方法

王曉斌，馮魯橋，楊媛靜

(電子科技大學計算機科學與工程學院 成都 611731)

基于模擬退火算法，利用深度信息對三維人臉進行匹配和識別。通過具有全局優化能力的模擬退火算法搜索獲取全局極值，選擇合適的適應度函數MLESAC和SIM控制匹配過程獲得識別結果?；凇坝纱值郊殹钡乃枷?，分3步匹配三維人臉，并對精準匹配階段進行改進，通過選擇合適的區域和分類器能夠更好地應對表情的影響。實驗結果表明，模擬退火算法跳出了局部最優解而獲得了全局優化解，同時通過選擇MLESAC和SIM作為不同匹配階段的適應度函數能夠有效控制匹配過程，提高了識別精準率。

三維人臉匹配; 隨機抽樣最大似然; 模擬退火算法; 曲面滲透測度

隨著信息技術的飛速發展，人們對身份認證的可靠度和方式提出了新的要求，傳統的身份認證技術已經不能滿足人們的需求[1]。作為生物特征識別技術的一種，人臉識別因其符合人類自身的生理視覺習慣，是用戶接受度最高的生物識別方式。

二維人臉識別經過多年的發展已經能夠獲得高識別率，但是單純依靠二維圖像信息的人臉識別存在諸多難題(如表情、姿勢和光照等)，在應用各方面遭受到了巨大的挑戰。而三維人臉識別比二維人臉識別有著顯著的優勢，首先三維人臉富含海量信息；其次，有研究證明三維人臉識別技術使用的形狀信息能夠更好地應對光照和姿勢的挑戰。同時隨著硬件(存儲、計算等設備)的飛速發展以及三維數據采集技術的迅猛發展，越來越多的學者將目光投向了三維人臉識別的研究。完整的三維人臉識別系統主要包括數據采集、預處理、特征提取和匹配，根據匹配結果得出識別結果。三維人臉匹配是最關鍵的步驟，直觀地說就是目標人臉與模型人臉的匹配，根據匹配結果判斷是否所需人臉。常用的三維人臉匹配方法有基于整體特征[2-4]、基于局部特征[5-7]、基于空域信息[8]、基于深度圖[9-10]和雙模態融合[11]，其中基于深度圖的匹配是應用最廣泛的方法。深度圖是三維人臉的主要表達方式，能夠有效避免光照的影響，表示的是深度信息z。常見的方法如ICP、遺傳算法和模擬退火算法等。本文基于模擬退火算法，選取合適的適應度函數——MLESAC和SIM，利用三維人臉的深度信息進行匹配，經過測試驗證，展現了高識別率。

1 基本原理

1.1 模擬退火算法

模擬退火算法(SA)[12]是一種常用的優化算法，通過給予整個搜索過程一個時變且最后趨向零的概率突變性，跳出了局部最優解而具有了全局最優解。SA包括兩重循環：參數的隨機擾動和溫度降低。在初始時給出一個試探解，然后在領域中隨機產生另一個解，該新解要滿足Metropolis所提出的規則限制，而整個變化過程都由控制參數t所決定。對于t的每一次取值，SA都不斷進行“產生?判斷?接受(或舍去)”的多次迭代，當t逐漸減小并逐漸趨向于0時的系統狀態對應優化問題的全局最優解。

1.2 MLESAC算法

隨機抽樣最大似然(MLESAC)算法由文獻[13]提出，被廣泛地應用于估計三維圖像匹配過程中產生的內外點，從而得到最優匹配點。

通過基于MLESAC的孤立點分類方法定義適應度函數為：

式中，N是待匹配圖像A中的點數量；ρ(ri)為：

式中，d是閾值，被稱為距離閾值，它限定了點與點之間距離的最大值。一旦點與點之間的距離高于該閾值，則待匹配點將被視為外點(outlier)；否則視為內點(inlier)。人們所希望的結果是適應度函數F的值最小，即適應度函數的值最小且能夠包含數量最多的內點。

1.3 SIM算法

曲面滲透測度(SIM)[14]基于每個點的曲面法向量定量匹配結果，計算出兩幅圖像的對應點集C(A,B)后，通過計算控制匹配流程和識別結果。SIM的具體步驟如下：

1) 對于A中的點p定義一個n×n的鄰域點集；

2) 尋找p在B中的匹配點c；

3) 計算點p和點c處的法向量np和nc；

4) 計算np和nc的夾角θ；

5) 如果θ

6) 重復步驟1)～步驟5)，直到A中所有點都計算完畢。

一個好的匹配擁有較高的SIM值，而誤差匹配則產生較低的SIM值。誤差匹配時SIM值與值之間的差異相較于MSE更大，即SIM更敏感。但是，SIM只有在已經進行了粗略匹配時才能夠展現其優勢。

2 基于SA的三維人臉匹配

在三維人臉匹配中，由于圖像維數較高，數據信息量大而導致計算量巨大，從而引發識別速度慢。為此，采用了“由粗到細”(coarse to fine)的策略，分兩步或多步匹配圖像。

如圖1所示，利用模擬退火算法進行匹配主要分3步：1) 基于重心的初始匹配；2) 基于MLESAC的SA粗略匹配；3) 基于SIM的SA精準匹配。具體來說，首先利用重心對齊，把兩幅人臉轉換到相同的坐標系；再利用MLESAC作為適應度函數進行粗略匹配，找出對應點；最后通過更精細的方法，采用SIM作為適應度函數選取更準確的對應點，并以SIM值作為識別依據對人臉進行判定。三維人臉識別的判斷基于兩個閾值：1) 識別閾值；2) 拒絕閾值。如果計算結果高于識別閾值，人臉被認定是相互匹配的；如果結果低于拒絕閾值，則被認定是不相互匹配的。

圖1 基于模擬退火算法的三維人臉匹配流程

3 精準匹配的改進實現

3.1 匹配區域改進

三維人臉識別的一個難點就是表情的存在。當進行帶表情人臉VS不帶表情人臉的匹配時，無論匹配與否得到的SIM值都較低，于是很難得到一個精準的匹配結果。針對這個難點，提出一個改進的精準匹配過程。

圖2中，圖2a是沒有改進時所使用的整張人臉區域；圖2b是通過眼角、鼻翼、鼻尖特征點劃分的9塊人臉區域；圖2c中亮區域表示改進后所使用的剛性區域。在沒有改進的精準匹配過程中，SIM的值通過計算所有的匹配點得到。在本文改進的精準匹配過程中，通過權值對剛性區域投以更多的關注，對于不變區域的匹配點給定高權值(如，w=500)；對于變化區域的匹配點給定低權值(如，w=0)。當然，最后計算SIM值時，所有匹配點的權值均為w=1。

圖2 三維人臉區域劃分

3.2 分類器改進

大部分三維人臉識別都是使用整張人臉進行識別判定，或者為了避免表情的影響僅僅使用剛性區域進行識別判定。有些學者也通過選擇不同分類器整合不同的區域進行識別判定，如乘積規則、求和規則等，但文獻[15]證明求和規則比其他的組合分類器更優秀。

為了得到最佳識別結果，本文使用求和規則組合所有區域的SIM值，即C+E+U+F+M得到最后的SIM值來進行識別。在實驗中，通過求和規則整合所有區域得到的識別率達到了99.2%，而其他的整合區域，如C+E+U+F只達到了98.9%，甚至有U+M僅僅達到了86.7%的識別率。

3.3 改進精準匹配流程

在整個精準匹配的過程中，利用模擬退火算法作為搜索對應點的迭代算法；同時利用SIM作為適應度函數來得到最終的對應點集；最后計算最終對應點集的SIM值作為三維人臉識別的依據。根據SIM算法流程、模擬退火算法流程以及本文提出的改進，實現該階段整個匹配過程的具體步驟如下：

1) 獲取目標和模型人臉各個人臉區域粗略匹配后的點集，包括5個區域：鼻子圓形區域C、鼻子橢圓區域E、面部區域上半部分U、整個面部區域F、基于改進SA的面部區域M；

2) 初始化參數；

3) 產生新解；

4) 計算新舊參數下，目標人臉與模型人臉的對應點集；

5) 根據對應點集計算函數差值；

6) 根據模擬退火的各種收斂條件判斷是否接受新解；

7) 同一溫度下，重復執行兩次步驟3)～步驟6)；8) 緩慢降低溫度t，直至達到收斂條件為止，即步驟3)～步驟7)；

9) 得出各個人臉區域的最終坐標變換，并根據SIM得到相應的對應點集，計算各個人臉區域的SIM值；

10) 利用求和規則總和各個區域C+E+U+F+M的值，并以此為依據與閾值相比較得出識別結果。

精準匹配階段，利用SIM作為適應度函數進行更精準的匹配，通過匹配后得到的SIM值來判斷獲得最后的識別結果：如果兩幅圖像均來自同一個人，匹配后會得到較高的SIM值；否則，將會得到一個較低的SIM值。

4 算法的實現與測試

為了驗證算法的健壯性和精準性，分別進行verification實驗、identification實驗和增加迭代次數的實驗。首先進行數據集的分類。

4.1 數據集分類

本文實驗采用3D_RMA數據庫，共計120副人臉，每個人臉有6副圖像，這些人臉都有正面人臉圖像并且具有不同的表情。最常見的表情是：無表情、笑、悲傷、討厭、驚訝。根據圖像是否帶噪聲或者表情把三維人臉數據庫分成4個數據集，數據集的識別難度逐步遞增，具體分類如表1所示。

表1 數據集分類

4.2 verification實驗

參照表1所展示的各數據集，定義其中的一個數據集為gallery數據集，那么其他的數據集就作為probe數據集，實驗通過匹配gallery和probe數據集進行，實驗結果如表2所示。表2的前兩列分別表示相應的gallery和probe數據集，后一列展示了各個數據集的識別率。而圖3和圖4則是三維人臉匹配的兩個示例。其中，圖a表示模型人臉，即位于gallery數據集中的人臉數據；圖b表示待匹配人臉，即位于probe數據集中的人臉數據；圖c表示兩幅人臉匹配后的效果圖，表現為一個“相互滲透”的效果。

圖3是來自相同三維人臉的匹配示例圖，其中，圖3a是中性表情人臉，而圖3b是帶了微笑的表情；圖4是來自不同三維人臉的匹配示例圖，兩幅人臉都是中性表情人臉。

表2 verification識別率

圖3 相同三維人臉匹配示例

圖4 不同三維人臉匹配示例

從定性角度可以看到圖3的“相互滲透”比較多，尤其在下半部人臉，圖4中幾乎沒有表現出“相互滲透”的區域。而從定量角度的SIM值來看，實驗所得的圖3的SIM值比圖4的高。從這里也可以看到本文的方法對中性表情VS帶表情人臉時，具有較好的識別效果。

表2的實驗結果表明，當人臉帶有表情和噪聲時，人臉數據會發生相應的變化，從而增加識別的難度。而從表中的實驗數據也可以看到本文的識別率也不高，尤其是最后的All VS All實驗，只達到了70.8%的結果。

但是在實驗中可以發現，在進行帶表情人臉VS中性人臉的匹配時，改進方法比原始方法更優秀，高了幾乎15%的識別率。

4.3 identification實驗

不同于verification實驗，在identification實驗中，定義4個gallery數據集：

1) Level0：28副人臉；2) Level1：65副人臉；3) First：挑選數據庫中每個人的第一幅人臉，共計20副人臉；4) All：120副人臉。

其中Level0和Level1是verification實驗中的Level0和Level1。對應每個gallery數據集的probe數據集則是包含了該gallery數據集剩下后的所有人臉。

通過觀察表3的實驗結果，本文使用的方法在rank-1的識別下仍然取得了較高的識別率。而表3中的最后一行，與verification實驗一樣，同樣是進行了All VS All的實驗，probe中的每幅人臉都同剩余人臉相匹配，確認每幅人臉的身份，獲得了高達98.3%的識別率。在所有數據集的識別中，All VS All的實驗獲得最高的識別率，是因為一個人可能有多幅人臉被歸類在gallery數據集中，增大了確認身份的機會。

表3 identification實驗：rank-1的識別率

4.4 增加迭代次數

在SA匹配過程中，通過限制迭代次數K減少執行時間，提高執行效率。規定當某一解迭代了K=200次后都沒發生變化時，結束匹配過程，稱該解為最優解。但是，究竟迭代次數對識別率有沒有影響？本文通過增加迭代次數K進行了相關實驗，希望能夠找出迭代次數對識別率是否有沒有影響，或者有多大的影響，能夠提高多大幅度的識別率。在實驗中，為了檢驗增加迭代次數是否能夠提高識別率，同時也為了提高效率，并沒有對所有的SA識別過程都增加K值，而是只有當人臉被錯誤接受或者錯誤拒絕時，才增加K為2 000。

表4展示了增加迭代次數后，verification實驗和rank-1下identification實驗的識別率。通過觀察發現，在SA的搜索過程中，通過增加迭代次數K可以提高識別率。但是相應的，會增加匹配所需的時間成本。

表4 增加迭代次數實驗

以上所有的實驗結果表明，SIM在三維人臉識別中是一個很好的適應度函數，不僅對識別結果敏感，還能對整個識別過程進行控制。同時，也驗證了分階段進行匹配和改進方法的健壯性和精準性。

5 結 論

通過上面的分析以及實驗結果可以得出以下結論：1) SA開辟了求解組合優化問題的新途徑，與其他局部搜索算法(如爬山算法)的最大區別在于，SA能夠在迭代過程中接受更糟的解決方案。就是因為這個不同點，SA并不趨向于局部最小，而能夠無限接近于全局最優解。2) 通過選擇正確的人臉區域能夠有效克服表情帶來的影響，提高識別率。3) 通過選擇正確的分類器能夠提高識別率。4) 提出的改進方法對帶表情人臉VS不帶表情人臉的匹配獲得高識別率，但是對帶表情人臉VS帶表情人臉的匹配無法獲得良好的效果，仍需進一步加強對人臉表情處理方法的研究。

[1] 琚生根, 周激流, 何坤, 等. 頻域光照歸一化的人臉識別[J]. 電子科技大學學報, 2009, 38(6): 1021-1026. JU Sheng-gen, ZHOU Ji-liu, HE Kun, et al. Face recognition based on illumination normalization in frequency-domain[J]. Journal of University of Electronic Science and Technology of China, 2009, 38(6): 1021-1026.

[2] GUNLU G, BILGE H S. 3D face decomposition and region selection against expression variations[J]. Internation Conference on Pattern Recognition, 2010, 323: 2-3.

[3] BRONSTEIN A M, BRONSTEIN M M, KIMMEL R. Expression invariant 3D face recognition[C]//Proc Int’l Conf Audio-and Video-Based Biometric Person Authentication. Berlin Heidelberg: Springer, 2003: 62-70.

[4] HESHER C, SRIVASTAVA A, ERLEBACHER G. A novel technique for face recognition using range imaging[J]. Proc Int’l Symp Signal Processing and Its Applications. [S.l.]: IEEE, 2003: 201-204.

[5] BERRETTI S. 3D face recognition using iso-geodesic stripes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(12): 4-10.

[6] WANG Yue-ming, LIU Jian-zhuang. Robust 3D face recognition by local shape difference boosting[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(10): 7-9.

[7] 王躍明. 表情不變的三維人臉識別[D]. 杭州: 浙江大學, 2007. WANG Yue-ming. Research on 3D face recognition across expression[D]. Hangzhou: Zhejiang University, 2007.

[8] WANG Y, PAN G, WU Z. Exploring facial expression effects in 3D face recognition using partial ICP[C]//Proc Asian Conf Computer Vision. Berlin Heidelberg: Springer, 2006, 3851: 581-590.

[9] GIVENS G, BEVERIDEG R, DRAPER B. A statistical assessment of subject factors in the PCA recognition of human faces[C]//Proceedings of the 2003 Conference on Computer Vision Pattern Recognition Workshop (CVPRW’03). [S.l.]: IEEE, 2003.

[10] CHANG K I, BOWYER K W. Multiple nose region matching for 3D face recognition under varying facial expression[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(10): 3-5.

[11] 李永安. 基于幾何信息的三維人臉識別研究[D]. 蘭州:蘭州大學, 2010。LI Yong-an. 3D face recognition using geometric information[D]. Lanzhou: Lanzhou University, 2010.

[12] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing science[J]. Science, 1983, 220(4598): 671-680.

[13] TORR P, ZISSERMAN A. MLESAC: a new robust estimator with application to estimating image geometry[J]. Computer Vision and Image Understanding, 2000, 78: 138-156.

[14] SILVA L, BELLON O R P, BOYER K L. Precision range image registration using a robust surface interpenetration measure and enhanced genetic algorithms[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(5): 2-10.

[15] KITTLER J, HATEF M, DUIN R, et al. On combining classifiers[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998, 20(3): 226-239.

編輯漆 蓉

3D Face Registration on Simulated Annealing Algorithm

WANG Xiao-bin, FENG Lu-qiao, and YANG Yuan-jing
(School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731)

Based on simulated annealing algorithm, this paper uses depth information to register and recognize 3D faces. The simulated annealing algorithm (SA) with global optimization capability is applied to search the global extremes, the appropriate fitness-maximum likelihood estimation sample consensus (MLESAC) and surface interpenetration measure (SIM) are selected to control the registering process for obtaining the recognition results. Based on ‘coarse to fine’, we use three steps to register the 3D faces and improve the fine alignment stage. By choosing appropriate regions and classifier, we can better respond to the expression. Simulation results show that simulated annealing algorithm can escape from local optimal solution, and converge to the global optimal solution quickly. Furthermore, MLESAC and SIM would help to effectively control the registering process, thus can improve the recognition accuracy.

3D face registration; MLESAC; SA; SIM

TP391.4

A doi:10.3969/j.issn.1001-0548.2015.04.018

2013 ? 12 ? 29；

2015 ? 04 ? 28

國家自然科學基金(61273308)

王曉斌(1964 ? )，男，博士，教授，主要從事計算智能方面的研究.