摘  要： 提出了一种基于离散曲率估计和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)也证明了本文算法实现在口、鼻处的精确配准。基于简化点云的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/.