尹逊刚，孙殿柱，李延瑞，徐 昭

(1.山东理工大学 机械工程学院，山东 淄博 255049；2.西安交通大学 机械工程学院，西安 711049)



三维物体的准最小包围盒快速求解方法*

尹逊刚1，孙殿柱1，李延瑞2，徐 昭1

(1.山东理工大学 机械工程学院，山东 淄博 255049；2.西安交通大学 机械工程学院，西安 711049)

针对现有求解精确三维物体最小包围盒算法的时间复杂度过高这一问题，提出一种基于物体表面采样点集的准最小包围盒快速求解方法。该方法首先提出一种增量式聚类简化算法对物体表面采样点集的非特征区域进行大幅简化，并将简化后点集的精确最小包围盒作为求解原始采样点集准最小包围盒的定位空间，以该空间下的最小轴向包围盒作为原始三维物体的准最小包围盒。试验结果表明，在满足求解精度要求的前提下，该方法与采样点集的精确最小包围盒求解方法相比，其计算效率提高90%左右，与基于遗传算法的求解方法相比，其计算效率最大可提高30%。

最小包围盒；k均值聚类；定位空间；轴向包围盒

0 引言

物体的最小包围盒在当今许多实际问题的解决中有着重要的应用。在工业设计领域中，针对产品的包装设计，快速成型等，利用包围盒技术可以为毛坯用料最优化设计提供依据；在机械零件的铸造分型中，利用最小包围盒可获得最优分型方向；碰撞检测中，用实物的最小包围盒代替复杂的几何物体，可显著提高相交测试的效率[1-3]。

国内外许多学者对包围盒求解方法进行了多方面的研究。O′Rourke[4]根据物体的凸包与其包围盒的关系实现了精确最小包围盒的求解方法。文献[5-7]以点集的主元向量作为坐标轴求解其轴向最小包围盒。陈华[8]通过固定步长的角度不断旋转模型所在坐标系计算旋转过程中的最小轴向包围盒。孙殿柱[9]等将遗传算法与O′Rourke 算法相结合求解物体的最小包围盒。宋洋[10]等基于型面特征和均值漂移的算法对原始数据进行二次精简来计算近似最小包围盒。

上述算法虽然取得了较好的计算效果，但是时间复杂度过高。因此，本文对物体表面采样点集进行聚类简化，基于简化结果采用 O′Rourke 算法确定物体准最小包围盒的定位空间，在该空间中求解采样点集的轴向包围盒，将所得结果作为物体的准最小包围盒。试验结果表明，所求解准最小包围盒能准确的逼近其精确最小包围盒，计算效率显著提高。

1 采样点集特征数据的分离

在求解物体表面采样点集最小包围盒时，特征样点是指边界样点及表面轮廓曲率变化较大的数据点，其与非特征样点的最主要区别在于其近邻点集密度分布的不同。

为准确地分离出特征样点，通过对目标样点的近邻点集进行识别，使得目标样点的近邻点集在一定程度上向该点稀疏区域扩展[11]，通过比较目标样点与其对应的模式点之间的距离识别出特征样点并实现与非特征样点的分离。以点数为n的采样点集X作为输入数据, 分离特征数据的计算步骤如下：

(1)

式中，N表示近邻点集个数,qi∈λ(ti),h为ti至λ(ti)中所有样点距离的最大值；

Step3: 沿目标样点与其模式点之间的概率密度梯度反向搜索新的近邻样点集S；

Step4: 若S=∅, 则可判定t为特征点，跳转步骤Step7;

(2)

Step7: 将识别出的特征样点归为点集M1，非特征样点归为点集M2；

Step8: 重复步骤Step1 至Step7直至遍历完全部数据。

以生产实践中的叶片采样点集为例，对其进行特征数据分离的效果如图1所示。图1a表示原始采样点集，图1b表示分离出的特征数据。

(a)叶片(点数: 50123) (b)特征数据(点数: 4816)图1 原始采样点集特征分离

2 非特征数据的增量式聚类简化

将采样点集的特征数据与非特征数据分离之后，非特征数据M2只包含少量影响凸包计算的数据点，为提高包围盒的求解效率，需要对非特征数据进行简化处理。

在对非特征数据进行简化时，k均值聚类[12]算法原理简单， 在数据简化中有重要应用。利用k均值聚类算法并结合主元分析的思想，对k均值聚类算法进行改进，首先过点集中心点并垂直于其第一主元向量构造初始分界面，以该分界面将原始点集分为两类，随后选择方差最大的子集进行下次聚类分簇，如此循环直至给定的聚类簇数，最后以各个聚类子集中心点代替原始点集，实现对非特征数据的简化。下面提出一种增量式聚类简化的算法, 具体计算步骤如下：

Step2: 对于F1的协方差矩阵, 应用奇异值分解方法获取其最大特征值对应的特征向量u，过d1且垂直于u构建分界面U，将F1中分布于U两侧的点集分别归为C1和C2， 得到第二次分类结果；

