基于球心点互斥的球目标识别方法

李子宽，廖 威，蓝秋萍



基于球心点互斥的球目标识别方法

李子宽1，廖 威2，蓝秋萍1

(1. 河海大学地球科学与工程学院，江苏 南京 211100；2. 宁波市规划设计研究院，浙江 宁波 315042)

提出了一种基于球心点互斥的球目标识别方法，用于从大场景三维点云中自动识别未知个数和未知半径的球目标。首先，根据专门设计的球面点响应函数滤除大量非球面点，并根据法向与曲率将剩余的球面点映射到球心位置；然后，构建用以描述局部密度渐变规律的球心点互斥树，通过剪枝操作将其分裂成若干子树，其分别对应不同球目标的球心点聚类；最后，根据球心点局部密度和球面点覆盖率估计值确认真实存在的球目标。实验结果表明：基于球心点互斥的球目标识别方法能够有效解决大场景三维点云中球目标的识别问题，即使是存在严重遮挡的情况下，暴露表面不足整个球面6%的球目标也都能够被识别出来。

球目标识别；球面点响应函数；球心点互斥；聚类；球面覆盖率

球形具有良好的几何特性[1]，在光学相机标定[2]、机器人手臂引导[3]、骨外科手术[4]等基于目标识别的应用中，被广泛用作合作目标的首选形状。因此，利用二维影像识别和定位球形目标或表面的方法研究已经取得了许多应用成果。随着三维激光扫描和立体视觉技术的持续发展，三维点云中球目标识别方法也开始受到越来越多的关注。

受到二维影像边缘检测方法的启发，WANG等[5]和BENLAMRI[6]将三维点云中球目标识别转化为二维深度图像上的圆形边缘检测问题，通过寻找深度不连续的边缘来识别场景中的球目标。但是，该方法要求目标边缘完全暴露，不能被遮挡。为了能够在杂乱场景中准确定位被遮挡的目标，MARSHALL等[7]设计了直接针对三维点云的试探性拟合方法，并根据拟合结果挑选最匹配模型完成点云分割。文献[8]则采用随机采样一致性(random sample consensus，RANSAC)算法分割椭球面，即：在三维点云中反复选取不同采样点，根据每次采样点构建假设模型及评价模型与点云的一致性，并依据一致性从高到低的顺序逐步完成点云分割。这两种通过反复试探和检验寻找目标的方法，能够解决小规模点云的分割问题，却并不适用于大场景中小目标的识别问题。

本文提出了一种根据映射球心点局部密度变化规律的球目标识别方法。该方法不需要预先假设场景中球目标的个数和尺寸，能够准确识别杂乱环境中被严重遮挡的球目标。识别过程只需要若干仅凭直觉即可设置的简单参数，并且能够自动适应不同密度的三维点云，高效率地完成大场景中多个球目标的识别任务。

1 方法

与其他的几何形状均不同，球形具有唯一的中心，并且依据法向和曲率，球面上的每一个点都能够映射到球心点上[9]。针对这一特性，本文提出了一种让真实球目标的球心位置出现显著高密度映射点的方法；并专门设计了一种描述映射球心点密度变化规律的树形结构，根据邻近球心点之间的互斥特性将树分割成若干子树，且每个子树对应一个球目标；最后根据原始点云在球面上的覆盖率确认场景中真实存在的球目标。

1.1 映射球心点

为了使正确的球心位置能够产生密度显著高于其他位置的映射球心点分布，本文设计了一种有效的球面点响应函数，如式(1)，其中主曲率1和2为输入量；为球面响应值，即

球面点存在稳定的映射关系：法线所在直线经过球心，且两个主曲率相等且倒数等于球面点到对应球心点的距离。据此，设计了从疑似球面点至球心点映射的方法。如图1所示，对于一个疑似球面点，沿着法向的相反方向，计算映射球心点，即

其中，代表取绝对值。

1.2 球心点互斥

