董 琳， 何 揚

(1.遼寧師范大學 計算機與信息技術(shù)學院，遼寧 大連116081；2.大連電子學校，遼寧 大連116023)

人臉識別是身份認證等領域的重要技術(shù)，一直受到眾多研究者的關(guān)注。隨著三維掃描技術(shù)的發(fā)展及三維掃描的普及應用，三維人臉的識別和匹配成為生物特征識別領域的研究熱點之一。在三維人臉識別與匹配過程中，有兩個步驟可應用點云配準過程：(1)使用三維掃描儀獲取人臉深度圖像，但要得到完整三維人臉點云數(shù)據(jù)往往需要多次掃描完成，因為每次掃描得到的點云數(shù)據(jù)往往只是部分人臉表面數(shù)據(jù)，所以需要對掃描得到的人臉深度圖像進行配準；(2)可將待匹配人臉模型與參考庫中人臉模型或兩者對應特征進行配準，通過比較配準誤差來判斷匹配程度。

隨著點云數(shù)據(jù)規(guī)模的擴大和配準精度要求的提高，傳統(tǒng)串行點云配準過程效率較低；而圖形處理單元GPU(Graphic Processing Unit)可應用于并行計算，適合大規(guī)模數(shù)據(jù)處理，尤其是Nvidia公司推出的統(tǒng)一計算架構(gòu)CUDA(Compute Unified Device Architecture)能為算法并行提供更直觀的編程模型和優(yōu)化原則，提高點云配準的運算效率。

本文基于GPU的高性能并行計算功能以及EM-ICP算法實現(xiàn)了對較大規(guī)模的人臉點云數(shù)據(jù)的并行配準，實驗證明了本文算法的配準精度和速度上的顯著提高。

1 相關(guān)工作

點云配準通常采用迭代最近點ICP（Iterative Closest Point)算法[1]，是通過迭代計算使兩點云上對應點對或點面的均方誤差最小，以實現(xiàn)點云的精確配準。ICP算法的不足之處是對初始對齊敏感，故通常采用主元分析PCA(Principal Component Analysis)等方法進行初始配準，即粗對齊，再以初始配準結(jié)果為條件進行ICP配準，即精確對齊。參考文獻[2]將最大期望算法EM(Expectation Maximization algorithm)算法[3]應用到 ICP算法中，提出了EM-ICP算法，從而避免了初始配準的步驟。

由于ICP和EM-ICP算法均含有大規(guī)模矩陣運算，串行的配準工作效率較低。參考文獻[4]基于CUDA對ICP算法進行了并行加速，實現(xiàn)了深度圖像的實時配準。參考文獻[5]基于GPU實現(xiàn)了EM-ICP的并行計算，配準效率較高，但由于顯存空間的限制，該工作對規(guī)模較大的點云模型進行簡單的隨機采樣簡化，其配準精度存在明確的損失，本文實驗也證明了該工作在應用于人臉點云配準時存在局部配準的缺陷。

解決因隨機采樣導致局部配準缺陷的關(guān)鍵在于簡化人臉點云的同時盡可能地保留點云的幾何特征。曲率是表示形狀的基本特征，能夠反映人臉三維表面的凹凸變化程度，且對旋轉(zhuǎn)、平移和縮放等變換具有幾何不變性，依據(jù)離散的高斯曲率估計[6]和 kd-tree[7]進行人臉點云簡化可以保留足夠的人臉幾何特征。

本文首先基于離散高斯曲率估計和kd-tree對三維人臉點云進行簡化，然后基于CUDA和EM-ICP算法對簡化點云進行并行加速配準。實驗證明，本文算法避免了局部配準的問題，提高了人臉點云配準的效率和精確度。

2 利用kd-tree進行點云簡化

本文在簡化點云過程中，將點云分為關(guān)鍵點與非關(guān)鍵點。三維人臉原始點云數(shù)據(jù)為X，首先求解點云中每點的高斯曲率，并與指定閾值進行比較，若高斯曲率大于指定閾值則判定此點為關(guān)鍵點,直接復制到簡化點云中；若小于指定閾值，判定此點是非關(guān)鍵點，再通過kdtree進行k鄰域搜索建立考查球，考查球內(nèi)的點密度，若點密度大于某閾值，則標記考查球內(nèi)所有點的平均點為關(guān)鍵點，否則將球內(nèi)所有點標記為關(guān)鍵點，據(jù)此實現(xiàn)對非關(guān)鍵點的簡化。

