统 仿 真 学 报 V ol. 20 No. 9
2008年5月 Journal of System Simulation May, 2008
第20卷第9期 系
基于高斯曲率极值点的散乱点云数据特征点提取
马骊溟，徐 毅，李泽湘
（哈尔滨工业大学深圳研究生院, 深圳 518055）
摘 要：提出了一种快速提取散乱点云数据特征点方法，首先求出空间一点邻域内的曲面片模型，在
此基础上利用梯度法搜索曲面上的高斯曲率极值点。然后再以该点作为搜索曲率极值点的初始点，根据判定准则搜索该点附近的曲率极值点。曲率极值点的搜索方法是边拟合局部曲面边搜索高斯曲率极值点，在搜索曲率极值点时，只需计算高斯曲率极值点附近点的曲率值。避免了传统算法中由于需要求出所有测量点的曲率值，然后进行比较求得曲率极值点而耗时间的缺点，从而提高了搜索效率。 关键词：特征点提取；曲率极值点；反求工程；高斯曲率
中图分类号：TP13 文献标识码：A 文章编号：1004-731X (2008) 09-2341-04
Extracting Feature Points for Scattered Points Based on Gauss Curvature Extreme Point
MA Li-ming, XU Yi, LI Ze-xiang
(Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen 518055, China)
Abstract: A fast method was proposed to extract the feature points from scattered point sets. A local surface was constructed from a spatial point and its nearest neighbors, from which the maximal point of Gaussian curvature was computed by means of gradient searching. Taking this point as start point, the maximal curvature point was searched near the area of this point. An advantage of the scheme is the local surface was fitted, at the same time, the maximal point of Gaussian curvature was computed. When the maximal curvature point was calculated, only the area of maximal Gaussian curvature was searched. It could avoid the drawback of the computing the curvature for the whole points and the time cost of comparing the maximal curvatue point. So the new scheme has higher searching efficiency.
Key words: feature point extraction; curvature extreme point; reverse engineering; Gaussian curvature
引 言
通常情况测量得到的曲面表面信息为三维坐标信息，随着测量坐标系的改变，三维坐标值也发生改变，因此无法准确获得曲面真实信息。特征点是最基本的曲面几何形状的特征基元，它不会因为坐标系的改变而发生变化。因此特征点的获得，对反求工程中的测量数据曲面分割技术[1-5]和测量数据多视角拼合技术
[6-7]
过这些模型都是对原散乱点的逼近表示，其过程复杂，形状逼近精度不能很好保证。胡[5]方法与文献[4]相似，只是在求取曲率极值点的方法上做了优化。以上基于曲率的散乱测量点的特征点提取算法的共同缺点是需要计算每个测量点的曲率值，然后通过比较找到曲率极值点，因此计算效率不高。针对以上算法的不足，本文提出了一种的计算曲率极值点的新方法，首先通过搜索高斯曲率极值点获得搜索曲率极值点的初始点，然后根据该点沿着主曲率方向给出的极值点判定方法确定搜索该点邻域其余的主方向上的极值点。该方法避免了求解每一个测量点的曲率值，因此搜索效率大大提高。
起着相当重要的作用。针对不同的
数据来源，特征点的提取方法分为扫描数据[1]和完全散乱测量数据[2-5]的特征提取方法。本文研究的是散乱测量点的特征点提取方法。Woo 认为测量点的法矢或曲率的突变是一个区域与另一个区域的边界，将法矢或曲率的突变点作为特征点。吕[3]根据OCS(Orthogonal Cross Section)模型估算出各点处的法矢，利用法矢和邻点拟合一张二次曲面，计算该二次曲面的主曲率和主方向，主曲率在主方向的极值点被确定为特征点。Huang [4]在完成数据点三角网格化的基础上，估算各测点的法矢和曲率，把曲率极值点作为边界特征点。不
收稿日期：2007-01-19 修回日期：2007-08-07 基金项目：国家自然科学基金资助项目(50505009)
作者简介：马骊溟(1971-), 女, 博士后, 研究方向为CAD/CAM及机电一体化; 徐毅(1979-) , 男, 博士生, 研究方向为先进电子制造、优化设计、精密测量与工程; 李泽湘, 男, 教授, 博导, 长江学者, 研究方向为机器人、先进制造、运动控制。
[2]
1 曲率极值点定义
在反求过程中，测量数据分片区域和多视角数据配准的重叠区域中，存在这样的点，该点的2个主曲率(k 1和k 2) 中任何一个沿着对应的主方向上为极值，那么该点称为曲率极值点。
那若高斯曲率K 有极值点 则K 的偏导数K u 和K v 为零，么
K u =(k1⋅k 2) u =k1u ⋅k 2+
k1⋅k 2u =0K v =(k1⋅k 2) v =k1v ⋅k 2+k1⋅k 2v =0
(1)
若k 1和k 2不为零(高斯曲率K ≠0) ，则要使公式(1)成
立则必
k1u =k 2u =k1v =k 2v =0 (2)
• 2341 •
2008年5月 系 统 仿 真 学 报 May, 2008
由公式(2)可以推出，k 1、k 2也为极值点，这说明高斯是曲率极值点的特殊曲率极值点也是2个主曲率的极值点，
情况，即在该点的两个主方向上都是曲率极值点(因为通常意义上的曲率极值点只是沿着一个主方向的曲率为极值就可以了，不需要同时达到极值) 。因此在该点的邻域附近的点沿某一主方向存在曲率极值点，具体是极大值还是极小值根据该点的局部形状确定
由微分几何[8]可知，高斯曲率K 是主曲率的乘积，其符号可以确定曲面上的点的性质，表明该点是椭圆点(K >0)、抛物点(K =0)还是双曲面(K 0、H =0在数学上相互矛盾，因而是不存在的。
表1 点的局部曲面类型
序号
K
H
曲面类型
k1 k2 k1 > 0, k2 > 0 k1 = 0, k2 > 0 k1 0, |k1| 0, |k1| = |k2|
k1 = 0, k2 =0 k1 0, |k1| > |k2|
k1
几何描述
点在所有方向上局部为凸 点局部为凸, 在一个方向上为平
点在大部分方向上局部为凸，在小部分方向上为凹
点的局部为凸凹分布各占半
平面
点在所有方向上局部均为凹 点局部为凹, 在一个主方向上为平
点在大部分方向上局部为凹，在小部分方向上为凸
1 >0 >0 峰 2 0 >0 脊 3 0 鞍形脊 4 0 0 0 不存在
表1中的8种曲面形式中，高斯曲率K = 0的这3种曲
=
(在下面将面形式中不存在高斯曲率极值点，因此不予考虑==K 的正负分为两类： 会讨论) ，将其余5种根据
=
=
高斯曲率极值点的搜索过程是一个寻优过程，即在整个数据点中搜寻高斯曲率极大值点或极小值点。由于我们是在整个曲面上找出极值点，而不是最值点，因此不必采用具有全局优化功能的优化方法，可以采用有局部优化功能的梯度法。然而梯度法在搜索到一个极值点后就会停止搜索。为了搜索到所有的高斯曲率极值点，本文采用曲面分片搜索。即首先将数据点进行栅格化，然后在每个栅格里搜索高斯曲率极值点，直至搜索所有的栅格。
1) 当K > 0时，存在两种情况：
当H > 0，在最大主曲率方向上存在曲率极大值 当H
=
2) 当K
当H >0，在最大主曲率方向上存在曲率极大值 当H
由以上可以看出无论高斯曲的极值点的高斯曲率值是正还是负，只要根据平均曲率的正负就可决定是沿着最大主曲率方向上搜索曲率极大值，还是沿着最小主曲率方向上搜索曲率极小值。
当高斯曲率K =0时，对应在表1的三种曲面分别为2、5和7曲面。其中第5种是平面不存在曲率极值点，不与考虑；
图1 高斯曲率极值点的搜索
第2种曲面：k 1=0，H = k 2 / 2；第7种曲面：k 2=0，H = k 1/2。
虽然这后两种曲面形式不存在高斯曲率极值点，但仍然因此当搜存在平均曲率H 的极值点(也就是主曲率极值点) 。索不到高斯曲率极值点时，可以搜索平均曲率极值点。
从以上分析可以得知，高斯曲率极值点(平均曲率极值点) 必然是曲率极值点，而曲率极值点不一定是高斯曲率极值点，因此可以将高斯曲率极值点作为搜索曲率极值点的初始点。
如图1，首先搜索P 点的k 邻近点，并将这k+1个点进行局部二次曲面拟合，当局部二次曲面r 0(u, v)拟合完成，以点P 作为起始点搜索这个局部二次曲面上的高斯曲率极值点。当在r 0(u, v)上搜索到曲率极值点C 1时，用点C 1的k 近邻再拟合成一个二次曲面r 1(u, v)，并以点C 1作为起始点搜索这个局部二次曲面上的曲率极值点C 2。然后再以点C 2作依此类推，直为起始点搜索k 近邻点拟合二次曲面r 2(u, v)。
至搜索到整张曲面上的曲率极值点。整个迭代搜寻过程只有起始点是数据点，其后的迭代过程中的起始点（例如C 1和C 2）不一定是数据点，而是拟合二次曲面上的点。
高斯曲率极值点的搜索过程分为两步，首先搜索极大值，然后搜索极小值。无论极小值还是极大值都称为基于高
2 曲率极值点初始点的搜索
在搜索曲率极值点的初始点时，首先搜索高斯曲率极值点，如果搜索不到再搜索平均曲率极值点，搜索方法相同。因此下面只介绍高斯曲率极值点的搜索过程。
• 2342 •
2008年5月 马骊溟，等：基于高斯曲率极值点的散乱点云数据特征点提取 May, 2008
斯曲率的特征点。然后以该点作为搜索主曲率极值点的初始点。当搜索不到高斯曲率点时，搜索平均曲率极值点。
的栅格。计算P 点与下一个栅格内所有点构成的矢量与M 1+的夹角θ，给定阈值，将夹角过大的点剔除，并按照由小到大的顺序排列，作为候选点。然后重复上述搜索曲率极大值的过程，直到搜索停止；接着沿着的最小主曲率方向的反方向做一个矢量M 1-，重复上面的过程搜索曲率极值点。
3 曲率极值点的搜索
以高斯曲率极值点作为初始点，沿着最大主曲率方向和最小主曲率方向搜索曲率极值点。如图2所示，假设点Q 为高斯曲率极值点，计算Q 点的平均曲率值H (Q ) 。
(2) 如果H (Q )
M 2+、M 2+换成M 1+。同理，沿着最大主曲率方向的反方向做一个矢量M 2-，重复上面的过程。
(1) 如果H (Q )>0，那么在最大主曲率方向上存在曲率极计算大值，首先沿点Q 的最小主曲率方向做一个矢量M 1+，点Q 与所在的栅格内所有点构成的矢量与M 1+的夹角θ，给定阈值，将夹角过大的点剔除，并按照由小到大的顺序排列，这些点作为曲率极值点的候选点。取出序列中第一个点Q 1，如图3所示，沿最大曲率方向M 2找到该点的左右两个邻接点Q 1l 、Q 1r ，如果k 2(Q 1) ≥k 2(Q 1l ) 并且k 2(Q 1) ≤k 2(Q 1r ) ，那么点Q 1是曲率极值点。否则该点不是曲率极值点。对所有候选点进行上述操作，就可以得到该栅格内的沿着最大主曲率方向的曲率的极大值点，并将它们依次储存在链表。取出链表末尾的点P ，沿P 点的最小主曲率方向重新做一个矢量M 1+代替原来的矢量，矢量M 1+所指向的栅格即为将要搜索 极值点 非极值点
(3) 如果H (Q )=0，重复(1)和(2)的步骤。
4 实例
图4(a)为采用激光扫描仪对某鼠标测得表面点云数据。图4(b)为按照本文的算法提取的基于曲率极值点的特征点集。图5(a)为某汽车车灯原始点云数据。图5(b)为按照本文算法将提取到特征点利用自由曲线拟合技术进一步拟合成边界曲线，作为各曲面片之间的边界。
Q
图2 曲率极值点的自动搜索 图3 曲率极值点的判定
(a) 测量点云数据 (b) 基于曲率极值点的特征点
图4 鼠标点云数据特征点提取
(a) 测量点云数据 (b) 点云数据的区域分割
图5 汽车车灯点云数据的边界识取
由于文献[5]方法与文献[4]相似，只是在求取曲率极值点的方法上做了优化。因此本文只进行了本文算法与文献[5]算法的计算，在Pentium4，3.00GHz ，512MB 内存的计算机上运行，用C++语言在VC++6编译器上成功地计算出表2的
数据。其中平均误差e a 和最大误差e m 单位为mm ，耗时单位为s 。从表1中的结果可以看出，精度上两个算法差别不大。在计算效率上本文算法较高，特别当云点数量较大时，优势更为明显。
• 2343 •
2008年5月 系 统 仿 真 学 报 May, 2008
表2 计算结果
特征点 提取方法
汽车车灯(326182点)
平均误差e a
最大误差e m
耗时
平均误差e a
鼠标(28000点)
最大误差e m
耗时
文献[5] 0.031 0.043 29.85 0.024 0.036 5.16 本文 0.027 0.078 18.54 0.029 0.045 4.22
Manufacture (S0890-6955), 2002, 42(2): 167-178.
[3] 吕震, 柯映林, 孙庆, 等. 反求工程中过渡曲面特征提取算法研究
[J]. 计算机集成制造系统, 2003, 9(2): 154-157.
[4] Huang J, Menq C H. Automatic data segmentation for geometric feature
extraction from unorganized 3-D coordinate points [J]. IEEE Transactions on Robotics and Automation (S1042-296X), 2001, 17(3): 268-279. [5] 胡鑫, 习俊通, 金烨. 反求工程中散乱点云数据的自动分割与曲面
重构[J]. 上海交通大学学报, 2004, 38(1): 62-65.
[6] Jun Yongtae, Choi Kuiwon. Automated feature-based registration for
reverse engineering of human models [J]. Journal of Mechanical Science and Technology (S1738-494X), 2005, 19(12): 2213-2223. [7]
Tahir Rabbani, Sander Dijkman. An integrated approach for modeling and global registration of point clouds [J]. ISPRS Journal of Photogrammetry and Remote Sensing (S0924-2716), 2007, 2(61): 355-370.
[8] 吴大任. 微分几何讲义[M]. 北京: 人民教育出版社, 1984:
126-128.
[9] 刘胜兰, 周儒荣, 安鲁陵. 三角网格的数据分块算法[J]. 南京航空
航天大学学报, 2003, 35(6): 653-658.
4 结论
本文提出不需要知道曲面模型而直接根据离散点数据求解曲率极值点的方法。首先根据最小二乘法求出空间一点邻域内的曲面模型，然后在此基础上采用梯度法搜索曲面上的高斯曲率极值点。接着将该点作为搜索曲率极值点的初始点，并沿着主曲率方向搜索该点邻域其余的主方向上的极值点。本文的创新之处在于，不需要求出所有点的曲率值就可以搜索到曲率极值点，极大的提高了计算效率。为反求工程中测量数据的曲面分割和多视角拼合提供了极大的技术支持。
参考文献：
[1] Yang M, Lee E. Segmentation of measured data using a parametric
quadric surface approximation [J]. Computer Aided Design (S1573-4099), 1999, 31(7): 449-457.
[2] Woo H, Kang E, Wang Sem-yung, et al. A new segmentation method
for point cloud data [J]. International Journal of Machine Tools and
（上接第2340页）
从图6中可以看出有DYC 控制的车辆侧向加速度超调量小，达到稳态值的时间少。侧向加速度超调量的减少可以使车辆的转向运动更加平稳。在图8所示的质心侧偏角对比曲线中，可以看出采用DYC 控制的车辆能够控制车辆的质心侧偏角在理想值附近，保持车辆的平衡，提高了车辆的稳定性。
参考文献：
[1] Yoichi Hori. Future Vehicle Driven by Electricity and
Control-Research on Four-Wheel-Motored “UOT Electric March” [J]. IEEE Transaction on Industrial Electronics (S0278-0046), 2004, 51(5), 954-962. [2]
Motoki Shino, Masao Nagai. Yaw-moment control of electric vehicle for improving handling and stability [J]. JSAE Review (S0389-4304), 2001, 22(4), 473-480. [3] [4] [5]
陈晓波, 熊光楞, 郭斌, 张和明. 基于HLA 的多领域建模研究[J]. 系统仿真学报, 2003, 15 (11): 1537-1542.
熊光楞, 范文慧, 陈晓波. 复杂产品开发的仿真技术[J]. 系统仿真学报, 2004, 16 (2): 194-201.
李伯虎, 柴旭东, 熊光楞, 等. 复杂产品虚拟样机工程的研究与初步实践 [J]. 系统仿真学报, 2002, 14 (3): 336-341.
[6] Farzad Tahami, Shahrokh Farhang. A Fuzzy Logic Direct
Yaw-Moment Control System for All-Wheel-Drive Electric Vehicles [J]. Vehicle System Dynamics (S0042-3114), 2004, 41(3): 203-221. [7]
Shin-ichiro Sakai, Yoichi Hori. Robustified Model Matching Control for Motion Cotrol of Elctric Vehicle. [C]// Proc. IEEE Workshop Advanced Motion Control, 1988. USA: IEEE, 1988: 574-579.
4 结论
本文基于虚拟样机协同仿真平台，建立了电动车横摆力矩控制系统的协同仿真模型，通过相关工况的仿真分析，表明该技术在车辆控制系统的研发中具有相当的优势，人工编程量小，求解精度有保证，还可方便进行控制算法的修改、参数调试和数据处理，从而大大提高建模效率。仿真分析结果也验证了DYC 控制系统的有效性，为后续其他控制策略研究工作的展开奠定了基础。
• 2344 •
统 仿 真 学 报 V ol. 20 No. 9
2008年5月 Journal of System Simulation May, 2008
第20卷第9期 系
基于高斯曲率极值点的散乱点云数据特征点提取
马骊溟，徐 毅，李泽湘
（哈尔滨工业大学深圳研究生院, 深圳 518055）
摘 要：提出了一种快速提取散乱点云数据特征点方法，首先求出空间一点邻域内的曲面片模型，在
此基础上利用梯度法搜索曲面上的高斯曲率极值点。然后再以该点作为搜索曲率极值点的初始点，根据判定准则搜索该点附近的曲率极值点。曲率极值点的搜索方法是边拟合局部曲面边搜索高斯曲率极值点，在搜索曲率极值点时，只需计算高斯曲率极值点附近点的曲率值。避免了传统算法中由于需要求出所有测量点的曲率值，然后进行比较求得曲率极值点而耗时间的缺点，从而提高了搜索效率。 关键词：特征点提取；曲率极值点；反求工程；高斯曲率
中图分类号：TP13 文献标识码：A 文章编号：1004-731X (2008) 09-2341-04
Extracting Feature Points for Scattered Points Based on Gauss Curvature Extreme Point
MA Li-ming, XU Yi, LI Ze-xiang
(Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen 518055, China)
Abstract: A fast method was proposed to extract the feature points from scattered point sets. A local surface was constructed from a spatial point and its nearest neighbors, from which the maximal point of Gaussian curvature was computed by means of gradient searching. Taking this point as start point, the maximal curvature point was searched near the area of this point. An advantage of the scheme is the local surface was fitted, at the same time, the maximal point of Gaussian curvature was computed. When the maximal curvature point was calculated, only the area of maximal Gaussian curvature was searched. It could avoid the drawback of the computing the curvature for the whole points and the time cost of comparing the maximal curvatue point. So the new scheme has higher searching efficiency.
Key words: feature point extraction; curvature extreme point; reverse engineering; Gaussian curvature
引 言
通常情况测量得到的曲面表面信息为三维坐标信息，随着测量坐标系的改变，三维坐标值也发生改变，因此无法准确获得曲面真实信息。特征点是最基本的曲面几何形状的特征基元，它不会因为坐标系的改变而发生变化。因此特征点的获得，对反求工程中的测量数据曲面分割技术[1-5]和测量数据多视角拼合技术
[6-7]
过这些模型都是对原散乱点的逼近表示，其过程复杂，形状逼近精度不能很好保证。胡[5]方法与文献[4]相似，只是在求取曲率极值点的方法上做了优化。以上基于曲率的散乱测量点的特征点提取算法的共同缺点是需要计算每个测量点的曲率值，然后通过比较找到曲率极值点，因此计算效率不高。针对以上算法的不足，本文提出了一种的计算曲率极值点的新方法，首先通过搜索高斯曲率极值点获得搜索曲率极值点的初始点，然后根据该点沿着主曲率方向给出的极值点判定方法确定搜索该点邻域其余的主方向上的极值点。该方法避免了求解每一个测量点的曲率值，因此搜索效率大大提高。
起着相当重要的作用。针对不同的
数据来源，特征点的提取方法分为扫描数据[1]和完全散乱测量数据[2-5]的特征提取方法。本文研究的是散乱测量点的特征点提取方法。Woo 认为测量点的法矢或曲率的突变是一个区域与另一个区域的边界，将法矢或曲率的突变点作为特征点。吕[3]根据OCS(Orthogonal Cross Section)模型估算出各点处的法矢，利用法矢和邻点拟合一张二次曲面，计算该二次曲面的主曲率和主方向，主曲率在主方向的极值点被确定为特征点。Huang [4]在完成数据点三角网格化的基础上，估算各测点的法矢和曲率，把曲率极值点作为边界特征点。不
收稿日期：2007-01-19 修回日期：2007-08-07 基金项目：国家自然科学基金资助项目(50505009)
作者简介：马骊溟(1971-), 女, 博士后, 研究方向为CAD/CAM及机电一体化; 徐毅(1979-) , 男, 博士生, 研究方向为先进电子制造、优化设计、精密测量与工程; 李泽湘, 男, 教授, 博导, 长江学者, 研究方向为机器人、先进制造、运动控制。
[2]
1 曲率极值点定义
在反求过程中，测量数据分片区域和多视角数据配准的重叠区域中，存在这样的点，该点的2个主曲率(k 1和k 2) 中任何一个沿着对应的主方向上为极值，那么该点称为曲率极值点。
那若高斯曲率K 有极值点 则K 的偏导数K u 和K v 为零，么
K u =(k1⋅k 2) u =k1u ⋅k 2+
k1⋅k 2u =0K v =(k1⋅k 2) v =k1v ⋅k 2+k1⋅k 2v =0
(1)
若k 1和k 2不为零(高斯曲率K ≠0) ，则要使公式(1)成
立则必
k1u =k 2u =k1v =k 2v =0 (2)
• 2341 •
2008年5月 系 统 仿 真 学 报 May, 2008
由公式(2)可以推出，k 1、k 2也为极值点，这说明高斯是曲率极值点的特殊曲率极值点也是2个主曲率的极值点，
情况，即在该点的两个主方向上都是曲率极值点(因为通常意义上的曲率极值点只是沿着一个主方向的曲率为极值就可以了，不需要同时达到极值) 。因此在该点的邻域附近的点沿某一主方向存在曲率极值点，具体是极大值还是极小值根据该点的局部形状确定
由微分几何[8]可知，高斯曲率K 是主曲率的乘积，其符号可以确定曲面上的点的性质，表明该点是椭圆点(K >0)、抛物点(K =0)还是双曲面(K 0、H =0在数学上相互矛盾，因而是不存在的。
表1 点的局部曲面类型
序号
K
H
曲面类型
k1 k2 k1 > 0, k2 > 0 k1 = 0, k2 > 0 k1 0, |k1| 0, |k1| = |k2|
k1 = 0, k2 =0 k1 0, |k1| > |k2|
k1
几何描述
点在所有方向上局部为凸 点局部为凸, 在一个方向上为平
点在大部分方向上局部为凸，在小部分方向上为凹
点的局部为凸凹分布各占半
平面
点在所有方向上局部均为凹 点局部为凹, 在一个主方向上为平
点在大部分方向上局部为凹，在小部分方向上为凸
1 >0 >0 峰 2 0 >0 脊 3 0 鞍形脊 4 0 0 0 不存在
表1中的8种曲面形式中，高斯曲率K = 0的这3种曲
=
(在下面将面形式中不存在高斯曲率极值点，因此不予考虑==K 的正负分为两类： 会讨论) ，将其余5种根据
=
=
高斯曲率极值点的搜索过程是一个寻优过程，即在整个数据点中搜寻高斯曲率极大值点或极小值点。由于我们是在整个曲面上找出极值点，而不是最值点，因此不必采用具有全局优化功能的优化方法，可以采用有局部优化功能的梯度法。然而梯度法在搜索到一个极值点后就会停止搜索。为了搜索到所有的高斯曲率极值点，本文采用曲面分片搜索。即首先将数据点进行栅格化，然后在每个栅格里搜索高斯曲率极值点，直至搜索所有的栅格。
1) 当K > 0时，存在两种情况：
当H > 0，在最大主曲率方向上存在曲率极大值 当H
=
2) 当K
当H >0，在最大主曲率方向上存在曲率极大值 当H
由以上可以看出无论高斯曲的极值点的高斯曲率值是正还是负，只要根据平均曲率的正负就可决定是沿着最大主曲率方向上搜索曲率极大值，还是沿着最小主曲率方向上搜索曲率极小值。
当高斯曲率K =0时，对应在表1的三种曲面分别为2、5和7曲面。其中第5种是平面不存在曲率极值点，不与考虑；
图1 高斯曲率极值点的搜索
第2种曲面：k 1=0，H = k 2 / 2；第7种曲面：k 2=0，H = k 1/2。
虽然这后两种曲面形式不存在高斯曲率极值点，但仍然因此当搜存在平均曲率H 的极值点(也就是主曲率极值点) 。索不到高斯曲率极值点时，可以搜索平均曲率极值点。
从以上分析可以得知，高斯曲率极值点(平均曲率极值点) 必然是曲率极值点，而曲率极值点不一定是高斯曲率极值点，因此可以将高斯曲率极值点作为搜索曲率极值点的初始点。
如图1，首先搜索P 点的k 邻近点，并将这k+1个点进行局部二次曲面拟合，当局部二次曲面r 0(u, v)拟合完成，以点P 作为起始点搜索这个局部二次曲面上的高斯曲率极值点。当在r 0(u, v)上搜索到曲率极值点C 1时，用点C 1的k 近邻再拟合成一个二次曲面r 1(u, v)，并以点C 1作为起始点搜索这个局部二次曲面上的曲率极值点C 2。然后再以点C 2作依此类推，直为起始点搜索k 近邻点拟合二次曲面r 2(u, v)。
至搜索到整张曲面上的曲率极值点。整个迭代搜寻过程只有起始点是数据点，其后的迭代过程中的起始点（例如C 1和C 2）不一定是数据点，而是拟合二次曲面上的点。
高斯曲率极值点的搜索过程分为两步，首先搜索极大值，然后搜索极小值。无论极小值还是极大值都称为基于高
2 曲率极值点初始点的搜索
在搜索曲率极值点的初始点时，首先搜索高斯曲率极值点，如果搜索不到再搜索平均曲率极值点，搜索方法相同。因此下面只介绍高斯曲率极值点的搜索过程。
• 2342 •
2008年5月 马骊溟，等：基于高斯曲率极值点的散乱点云数据特征点提取 May, 2008
斯曲率的特征点。然后以该点作为搜索主曲率极值点的初始点。当搜索不到高斯曲率点时，搜索平均曲率极值点。
的栅格。计算P 点与下一个栅格内所有点构成的矢量与M 1+的夹角θ，给定阈值，将夹角过大的点剔除，并按照由小到大的顺序排列，作为候选点。然后重复上述搜索曲率极大值的过程，直到搜索停止；接着沿着的最小主曲率方向的反方向做一个矢量M 1-，重复上面的过程搜索曲率极值点。
3 曲率极值点的搜索
以高斯曲率极值点作为初始点，沿着最大主曲率方向和最小主曲率方向搜索曲率极值点。如图2所示，假设点Q 为高斯曲率极值点，计算Q 点的平均曲率值H (Q ) 。
(2) 如果H (Q )
M 2+、M 2+换成M 1+。同理，沿着最大主曲率方向的反方向做一个矢量M 2-，重复上面的过程。
(1) 如果H (Q )>0，那么在最大主曲率方向上存在曲率极计算大值，首先沿点Q 的最小主曲率方向做一个矢量M 1+，点Q 与所在的栅格内所有点构成的矢量与M 1+的夹角θ，给定阈值，将夹角过大的点剔除，并按照由小到大的顺序排列，这些点作为曲率极值点的候选点。取出序列中第一个点Q 1，如图3所示，沿最大曲率方向M 2找到该点的左右两个邻接点Q 1l 、Q 1r ，如果k 2(Q 1) ≥k 2(Q 1l ) 并且k 2(Q 1) ≤k 2(Q 1r ) ，那么点Q 1是曲率极值点。否则该点不是曲率极值点。对所有候选点进行上述操作，就可以得到该栅格内的沿着最大主曲率方向的曲率的极大值点，并将它们依次储存在链表。取出链表末尾的点P ，沿P 点的最小主曲率方向重新做一个矢量M 1+代替原来的矢量，矢量M 1+所指向的栅格即为将要搜索 极值点 非极值点
(3) 如果H (Q )=0，重复(1)和(2)的步骤。
4 实例
图4(a)为采用激光扫描仪对某鼠标测得表面点云数据。图4(b)为按照本文的算法提取的基于曲率极值点的特征点集。图5(a)为某汽车车灯原始点云数据。图5(b)为按照本文算法将提取到特征点利用自由曲线拟合技术进一步拟合成边界曲线，作为各曲面片之间的边界。
Q
图2 曲率极值点的自动搜索 图3 曲率极值点的判定
(a) 测量点云数据 (b) 基于曲率极值点的特征点
图4 鼠标点云数据特征点提取
(a) 测量点云数据 (b) 点云数据的区域分割
图5 汽车车灯点云数据的边界识取
由于文献[5]方法与文献[4]相似，只是在求取曲率极值点的方法上做了优化。因此本文只进行了本文算法与文献[5]算法的计算，在Pentium4，3.00GHz ，512MB 内存的计算机上运行，用C++语言在VC++6编译器上成功地计算出表2的
数据。其中平均误差e a 和最大误差e m 单位为mm ，耗时单位为s 。从表1中的结果可以看出，精度上两个算法差别不大。在计算效率上本文算法较高，特别当云点数量较大时，优势更为明显。
• 2343 •
2008年5月 系 统 仿 真 学 报 May, 2008
表2 计算结果
特征点 提取方法
汽车车灯(326182点)
平均误差e a
最大误差e m
耗时
平均误差e a
鼠标(28000点)
最大误差e m
耗时
文献[5] 0.031 0.043 29.85 0.024 0.036 5.16 本文 0.027 0.078 18.54 0.029 0.045 4.22
Manufacture (S0890-6955), 2002, 42(2): 167-178.
[3] 吕震, 柯映林, 孙庆, 等. 反求工程中过渡曲面特征提取算法研究
[J]. 计算机集成制造系统, 2003, 9(2): 154-157.
[4] Huang J, Menq C H. Automatic data segmentation for geometric feature
extraction from unorganized 3-D coordinate points [J]. IEEE Transactions on Robotics and Automation (S1042-296X), 2001, 17(3): 268-279. [5] 胡鑫, 习俊通, 金烨. 反求工程中散乱点云数据的自动分割与曲面
重构[J]. 上海交通大学学报, 2004, 38(1): 62-65.
[6] Jun Yongtae, Choi Kuiwon. Automated feature-based registration for
reverse engineering of human models [J]. Journal of Mechanical Science and Technology (S1738-494X), 2005, 19(12): 2213-2223. [7]
Tahir Rabbani, Sander Dijkman. An integrated approach for modeling and global registration of point clouds [J]. ISPRS Journal of Photogrammetry and Remote Sensing (S0924-2716), 2007, 2(61): 355-370.
[8] 吴大任. 微分几何讲义[M]. 北京: 人民教育出版社, 1984:
126-128.
[9] 刘胜兰, 周儒荣, 安鲁陵. 三角网格的数据分块算法[J]. 南京航空
航天大学学报, 2003, 35(6): 653-658.
4 结论
本文提出不需要知道曲面模型而直接根据离散点数据求解曲率极值点的方法。首先根据最小二乘法求出空间一点邻域内的曲面模型，然后在此基础上采用梯度法搜索曲面上的高斯曲率极值点。接着将该点作为搜索曲率极值点的初始点，并沿着主曲率方向搜索该点邻域其余的主方向上的极值点。本文的创新之处在于，不需要求出所有点的曲率值就可以搜索到曲率极值点，极大的提高了计算效率。为反求工程中测量数据的曲面分割和多视角拼合提供了极大的技术支持。
参考文献：
[1] Yang M, Lee E. Segmentation of measured data using a parametric
quadric surface approximation [J]. Computer Aided Design (S1573-4099), 1999, 31(7): 449-457.
[2] Woo H, Kang E, Wang Sem-yung, et al. A new segmentation method
for point cloud data [J]. International Journal of Machine Tools and
（上接第2340页）
从图6中可以看出有DYC 控制的车辆侧向加速度超调量小，达到稳态值的时间少。侧向加速度超调量的减少可以使车辆的转向运动更加平稳。在图8所示的质心侧偏角对比曲线中，可以看出采用DYC 控制的车辆能够控制车辆的质心侧偏角在理想值附近，保持车辆的平衡，提高了车辆的稳定性。
参考文献：
[1] Yoichi Hori. Future Vehicle Driven by Electricity and
Control-Research on Four-Wheel-Motored “UOT Electric March” [J]. IEEE Transaction on Industrial Electronics (S0278-0046), 2004, 51(5), 954-962. [2]
Motoki Shino, Masao Nagai. Yaw-moment control of electric vehicle for improving handling and stability [J]. JSAE Review (S0389-4304), 2001, 22(4), 473-480. [3] [4] [5]
陈晓波, 熊光楞, 郭斌, 张和明. 基于HLA 的多领域建模研究[J]. 系统仿真学报, 2003, 15 (11): 1537-1542.
熊光楞, 范文慧, 陈晓波. 复杂产品开发的仿真技术[J]. 系统仿真学报, 2004, 16 (2): 194-201.
李伯虎, 柴旭东, 熊光楞, 等. 复杂产品虚拟样机工程的研究与初步实践 [J]. 系统仿真学报, 2002, 14 (3): 336-341.
[6] Farzad Tahami, Shahrokh Farhang. A Fuzzy Logic Direct
Yaw-Moment Control System for All-Wheel-Drive Electric Vehicles [J]. Vehicle System Dynamics (S0042-3114), 2004, 41(3): 203-221. [7]
Shin-ichiro Sakai, Yoichi Hori. Robustified Model Matching Control for Motion Cotrol of Elctric Vehicle. [C]// Proc. IEEE Workshop Advanced Motion Control, 1988. USA: IEEE, 1988: 574-579.
4 结论
本文基于虚拟样机协同仿真平台，建立了电动车横摆力矩控制系统的协同仿真模型，通过相关工况的仿真分析，表明该技术在车辆控制系统的研发中具有相当的优势，人工编程量小，求解精度有保证，还可方便进行控制算法的修改、参数调试和数据处理，从而大大提高建模效率。仿真分析结果也验证了DYC 控制系统的有效性，为后续其他控制策略研究工作的展开奠定了基础。
• 2344 •