球面响应函数仅对局部形状类似于球面的点输出正值，因此能够滤除大部分非球面点，使球面以外的区域被显著稀释；而随后的球心点映射计算可使剩余点中真正的球面点进一步向各自的球心汇聚。因此，真实球目标的球心位置会出现比其他位置更加显著的映射点聚集现象。不同于一般空间点，映射点是位于球心位置的假想点，只有当两球心点之间的距离大于各自对应球目标的半径之和时，其才能够同时存在。针对该特征，本文设计了一种球心点互斥方法，能够快速找出高密度的球心点聚类，每一个聚类对应一个可能的目标球，而聚类中心则是最有可能的球心点位置。

1.2.1 球心点互斥树

其中，d是c与另一个球心点c之间的距离；与分别为点c与c的局部密度。本文采用一种简便的局部密度计算方法，统计与c的距离小于指定值dc的球心点个数，将其作为c的局部密度。

以图2所示的32个映射球心点分布为例，按照上述方法建立球心点互斥树，如图3所示。互斥树上一个节点代表一个球心点，节点圆圈中记录了球心点编号和对应的球目标半径，例如根节点记录了1号球心点和其对应的半径为1.92。互斥树中每一条边都连接着两个节点，其中上层节点是下层节点的父节点，即：上层节点是与之相连的下层节点的最近且密度更高的球心点。每条边都具有一个距离属性值，记录了其所连接的两个点之间的距离，例如1号点与31号点的连接边记录了其之间的距离为4.16。

图2 映射球心点分布图

图3 球心点互斥树

1.2.2 球心点互斥

从下往上看，互斥树中的边-连接了一个下层点c和一个上层点c，c是距离c最近的更高密度点。如果c与c的距离非常近，则可以认定其对应同一个球目标，由于<，c比c更加靠近真实的球心位置，于是可排除c是真实球心的可能性；如果c与c的距离较远，例如大于其半径之和，那么c与c很可能来自于两个不同的球目标，可以共存，与其各自代表一个球目标的可能性不能被排除。这种距离近则相互排斥的现象类似于同性电荷互斥的现象，因此，可将其称为球心点互斥。

基于互斥树的球心点互斥算法可描述为：当边-的距离属性d小于其所连接的两个球心点半径之和(r+r)时，即：d<r+r，认定c与c来自同一个球，且上层点c比下层点c更靠近球心，c作为c的父节点是非常合理的，边-被保留下来；当d≥r+r时，c和c很可能来自两个不同的球，c作为c的父节点不再合理，断开边-。考虑到球心点坐标和球半径都会存在估计误差，所以设定一个调节因子，当d<×(r+r)时，保留该边；当d≥×(r+r)时，则断开该边。本文实验取=0.7。

经过球心点互斥后，图3中的15-1、31-1、23-1、30-15、29-23这5条连接边会被断开，如图4中的虚线边。互斥树被分成6个子树，其根节点分别是1、15、23、29、30、31，如图4中灰色填充的节点。每个子树对应着同一个球目标，其根节点的局部密度在该子树的所有节点中最高，所以根节点所对应的球目标估计参数具有最高的可信度。其中，节点1、15和23的确是图2中3个显著聚类的聚类中心，而29、30、31则是由于距离这3个聚类较远，位于安全距离之外，所以在互斥计算中才被保留了下来。

图4 经互斥计算后的球心点互斥树

球面点向球心点的映射，使真实球心位置的局部密度显著高于原始点云的点密度；而球面响应函数会显著稀释非球面点，从而致使非球面位置的映射球心点密度低于原始点云密度。所以，以原始点云的平均点密度0作为阈值，能够进一步排除那些孤立点形成假性聚类中心，如图2中29、30、31号球心点。

1.3 确认球目标

除了真正的球面之外，杂乱场景中大量不规则表面也会偶然引起映射点的聚集现象，所以针对上一步得到的聚类中心点，还需要进一步确认对应球目标是否真实存在。本文根据原始点云在球目标表面的覆盖率确认球目标，具体做法是：从原始点云中找出位于球目标表面且与球面法向一致的点，计算这些点覆盖面积占整个球面的比率，将覆盖率较低的球目标排除掉。