算法1利用高斯曲率和kd-tree進行點云簡化[7]

輸入：原始點云X

輸出：簡化點云XR

具體步驟如下。

(1)輸入原始點云X；

(2)對 X建立 kd-tree，設定鄰域半徑，在鄰域內(nèi)計算每個點的高斯曲率；

(3)設定閾值,高斯曲率大于閾值的點標記為關(guān)鍵點，并復制到 XR；

(4)對于非關(guān)鍵點，通過隨機采樣選取n個隨機點；

(5)for i=0;i

以第i點為中心，利用kd-tree搜索離中心點最近的k個點，(a)如果找到的k個點均為非關(guān)鍵點，以中心點為球心,以第k個點到中心點的歐氏距離為半徑，建立考查球；(b)如果找到的離中心點最近的第l(l

end

3 EM-ICP配準算法

對待配準人臉點云X和Y，經(jīng)過點云簡化后得到人臉簡化點云 XR和 YR，對于 EM-ICP算法，點云 YR中的每個點都可與xRi有對應關(guān)系，以權(quán)重來表示配準概率。因此，EM-ICP算法通過最小化誤差函數(shù)式(1)以找到旋轉(zhuǎn)矩陣 R和位移向量 t,使得XR和YR的配準誤差最小[2,5]。

其中,nx、ny表示兩簡化點云規(guī)模;αij表示點 xRi與點 yRj配準的概率：

其中,σp和 d0是常數(shù)，在算法執(zhí)行中指定。

所以，EM-ICP算法最終就是找到最優(yōu)的R、t使目標函數(shù)式(1)最小，從初始條件 R=I和 t=0到最優(yōu) R、t的過程中，反復迭代應用EM的算法思想，故稱為EMICP算法。

4 EM-ICP算法并行加速

EM-ICP算法中含有大規(guī)模矩陣乘等相關(guān)運算，可利用GPU進行并行加速。并行加速的關(guān)鍵在于把原算法的運算過程分為向量與矩陣間運算以及矩陣內(nèi)元素間運算，從而利用CUBLAS (CUDA Basic Linear Algebra Subprograms)[9]來加速向量與矩陣間的運算，并利用CUDA kernel函數(shù)加速矩陣元素間的運算[5]。利用CUBLAS及CUDA kernel函數(shù)對EM-ICP算法進行并行加速算法如下。

算法2基于CUDA的并行加速EM-ICP算法[5]

輸入：簡化點云 XR、YR，初始配準 R0、t0

輸出：R、t。

具體步驟如下：

(1)XR、YR、Rk-1、tk-1初始化，并拷貝至顯存；

(2)CUDA運行環(huán)境及CUBLAS初始化；

(4)計 算 Ci：

①用CUBLAS sgemv函數(shù)求解A的每行元素和，A1→C,C=(C1,…,Cny)T；

(5)虛對齊

②用 CUDA kernel函數(shù)來計算矩陣 XR′中每一個元素 X′Ri除以 λi；

(8)將X?和Y?及部分中間數(shù)據(jù)拷回內(nèi)存；

(9)利用四元數(shù)方法[8]求解 R*、t*,輸出 R*、t*。

在算法2中，通過CUBLAS相關(guān)函數(shù)計算的部分可直接在程序中調(diào)用相關(guān)CUBLAS API函數(shù),如sgemv、saxpy、sgemv、sasum 等；步驟(4)中的③、步驟(5)中的②和步驟(7)中的CUDA kernel函數(shù)是手工編寫的，實現(xiàn)相應步驟中的計算，并在程序中可控制執(zhí)行。

5 實驗結(jié)果及分析

實驗所用三維掃描儀的分辨率為640×480,幀頻為24 f/s。實驗程序運行硬件配置為：Intel Celeron 2.66 GHz處理器，1 GB內(nèi)存，GeForce GTS 250顯卡，128個 CUDA處理器核心，1.1 GHz顯存頻率，1 GB顯存容量。系統(tǒng)環(huán)境：Gentoo Linux，CUDA 4.1，GCC4.5.3。

5.1 三維人臉點云簡化

圖1 參考文獻[5]隨機采樣結(jié)果與本文簡化算法結(jié)果對比

實驗結(jié)果如圖1所示。可以看出,本文基于kd-tree的點云簡化算法對人臉點云中高斯曲率值較大的區(qū)域有很好的保留，并且可以看到，兩個簡化點云中曲率較大的區(qū)域基本一致，主要集中在眼、鼻、口等區(qū)域，而參考文獻[5]隨機采樣由于選點的隨機性難以得到一致性對應。

5.2EM-ICP算法應用于人臉點云配準效果

由于參考文獻[5]隨機采樣的人臉點云中臉部點所占比重較大，應用EM-ICP算法進行點云配準可能會出現(xiàn)局部配準的缺陷，即：對臉部實現(xiàn)較好配準，而對眼、鼻、口等部位未完全對齊。圖2(a)是隨機采樣點云對齊后的截面圖，可見在對兩采樣點云的鼻、口等部位配準出現(xiàn)一定偏差；圖2(b)和圖2(c)是采用本文點云簡化算法配準結(jié)果的截面圖，效果均比圖2(a)的配準好。

圖2 參考文獻[5]隨機采樣方法與本文點云簡化算法的EM-ICP配準效果截面圖比較

本文點云簡化算法能夠保留更多眼、鼻、口等部位的點，增加這些部位的比重，因此可以避免圖2(a)所示的局部配準情形。整體配準效果如圖3所示，可以看出，最終配準結(jié)果均較為理想，兩人臉點云實現(xiàn)很好對齊，下巴等點云連接處過渡平滑，圖2(b)和圖 2(c)也證明了本文算法實現(xiàn)在口、鼻處的精確配準?；诤喕c云的EM-ICP算法在人臉點云配準中能夠避免局部配準，提高配準算法魯棒性。

5.3 EM-ICP算法并行加速

利用參考文獻[5]的方法實現(xiàn)了基于CUDA的EM-ICP算法并行，加速效果明顯，針對不同點云規(guī)模的EM-ICP并行與串行效率對比如圖4所示，最大加速比可達近450倍。

圖3 基于本文點云簡化的EM-ICP算法人臉點云配準實驗效果圖

圖4 不同點云規(guī)模下EM-ICP算法并行與串行實現(xiàn)效率比較

點云配準精度直接影響著三維人臉識別和匹配的準確度。本文提出的基于高斯曲率簡化點云的EM-ICP并行配準算法實現(xiàn)了三維人臉點云的有效配準，改進了局部配準等不足，提高了算法的健壯性，具有較高的實際應用價值。后續(xù)工作將考慮如何基于高斯曲率等幾何信息提取人臉點云的顯著性特征點云，以期進一步提高配準算法的計算效率和配準精度。

[1]BESL P J,MCKAY N D.A method for registration of 3-d shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2)：239-256.

