摘  要： 提出了一種基于離散曲率估計和kd-tree簡化人臉點云的并行EM-ICP配準(zhǔn)算法。首先建立人臉點云的三維空間kd-tree，并結(jié)合離散高斯曲率對點云進(jìn)行了保留幾何特征的簡化,；然后基于CUDA對EM-ICP算法進(jìn)行并行加速,，對簡化的人臉點云進(jìn)行配準(zhǔn)。該算法能夠避免局部配準(zhǔn)等缺陷,，同時EM-ICP算法并行保證了配準(zhǔn)工作的高效,。實驗證實了本文算法的健壯性和穩(wěn)定性。
關(guān)鍵詞： 點云配準(zhǔn),； EM-ICP,； kd-tree； CUDA

    人臉識別是身份認(rèn)證等領(lǐng)域的重要技術(shù),，一直受到眾多研究者的關(guān)注,。隨著三維掃描技術(shù)的發(fā)展及三維掃描的普及應(yīng)用，三維人臉的識別和匹配成為生物特征識別領(lǐng)域的研究熱點之一,。在三維人臉識別與匹配過程中,，有兩個步驟可應(yīng)用點云配準(zhǔn)過程：(1)使用三維掃描儀獲取人臉深度圖像，但要得到完整三維人臉點云數(shù)據(jù)往往需要多次掃描完成,，因為每次掃描得到的點云數(shù)據(jù)往往只是部分人臉表面數(shù)據(jù),，所以需要對掃描得到的人臉深度圖像進(jìn)行配準(zhǔn)； (2)可將待匹配人臉模型與參考庫中人臉模型或兩者對應(yīng)特征進(jìn)行配準(zhǔn),，通過比較配準(zhǔn)誤差來判斷匹配程度,。
    隨著點云數(shù)據(jù)規(guī)模的擴(kuò)大和配準(zhǔn)精度要求的提高，傳統(tǒng)串行點云配準(zhǔn)過程效率較低,；而圖形處理單元GPU(Graphic Processing Unit)可應(yīng)用于并行計算,，適合大規(guī)模數(shù)據(jù)處理，尤其是Nvidia公司推出的統(tǒng)一計算架構(gòu)CUDA(Compute Unified Device Architecture)能為算法并行提供更直觀的編程模型和優(yōu)化原則,，提高點云配準(zhǔn)的運(yùn)算效率,。
    本文基于GPU的高性能并行計算功能以及EM-ICP算法實現(xiàn)了對較大規(guī)模的人臉點云數(shù)據(jù)的并行配準(zhǔn)，實驗證明了本文算法的配準(zhǔn)精度和速度上的顯著提高,。
1 相關(guān)工作
    點云配準(zhǔn)通常采用迭代最近點ICP（Iterative Closest Point)算法[1],，是通過迭代計算使兩點云上對應(yīng)點對或點面的均方誤差最小，以實現(xiàn)點云的精確配準(zhǔn),。ICP算法的不足之處是對初始對齊敏感,，故通常采用主元分析PCA(Principal Component Analysis)等方法進(jìn)行初始配準(zhǔn)，即粗對齊,，再以初始配準(zhǔn)結(jié)果為條件進(jìn)行ICP配準(zhǔn),，即精確對齊。參考文獻(xiàn)[2]將最大期望算法EM(Expectation Maximization algorithm)算法[3]應(yīng)用到ICP算法中,，提出了EM-ICP算法,，從而避免了初始配準(zhǔn)的步驟,。
    由于ICP和EM-ICP算法均含有大規(guī)模矩陣運(yùn)算，串行的配準(zhǔn)工作效率較低,。參考文獻(xiàn)[4]基于CUDA對ICP算法進(jìn)行了并行加速,，實現(xiàn)了深度圖像的實時配準(zhǔn)。參考文獻(xiàn)[5]基于GPU實現(xiàn)了EM-ICP的并行計算,，配準(zhǔn)效率較高,，但由于顯存空間的限制，該工作對規(guī)模較大的點云模型進(jìn)行簡單的隨機(jī)采樣簡化,，其配準(zhǔn)精度存在明確的損失,，本文實驗也證明了該工作在應(yīng)用于人臉點云配準(zhǔn)時存在局部配準(zhǔn)的缺陷。
    解決因隨機(jī)采樣導(dǎo)致局部配準(zhǔn)缺陷的關(guān)鍵在于簡化人臉點云的同時盡可能地保留點云的幾何特征,。曲率是表示形狀的基本特征,，能夠反映人臉三維表面的凹凸變化程度，且對旋轉(zhuǎn),、平移和縮放等變換具有幾何不變性,，依據(jù)離散的高斯曲率估計[6]和kd-tree[7]進(jìn)行人臉點云簡化可以保留足夠的人臉幾何特征。
    本文首先基于離散高斯曲率估計和kd-tree對三維人臉點云進(jìn)行簡化,，然后基于CUDA和EM-ICP算法對簡化點云進(jìn)行并行加速配準(zhǔn),。實驗證明,，本文算法避免了局部配準(zhǔn)的問題,，提高了人臉點云配準(zhǔn)的效率和精確度。