为一个百分比数值，其值越大说明目标球存在的概率越大。而且，非常容易被人类感知，即使不知道点云密度和球目标半径的精确数据，通过在扫描仪视角上的简单观察，就可以轻松地给出一个合适的阈值，用以最终确认球目标。即使是毫无先验知识的未知场景，为了确保球目标识别结果的可靠性，也可以给出一个与球目标半径和扫描密度无关的阈值。例如：为了进一步提高球目标的定位精度，可以根据这个球面点重新进行球面拟合计算[10]，得到更加精确的几何参数，为了确保拟合计算结果的精确性，可以在密度阈值0的基础上设置更加严格的覆盖率阈值，即：只有大于10%的球目标才被认定为可靠的球目标，其重新拟合的计算结果才具有较高的可信度。

2 实验与分析

在阅览室布置了如图6(a)所示的实验场景。场景中放置了8个不同半径的球目标，其中，2#、3#和7#球都存在较严重的遮挡，5#和6#球彼此接触。利用TrimbleGX200三维激光扫描仪在拍摄照片的位置扫描场景，采集到约141万个点，其中真实球面点在整幅点云中的比例少于0.4%。

采用文献[9]中的方法计算点云中每一个点的法向、高斯曲率和平均曲率。设定=0.15，=0.0001，根据式(2)计算每个点的球面响应值，并滤除超过94%的非球面点，剩余84404个疑似球面点。针对疑似球面点利用式(3)计算映射球心点坐标，将映射球心点叠加显示到原始点云中，如图6(b)所示，可以观察到在8个真实球心附近出现了较为明显的聚类现象，同时在桌椅的棱角位置也出现了一些高密度球心点。

图6 实验场景照片以及映射球心点分布

通过球心点互斥计算，又有超过98%的点被排除掉，剩余1447个聚类中心点。将其按照局部密度由高至底排序，局部密度最高的前50个点如图7(a)所示，其中有18个点的局部密度高于原始扫描点云密度0=52.4。根据这些聚类中心建球模型，其在空间中的分布如图7(b)所示，密度最高的8个聚类中心在空间上位于8个真实球目标的球心附近，其余10个高密度聚类中心则分布于桌角、椅背顶端等可能引起映射点聚集的易混淆区域上。观察图7(a)可以发现，除了遮挡非常严重的3#球之外，7个球目标的聚类中心密度都在原始点云平均密度的3倍以上，3#球的暴露面积不足整个球面的6%，对应映射球心点的局部密度为70。而在所有聚类中心点中，另外1439个非球心点的平均密度只有5.29，约为原始点云密度的1/10，标准差为8.24。因此，以原始点云的平均密度作为阈值能够有效地排除大量非球心点，并且确保真实球心点不会被错误地排除掉。

最后，针对18个高于0的高密度聚类中心点利用式(5)计算球面点覆盖率。设定1=3 cm，2=5°，为每一个聚类中心点找出可靠地球面点。场景中8个真实球目标的实际半径、识别出的球面点个数、覆盖率都记录在表1中。其中2#和3#球遮挡较为严重，分别为8.7%和5.6%，其余真实球目标的均在25%以上。而另外10个桌椅棱角附近的高密度聚类中心，由于找不到足够多的可靠球面点，覆盖率均小于0.1%，所以很容易与真实球目标区分开来。对分割出的可靠球面点重新拟合球面，得到精确的球心点坐标和半径，其与真实值的偏差值见表1。由于遮挡较为严重的2#和3#球，覆盖率在8个真实球目标中也最低，半径与球心点坐标的估计误差都明显大于其他球。所以，对于识别出的球目标，如果球面点覆盖率较小，例如小于10%，那么其重新拟合后的半径估计值和球心定位值的可靠性会较低，在后续应用中建议慎重考虑这些球目标。

图7 映射球心点密度降序排列及识别出的目标球分布

表1 各个球目标的相关参数统计值