[2]GRANGER S,PENNEC X.Multi-scale EM-ICP：a fast and robust approach for surface registration[C].Proceedings of the 7th European Conference on Computer Vision，Copen-hagen,Denmark：Springer-Verlag,2002：418-432.

[3]DEMPSTER A,LAIRD N,RUBIN D.Maximum likelihood estimation from incomplete data via EM Algorithm[J].Journal of the Royal Statistical Society,1977,39(1)：1-38.

[4]CHOI S I,PARK S Y,KIM J,et al.Multi-view range image registration using CUDA[C].Proceedings of the 23rd International Technical Conference on Circuits/Systems,Computers and Communications,2008：733-736.

[5]TAMAKI T,ABE M,RAYTCHEV B,et al.Softassign and EM-ICP on GPU[C].Proceedings of the 2010 1st International Conference on Networking and Computing,Washington DC,USA：IEEE,2010：179-183.

[6]WOLFGANG K.Differential geometry：curves-surfacesmanifolds[M].2nd Edition,Kuhnel,Wolfgang：American Mathematical Society,2006：158-165.

[7]De Berg M,CHEONG O.Computational geometry：algorithms and applications[M].3rd Edition,New York：Springer,2008：99-105.

[8]HORN B P.Closed-form solution of absolute orientation using unit quaternions[J].Journal of the Optical Society of America,1987：629-642.

[9]Nvidia.CUDA CUBLAS Library[Z].http：//cudazone.nvidia.cn/cublas/.