Step3: 在Fj中选择方差最大的分类C(v)，并对C(v)采用k均值聚类算法将其分为两类，其中Fj，j={2,3,…,h}，表示第j次聚类结果；

Step4: 给定最终的聚类子集数K, 重复步骤Step3，直至h=K；

(a)非特征数据(点数: 45277) (b)聚类简化(点数: 230)图2 非特征数据简化结果

3 准最小包围盒定位空间的构造

非特征数据M2经聚类简化后数据量已经大幅减少，此时若将简化结果P与特征数据M1合并为新点集X′，通过求取该合并点集的最小包围盒构造原始采样点集准最小包围盒的定位空间，可提高所构造定位空间的准确性。

利用O’Rourke算法求解合并点集X′的精确最小包围盒， 由于此时合并点集相对于原始采样点集的数据量已显著减少，所以会有部分数据点在所求最小包围盒的外部，为求得原始采样点集的包围盒。可选择X′的最小包围盒相互垂直的边构造定位坐标系，并通过坐标变换将原始数据点集变换到该坐标系下。

以合并点集X′作为输入数据，构造定位空间的具体步骤如下：

Step1: 获取X′的凸包点集；

Step2: 任意选取凸包上的两条边a1和a2，分别转化为向量a1和a2，将两个向量的始端平移到原点。旋转凸包，使a1与坐标轴z重合且a2与yz平面平行。构造向量n1和n2，其中向量n1和n2分别是包围盒上包含a1和a2的两个相邻面的单位法向量；

Step4: 分别求解-n1、±n2和±n3的轨迹与高斯球上的弧的下一个交点以及交点处的θ1的值,其中-n1和-n2分别为Step2中两个面相对面的法向量，±n3为其余两个面的单位法向量；

Step5: 令θ2等于Step4中所求值的最小值；

Step7: 令θ=θ2，如果θ≥θmax，返回Step2，否则程序结束；

根据构建的定位坐标系，获得坐标变换矩阵C，并利用公式(3)将原始采样点集经过坐标变换转化为该定位坐标系下的点。

(3)

将从叶片分离出的特征数据与非特征数据的简化结果合并后的点集如图3a所示，可知非特征数据经过简化后与特征数据合并点集的数据量相对原始采样点集已大幅减少，只有原始数据量大小的十分之一左右。基于简化的合并点集，依然能够获得较好的凸包数据，效果如图3b所示。由于此时只计算了合并点集的精确最小包围盒，原始点集经坐标变换后与合并点集重合，所构造的定位坐标C系在世界坐标系O下的位置效果如图3c所示，可以看出，原始点集的部分数据依然在该包围盒的外部。

(a)合并点集(点数: 5046) (b)凸包点集(点数: 219)

(c)定位空间效果图图3 定位空间的构造

4 原始点集的准最小包围盒求解

根据所构建的轴向包围盒，获取该包围盒各个顶点信息， 并利用公式(4)将各顶点转换为原世界坐标系下的点，最终获得原始采样点集的准最小包围盒。

(4)

5 试验结果

为验证文中所提出的增量式k均值算法在聚类分析中的有效性，将该算法和文献[12]的算法的进行聚类比较。通过随机选取点数为10 000的非均匀分布的点集，取K∈[4,10]。统计平均计算时间T、聚类优度S和平均迭代次数I，聚类优度采用Silhouette指标，其值越大，聚类结果越好[14-15]。结果如表1所示。由表1可知，本文增量式k均值聚类算法显著提高了计算效率且聚类优度与文献[12]算法基本接近，基于较好的聚类优度，使得后续的简化结果更能准确反应采样点集的表面信息。

表1 两种算法性能比较

为验证本文算法对求解任意物体表面采样点集包围盒的有效性，选取不同的机械零件采样数据进行测试。根据文献[12]的建议， 对于车身模型，取敏感因子ε=0.8，近邻点个数N=20；对于箱盖模型，取ε=1.0，N=15；对于轮毂模型，取ε=0.8，N=15； 对于叶片模型，取ε=1.1，N=20。求解的准最小包围盒如图4所示。所采用的计算机主频2.5GHz，采用C语言编程实现。

在对最小包围盒求解算法的性能描述中，求解效率与包围盒体积是两个重要的指标。鉴于O’Rourke算法求解的包围盒为精确最小包围盒，针对上述采样点集，可将文献[4]算法求解的体积值视为基准，并将本文算法的运行时间和求解结果与文献[4,9]算法比较分别得表2和表3。由表2可知，本文算法求解准最小包围盒的时间约为文献[4]算法的1.7% ～3.3%之间，计算效率提高90%以上；与文献[9]相比，本文算法计算效率提高10%～30%。由表3可知，本文算法求解误差略小于文献[9]的求解误差，与文献[4]求解的精确最小包围盒相比，体积误差在0.4%～5.1%之间。试验表明，本文算法能够保证较高的求解精度，且计算效率显著提高，能够满足生成实践中的应用要求。

图4 本文求解的准最小包围盒

采样点集点数本文文献[4]文献[9]车身14719222.47948.1224.43箱盖155275.18336.366.56轮毂11450416.27717.4718.32叶片5012311.16436.9613.69