考虑到本文球目标识别方法与文献[9]有相似地执行策略，所以可利用文献[9]的桌面场景，对比两种方法的计算效率和球目标识别精确性。桌面场景扫描点云如图8所示，扫描得到51896个点，场景中布置了5个球目标，落在球面上的扫描点约占整幅点云的30%。采用相同方法估计点云的法向和曲率，然后利用本文响应函数和文献[9]的主曲率比较方法分别识别出14088个和14736个可能的球面点，并推算可能的球心点。应用本文的球心点互斥聚类方法(mutual exclusion semaphores, MutEx)和文献[9]的层次聚类方法(hierarchical agglomerative clustering, HAC)针对各自的推算球心点计算聚类中心。MutEx聚类耗时15.75 s，得到10个聚类中心；而HAC聚类耗时749.1 s，得到104个聚类。对应5个真实球目标的聚类计算结果见表2，其中Δ与Δ的含义与表1相同，SN/total代表“在聚类结果中的排序/聚类结果总数”，本文的MutEx聚类根据聚类密度排序，HAC聚类根据类内点个数排序。

图8 包含5个球目标的桌面场景扫描点云

表2 本文MutEx聚类与文献[9]HAC聚类实验结果

由于MutEx依据局部密度对聚类结果排序，并利用原始点云密度作为阈值排除低密度聚类，所以仅得到10个聚类结果，且对应于5个真实球目标的聚类依据局部密度均排在最前面。而HAC仅以类内点个数作为判别聚类结果可靠性的依据，所以除了2#球对应聚类排在聚类结果第1位之外，其他4个球目标都未获得区别于其他错误聚类的显著性优势。MutEx直接采用聚类最高密度点的坐标和半径作为对应球目标的球心点坐标和半径，不容易受到类内大误差点的影响；而HAC采用了类内求平均的方法，位于聚类边缘位置的大误差点会影响球目标参数的精度。因此，除了无遮挡的3#球之外，其余4个球目标的HAC球心定位与半径估计精度均低于本文MutEx方法。另尝试利用文献[9]的方法识别本文阅览室场景中的8个球目标，在经历超过1.5 h的运算后得到超过1810个聚类，由于严重地遮挡和太少的球面点个数，最终未能在其中找到能够正确对应8个球目标的聚类。

本文实验所使用计算机配置了Inteli7-6700HQ型号CPU(主频2.6 GHz)和16 GB内存，计算程序由C++语言编写，编译为64位Release版可执行程序，程序对输入点云建立八叉树空间索引，点云微分属性计算与球心点互斥聚类皆利用八叉树优化邻近点查询效率。针对上述两幅实验点云图，本文方法各步骤计算耗时见表3。

表3 本文方法各步骤计算耗时

3 结 论

为了解决大场景中球目标的识别问题，本文设计了一个以曲率为输入量的球面点响应函数，能够快速排除大部分非球面点；而与这种非球面点的稀释作用相反，利用法向和曲率的球心点映射过程却让球面点大量汇聚于球心位置，从而使真实球目标的中心位置产生显著高于周围的映射点聚集现象。为正确识别这些聚类，还提出了球心点互斥的映射球心点自动聚类算法。与现有聚类方法不同，其构建了一个用以描述最邻近高密度点的树状结构，根据球心点之间的互斥特性对树进行快速剪枝，剪枝形成的子树即为球心点的自动聚类结果，而子树的根节点则是最有可能的球心点位置。通过对球心点局部密度和原始点云在对应球目标表面的覆盖率估计，最终确认场景中的球目标。这种聚类方法仅以原始点云的自然密度作为阈值，能够自动适应不同密度的点云，聚类结果与实际球目标的分布相一致。

利用真实场景扫描点云的实验结果证明，与现有的基于球心点聚类的球目标识别方法相比，在解决小场景中大占比球目标的识别问题时，本文方法具有更高地识别准确率和定位精度；而在解决大场景中小目标的识别问题时，更表现出突出的效率优势；同时，具有极强的敏感性，即使是在严重遮挡的情况下，场景中的小型球目标也都能够被准确地识别出来。