2 利用kd-tree進(jìn)行點云簡化
    本文在簡化點云過程中,，將點云分為關(guān)鍵點與非關(guān)鍵點,。三維人臉原始點云數(shù)據(jù)為X，首先求解點云中每點的高斯曲率,，并與指定閾值進(jìn)行比較,，若高斯曲率大于指定閾值則判定此點為關(guān)鍵點,直接復(fù)制到簡化點云中；若小于指定閾值,，判定此點是非關(guān)鍵點,，再通過kd-tree進(jìn)行k鄰域搜索建立考查球，考查球內(nèi)的點密度,，若點密度大于某閾值,，則標(biāo)記考查球內(nèi)所有點的平均點為關(guān)鍵點，否則將球內(nèi)所有點標(biāo)記為關(guān)鍵點,，據(jù)此實現(xiàn)對非關(guān)鍵點的簡化,。
    算法1 利用高斯曲率和kd-tree進(jìn)行點云簡化[7]
　    輸入：原始點云X
　    輸出：簡化點云XR
    具體步驟如下。
　　(1) 輸入原始點云X,；
　　(2) 對X建立kd-tree,，設(shè)定鄰域半徑,，在鄰域內(nèi)計算每個點的高斯曲率；
　    (3) 設(shè)定閾值,高斯曲率大于閾值的點標(biāo)記為關(guān)鍵點,，并復(fù)制到XR,；
　    (4) 對于非關(guān)鍵點，通過隨機(jī)采樣選取n個隨機(jī)點,；
　　(5) for i=0; i<n; i++ do
　　    以第i點為中心,，利用kd-tree搜索離中心點最
        近的k個點，(a)如果找到的k個點均為非關(guān)鍵
        點,，以中心點為球心,以第k個點到中心點的歐
        氏距離為半徑,，建立考查球； (b)如果找到的離
        中心點最近的第l(l<k)個點是已標(biāo)記的關(guān)鍵點,，
        則以中心點為球心,， 以第l-1個點到中心點的
        歐氏距離為半徑， 建立考查球,； 計算考查球內(nèi)
        點密度,若大于指定閾值,，標(biāo)記考查球內(nèi)所有點
        的平均點為關(guān)鍵點，復(fù)制到XR,；若小于指定閾
        值,，將球內(nèi)所有點標(biāo)記為關(guān)鍵點，復(fù)制到XR,；
　　    i←i+1    
　    end

5 實驗結(jié)果及分析
    實驗所用三維掃描儀的分辨率為640×480,幀頻為24 f/s,。實驗程序運(yùn)行硬件配置為：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 三維人臉點云簡化
    實驗結(jié)果如圖1所示?？梢钥闯?本文基于kd-tree的點云簡化算法對人臉點云中高斯曲率值較大的區(qū)域有很好的保留,，并且可以看到，兩個簡化點云中曲率較大的區(qū)域基本一致,，主要集中在眼,、鼻、口等區(qū)域,，而參考文獻(xiàn)[5]隨機(jī)采樣由于選點的隨機(jī)性難以得到一致性對應(yīng),。

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

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

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

    點云配準(zhǔn)精度直接影響著三維人臉識別和匹配的準(zhǔn)確度。本文提出的基于高斯曲率簡化點云的EM-ICP并行配準(zhǔn)算法實現(xiàn)了三維人臉點云的有效配準(zhǔn),，改進(jìn)了局部配準(zhǔn)等不足,，提高了算法的健壯性，具有較高的實際應(yīng)用價值,。后續(xù)工作將考慮如何基于高斯曲率等幾何信息提取人臉點云的顯著性特征點云,，以期進(jìn)一步提高配準(zhǔn)算法的計算效率和配準(zhǔn)精度。
參考文獻(xiàn)
[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-surfaces-manifolds[M]. 2nd Edition, Kuhnel, Wolfgang: American  Mathematical Society, 2006:158-165.
[7] De Berg M, CHEONG O. Computational geometry: algo-rithms 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/.