局部相关点平衡的三维激光点云骨架提取

局部相关点平衡的三维激光点云骨架提取 3D laser point cloud skeleton extraction via balance of local correlation points first-author 周明全（1954-），男，陕西西安人，教授，博士生导师，现任北京师范大学信息科学与技术学院院长，主要从事虚拟现实与可视化技术、智能信息处理、数据库与模式识别等方面的研究．E-mail： mqzhou@nwu.edu.cn http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226270&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226279&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226275&type= 22.01333237 32.00400543 周明全 （1954-），男，陕西西安人，教授，博士生导师，现任北京师范大学信息科学与技术学院院长，主要从事虚拟现实与可视化技术、智能信息处理、数据库与模式识别等方面的研究．E-mail： mqzhou@nwu.edu.cn mqzhou@nwu.edu.cn 李纯辉（1996-），男，陕西安康人，硕士研究生，主要从事计算机图形学、虚拟现实与可视化技术等方面的研究。E-mail：202021334@stumail.nwu.edu.cn http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226285&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226293&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226289&type= 22.01334000 32.00399780 李纯辉 （1996-），男，陕西安康人，硕士研究生，主要从事计算机图形学、虚拟现实与可视化技术等方面的研究。E-mail： 202021334@stumail.nwu.edu.cn 202021334@stumail.nwu.edu.cn corresp E-mail： ghgeng@nwu.edu.cn E-mail： ghgeng@nwu.edu.cn 耿国华（1955-），女,陕西西安人，博士，教授，博士研究生导师，CCF会员，主要从事智能信息处理、数据库与知识库、图形图像处理的研究。E-mail ： ghgeng@nwu.edu.cn http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226298&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226308&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226303&type= 22.01332855 32.00400162 耿国华 （1955-），女,陕西西安人，博士，教授，博士研究生导师，CCF会员，主要从事智能信息处理、数据库与知识库、图形图像处理的研究。E-mail ： ghgeng@nwu.edu.cn ghgeng@nwu.edu.cn 西北大学 信息科学与技术学院，陕西 西安 710127 西北大学 信息科学与技术学院，陕西 西安 710127 College of Information Science and Technology， Northwest University， Xi'an 710127， China College of Information Science and Technology， Northwest University， Xi'an 710127， China 激光扫描获取的点云模型形状分析和变形需要依赖骨架线完成。本文提出了一种快速自动获取激光扫描点云骨架线用以对模型进行形状变换的方法，同时减少手动绑定骨架导致的时间耗费。该方法将初始骨架点定义为点云模型中具有对称法向的最近相关点的中点，通过中点状态的平衡化得到最终的骨架点；然后采用主成分分析法搜寻满足方向一致性要求的骨架点组合，并利用广度优先搜索方法合并不同骨架分支；最后将各分支通过拉普拉斯平滑后相连，从而得到完整的骨架线，并将此骨架线应用于模型形状变换的任务中。实验将本文方法与 <math id="M1"><msub><mrow><mi>L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226317&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226313&type= 3.13266683 3.21733332 中轴骨架、质量驱动拓扑感知曲线骨架等方法进行对比，采用激光扫描的点云作为测试数据，验证了该算法的有效性、鲁棒性和高效性。本文算法提取效率提高到对于由8 077个点组成的点云提取骨架线仅需0.764 s，处理具有33 041个点的点云需4.356 s。将本文提取的激光扫描点云的骨架线应用于点云形状变化任务中，展示了此方法的实用性。 The shape analysis and shape transformation of the laser-scanning point cloud model depend on the curve skeleton. We proposed a fast and automatic method to obtain the curve skeleton of laser-scanning point cloud to transform the shape of the model and reduce the time consumption caused by manually binding the skeleton. In this method， the initial skeleton point is defined as the midpoint of the nearest correlation point with symmetrical normal in the point cloud. The final skeleton point is obtained by iterating the initial skeleton point to a balance position. Then the principal component analysis method is used to search for the combination of skeleton points that meet the requirements of direction consistency， and the breadth-first search method is used to merge the growing different skeleton branches. Finally， each branch is smoothed and connected by the Laplace smoothing method， a complete skeleton line is obtained and the curve skeleton is used in the task of model shape transformation. The proposed method is compared with the L 1 -Medial Skeleton， the Mass-driven Topology-aware Curve Skeleton method and other methods， and the original scanned point cloud is used as the test data to verify the effectiveness， robustness， and efficiency. The extraction efficiency of the proposed model is improved to the level that it takes 0.764 s to process the point cloud composed of 8 077 points， and it takes 4.356 s to process a point cloud with 33 041 points. The curve skeleton of laser scanned point cloud extracted is applied to the task of shape transformation of point cloud， which shows the practicability of this method. 计算机视觉 点云 激光扫描 骨架线 主成分分析法 拉普拉斯平滑 computer vision point cloud laser scanning curve skeleton PCA Laplacian smoothing 1 引 言 1 通过激光扫描设备扫描获取物体的点云模型，具有简单便捷、准确率高等优点 ［ 1 1 ］ ，成为目前最常用的数字化手段之一 ［ 2 2 ］ 。由一组骨架点和骨架点之间的拓扑关系 ［ 2 2 - 4 4 2-4 ］ 构成的点云模型骨架线能够有效描述点云模型的整体形状和拓扑结构 ［ 4 4 - 5 5 4-5 ］ 。因此，骨架线的计算、提取和匹配等成为计算机图形学 ［ 6 6 - 7 7 6-7 ］ 、计算机视觉 ［ 8 8 - 9 9 8-9 ］ 和机器智能 ［ 10 10 ］ 等领域的研究热点，并被广泛应用于形状分析 ［ 11 11 ］ 与重建 ［ 12 12 ］ 、路径规划 ［ 13 13 - 14 14 13-14 ］ 、动作和手势识别 ［ 15 15 - 17 17 15-17 ］ 、模型检索 ［ 18 18 - 20 20 18-20 ］ 以及植物分析 ［ 21 21 - 22 22 21-22 ］ 等任务中。基于骨架分析的相关研究都需要以骨架提取为基础，因此骨架线的提取至关重要。常见的骨架类型按照空间维度可以分为2D骨架和3D骨架两类 ［ 12 12 ］ ，其中2D骨架是由一组位于模型各分支的中间曲线构成的 ［ 4 4 ， 6 6 ， 23 23 ］ ，而3D骨架 ［ 24 24 ］ 则是由中心曲面和中心曲线共同构成的。相较于3D骨架，2D骨架线具有信息压缩程度高、拓扑关系明确等优势，因此其应用也更为广泛 ［ 9 9 ］ 。 目前已有诸多研究人员开展了点云模型2D骨架线提取相关工作，具体可以分为：（1）基于质心Voronoi细分（Centroidal Voronoi Tessellation， CVT）的方法 ［ 25 25 - 26 26 25-26 ］ 。该方法是骨架提取中应用最多的策略。例如：Lu等 ［ 26 26 ］ 通过变分特征将CVT概念推广到图中，将CVT应用在骨架提取的任务中，在提取骨架的同时还实现了对模型的形状分割，但该方法时间复杂度较高，针对大规模点云模型处理时间较长。（2）基于平均曲率流（Mean Curvature Flow， MCF）的方法 ［ 27 27 - 29 29 27-29 ］ ，该方法能提取到高质量的骨架。例如：Chuang等 ［ 29 29 ］ 发表了一种基于有限元跟踪的快速MCF的方法，随后Tagliasacchi等 ［ 27 27 ］ 将MCF应用在骨架提取的任务中，通过分析流动的微分特征，发现MCF局部增加了形状各向异性，利用其面积最小化的特性将曲率流推向极值，从而折叠输入网格几何体并获得骨架结构。（3）基于拉普拉斯收缩的算法。Cao等 ［ 4 4 ］ 提出了一种基于拉普拉斯收缩的曲线骨架提取算法（Laplacian-Based Contraction， LBC）。但是这些方法只能应用在经过降噪、去除异常值等操作处理之后的模型上，难以应用于使用激光扫描设备所获取的点云模型。（4）基于深度学习的方法。Atienza等 ［ 30 30 ］ 基于Pyramid U-Nets提出了PSPU-SkelNet，适用于从二维形状点云模型中提取曲线骨架任务。Lin等 ［ 24 24 ］ 基于中轴变换（Medial Axis Transform， MAT）提出了Point2Skeleton （P2S），用于从三维点云模型中提取二维骨架，从而指导表面重构和分割。Dou等 ［ 31 31 ］ 基于覆盖轴（Coverage Axis）提出一种深度学习的提取骨架的算法，其结果接近基于MAT的骨架提取算法。 适用于激光扫描点云模型的曲线骨架提取方法，大多都基于几何学相关原理 ［ 2 2 - 7 7 2-7 ］ 。Tagliasacchi等 ［ 2 2 ］ 基于旋转对称轴（Rotational Symmetry Axis， ROSA）的概念，构造了一种可以针对缺失大量数据的不完整点云模型的曲线骨架提取方法。Huang等 ［ 6 6 ］ 将 <math id="M2"><msub><mrow><mi mathvariant="normal">L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227841&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227839&type= 3.64066648 3.64066648 中轴（ <math id="M3"><msub><mrow><mi mathvariant="normal">L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227841&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227839&type= 3.64066648 3.64066648 -Medial）应用于曲线骨架提取任务中，将 <math id="M4"><msub><mrow><mi mathvariant="normal">L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227841&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227839&type= 3.64066648 3.64066648 中轴局部化自适应提取不同位置的中值点作为骨架点。Qin等 ［ 7 7 ］ 通过构建基于质量驱动拓扑感知的最优传输方案提取粗糙曲线骨架（MdCS），然后使用能量正则化完成几何优化，最终获得平滑曲线骨架。ROSA虽然能够应对大面积缺失数据的原始扫描点云模型，但是旋转对称轴的计算需要无噪声扰动的点云，因此针对噪声点云效果较差。 <math id="M5"><msub><mrow><mi mathvariant="normal">L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226351&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226348&type= 3.64066648 3.64066648 中轴骨架和MdCS虽然能应对存在噪声、异常值和缺失数据的原始扫描点云模型，但是 <math id="M6"><msub><mrow><mi mathvariant="normal">L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227841&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227839&type= 3.64066648 3.64066648 中轴骨架不能处理多分支结构的模型，MdCS拓扑结构准确度不高，且计算所需时间资源消耗巨大。 针对上述工作中存在的问题，受文献［ 32 32 - 34 34 32-34 ］的启发，本文提出一种快速提取激光扫描点云骨架线的方法。该方法将初始骨架点定义为三维模型中具有对称法向的最近相关点的中点，通过中点状态的平衡化迭代得到最终的骨架点；然后使用主成分分析法（Principal Component Analysis， PCA）分析骨架点的方向一致性，从而得到骨架曲线段；最后将使用广度优先搜索（Breadth First Search， BFS）合并后的曲线段利用拉普拉斯平滑进行优化并得到最终曲线骨架。本文实验将此算法应用在通过激光扫描设备得到的点云模型上，验证了算法的有效性、鲁棒性和高效性。将提取的激光扫描点云的骨架线应用在点云模型的动作变换任务中，展示了骨架线的实际作用。 2 基本原理 1 本文的骨架提取方法主要可以分为两步：提取骨架点和生成骨架线。首先，通过选择具有对称法向和最近距离的对称点的中点，获取初始骨架点，如 图1 图1 （a）所示；应用射线法去除模型外的初始骨架点，如 图1 图1 （b）所示；通过迭代来平衡骨架点并筛选权重大的骨架点组成最终骨架点，如 图1 图1 （c）所示。然后，基于PCA判断骨架点的方向一致性并重建骨架曲线，采用广度优先遍历算法合并骨架曲线，效果如 图1 图1 （d）所示；最后将平滑后的骨架曲线相连得到最终的曲线骨架，如 图1 图1 （e）所示；基于骨架的模型动作变换实际效果如 图1 图1 （f）所示。 2.1　提取骨架点 2 骨架点可以看作模型的部分采样点投影到模型内部得到的局部中心点 ［ 6 6 ］ ，也就是说，初始的骨架点是模型的点集通过采样处理得到的子集；另外，直接对采样点进行计算，还可以有效提高骨架线提取的效率，避免遍历点云上的所有点数据。除了基于效率的考虑，对模型下采样还能减少模型本身的一些不利因素对最终骨架的影响。例如，当模型不均匀时，通过均匀采样便可以避免这一缺陷；当遇到噪声时，采样也会减少异常值噪声对骨架提取任务的干扰。因此，本文算法首先进行随机采样，使得采样点能均匀的覆盖模型，从而避免骨架线变形。具体而言，对于一个离散点云模型 <math id="M7"><mi mathvariant="bold-italic">P</mi><mo>=</mo><mo stretchy="false">{</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>i</mi></mrow></msub><msub><mrow><mo stretchy="false">}</mo></mrow><mrow><mi>i</mi><mo>∈</mo><mi>I</mi></mrow></msub><mo>⊂</mo><msup><mrow><mi mathvariant="bold-italic">R</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226384&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226380&type= 25.65399933 5.07999992 ，其中 <math id="M8"><mi mathvariant="bold-italic">I</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226392&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226389&type= 1.86266661 2.79399991 是点云 <math id="M9"><mi mathvariant="bold-italic">P</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226454&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226448&type= 2.70933342 2.79399991 的点数，将采样点组成的集合记作 <math id="M10"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226410&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226406&type= 3.38666677 3.72533321 ，从 <math id="M11"><mi mathvariant="bold-italic">P</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226454&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226448&type= 2.70933342 2.79399991 中使用随机算法获得点的索引，本文实验中采样点的规模为 <math id="M12"><mn mathvariant="normal">0.1</mn><mo>×</mo><mi mathvariant="bold-italic">I</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226427&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226423&type= 12.19200039 2.79399991 。 2 . 1 . 1　法向估计和重定向 3 本文中初始骨架点需要基于法向求解，所以首先需要估计采样点的法向 ［ 35 35 - 36 36 35-36 ］ 。本文使用PCA对 <math id="M13"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226435&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226432&type= 3.38666677 3.72533321 中的点进行法向估计，即： <math id="M14"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226516&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226512&type= 3.21733332 4.57200003 及其在 <math id="M15"><mi mathvariant="bold-italic">P</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226454&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226448&type= 2.70933342 2.79399991 上的邻域点共同构成点集 <math id="M16"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226464&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226460&type= 3.30200005 3.72533321 ，对 <math id="M17"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226713&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226710&type= 3.30200005 3.72533321 进行特征分解得到特征值和特征向量，将最小特征值对应的特征向量 <math id="M18"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226533&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226528&type= 3.55599999 4.82600021 作为 <math id="M19"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226516&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226512&type= 3.21733332 4.57200003 的法向。具体如下，利用 式（1） 式（1） 计算邻域点集 <math id="M20"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226713&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226710&type= 3.30200005 3.72533321 的中心点 <math id="M21"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226500&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226497&type= 4.06400013 4.57200003 ： <math display="block" id="M22"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>m</mi></mrow></msub><mo>=</mo><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mi>k</mi></mrow></mfrac><mstyle displaystyle="true"><munderover><mo largeop="true">∑</mo><mrow><mi>t</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><mi>k</mi></mrow></munderover></mstyle><mrow><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow></msub></mrow></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226509&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226504&type= 19.55800056 8.63599968 . 此时 <math id="M23"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226516&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226512&type= 3.21733332 4.57200003 和法向 <math id="M24"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226523&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226520&type= 3.55599999 4.82600021 应该满足 <math id="M25"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226533&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226528&type= 3.55599999 4.82600021 使得 <math id="M26"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226713&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226710&type= 3.30200005 3.72533321 中所有的邻域点在方向 <math id="M27"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226552&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226548&type= 3.55599999 4.82600021 上的投影分布最密集： <math display="block" id="M28"><munder><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi></mrow><mrow><msub><mrow><mi>p</mi></mrow><mrow><mi>m</mi></mrow></msub><mo>,</mo><msub><mrow><mi>p</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>,</mo><mfenced open="‖" close="‖" separators="|"><mrow><msubsup><mrow><mi>p</mi></mrow><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msubsup></mrow></mfenced><mo>=</mo><mn mathvariant="normal">1</mn></mrow></munder><mstyle displaystyle="true"><munderover><mo largeop="true">∑</mo><mrow><mi>t</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><mi>k</mi></mrow></munderover></mstyle><mrow><mo stretchy="false">(</mo><mo stretchy="false">(</mo><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow></msub><mo>-</mo><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>m</mi></mrow></msub><msup><mrow><mo stretchy="false">)</mo></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msubsup><msup><mrow><mo stretchy="false">)</mo></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup></mrow></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226560&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226556&type= 43.18000031 8.63599968 ， 式中： <math id="M29"><mi>k</mi><mo>=</mo><mn mathvariant="normal">20</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226570&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226567&type= 10.24466610 2.79399991 ，将 <math id="M30"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow></msub><mo>-</mo><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226577&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226574&type= 11.59933376 4.57200003 记作 <math id="M31"><msub><mrow><mover><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>˜</mi></mrow></mover></mrow><mrow><mi>t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226585&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226581&type= 3.13266683 4.74133301 ，则有 <math id="M32"><mi mathvariant="normal">m</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi><mo>∑</mo><msubsup><mrow/><mrow><mi>t</mi><mo>=</mo><mn mathvariant="normal">1</mn></mrow><mrow><mi>k</mi></mrow></msubsup><mo stretchy="false">(</mo><msup><mrow><msub><mrow><mover><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>˜</mi></mrow></mover></mrow><mrow><mi>t</mi></mrow></msub></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msubsup><msup><mrow><mo stretchy="false">)</mo></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup><mo>,</mo><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>∈</mo><msup><mrow><mi mathvariant="bold-italic">R</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msup><mo>,</mo><mi>s</mi><mo>.</mo><mi>t</mi><mo>.</mo><mo>:</mo><mfenced open="‖" close="‖" separators="|"><mrow><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msubsup></mrow></mfenced><mo>=</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226594&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226591&type= 66.12466431 4.91066647 ，展开可以得到： <math id="M33"><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi><msup><mrow><mi mathvariant="bold-italic">z</mi></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup><mo stretchy="false">(</mo><mover><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>˜</mi></mrow></mover><msup><mrow><mover><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>˜</mi></mrow></mover></mrow><mrow><mi mathvariant="normal">T</mi></mrow></msup><mo stretchy="false">)</mo><mi mathvariant="bold-italic">z</mi><mo>,</mo><mi mathvariant="bold-italic">z</mi><mo>∈</mo><msup><mrow><mi mathvariant="bold-italic">R</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msup><mo>,</mo><mi>s</mi><mo>.</mo><mi>t</mi><mo>.</mo><mo>:</mo><mfenced open="‖" close="‖" separators="|"><mrow><mi mathvariant="bold-italic">z</mi></mrow></mfenced><mo>=</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226601&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226597&type= 56.72666931 4.31799984 ，对协方差矩阵进行特征值分解之后得到特征值 <math id="M34"><msub><mrow><mi>λ</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226609&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226606&type= 2.96333337 3.72533321 ， <math id="M35"><msub><mrow><mi>λ</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226616&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226613&type= 2.96333337 3.72533321 ， <math id="M36"><msub><mrow><mi>λ</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226623&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226620&type= 2.96333337 3.72533321 及其对应的特征向量 <math id="M37"><msub><mrow><mi mathvariant="bold-italic">n</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226630&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226627&type= 3.30200005 3.72533321 ， <math id="M38"><msub><mrow><mi mathvariant="bold-italic">n</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226637&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226634&type= 3.30200005 3.72533321 ， <math id="M39"><msub><mrow><mi mathvariant="bold-italic">n</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226646&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226642&type= 3.30200005 3.72533321 。其中最小特征值对应的特征向量便是所求的采样点 <math id="M40"><msub><mrow><mi>p</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226651&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226648&type= 3.13266683 4.57200003 的法向 <math id="M41"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>t</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226657&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226654&type= 3.55599999 4.82600021 ，即 <math id="M42"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>s</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226674&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226671&type= 3.55599999 4.82600021 。使用PCA还可以抵抗噪声带来的影响。当模型表面存在噪声时，噪声会影响最小特征值的大小，但是由于噪声相较于模型点集的占比很小，并不足以导致特征值的顺序重排，最小特征值相较于其他两个特征值的顺序与不受噪声干扰时排序是一致的，此时最小特征值对应的特征向量还是可以看作 <math id="M43"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226668&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226665&type= 3.21733332 4.57200003 的法向量 <math id="M44"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>s</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226674&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226671&type= 3.55599999 4.82600021 。 由于上述过程计算的法向具有二义性 ［ 37 37 ］ ，如 图2 图2 （a）所示，而这种二义性会影响骨架点的求解过程，所以还需要对法向的二义性进行消除，即法向的重定向。具体而言，对于两个距离很近的采样点 <math id="M45"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226931&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226928&type= 3.21733332 4.57200003 ， <math id="M46"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226688&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226684&type= 3.13266683 4.57200003 ，如果他们的法向 <math id="M47"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226891&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226887&type= 3.55599999 4.82600021 ， <math id="M48"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226902&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226899&type= 3.55599999 4.82600021 同向，则满足 <math id="M49"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>⋅</mo><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>≈</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226708&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226703&type= 15.57866764 4.82600021 。本文使用深度优先算法（Depth First Search， DFS）来快速完成重定向。具体而言，选择距离 <math id="M50"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226713&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226710&type= 3.30200005 3.72533321 的中心点 <math id="M51"><msubsup><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>s</mi></mrow><mrow><mi mathvariant="normal">O</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226721&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226716&type= 4.57200003 3.97933316 最远的采样点 <math id="M52"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226931&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226928&type= 3.21733332 4.57200003 ，如果 <math id="M53"><mfenced open="‖" close="‖" separators="|"><mrow><mo stretchy="false">(</mo><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>+</mo><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo stretchy="false">)</mo><mo>-</mo><msubsup><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>s</mi></mrow><mrow><mi mathvariant="normal">O</mi></mrow></msubsup></mrow></mfenced><mo>></mo><mfenced open="‖" close="‖" separators="|"><mrow><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>-</mo><msubsup><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>s</mi></mrow><mrow><mi mathvariant="normal">O</mi></mrow></msubsup></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226735&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226732&type= 46.31266785 4.82600021 ，则 <math id="M54"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>=</mo><mo>-</mo><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226742&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226738&type= 14.73200035 4.82600021 ，反之则不改变 <math id="M55"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226751&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226745&type= 3.55599999 4.82600021 。随后使用K最邻近算法（K-Nearest Neighbor， KNN）可以直接得到 <math id="M56"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226931&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226928&type= 3.21733332 4.57200003 的距离最近的一个 <math id="M57"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226768&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226764&type= 3.38666677 3.72533321 中的点 <math id="M58"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226907&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226905&type= 3.13266683 4.57200003 ，如果 <math id="M59"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>⋅</mo><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>/</mo><mo stretchy="false">(</mo><mfenced open="|" close="|" separators="|"><mrow><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup></mrow></mfenced><mo>×</mo><mfenced open="|" close="|" separators="|"><mrow><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow><mrow><mi>n</mi></mrow></msubsup></mrow></mfenced><mo stretchy="false">)</mo><mo>≤</mo><mo>-</mo><mn mathvariant="normal">0.5</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226780&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226776&type= 45.80466461 4.82600021 ，则 <math id="M60"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>=</mo><mo>-</mo><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226786&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226782&type= 15.07066536 4.82600021 ，并将 <math id="M61"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226925&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226923&type= 3.13266683 4.57200003 标记为已经访问的状态，此时令 <math id="M62"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>=</mo><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226798&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226795&type= 10.75266743 4.57200003 。通过KNN算法寻找一个没有被标记为已访问状态的采样点作为 <math id="M63"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226805&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226801&type= 3.13266683 4.57200003 ，重复上述过程，直到 <math id="M64"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226818&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226815&type= 3.30200005 3.72533321 中所有的点都被标记为访问的状态。此时 <math id="M65"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>t</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226818&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226815&type= 3.30200005 3.72533321 中所有的点都将指向模型的同侧，消除了法向的二义性，如 图2 图2 （b）所示。用该重定向方法重定向之后的法向，都指向模型的内部。 2 . 1 . 2　骨架点的求解 3 要进行骨架点识别，本节首先做以下定义： 定义一：对于采样点集合 <math id="M66"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226885&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226882&type= 3.38666677 3.72533321 中的任意一点 <math id="M67"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226931&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226928&type= 3.21733332 4.57200003 ，存在 <math id="M68"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow></msub><mo>∈</mo><mi mathvariant="bold-italic">P</mi><mo>,</mo><mi mathvariant="bold-italic">j</mi><mo>∈</mo><mi mathvariant="bold-italic">S</mi><mo>\</mo><mo stretchy="false">{</mo><mi>i</mi><mo stretchy="false">}</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226846&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226843&type= 25.82333374 4.91066647 是和 <math id="M69"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226931&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226928&type= 3.21733332 4.57200003 具有相反法向的点中距离 <math id="M70"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226931&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226928&type= 3.21733332 4.57200003 最近的点，将 <math id="M71"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226925&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226923&type= 3.13266683 4.57200003 和 <math id="M72"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226931&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226928&type= 3.21733332 4.57200003 定义为一组相关点。 定义二：一组相关点的中点是初始骨架点。 对于 <math id="M73"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226885&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226882&type= 3.38666677 3.72533321 中的任意一点 <math id="M74"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226931&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226928&type= 3.21733332 4.57200003 ，从 <math id="M75"><msub><mrow><mi mathvariant="bold-italic">P</mi></mrow><mrow><mi>s</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226885&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226882&type= 3.38666677 3.72533321 中识别出一组法向与 <math id="M76"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226891&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226887&type= 3.55599999 4.82600021 相反的点，在这里法向 <math id="M77"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226898&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226895&type= 3.55599999 4.82600021 和 <math id="M78"><msubsup><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226902&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226899&type= 3.55599999 4.82600021 使用一个带阈值的点积来判断。在得到的这一组法向中，进一步找到特定点 <math id="M79"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226907&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226905&type= 3.13266683 4.57200003 ，使得 <math id="M80"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226925&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226923&type= 3.13266683 4.57200003 到 <math id="M81"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226921&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226917&type= 3.21733332 4.57200003 的欧氏距离最小，随后计算出 <math id="M82"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226925&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226923&type= 3.13266683 4.57200003 和 <math id="M83"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226931&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226928&type= 3.21733332 4.57200003 的中点作为初始骨架点。当模型的分支之间的距离较小时，识别到的相关点可能并不在一个分支上，导致提取到无效的冗余骨架点，如 图1 图1 （a）中手臂和身体之间产生的无效骨架点，此时需要通过算法将不在模型中的相关点之间的中点，也就是无效的骨架点去除掉。具体而言，本文使用射线法来去除无效骨架点，从而得到有效骨架点。射线法具体是指从任意一点出发，从该点射出的射线，如果与模型边界的交点数量为奇数，则该点在模型内部；反之，如果交点为偶数，则该点在模型的外部，如 图3 图3 所示（彩图见期刊电子版）。 在将无效的骨架点去除之后，效果如 图1 图1 （b）所示。当模型足够简单时，例如圆柱模型，这些点可以直接形成模型 <math id="M84"><mi mathvariant="bold-italic">P</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227299&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227296&type= 2.70933342 2.79399991 的骨架，但是当模型不是简单的基本几何形状时，还需要使初始骨架点进一步收敛到最终骨架点的位置。由于此时的有效骨架点 <math id="M85"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>∈</mo><mi mathvariant="bold-italic">Q</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226951&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226948&type= 9.48266602 4.57200003 可以看作是模型上的采样点 <math id="M86"><msub><mrow><mi mathvariant="bold-italic">p</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226957&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226954&type= 3.21733332 4.57200003 经过位置变换得到的，受文献［ 38 38 ］的启发，在垂直于骨架点法向 <math id="M87"><msubsup><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow><mrow><mi>n</mi></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226962&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226960&type= 3.13266683 4.82600021 的平面上，在每个有效的骨架点 <math id="M88"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 处均匀地发射出 <math id="M89"><mi>m</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227019&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227016&type= 2.87866688 2.79399991 条射线，其中第 <math id="M90"><mi>j</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226980&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226977&type= 1.60866666 3.64066648 条和第 <math id="M91"><mi>j</mi><mo>+</mo><mi>m</mi><mo>/</mo><mn mathvariant="normal">2</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226985&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226983&type= 12.95400047 3.89466691 条射线的方向是相反的。从骨架点 <math id="M92"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 出发，沿着每条射线方向迭代地向前搜索，直到靠近模型上的任意一点，将 <math id="M93"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 到该点的距离记作 <math id="M94"><msub><mrow><mi>d</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227002&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37226999&type= 2.87866688 3.72533321 ，将 <math id="M95"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 到模型上该点的方向标记为向量 <math id="M96"><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>j</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227013&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227009&type= 3.64066648 3.89466691 。本文实验中， <math id="M97"><mi>m</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227019&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227016&type= 2.87866688 2.79399991 的数量为16条，被分为8对，每对由两个方向相反的向量 <math id="M98"><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>j</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227024&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227022&type= 3.64066648 3.89466691 ， <math id="M99"><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>j</mi><mo>+</mo><mn mathvariant="normal">8</mn></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227030&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227027&type= 6.26533365 3.97933316 组成。对于点集 <math id="M100"><mi mathvariant="bold-italic">Q</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227309&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227304&type= 2.96333337 3.13266683 中的任意一点 <math id="M101"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 ，定义 <math id="M102"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227511&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227506&type= 2.70933342 4.57200003 的能量 <math id="M103"><msub><mrow><mi mathvariant="bold-italic">E</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227052&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227049&type= 4.40266657 3.72533321 为： <math display="block" id="M104"><msub><mrow><mi mathvariant="bold-italic">E</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msub><mo>=</mo><munder><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi></mrow><mrow><mn mathvariant="normal">1</mn><mo><</mo><mi>j</mi><mo><</mo><mfrac><mrow><mi>m</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac></mrow></munder><mfenced open="‖" close="‖" separators="|"><mrow><msubsup><mrow><mi>d</mi></mrow><mrow><mi>j</mi></mrow><mrow><mi>i</mi></mrow></msubsup><mo>-</mo><msubsup><mrow><mi>d</mi></mrow><mrow><mi>j</mi><mo>+</mo><mfrac><mrow><mi>m</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac></mrow><mrow><mi>i</mi></mrow></msubsup></mrow></mfenced><mo>/</mo><mi>m</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227057&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227054&type= 42.58732986 10.75266743 . 由上述定义可得到骨架点 <math id="M105"><mi mathvariant="bold-italic">Q</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227309&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227304&type= 2.96333337 3.13266683 的平衡状态如 式（4） 式（4） 所示： <math display="block" id="M106"><mtable columnalign="left"><mtr><mtd><munder><mrow><mi mathvariant="normal">a</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">g</mi><mi mathvariant="normal">m</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>∈</mo><mi>Q</mi></mrow></munder><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mi>r</mi></mrow></mfrac><munder><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi></mrow><mrow><mn mathvariant="normal">1</mn><mo><</mo><mi>j</mi><mo><</mo><mfrac><mrow><mi>m</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac></mrow></munder><msub><mrow><mfenced open="‖" close="‖" separators="|"><mrow><msubsup><mrow><mi>d</mi></mrow><mrow><mi>j</mi></mrow><mrow><mi>i</mi></mrow></msubsup><mo>-</mo><msubsup><mrow><mi>d</mi></mrow><mrow><mi>j</mi><mo>+</mo><mfrac><mrow><mi>m</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac></mrow><mrow><mi>i</mi></mrow></msubsup></mrow></mfenced></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msub><mo>/</mo><mi>m</mi><mo>=</mo></mtd></mtr><mtr><mtd><munder><mrow><mi mathvariant="normal">a</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">g</mi><mi mathvariant="normal">m</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>t</mi></mrow></msub><mo>∈</mo><mi>Q</mi></mrow></munder><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mi>r</mi></mrow></mfrac><mstyle displaystyle="true"><munderover><mo largeop="true">∑</mo><mrow><mi>t</mi><mo>=</mo><mn mathvariant="normal">0</mn></mrow><mrow><msub><mrow><mi>N</mi></mrow><mrow><mi>Q</mi></mrow></msub></mrow></munderover></mstyle><mrow><msub><mrow><mi>E</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msub></mrow><mo>,</mo></mtd></mtr></mtable></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227069&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227066&type= 54.01733780 21.84399986 其中： <math id="M107"><msub><mrow><mi>N</mi></mrow><mrow><mi mathvariant="normal">Q</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227075&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227072&type= 4.65666676 3.80999994 是 <math id="M108"><mi>Q</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227083&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227079&type= 2.87866688 3.21733332 中点的数量， <math id="M109"><mi>r</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227088&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227086&type= 1.69333339 2.79399991 是模型的最小边界球的半径。根据上述定义，可知 <math id="M110"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 和 <math id="M111"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227536&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227532&type= 6.26533365 4.57200003 之间的关系如 式（5） 式（5） 所示： <math display="block" id="M112"><mtable columnalign="left"><mtr><mtd><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow></msub><mo>=</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>+</mo><munder><mo movablelimits="false">∑</mo><mrow><mn mathvariant="normal">1</mn><mo><</mo><mi>j</mi><mo><</mo><mfrac><mrow><mi>m</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac></mrow></munder><mrow><mo stretchy="false">(</mo><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>j</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msubsup><mo>-</mo><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>j</mi><mo>+</mo><mfrac><mrow><mi>m</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msubsup><mo stretchy="false">)</mo></mrow><mo>/</mo></mtd></mtr><mtr><mtd><mfenced open="‖" close="‖" separators="|"><mrow><munder><mo movablelimits="false">∑</mo><mrow><mn mathvariant="normal">1</mn><mo><</mo><mi>j</mi><mo><</mo><mfrac><mrow><mi>m</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac></mrow></munder><mrow><mo stretchy="false">(</mo><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>j</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msubsup><mo>-</mo><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>j</mi><mo>+</mo><mfrac><mrow><mi>m</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></mrow></msubsup><mo stretchy="false">)</mo></mrow></mrow></mfenced><mo>×</mo><mi mathvariant="normal">L</mi><mo>,</mo></mtd></mtr></mtable></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227107&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227103&type= 48.93733215 26.16200066 其中， <math id="M113"><mi>L</mi><mo>=</mo><mn mathvariant="normal">0.01</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227113&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227110&type= 14.90133286 2.79399991 是步长参数。当 式（3） 式（3） 中能量梯度为0时，意味着任意一个 <math id="M114"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 的 <math id="M115"><mi>E</mi><mo>=</mo><mn mathvariant="normal">0</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227126&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227122&type= 9.39799976 2.79399991 ，也就是 <math id="M116"><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227334&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227329&type= 2.62466669 4.57200003 的位置处于模型横截面的中心位置，如 图4 图4 （c）所示。根据上述过程，便可以完成骨架点的提取。在获取初始骨架点下个位置的同时也可以得到下次移动的方向，可以加速初始骨架点平衡化的过程。但是此时的骨架点数量还是远远大于最终用来生成骨架点的数量，所以还需要进一步从骨架点中筛选合适的骨架点。这里使用二次邻域中权值比较的方式来完成骨架点的选择。具体而言，对于一个骨架点 <math id="M117"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 ，其权值被定义为骨架点 <math id="M118"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 的 <math id="M119"><msub><mrow><mi>r</mi></mrow><mrow><mi mathvariant="normal">k</mi><mi mathvariant="normal">n</mi><mi mathvariant="normal">n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227178&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227175&type= 4.65666676 3.72533321 邻域内点的数量 <math id="M120"><mi>N</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227154&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227151&type= 3.30200005 2.87866688 。对于 <math id="M121"><mi mathvariant="bold-italic">Q</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227309&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227304&type= 2.96333337 3.13266683 中任意一个骨架点 <math id="M122"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227168&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227165&type= 2.70933342 4.57200003 ，将 <math id="M123"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 的 <math id="M124"><msub><mrow><mi>r</mi></mrow><mrow><mi mathvariant="normal">k</mi><mi mathvariant="normal">n</mi><mi mathvariant="normal">n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227178&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227175&type= 4.65666676 3.72533321 邻域中的点记作 <math id="M125"><mi mathvariant="bold-italic">Q</mi><mmultiscripts><mrow/><mprescripts/><mrow><mi>r</mi></mrow><mrow/></mmultiscripts></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227190&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227187&type= 4.57200003 4.06400013 ，则对于 <math id="M126"><mi mathvariant="bold-italic">Q</mi><mmultiscripts><mrow/><mprescripts/><mrow><mi>r</mi></mrow><mrow/></mmultiscripts></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227190&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227187&type= 4.57200003 4.06400013 中所有的骨架点而言，应该保留的 <math id="M127"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>r</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227197&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227193&type= 2.96333337 4.57200003 应该满足 式（6） 式（6） ： <math display="block" id="M128"><msub><mrow><mi>q</mi></mrow><mrow><mi>r</mi></mrow></msub><mo>=</mo><munder><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>r</mi></mrow></msub><mo>∈</mo><msub><mrow><mi>Q</mi></mrow><mrow><mi>r</mi></mrow></msub></mrow></munder><msub><mrow><mi>W</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>r</mi></mrow></msub></mrow></msub><mo>=</mo><munder><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">x</mi></mrow><mrow><msub><mrow><mi>q</mi></mrow><mrow><mi>r</mi></mrow></msub><mo>∈</mo><msub><mrow><mi>Q</mi></mrow><mrow><mi>r</mi></mrow></msub></mrow></munder><msub><mrow><mi>N</mi></mrow><mrow><mi mathvariant="normal">K</mi><mi mathvariant="normal">N</mi><mi mathvariant="normal">N</mi><mo stretchy="false">(</mo><msub><mrow><mi>q</mi></mrow><mrow><mi>r</mi></mrow></msub><mo>,</mo><msub><mrow><mi>r</mi></mrow><mrow><mi mathvariant="normal">k</mi><mi mathvariant="normal">n</mi><mi mathvariant="normal">n</mi></mrow></msub><mo stretchy="false">)</mo></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227205&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227200&type= 47.24399948 5.67266655 . 2.2　骨架生成 2 上述迭代过程能够得到一组骨架点 <math id="M139"><mi mathvariant="bold-italic">Q</mi><mo>=</mo><mo stretchy="false">{</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">}</mo><mo>,</mo><mi>i</mi><mo>∈</mo><msub><mrow><mi>N</mi></mrow><mrow><mi>Q</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227282&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227277&type= 25.73866653 4.91066647 ，它是输入点云模型 <math id="M140"><mi mathvariant="bold-italic">P</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227299&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227296&type= 2.70933342 2.79399991 的各个分支的中间地带，仅表示了模型 <math id="M141"><mi mathvariant="bold-italic">P</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227299&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227296&type= 2.70933342 2.79399991 骨架的位置信息，而完整的骨架线还包含了骨架点之间及骨架分支之间的拓扑连接信息。所以本节计算骨架点 <math id="M142"><mi mathvariant="bold-italic">Q</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227309&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227304&type= 2.96333337 3.13266683 的拓扑连接信息。 首先，使用PCA来检查 <math id="M143"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 和它的邻域点集是否满足方向一致性的条件，随后将满足要求的邻域点集生成模型曲线骨架拓扑关系的子集，进一步通过广度优先搜索算法将存在连接关系的子集合并得到模型的骨架曲线分支，再通过拉普拉斯平滑骨架曲线分支，最后将平滑后的骨架曲线分支组织成完整的曲线骨架。 PCA常被用来检测骨架点是否达到收敛要求 ［ 6 6 ， 23 23 ］ ，即：对于骨架点 <math id="M144"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 ，计算 <math id="M145"><msub><mrow><mi>q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227334&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227329&type= 2.62466669 4.57200003 及其 <math id="M146"><mi>k</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227342&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227339&type= 1.69333339 2.79399991 邻域内点集的协方差矩阵的特征值和特征向量，如 式（7） 式（7） 所示： <math display="block" id="M147"><msub><mrow><mi mathvariant="bold-italic">C</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>=</mo><munder><mo movablelimits="false">∑</mo><mrow><mn mathvariant="normal">0</mn><mo><</mo><mi>i</mi><mi>'</mi><mo><</mo><mi>k</mi><mo>,</mo><mi>i</mi><mi>'</mi><mo>≠</mo><mi>i</mi></mrow></munder><mrow><mo stretchy="false">(</mo><mfenced open="‖" close="‖" separators="|"><mrow><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>-</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><msup><mrow><mi>i</mi></mrow><mrow><mi mathvariant="normal">'</mi></mrow></msup></mrow></msub></mrow></mfenced><mo stretchy="false">)</mo><mo stretchy="false">(</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>-</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><msup><mrow><mi>i</mi></mrow><mrow><mi>'</mi></mrow></msup></mrow></msub><msup><mrow><mo stretchy="false">)</mo></mrow><mrow><mi>T</mi></mrow></msup><mo stretchy="false">(</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>-</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><msup><mrow><mi>i</mi></mrow><mrow><mi>'</mi></mrow></msup></mrow></msub><mo stretchy="false">)</mo></mrow></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227352&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227347&type= 66.46333313 7.28133297 ， 其中：所有的特征值满足 <math id="M148"><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msubsup><mo>≤</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msubsup><mo>≤</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227365&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227358&type= 18.37266731 4.48733330 都是实值，对应的特征向量 <math id="M149"><mo stretchy="false">{</mo><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msubsup><mo>,</mo><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msubsup><mo>,</mo><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo stretchy="false">}</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227374&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227370&type= 16.84866714 4.74133301 形成一个正交框架，即 <math id="M150"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 和其邻域点的主成分。定义 <math id="M151"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227393&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227388&type= 2.70933342 4.57200003 和其邻域点的方向一致性为 <math id="M152"><msub><mrow><mi>σ</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227427&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227423&type= 2.45533323 3.72533321 ，则有如 式（8） 式（8） 的关系： <math display="block" id="M153"><msub><mrow><mi>σ</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>=</mo><mi>σ</mi><mo stretchy="false">(</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub><mo stretchy="false">)</mo><mo>=</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo>/</mo><mo stretchy="false">(</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msubsup><mo>+</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msubsup><mo>+</mo><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227410&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227406&type= 46.99000168 5.07999992 . <math id="M154"><msub><mrow><mi>σ</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227427&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227423&type= 2.45533323 3.72533321 的实际含义是当 <math id="M155"><msub><mrow><mi>σ</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227427&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227423&type= 2.45533323 3.72533321 越接近1，即 <math id="M156"><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227436&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227432&type= 2.96333337 3.97933316 ， <math id="M157"><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227445&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227441&type= 2.96333337 3.97933316 和 <math id="M158"><msubsup><mrow><mi>λ</mi></mrow><mrow><mi>i</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msubsup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227454&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227450&type= 2.96333337 3.97933316 相比越小，更多的点分布在沿着分支对齐的位置，也就是方向一致性越高。实践中，设置 <math id="M159"><mi>k</mi><mo>=</mo><mn mathvariant="normal">3</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227480&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227474&type= 8.38199997 2.79399991 ，对于任意 <math id="M160"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 而言，如果 <math id="M161"><msub><mrow><mi>σ</mi></mrow><mrow><mi>i</mi></mrow></msub><mo>></mo><mn mathvariant="normal">0.9</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227502&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227493&type= 13.03866673 3.72533321 ，便可以认为 <math id="M162"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227511&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227506&type= 2.70933342 4.57200003 和它的两个邻域点已经满足骨架点的收敛要求，可以认为对于点 <math id="M163"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227518&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227514&type= 2.70933342 4.57200003 和 <math id="M164"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227536&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227532&type= 6.26533365 4.57200003 ， <math id="M165"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227536&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227532&type= 6.26533365 4.57200003 和 <math id="M166"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>i</mi><mo>+</mo><mn mathvariant="normal">2</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227546&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227540&type= 6.26533365 4.57200003 而言，存在拓扑关系。随后遍历所有骨架点，便可以得到达到要求的所有的两个点之间的拓扑关系，记作 <math id="M167"><mi mathvariant="bold-italic">R</mi><mo>=</mo><mo stretchy="false">{</mo><mo stretchy="false">(</mo><msubsup><mrow><mi mathvariant="bold-italic">r</mi></mrow><mrow><mi>m</mi></mrow><mrow><mi>n</mi></mrow></msubsup><msub><mrow><mo stretchy="false">)</mo><mo stretchy="false">}</mo></mrow><mrow><mi>m</mi><mo>∈</mo><mi>Q</mi><mo>,</mo><mi>n</mi><mo>∈</mo><mi>Q</mi><mo>,</mo><mi>m</mi><mo>≠</mo><mi>n</mi></mrow></msub><mo>,</mo><msubsup><mrow><mi mathvariant="bold-italic">r</mi></mrow><mrow><mi>m</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>=</mo><mo stretchy="false">(</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi></mrow></msub><mo>,</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227555&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227549&type= 55.45666885 5.07999992 ，如 图5 图5 （a）所示。 得到 <math id="M178"><mi mathvariant="bold-italic">R</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227656&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227650&type= 2.87866688 2.79399991 之后，使用广度优先搜索，增长 <math id="M179"><mo stretchy="false">(</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi></mrow></msub><mo>,</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227665&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227660&type= 11.76866722 4.82600021 的关系，得到 <math id="M180"><msub><mrow><mi>R</mi></mrow><mrow><mi mathvariant="normal">L</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227673&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227671&type= 4.23333359 3.72533321 ，如 图5 图5 （b）所示。增长后的效果如 图1 图1 （c）所示。随后对于 <math id="M181"><msub><mrow><mi mathvariant="bold-italic">R</mi></mrow><mrow><mi mathvariant="normal">L</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227681&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227677&type= 4.31799984 3.72533321 中任意 <math id="M182"><msubsup><mrow><mi mathvariant="bold-italic">r</mi></mrow><mrow><mi>m</mi></mrow><mrow><mi>n</mi></mrow></msubsup><mo>=</mo><mo stretchy="false">(</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi></mrow></msub><mo>,</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msub><mo>,</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>n</mi></mrow></msub><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227688&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227685&type= 43.09533310 5.07999992 两端的端点 <math id="M183"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227735&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227733&type= 3.64066648 4.57200003 和 <math id="M184"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227724&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227721&type= 3.13266683 4.57200003 ，对 <math id="M185"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227735&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227733&type= 3.64066648 4.57200003 寻找最近骨架点 <math id="M186"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227711&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227708&type= 7.19666624 4.57200003 ，构成方向向量 <math id="M187"><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>m</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow></msubsup><mo>=</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow></msub><mo>-</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227718&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227715&type= 27.68600082 4.82600021 ，同理得 <math id="M188"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227724&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227721&type= 3.13266683 4.57200003 的方向向量 <math id="M189"><msubsup><mrow><mi mathvariant="bold-italic">v</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow><mrow><mi>n</mi></mrow></msubsup><mo>=</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>-</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227730&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227727&type= 26.24666595 4.82600021 ，使它们在此方向上迭代寻找合适的骨架点相连即可得到完整的骨架。由于在此过程中，在尺度变化剧烈时，可能会导致骨架曲线的变化不够平滑。为了减少这种剧烈变化带来的质量上的影响，采用拉普拉斯收缩以获得平滑的骨架曲线。对于拉普拉斯平滑策略点 <math id="M190"><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227735&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227733&type= 3.64066648 4.57200003 的定义如 式（9） 式（9） 所示： <math display="block" id="M191"><mfenced open="{" close="" separators="|"><mrow><mtable columnalign="left"><mtr><mtd><msubsup><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi></mrow><mrow><mi mathvariant="normal">'</mi></mrow></msubsup><mo>=</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi></mrow></msub></mtd></mtr><mtr><mtd><msubsup><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow><mrow><mi mathvariant="normal">'</mi></mrow></msubsup><mo>=</mo><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">4</mn></mrow></mfrac><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi></mrow></msub><mo>+</mo><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">2</mn></mrow></mfrac><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn mathvariant="normal">1</mn></mrow></msub><mo>+</mo><mfrac><mrow><mn mathvariant="normal">1</mn></mrow><mrow><mn mathvariant="normal">4</mn></mrow></mfrac><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn mathvariant="normal">2</mn></mrow></msub></mtd></mtr><mtr><mtd><msubsup><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>n</mi></mrow><mrow><mi mathvariant="normal">'</mi></mrow></msubsup><mo>=</mo><msub><mrow><mi mathvariant="bold-italic">q</mi></mrow><mrow><mi>n</mi></mrow></msub></mtd></mtr></mtable></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227740&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227738&type= 51.39266586 20.23533440 ， 其中： <math id="M192"><mi>i</mi><mo>=</mo><mi>m</mi><mo>+</mo><mn mathvariant="normal">1</mn><mo>,</mo><mi>m</mi><mo>+</mo><mn mathvariant="normal">2</mn><mo>,</mo><mo>⋯</mo><mo>,</mo><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227746&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227744&type= 43.01066971 3.30200005 。 经过平滑后，便可以得到完整的曲线骨架，如 图1 图1 （d）所示。 3 实验以及结果分析 1 本文实验所用硬件和实验环境包括：CPU是AMD的锐龙7代3700X，内存为32 GB，GPU为NVIDIA GeForce RTX 2060 SUPER，Visual Studio 2017 Professional，PCL （Point Cloud Library） 1.8.0，开发语言为C++。为了测试和评估算法的实际性能和效果，本文实验采用了公开数据集Visionair Repository中的多个三维模型，以及部分利用FARO Focus Premium激光扫描仪激光扫描设备扫描获取的点云模型作为测试数据，测试本文方法及对比方法的结果。 3.1　本文方法实验结果 2 图6 图6 所示为本文算法应用于鹿、手掌、人、雕塑模型的实验结果。 图6 图6 （a）中鹿模型的难点在于，鹿的脖子部位存在轴向偏转，骨架点位置易偏移，导致骨架线失真；然而，从 图6 图6 中的结果可以看出本文算法受到的扰动较小，原因是虽然存在轴向偏转，但轴向偏转并没有导致模型脖子部位的形状产生较大变化，所以对骨架生成没有产生干扰。 图6 图6 （b）中手掌模型的难点在于多个距离很近的手指会导致骨架点出现在手指之间的位置，产生错误的骨架点和骨架线。在本文中，为了避免这种现象的产生，采用了射线法来去除掉出现在模型之外的错误位置的骨架点，最终结果证实了此算法的有效性。 图6 图6 （c）中人模型对于骨架提取算法的挑战在于可能会在手臂和身体之间产生错误的分支； 图6 图6 （d）中雕塑模型的难点在于存在复杂的拓扑结构，然而本文算法都能有效应对这些难点，提取出完整平滑的曲线骨架。 为了进一步验证本文算法的有效性和优势，本文将其与目前3种前沿方法进行比较，即： <math id="M193"><msub><mrow><mi>L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227847&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227844&type= 3.64066648 3.72533321 中轴骨架算法、MdCS算法和Point2Skeleton算法。Point2Skeleton所使用的模型已按照其要求通过均匀采样，将点云下采样到2 000点后作为其输入。 图7 图7 （a）为4种算法应用于稀疏点云狗模型上的结果。由于狗模型本身的点数较少，狗模型的腹部存在一些点的空白，导致使用点的坐标作为输入的方法提取到曲线骨架的难度更高。 <math id="M194"><msub><mrow><mi>L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227847&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227844&type= 3.64066648 3.72533321 中轴骨架算法由于内切球的半径增长，导致无法提取到其他腿部的骨架。MdCS算法在狗模型的身体上提取到了错误的拓扑结构。Point2Skeleton算法将狗的身体提取为二维骨架，虽然存在拓扑连接错误和狗模型的右前腿的骨架缺失，但整体效果好于 <math id="M195"><msub><mrow><mi>L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227847&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227844&type= 3.64066648 3.72533321 中轴骨架算法。然而，本文算法能够得到较为满意的效果，这是因为虽然模型上点缺失的部分难以估计法向，但本文采用了迭代提取骨架点的方法，降低了这种稀疏采样对骨架线提取的影响。 图7 图7 （b）所示为马模型的骨架线提取结果。马模型在骨架线提取任务中的难点在于，四肢和身躯之间存在巨大的尺度变化，这种尺度变化会影响基于几何性质收缩或者内切球增长的算法的有效性。从图中可以看出， <math id="M196"><msub><mrow><mi>L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227847&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227844&type= 3.64066648 3.72533321 中轴骨架算法继续受到内切球半径增长导致分支骨架缺失，MdCS算法即使存在拓扑检查的过程，但依然不能应对马腿和身体之间的巨大尺度变化。Point2Skeleton算法在马头部位与真实情况相差较大，在身体部位提取的二维骨架失真严重。而本文算法能够得到合理的拓扑关系并生成完整的骨架线。 图7 图7 （c）所示为人模型，人腿部和腹部的连接点的选择是一个难点，导致 <math id="M197"><msub><mrow><mi>L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227847&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227844&type= 3.64066648 3.72533321 中轴骨架算法选择的连接点不在模型的内部，MdCS算法在腹部依然存在拓扑结构错误，Point2Skeleton算法则未提取到模型的左手。而本文算法在腹部未选择合并，导致腿部骨架和身体骨架合二为一。 3.2　鲁棒性实验 2 为了验证本文算法的鲁棒性，本节针对添加高斯噪声的模型开展实验。本节实验中，定义高斯噪声的标准差为2× <math id="M198"><msub><mrow><mi>d</mi></mrow><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227809&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227806&type= 5.33400011 3.72533321 。其中 <math id="M199"><msub><mrow><mi>d</mi></mrow><mrow><mi mathvariant="normal">m</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227809&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227806&type= 5.33400011 3.72533321 是模型中点之间最小距离。结果如 图8 图8 所示。MdCS算法在应对有噪声的点云模型时效果好于没有噪声的模型，原因在于，添加噪声后，模型点的坐标发生了变化，导致算法在拓扑检查时使用了较大的半径，减少了拓扑错误。由于MAT易受噪声影响，所以Point2Skeleton算法在应对噪声时的表现变差，产生错误拓扑连接的可能性相较于不受噪声干扰时有所提高。受到噪声干扰时，Point2Skeleton生成了更少的拓扑连接，由此虽然拓扑连接错误的数量下降了，但是骨架的质量却没有提高。 由于较低程度的高斯噪声对PCA中最小特征值的影响有限，所以对基于PCA的法向计算的影响也非常有限。并且中点状态的平衡化迭代可以在得到居中性更好地骨架点的同时，降低噪声的干扰，所以本文算法受到噪声影响较小。 为了定量地分析几种算法的实际效果，统计了几种方法在应对模型无噪声和有噪声的情况下的骨架点数量、拓扑连接的数量、交叉点数量和拓扑连接错误的数量。其中，拓扑连接错误的数量等于骨架缺少的分支数量和去掉的拓扑连接数量的和，去掉的拓扑连接数量为去掉拓扑能使拓扑连接正确所需去除的数量。如 表1 表1 所示。从 表1 表1 可以看出， <math id="M200"><msub><mrow><mi>L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227847&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227844&type= 3.64066648 3.72533321 中轴骨架线提取算法提取的骨架点数量较多，拓扑连接错误的数量也较多，骨架分支缺失的情况较多。MdCS算法由于提取的骨架线可能存在环结构，所以拓扑连接错误较多，而且可能存在骨架点和拓扑连接在模型外的情况。Point2Skeleton具有固定的输出，即：100个骨架点和骨架点的拓扑关系。由于其输出的是二维骨架，二维骨架的连接状态较多，所以拓扑连接关系出现错误的可能性较大，这也反应在了 图8 图8 中。本文算法提取的骨架线和骨架点数量中等，交叉点较少，拓扑连接数量错误较少，并且受到噪声影响时，提取的骨架点数量和拓扑连接数量变化不大，表现出了对噪声的鲁棒性。 注： “None”表示使用了没有噪声的模型 2 3 Method 6 Model 2 Dog 2 Horse 2 Human-1 None Noise None Noise None Noise 4 <math id="M201"><msub><mrow><mi mathvariant="normal">L</mi></mrow><mrow><mn>1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227829&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227827&type= 3.13266683 3.13266683 -Medial Number of skeleton points 43 48 53 66 63 61 Number of topologies 41 45 52 64 62 59 Number of junction points 2 0 1 2 2 2 Number of topology errors 4 4 4 1 0 1 4 MdCS Number of skeleton points 41 24 14 20 23 24 Number of topologies 43 24 16 19 24 24 Number of junction points 12 1 6 2 5 4 Number of topology errors 6 1 4 1 2 1 4 Point2Skeleton Number of skeleton points 100 100 100 100 100 100 Number of topologies 19 21 14 14 21 14 Number of junction points 1 1 7 5 3 1 Number of topology errors 13 17 8 7 15 12 4 Ours Number of skeleton points 47 47 42 42 48 46 Number of topologies 46 46 41 41 47 45 Number of junction points 2 2 2 2 1 2 Number of topology errors 0 0 0 0 1 0 3.3　算法效率 2 利用相同的软硬件设备运行 <math id="M202"><msub><mrow><mi mathvariant="normal">L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227841&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227839&type= 3.64066648 3.64066648 中轴骨架线提取算法、MdCS算法、Point2Skeleton算法和本文算法，并对计算耗时进行统计，结果如 表2 表2 所示。从 表2 表2 中可以看到，本文算法的时间损耗小于其他三种算法，即：略小于Point2Skeleton算法，相较于 <math id="M203"><msub><mrow><mi>L</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227847&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227844&type= 3.64066648 3.72533321 中轴骨架算法速度提升了10倍以上，比MdCS算法速度提升了百倍以上。由于Point2Skeleton是基于深度学习的算法，所以在计算骨架时相较于传统算法更有优势，而该方法实际耗时表现略差与本文方法的原因是，Point2Skeleton在加载深度学习模型和保存运算结果步骤中耗时较多。 Data set #Points <math id="M204"><msub><mrow><mi>L</mi></mrow><mrow><mn>1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227854&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227850&type= 3.13266683 3.21733332 -Medial MdCS P2S Ours Horse 8 077 11.520 125.158 7.729 0.764 Dog 9 009 15.491 213.076 7.608 0.830 Indore 12 128 19.452 360.912 8.315 1.029 Human-1 28 518 72.321 <math id="M205"><mi mathvariant="normal">∞</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227866&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227863&type= 3.13266683 2.37066650 8.235 3.328 Human-2 33 041 86.110 <math id="M206"><mi mathvariant="normal">∞</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227866&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=37227863&type= 3.13266683 2.37066650 8.469 4.356 s 本文算法速度较快的原因是，使用了降采样的方式降低了参与运算的点的数量。骨架点迭代时，由于骨架点平衡状态判断的同时，也会在常数时间内获取骨架点迭代的方向，这种设计加速了骨架点的平衡移动过程。 3.4　应用 2 骨架线常被应用于动作捕捉识别 ［ 15 15 - 17 17 15-17 ］ ，基于骨架线可以改变模型的姿态和动作，对于点云重建、数据生成以及形状变化具有重要作用。直接通过三维图形编辑软件制作动画的效率瓶颈是导入的模型需要手动绑定系统内预置的骨架，包括骨架的三维坐标和拓扑连接关系。此过程不仅耗费时间，并且因为系统预置骨架的种类有限，也会影响软件的通用性。通过骨架线提取算法得到骨架线后，三维图形图像编辑软件可以自动获取骨架点的三维坐标、构建拓扑连接，不再需要手动调整参数和绑定骨架设定，可以提高动画制作的效率。 图9 图9 （a）中展示的是，使用FARO Focus Premium激光扫描仪得到玩具马（右上黄棕色）的三维点云模型（右下）；通过本文的算法提取到计算扫描点云的骨架线，如 图9 图9 （b）所示；将骨架线和点云模型导入三维图形编辑软件Blender中，可以轻松实现对于模型动作的改变， 图9 图9 （c）中展示的是对马的激光扫描点云基于骨架线的动作变形，将马的右前腿从弯曲动作改变为向前翘起。图 1 1 （e）和 1 1 （f）展示了基于骨架线将人模型的右脚和右手臂抬起后的效果（彩图见期刊电子版）。 4 结 论 1 本文提出了一种适用于激光扫描点云的骨架线的方法，并在此骨架基础上实现了对模型的变形。通过将骨架点定义为具有对称法向且距离最近相关点的中点，通过迭代使中点平衡化得到骨架点。然后采取主成分分析法寻找满足方向一致性要求的曲线段，使用广度优先搜索算法合并各曲线段，最后将拉普拉斯平滑后的曲线段相连得到完整的骨架线。通过在多个点云模型上开展对比实验，验证了本文算法的有效性、鲁棒性和高效性，将原本处理由33 041个点组成的点云所需86.110 s缩短到4.356 s。将提取的骨架应用在激光雷达点云的动作变换任务中，展示骨架线的实际作用。 参考文献 耿国华 ， 张鹏飞 ， 刘雨萌 ， 等 . 基于断裂面邻域特征的文物碎片拼接 ［J］. 光学 精密工程 ， 2021 ， 29 （ 5 ）： 1169 - 1179 . doi: 10.37188/OPE.20212905.1169 http://dx.doi.org/10.37188/OPE.20212905.1169 基于断裂面邻域特征的文物碎片拼接 GENG G H ， ZHANG P F ， LIU Y M ， et al . Reassembly method of cultural relic fragments based on the neighborhood characteristics of fracture surface ［J］. Opt. Precision Eng. ， 2021 ， 29 （ 5 ）： 1169 - 1179 . （in Chinese） . doi: 10.37188/OPE.20212905.1169 http://dx.doi.org/10.37188/OPE.20212905.1169 Reassembly method of cultural relic fragments based on the neighborhood characteristics of fracture surface 林森 ， 张强 . 应用邻域点信息描述与匹配的点云配准 ［J］. 光学 精密工程 ， 2022 ， 30 （ 8 ）： 984 - 997 . doi: 10.37188/OPE.20223008.0984 http://dx.doi.org/10.37188/OPE.20223008.0984 应用邻域点信息描述与匹配的点云配准 LIN S ， ZHANG Q . Point cloud registration using neighborhood point information description and matching ［J］. Opt. Precision Eng. ， 2022 ， 30 （ 8 ）： 984 - 997 . （in Chinese） . doi: 10.37188/OPE.20223008.0984 http://dx.doi.org/10.37188/OPE.20223008.0984 Point cloud registration using neighborhood point information description and matching TAGLIASACCHI A ， ZHANG H ， COHEN-OR D . Curve skeleton extraction from incomplete point cloud ［J］. ACM Transactions on Graphics ， 2009 ， 28 （ 3 ）： 71 . doi: 10.1145/1531326.1531377 http://dx.doi.org/10.1145/1531326.1531377 Curve skeleton extraction from incomplete point cloud CAO J J ， TAGLIASACCHI A ， OLSON M ， et al . Point cloud skeletons via Laplacian based contraction ［C］. 2010 Shape Modeling International Conference. Aix-en-Provence ， France . IEEE ， 2010 ： 187 - 197 . Point cloud skeletons via Laplacian based contraction LI L ， WANG W C ， CHU Y Y . A simple and stable centeredness measure for 3D curve skeleton extraction ［J］. IEEE Transactions on Visualization and Computer Graphics ， 2022 ， 28 （ 3 ）： 1486 - 1499 . doi: 10.1109/tvcg.2020.3018483 http://dx.doi.org/10.1109/tvcg.2020.3018483 A simple and stable centeredness measure for 3D curve skeleton extraction HUANG H ， WU S H ， COHEN-OR D ， et al . L 1 -medial skeleton of point cloud ［J］. ACM Transactions on Graphics ， 2013 ， 32 （ 4 ）： 1 - 8 . doi: 10.1145/2461912.2461913 http://dx.doi.org/10.1145/2461912.2461913 L 1-medial skeleton of point cloud QIN H X ， HAN J ， LI N ， et al . Mass-driven topology-aware curve skeleton extraction from incomplete point clouds ［J］. IEEE Transactions on Visualization and Computer Graphics ， 2020 ， 26 （ 9 ）： 2805 - 2817 . doi: 10.1109/tvcg.2019.2903805 http://dx.doi.org/10.1109/tvcg.2019.2903805 Mass-driven topology-aware curve skeleton extraction from incomplete point clouds SAHA P K ， BORGEFORS G ， SANNITI DI BAJA G . A survey on skeletonization algorithms and their applications ［J］. Pattern Recognition Letters ， 2016 ， 76 ： 3 - 12 . doi: 10.1016/j.patrec.2015.04.006 http://dx.doi.org/10.1016/j.patrec.2015.04.006 A survey on skeletonization algorithms and their applications CORNEA N D ， SILVER D ， MIN P . Curve-skeleton properties， applications， and algorithms ［J］. IEEE Transactions on Visualization and Computer Graphics ， 2007 ， 13 （ 3 ）： 530 - 548 . doi: 10.1109/tvcg.2007.1002 http://dx.doi.org/10.1109/tvcg.2007.1002 Curve-skeleton properties， applications， and algorithms LIVESU M ， GUGGERI F ， SCATENI R . Reconstructing the curve-skeletons of 3D shapes using the visual hull ［J］. IEEE Transactions on Visualization and Computer Graphics ， 2012 ， 18 （ 11 ）： 1891 - 1901 . doi: 10.1109/tvcg.2012.71 http://dx.doi.org/10.1109/tvcg.2012.71 Reconstructing the curve-skeletons of 3D shapes using the visual hull XIE S S ， LIU J D ， SMITH C D . Curve skeleton-based shape representation and classification ［C］. 2012 19th IEEE International Conference on Image Processing . Orlando， FL， USA . IEEE ， 2012 ： 529 - 532 . Curve skeleton-based shape representation and classification TAGLIASACCHI A ， DELAME T ， SPAGNUOLO M ， et al . 3D skeletons： a state-of-the-art report ［J］. Computer Graphics Forum ， 2016 ， 35 （ 2 ）： 573 - 597 . doi: 10.1111/cgf.12865 http://dx.doi.org/10.1111/cgf.12865 3D skeletons： a state-of-the-art report BOUIX S ， SIDDIQI K ， TANNENBAUM A . Flux driven fly throughs ［C］. 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition ， 2003 . Proceedings. Madison， WI， USA. IEEE ， 2003： I . doi: 10.1109/cvpr.2003.1211444 http://dx.doi.org/10.1109/cvpr.2003.1211444 Flux driven fly throughs HASSOUNA M S ， FARAG A A ， FALK R . Differential fly-throughs （DFT）： a general framework for computing flight paths ［C］. Medical Image Computing and Computer-Assisted Intervention- MICCAI 2005 ， 2005 ： 654 - 661 . doi: 10.1007/11566465_81 http://dx.doi.org/10.1007/11566465_81 Differential fly-throughs （DFT）： a general framework for computing flight paths CHUNDURU V ， ROY M ， S D R N ， et al . Hand tracking in 3D space using MediaPipe and PnP method for intuitive control of virtual globe ［C］. 2021 IEEE 9th Region 10 Humanitarian Technology Conference （R10-HTC）. Bangalore ， India . IEEE ， 2021 ： 1 - 6 . doi: 10.1109/r10-htc53172.2021.9641587 http://dx.doi.org/10.1109/r10-htc53172.2021.9641587 Hand tracking in 3D space using MediaPipe and PnP method for intuitive control of virtual globe TANG Y S ， TIAN Y ， LU J W ， et al . Deep progressive reinforcement learning for skeleton-based action recognition ［C］. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition . Salt Lake City， UT， USA . IEEE ， 2018 ： 5323 - 5332 . Deep progressive reinforcement learning for skeleton-based action recognition BOULAHIA S Y ， ANQUETIL E ， KULPA R ， et al . 3D multistroke mapping （3DMM）： transfer of hand-drawn pattern representation for skeleton-based gesture recognition ［C］. 2017 12th IEEE International Conference on Automatic Face & Gesture Recognition . Washington， DC， USA . IEEE ， 2017 ： 462 - 467 . doi: 10.1109/fg.2017.63 http://dx.doi.org/10.1109/fg.2017.63 3D multistroke mapping （3DMM）： transfer of hand-drawn pattern representation for skeleton-based gesture recognition LI C Y ， HAMZA A . Skeleton path based approach for nonrigid 3D shape analysis and retrieval ［C］. Combinatorial Image Analysis ， 2011 ： 84 - 95 . doi: 10.1007/978-3-642-21073-0_10 http://dx.doi.org/10.1007/978-3-642-21073-0_10 Skeleton path based approach for nonrigid 3D shape analysis and retrieval SIRIN Y ， DEMIRCI M F . 2D and 3D shape retrieval using skeleton filling rate ［J］. Multimedia Tools and Applications ， 2017 ， 76 （ 6 ）： 7823 - 7848 . doi: 10.1007/s11042-016-3422-2 http://dx.doi.org/10.1007/s11042-016-3422-2 2D and 3D shape retrieval using skeleton filling rate WANG T ， CHENG I ， LOPEZ V ， et al . Valence normalized spatial Median for skeletonization and matching ［C］. 2009 IEEE 12th International Conference on Computer Vision Workshops ， ICCV Workshops. Kyoto ， Japan . IEEE ， 2009 ： 55 - 62 . doi: 10.1109/iccvw.2009.5457719 http://dx.doi.org/10.1109/iccvw.2009.5457719 Valence normalized spatial Median for skeletonization and matching WU S ， WEN W L ， XIAO B X ， et al . An accurate skeleton extraction approach from 3D point clouds of maize plants ［J］. Frontiers in Plant Science ， 2019 ， 10 ： 248 . doi: 10.3389/fpls.2019.00248 http://dx.doi.org/10.3389/fpls.2019.00248 An accurate skeleton extraction approach from 3D point clouds of maize plants SU Z X ， ZHAO Y D ， ZHAO C J ， et al . Skeleton extraction for tree models ［J］. Mathematical and Computer Modelling ， 2011 ， 54 （ 3/4 ）： 1115 - 1120 . doi: 10.1016/j.mcm.2010.11.043 http://dx.doi.org/10.1016/j.mcm.2010.11.043 Skeleton extraction for tree models HU H L ， LI Z ， JIN X G ， et al . Curve skeleton extraction from 3D point clouds through hybrid feature point shifting and clustering ［J］. Computer Graphics Forum ， 2020 ， 39 （ 6 ）： 111 - 132 . doi: 10.1111/cgf.13906 http://dx.doi.org/10.1111/cgf.13906 Curve skeleton extraction from 3D point clouds through hybrid feature point shifting and clustering LIN C ， LI C J ， LIU Y ， et al . Point2Skeleton： learning skeletal representations from point clouds ［C］. 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition （CVPR）. Nashville ， TN ， USA . IEEE ， 2021 ： 4275 - 4284 . doi: 10.1109/cvpr46437.2021.00426 http://dx.doi.org/10.1109/cvpr46437.2021.00426 Point2Skeleton： learning skeletal representations from point clouds OGNIEWICZ R ， ILG M . Voronoi skeletons： theory and applications ［C］. Proceedings 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Champaign ， IL， USA. IEEE Comput . . 1992 ， 92 ： 63 - 69 . doi: 10.1109/cvpr.1992.223236 http://dx.doi.org/10.1109/cvpr.1992.223236 Voronoi skeletons： theory and applications LU L ， LÉVY B ， WANG W . Centroidal Voronoi tessellation of line segments and graphs ［C］. Computer Graphics Forum. Oxford， UK ： Blackwell Publishing Ltd ， 2012 ， 31 （2pt 4 ）： 775 - 784 . doi: 10.1111/j.1467-8659.2012.03058.x http://dx.doi.org/10.1111/j.1467-8659.2012.03058.x Centroidal Voronoi tessellation of line segments and graphs TAGLIASACCHI A ， ALHASHIM I ， OLSON M ， et al . Mean curvature skeletons ［J］. Computer Graphics Forum ， 2012 ， 31 （ 5 ）： 1735 - 1744 . doi: 10.1111/j.1467-8659.2012.03178.x http://dx.doi.org/10.1111/j.1467-8659.2012.03178.x Mean curvature skeletons VAHRENKAMP N ， KOCH E ， WÄCHTER M ， et al . Planning high-quality grasps using mean curvature object skeletons ［J］. IEEE Robotics and Automation Letters ， 2018 ， 3 （ 2 ）： 911 - 918 . doi: 10.1109/lra.2018.2792694 http://dx.doi.org/10.1109/lra.2018.2792694 Planning high-quality grasps using mean curvature object skeletons CHUANG M ， KAZHDAN M . Fast mean-curvature flow via finite-elements tracking ［J］. Computer Graphics Forum ， 2011 ， 30 （ 6 ）： 1750 - 1760 . doi: 10.1111/j.1467-8659.2011.01899.x http://dx.doi.org/10.1111/j.1467-8659.2011.01899.x Fast mean-curvature flow via finite-elements tracking ATIENZA R . Pyramid U-network for skeleton extraction from shape points ［C］. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops （CVPRW）. Long Beach ， CA， USA . IEEE ， 2019 ： 1177 - 1180 . doi: 10.1109/cvprw.2019.00155 http://dx.doi.org/10.1109/cvprw.2019.00155 Pyramid U-network for skeleton extraction from shape points DOU Z Y ， LIN C ， XU R ， et al . Coverage axis： inner point selection for 3D shape skeletonization ［J］. Computer Graphics Forum ， 2022 ， 41 （ 2 ）： 419 - 432 . doi: 10.1111/cgf.14484 http://dx.doi.org/10.1111/cgf.14484 Coverage axis： inner point selection for 3D shape skeletonization 吴庆华 ， 蔡琼捷思 ， 黎志昂 ， 等 . 扩展高斯图像聚类的缺失点云配准 ［J］. 光学 精密工程 ， 2021 ， 29 （ 5 ）： 1199 - 1206 . doi: 10.37188/OPE.20212905.1199 http://dx.doi.org/10.37188/OPE.20212905.1199 扩展高斯图像聚类的缺失点云配准 WU Q H ， CAI Q ， LI Z A ， et al . Registration of losing point cloud based on clustering extended Gaussian image ［J］. Opt. Precision Eng. ， 2021 ， 29 （ 5 ）： 1199 - 1206 . （in Chinese） . doi: 10.37188/OPE.20212905.1199 http://dx.doi.org/10.37188/OPE.20212905.1199 Registration of losing point cloud based on clustering extended Gaussian image 赵夫群 ， 周明全 . 层次化点云去噪算法 ［J］. 光学 精密工程 ， 2020 ， 28 （ 7 ）： 1618 - 1625 . doi: 10.37188/OPE.20202807.1618 http://dx.doi.org/10.37188/OPE.20202807.1618 层次化点云去噪算法 ZHAO F Q ， ZHOU M Q . Hierarchical point cloud denoising algorithm ［J］. Opt. Precision Eng. ， 2020 ， 28 （ 7 ）： 1618 - 1625 . （in Chinese） . doi: 10.37188/OPE.20202807.1618 http://dx.doi.org/10.37188/OPE.20202807.1618 Hierarchical point cloud denoising algorithm 汤慧 ， 周明全 ， 耿国华 . 基于扩展的点特征直方图特征的点云匹配算法 ［J］. 激光与光电子学进展 ， 2019 ， 56 （ 24 ）： 203 - 210 . doi: 10.3788/lop56.241503 http://dx.doi.org/10.3788/lop56.241503 基于扩展的点特征直方图特征的点云匹配算法 TANG H ， ZHOU M Q ， GENG G H . Point cloud registration algorithm based on extended point feature histogram feature ［J］. Laser ＆ Optoelectronics Progress ， 2019 ， 56 （ 24 ）： 203 - 210 . （in Chinese） . doi: 10.3788/lop56.241503 http://dx.doi.org/10.3788/lop56.241503 Point cloud registration algorithm based on extended point feature histogram feature OUYANG D S ， FENG H Y . On the normal vector estimation for point cloud data from smooth surfaces ［J］. Computer-Aided Design ， 2005 ， 37 （ 10 ）： 1071 - 1079 . doi: 10.1016/j.cad.2004.11.005 http://dx.doi.org/10.1016/j.cad.2004.11.005 On the normal vector estimation for point cloud data from smooth surfaces WANG Y T ， FENG H Y ， DELORME F É ， et al . An adaptive normal estimation method for scanned point clouds with sharp features ［J］. Computer-Aided Design ， 2013 ， 45 （ 11 ）： 1333 - 1348 . doi: 10.1016/j.cad.2013.06.003 http://dx.doi.org/10.1016/j.cad.2013.06.003 An adaptive normal estimation method for scanned point clouds with sharp features KLASING K ， ALTHOFF D ， WOLLHERR D ， et al . Comparison of surface normal estimation methods for range sensing applications ［C］. 2009 IEEE International Conference on Robotics and Automation . Kobe， Japan . IEEE ， 2009 ： 3206 - 3211 . doi: 10.1109/robot.2009.5152493 http://dx.doi.org/10.1109/robot.2009.5152493 Comparison of surface normal estimation methods for range sensing applications LI L ， WANG W C . Contracting medial surfaces isotropically for fast extraction of centred curve skeletons ［J］. Computer Graphics Forum ， 2017 ， 36 （ 8 ）： 529 - 539 . doi: 10.1111/cgf.13098 http://dx.doi.org/10.1111/cgf.13098 Contracting medial surfaces isotropically for fast extraction of centred curve skeletons 10.37188/OPE.20223022.2962 TP394.1 A 1004-924X（2022）22-2962-13 周明全,李纯辉,王丽清等.局部相关点平衡的三维激光点云骨架提取[J].光学精密工程,2022,30(22):2962-2974. 周明全,李纯辉,王丽清等.局部相关点平衡的三维激光点云骨架提取[J].光学精密工程,2022,30(22):2962-2974. ZHOU Minquan,LI Chunhui,WANG Liqing,et al.3D laser point cloud skeleton extraction via balance of local correlation points[J].Optics and Precision Engineering,2022,30(22):2962-2974. ZHOU Minquan,LI Chunhui,WANG Liqing,et al.3D laser point cloud skeleton extraction via balance of local correlation points[J].Optics and Precision Engineering,2022,30(22):2962-2974. 国家重点研发计划资助项目（No.2019YFC1521103）；国家自然科学基金重点资助项目（No.61731015） 2022-04-26 2022-07-08 2022-11-25 2022-11-24 光学精密工程 22 30