[1] YUN D, KIM S, HEO H, et al. Automated registration of multi-view point clouds using sphere targets [J]. Advanced Engineering Informatics, 2015, 29(4): 930-939.

[2] HUNTLEY J M. Fast Hough transform for automated detection of spheres in three-dimensional point clouds [J]. Optical Engineering, 2007, 46(5): 051002-1-051002-11.

[3] KHARBAT M, AOUF N, TSOURDOS A, et al. Sphere detection and tracking for a space capturing operation [C]// IEEE Conference on Advanced Video and Signal Based Surveillance. Los Alamitos: IEEE Computer Society Press, 2007: 182-187.

[4] MARJOLEIN V D G, FRANS M V, CHARL P B, et al. Determination of position and radius of ball joints [C]// Medical Imaging 2002 Conference. Bellingham: SPIE- International Society for Optical Engineering, 2002: 1571-1577.

[5] WANG A Y, SHI H, ZHANG Y, et al. Automatic registration of laser point cloud using precisely located sphere targets [J]. Journal of Applied Remote Sensing, 2014, 8(1): 5230-5237.

[6] BENLAMRI R. Curved shapes construction for object recognition [C]//Geometric Modeling and Processing — Theory and Applications. Los Alamitos: IEEE Computer Society Press, 2002: 197.

[7] MARSHALL D, LUKACS G, MARTIN R. Robust segmentation of primitives from range data in the presence of geometric degeneracy [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2001, 23(3): 304-314.

[8] 程志全, 叶永凯, 李宝. 一种基于RANSAC框架的椭球提取算法[J]. 图学学报, 2012, 33(2): 68-71.

[9] 李嘉, 阿依古丽•阿曼, 郑德华. 复杂场景三维点云中未知球形目标的自动识别方法[J]. 计算机辅助设计与图形学学报, 2013, 25(10): 1489-1495.

[10] 李胜男, 林晓, 陈言, 等. 基于点云的球面三维逆向建模[J]. 图学学报, 2013, 34(3): 49-52.

Spherical Target Recognition Method Based on Mutual Exclusion of Spherical Centers

LI Zikuan1, LIAO Wei2, LAN Qiuping1

(1. School of Earth Sciences and Engineering, Hohai University, Nanjing Jiangsu 211100, China; 2. Ningbo Urban Planning and Design Institute, Ningbo Zhejiang 315042, China)

A new spherical target recognition method based on mutual exclusion of sphere centers is proposed to solve the automatically identification problems of unknown number and unknown radius targets in large-scale 3D point clouds. First, an effective spherical point response function is specially designed to remove most of aspheric points, and every remaining spherical point is mapped to a sphere center by taking advantage of its normal and curvatures. Then, a novel tree-like structure for describing distribution and local density change rules of these centers is constructed, through a series of pruning operation complying with the mutually exclusion relationships between different sphere centers, the tree is split into several sub-trees, and a sub-tree correspond to a possible sphere target. Finally, the real sphere is confirmed by the local density of the root node of sub-tree and the coverage rate of points on the sphere surface. The experimental results demonstrate that the proposed sphere recognition method based on the mutual exclusion of sphere centers can effectively identify and precisely loc ate various spherical targets in a large and cluttered scene. Even in the case of serious occlusion, such as the exposed surface is less than 6%, the sphere can also be robustly identified.

spherical target recognition; spherical point response function; spherical center mutual exclusion; clustering; spherical coverage

TP 391

10.11996/JG.j.2095-302X.2018010050

A

2095-302X(2018)01-0050-07

2017-05-23；

2017-06-24

国家自然科学基金项目(41301406，41201439)；江苏省自然科学基金项目(BK20130829)

李子宽(1995–)，男，山西汾阳人，本科生。主要研究方向为点云数据处理与应用。E-mail：lzkcqz@163.com

蓝秋萍(1982–)，女，浙江衢州人，讲师，博士。主要研究方向为三维点云数据处理与三维建模。E-mail：lanqiuping@hhu.edu.cn