表3 本文算法与文献[4，9]算法包围盒体积(单位: mm3)

6 结束语

本文基于分类计算的思想，提出一种增量式聚类简化的算法，并基于该算法实现了一种准最小包围盒的快速求解方法。主要有以下特点：

(1) 通过对特征样点的准确识别与分离，在计算过程中保留全部特征数据，有助于保持所求解准最小包围盒的精度。

(2) 提出的增量式聚类简化算法能有效降低聚类过程的计算代价，并能获得较好的简化结果。基于该算法可大幅简化实物表面采样点集，从而显著降低准最小包围盒的计算量，适合处理大规模采样点集。

(3) 针对不同的实物表面采样点集，设置不同的敏感因子，可使得该算法适应多种实物表面采样数据的包围盒求解问题。

[1] 李明宇. 复杂产品装配序列规划方法研究[D].武汉:华中科技大学,2013.

[2] MATRIN P R, STEPHSON P C. Putting Objects into boxes[J].Computer Aided Design,1988,20(9): 506-521.

[3] 刘涛，王增波，李占利. 碰撞检测过程中的包围盒技术及应用研究[J]. 西安科技大学学报,2006, 26(3):395-399

[4] JOSEPH O’ROURKE. Finding minimal enclosing boxes[J].International Journal of Computer and Information Sciences,1985,14(3):183-199.

[5] 陈柏松，叶雪梅，安利. 基于非线性主成分分析的最小包围盒计算方法[J]. 计算机集成制造系统,2010,16(11):2375-2378.

[6] VRANIC D V, SAPUE D. 3D model retrieval[D]. Saxomy, Germany: University of Leipzig, 2004.

[7] DIMITORY D, KNAUER C, KRIEGEL K, et al. Bounds on the quality of the PCA bounding boxes[C]. Computational Geometry: Theory and Applications. Amsterdam: Elsevier,2009,42(8):772-789.

[8] 陈华. 确定任意形状物体最小包围盒的一种方法[J]. 工程图学学,2010,31(2):49-53.

[9] 孙殿柱, 史 阳, 刘华东, 等. 基于遗传算法的散乱点云最小包围盒求解[J]. 北京航空航天大学学报, 2013,39(8):995-998.

[10] 宋 洋, 孙殿柱, 刘晓红, 等. 物体表面采样数据近似最小包围盒快速求解[J]. 农业装备与车辆工程, 2012,50(4): 1-5.

[11] 李延瑞, 孙殿柱, 张英杰, 等. 曲面边界样点逆向均值漂移识别[J]. 计算机集成制系统, 2015, 21(7): 1719-1724.

[12] LIKAS A, VLASSISs N, J VERBEEK J. The global k-means clustering algorithm[J]. Pattern recognition, 2003, 36(2): 451-461.

[13] 杨善林, 李永森, 胡笑旋, 等. K-MEANS 算法中的K 值优化问题研究[J]. 系统工程理论与实践, 2006,26(2): 97-101.

[14] 王开军, 张军英, 李 丹,等. 自适应仿射传播聚类[J]. 自动化学报, 2007,33(12):1242-1246.

[15] THEODORIDIS Y，BRAKATSOULAS S，PFOSER D. Revis iting r-tree construction principles[C]. Advances in Databases and Information Systems，2002.

(编辑 李秀敏)

找检测仪器，请上

QC检测仪器网

WWW.QCtester.com

微信号：qctest

Fast Solution Method of Quasi Minimum Bounding Box for 3D Shape

YIN Xun-gang1, SUN Dian-zhu1，LI Yan-rui2，XU Zhao1

(1.School of Mechanical Engineering, Shandong University of Technology, Zibo Shandong 255049, China;2.School of Mechanical Engineering, Xi′an Jiaotong University, Xi′an 710049, China)

Aiming at high cost of solving the accurate minimum bounding box of 3D shape, a fast solution method for the quasi minimum bounding box based on sampling point set of the object surface was proposed. In this method, an incremental clustering algorithm was proposed to simplify the non-feature region of the point set. Then to solve the exact minimum bounding box of the simplified point set, which was used as the location space of the original point set. Finally, regard the minimum axial bounding box of the location space as the quasi minimum bounding box of 3D shape. The results show that, under the premise of accuracy requirement, the computational efficiency of this method is increased by 90% and 30% respectively compared with the O’Rourke method and genetic algorithm.

minimum bounding box; k means clustering; location space; axial bounding box

1001-2265(2017)07-0051-04

10.13462/j.cnki.mmtamt.2017.07.012

2016-11-07；

2016-11-17

国家自然科学基金资助项目(51575326)；山东省自然科学基金项目(ZR2015EM031)

尹逊刚(1990—)，男，济南人，山东理工大学硕士研究生，研究方向为CAD/CAM，(E-mail)770186316@qq.com；通讯作者：孙殿柱(1956—)，男，山东烟台人，山东理工大学教授，研究方向为CAD/CAM、逆向工程，(E-mail)dianzhus@sdut.edu.cn。

TH161；TG506

A