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

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

5 實驗結果及分析
    實驗所用三維掃描儀的分辨率為640×480,幀頻為24 f/s。實驗程序運行硬件配置為：Intel Celeron 2.66 GHz處理器，1 GB內存，GeForce GTS 250顯卡，128個CUDA處理器核心，1.1 GHz顯存頻率，1 GB顯存容量。系統環境：Gentoo Linux，CUDA 4.1，GCC4.5.3。
5.1 三維人臉點云簡化
    實驗結果如圖1所示。可以看出,本文基于kd-tree的點云簡化算法對人臉點云中高斯曲率值較大的區域有很好的保留，并且可以看到，兩個簡化點云中曲率較大的區域基本一致，主要集中在眼、鼻、口等區域，而參考文獻[5]隨機采樣由于選點的隨機性難以得到一致性對應。

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

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

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

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