基于密度峰值聚类的杆状物规则化三维建模方法及系统

摘要

本发明涉及一种基于密度峰值聚类的杆状物规则化三维建模方法及系统，包括针对车载激光雷达所获取原始的点云数据，进行体素重采样，去除离群点，将场景点云进行格网化分割，对各网格分别通过高程直通滤波去除地面点和高层建筑点，然后向三维坐标系的三个坐标平面分别投影；对各网格采用基于密度峰值和距离属性的聚类方式分别在三个投影平面中进行聚类；用规则的空间立方体包围盒对对同一类的点云限定其空间范围，根据先验知识对空间立方体包围盒内的杆状物进行提取，得到杆状物特征参数；进行建模，还原杆状物。本发明可以对绝大部分环境下的杆状物做到快速、高效、准确的提取，并与数字城市集成，实现数字城市中的杆状物精细化和真实化建模。

权利要求

1.一种基于密度峰值聚类的杆状物规则化三维建模方法，其特征在于：包括以下步骤，步骤一，点云数据的预处理，包括针对车载激光雷达所获取的原始的点云数据，进行体素重采样，去除离群点，将整个场景的点云进行格网化分割，对各网格分别通过高程直通滤波去除地面点和高层建筑点，然后向三维坐标系的三个坐标平面XOY、XOZ和YOZ分别投影，所述三维坐标系的Y方向指向正北方向、Z方向指向竖直方向，按右手规则建立；

步骤二，点云数据的聚类，包括针对步骤一的预处理结果，对各网格采用基于密度峰值和距离属性的聚类方式分别在三个投影平面中进行聚类，在聚类结束后，将每一类对应的点序号存入相应的动态链表中；

步骤三，杆状物的提取，包括根据步骤二所得三个投影平面的聚类结果，用规则的空间立方体包围盒对同一类的点云限定其空间范围，将每一类的立方体与立方体内的地物及构成地物的点云建立映射关系，根据先验知识对空间立方体包围盒内的杆状物进行提取，得到杆状物特征参数；

所述用规则的空间立方体包围盒对同一类的点云限定其空间范围，包括对各网格中每一类分别根据三个投影平面中所有点的X、Y、Z坐标最大最小值求交得到对应的包围立方体，同时获得该包围立方体对应的所有内部点序号索引，然后对将邻近的处理网格进行相近类别合并，并更新得到最终的空间立方体包围盒；

所述先验知识为，杆状物在XOY平面的投影面能够用参数椭圆进行最小二乘拟合，在XOZ或者YOZ平面的投影面能够用平行四边形进行最小二乘拟合；

所述对空间立方体包围盒内的杆状物进行提取，通过紧致性分析和连通域分析实现；

所述紧致性分析，实现如下，

在XOY平面内，从相应平面内杆状物的投影点中选取任意三点确定一个椭圆，当包含在某椭圆内的点数与总点数的比例大于一定的阈值时，该椭圆即为该平面内投影点云的紧致椭圆，之后再找出紧致椭圆的外接矩形，并利用该外接矩形对原先的空间立方体包围盒进行X、Y方向上的范围和点集映射更新；

在YOZ平面，从相应平面内杆状物的投影点中选取任意三点确定一个平行四边形，当包含在某平行四边形内的点数与总点数的比例大于一定的阈值时，该平行四边形即为该平面内投影点云的紧致平行四边形，之后再找出紧致平行四边形的外接矩形，并利用该外接矩形对原先的空间立方体包围盒进行Y、Z方向上的范围和点集映射更新；

在XOZ平面，从相应平面内杆状物的投影点中选取任意三点确定一个平行四边形，当包含在某平行四边形内的点数与总点数的比例大于一定的阈值时，该平行四边形即为该平面内投影点云的紧致平行四边形，之后再找出紧致平行四边形的外接矩形，并利用该外接矩形对原先的空间立方体包围盒进行X、Z方向上的范围和点集映射更新；

步骤四，杆状物的建模，包括根据步骤三所得杆状物特征参数，进行建模，还原杆状物。

2.根据权利要求1所述基于密度峰值聚类的杆状物规则化三维建模方法，其特征在于：

基于步骤四所得建模结果，当存在由点云缺失造成的地物提取遗漏现象时，利用杆状物的规则化分布特性进行缺失杆状物的填补。

3.根据权利要求1或2所述基于密度峰值聚类的杆状物规则化三维建模方法，其特征在于：基于步骤四所得建模结果，输出并集成到数字城市。

4.根据权利要求1或2所述基于密度峰值聚类的杆状物规则化三维建模方法，其特征在于：所述通过高程直通滤波去除地面点和高层建筑点，包括根据高程滤波区间进行滤波，高程滤波区间的下限根据地面高程均值设定，上限根据城市树冠底层高度设定。

5.根据权利要求4所述基于密度峰值聚类的杆状物规则化三维建模方法，其特征在于：

当地面存在坡度时，利用法线生长方式去除道路点。

6.一种基于密度峰值聚类的杆状物规则化三维建模系统，其特征在于：包括以下模块，预处理模块，用于针对车载激光雷达所获取的原始的点云数据，进行体素重采样，去除离群点，将整个场景的点云进行格网化分割，对各网格分别通过高程直通滤波去除地面点和高层建筑点，然后向三维坐标系的三个坐标平面XOY、XOZ和YOZ分别投影，所述三维坐标系的Y方向指向正北方向、Z方向指向竖直方向，按右手规则建立；

点云数据聚类模块，用于针对预处理结果，对各网格采用基于密度峰值和距离属性的聚类方式分别在三个投影平面中进行聚类，在聚类结束后，将每一类对应的点序号存入相应的动态链表中；

杆状物提取模块，用于根据三个投影平面的聚类结果，用规则的空间立方体包围盒对同一类的点云限定其空间范围，将每一类的立方体与立方体内的地物及构成地物的点云建立映射关系，根据先验知识对空间立方体包围盒内的杆状物进行提取，得到杆状物特征参数；

所述用规则的空间立方体包围盒对对同一类的点云限定其空间范围，包括对各网格中每一类分别根据三个投影平面中所有点的X、Y、Z坐标最大最小值求交得到对应的包围立方体，同时获得该包围立方体对应的所有内部点序号索引，然后对将邻近的处理网格进行相近类别合并，并更新得到最终的空间立方体包围盒；

所述先验知识为，杆状物在XOY平面的投影面能够用参数椭圆进行最小二乘拟合，在XOZ或者YOZ平面的投影面能够用平行四边形进行最小二乘拟合；

所述对空间立方体包围盒内的杆状物进行提取，通过紧致性分析和连通域分析实现；

所述紧致性分析，实现如下，

在XOY平面内，从相应平面内杆状物的投影点中选取任意三点确定一个椭圆，当包含在某椭圆内的点数与总点数的比例大于一定的阈值时，该椭圆即为该平面内投影点云的紧致椭圆，之后再找出紧致椭圆的外接矩形，并利用该外接矩形对原先的空间立方体包围盒进行X、Y方向上的范围和点集映射更新；

在YOZ平面，从相应平面内杆状物的投影点中选取任意三点确定一个平行四边形，当包含在某平行四边形内的点数与总点数的比例大于一定的阈值时，该平行四边形即为该平面内投影点云的紧致平行四边形，之后再找出紧致平行四边形的外接矩形，并利用该外接矩形对原先的空间立方体包围盒进行Y、Z方向上的范围和点集映射更新；

在XOZ平面，从相应平面内杆状物的投影点中选取任意三点确定一个平行四边形，当包含在某平行四边形内的点数与总点数的比例大于一定的阈值时，该平行四边形即为该平面内投影点云的紧致平行四边形，之后再找出紧致平行四边形的外接矩形，并利用该外接矩形对原先的空间立方体包围盒进行X、Z方向上的范围和点集映射更新；

杆状物建模模块，用于根据杆状物特征参数，进行建模，还原杆状物。

说明书

基于密度峰值聚类的杆状物规则化三维建模方法及系统

技术领域

[0001] 本发明主要涉及数字城市三维建模领域，尤其针对一种基于车载激光雷达获取的点云数据，利用密度峰值聚类手段提取杆状物并在3ds Max中对其建模的方法及系统。

背景技术

[0002] 三维激光点云是物体表面的高精度三维坐标，通过点云可以直接获取地物坐标及特征信息，具有密度大，精度高、数据量大等特点，因而三维点云作为一种新兴的3D技术，凭借其能够快速高效地还原真实场景的特点，受到了众多相关领域研究者的欢迎。在已有的大量研究成果中，针对点云的地物提取主要包括建筑物和道路的提取，建筑物的提取大多运用基于投影的方法，道路的提取则大多运用高程或者法线的方法，这些方法已经发展地较为成熟，针对不同的数据源和不同的地物空间结构的复杂程度，其提取效果也较为令人满意。

[0003] 但针对诸如电线杆、树木这类杆状物的提取仍然没有一套完整的方法，目前从点云中提取杆状物的研究主要有：邹晓亮针对电线杆这一单一地物标志运用点密度水平投影方法进行提取；Dinesh MANANDHARD等人根据每个断面扫描点的点位空间分布特征,对扫描点的距离数据进行一定的数学特征筛选,从而实现了对建筑物、道路和树木等的初步分离。以上方案虽然都有一些初步的特征分类效果，但因其分类时所遵循的思路较为单一，或仅关注于某些理想条件下的情况，使得算法的通用性、准确性和鲁棒性都远远不够。在应用于具有各类复杂特征地物的城市环境时，往往不能得到较为精细和准确的分类提取及定位效果。

[0004] 在从提取的杆状物中获取其特征信息之后，如何根据其特征参数在3ds Max中进行三维建模乃至建立精细化的特征模型也是目前此类研究中有待完善的地方。由于缺乏具有普适性的杆状物提取算法，便无法获得准确的杆状物位置、高度等规则化特征参数，不能真实还原电线杆、行道树等杆状物的详细信息，难以满足数字城市建模中保证地物真实性的要求，这样便无法区分不同类型的电线杆和不同品种的行道树，不能对此类地物进行精确重建。正是基于以上原因，使得目前针对杆状物可建立的模型十分单一，且人工集成至数字城市的工作大多繁琐重复、效率低下，成为数字城市发展的一大制约。此外，目前的研究中尚未有针对点云缺失的情况进行填补的技术方案。

发明内容

[0005] 本发明的内容主要包括利用基于密度峰值的聚类算法，针对车载激光雷达获取的点云数据中的杆状物，依据其规则化的特征进行提取，并在3ds Max中根据杆状物提取所得到的参数信息进行建模，同时依据其规则化分布的特征填补杆状物点云缺失的部分。

[0006] 本发明技术方案提供一种基于密度峰值聚类的杆状物规则化三维建模方法，包括以下步骤，

[0007] 步骤一，点云数据的预处理，包括针对车载激光雷达所获取原始的点云数据，进行体素重采样，去除离群点，将整个场景的点云进行格网化分割，对各网格分别通过高程直通滤波去除地面点和高层建筑点，然后向三维坐标系的三个坐标平面XOY、XOZ和YOZ分别投影，所述三维坐标系的Y方向指向正北方向、Z方向指向竖直方向，按右手规则建立；

[0008] 步骤二，点云数据的聚类，包括针对步骤一的预处理结果，对各网格采用基于密度峰值和距离属性的聚类方式分别在三个投影平面中进行聚类，在聚类结束后，将每一类对应的点序号存入相应的动态链表中；

[0009] 步骤三，杆状物的提取，包括根据步骤二所得三个投影平面的聚类结果，用规则的空间立方体包围盒对对同一类的点云限定其空间范围，将每一类的立方体与立方体内的地物及构成地物的点云建立映射关系，根据先验知识对空间立方体包围盒内的杆状物进行提取，得到杆状物特征参数；

[0010] 所述用规则的空间立方体包围盒对对同一类的点云限定其空间范围，包括对各网格中每一类分别根据三个投影平面中所有点的X、Y、Z坐标最大最小值求交得到对应的包围立方体，同时获得该包围立方体对应的所有内部点序号索引，然后对将邻近的处理网格进行相近类别合并，并更新得到最终的空间立方体包围盒；

[0011] 所述先验知识为，杆状物在XOY平面的投影面能够用参数椭圆进行最小二乘拟合，在XOZ或者YOZ平面的投影面能够用平行四边形进行最小二乘拟合；

[0012] 所述对空间立方体包围盒内的杆状物进行提取，通过紧致性分析和连通域分析实现；

[0013] 步骤四，杆状物的建模，包括根据步骤三所得杆状物特征参数，进行建模，还原杆状物。

[0014] 而且，基于步骤四所得建模结果，当存在由点云缺失造成的地物提取遗漏现象时，利用杆状物的规则化分布特性进行缺失杆状物的填补。

[0015] 而且，基于步骤四所得建模结果，输出并集成到数字城市。

[0016] 而且，所述通过高程直通滤波去除地面点和高层建筑点，包括根据高程滤波区间进行滤波，高程滤波区间的下限根据地面高程均值设定，上限根据城市树冠底层高度设定。

[0017] 而且，当地面存在坡度时，利用法线生长方式去除道路点。

[0018] 而且，所述紧致性分析，实现如下，

[0019] 在XOY平面内，从相应平面内杆状物的投影点中选取任意三点确定一个椭圆，当包含在某椭圆内的点数与总点数的比例大于一定的阈值时，该椭圆即为该平面内投影点云的紧致椭圆，之后再找出紧致椭圆的外接矩形，并利用该外接矩形对原先的空间立方体包围盒进行X、Y方向上的范围和点集映射更新；

[0020] 在YOZ平面，从相应平面内杆状物的投影点中选取任意三点确定一个平行四边形，当包含在某平行四边形内的点数与总点数的比例大于一定的阈值时，该平行四边形即为该平面内投影点云的紧致平行四边形，之后再找出紧致平行四边形的外接矩形，并利用该外接矩形对原先的空间立方体包围盒进行Y、Z方向上的范围和点集映射更新；

[0021] 在XOZ平面，从相应平面内杆状物的投影点中选取任意三点确定一个平行四边形，当包含在某平行四边形内的点数与总点数的比例大于一定的阈值时，该平行四边形即为该平面内投影点云的紧致平行四边形，之后再找出紧致平行四边形的外接矩形，并利用该外接矩形对原先的空间立方体包围盒进行X、Z方向上的范围和点集映射更新。

[0022] 本发明还相应提供一种基于密度峰值聚类的杆状物规则化三维建模系统，包括以下模块，

[0023] 预处理模块，用于针对车载激光雷达所获取原始的点云数据，进行体素重采样，去除离群点，将整个场景的点云进行格网化分割，对各网格分别通过高程直通滤波去除地面点和高层建筑点，然后向三维坐标系的三个坐标平面XOY、XOZ和YOZ分别投影，所述三维坐标系的Y方向指向正北方向、Z方向指向竖直方向，按右手规则建立；

[0024] 点云数据聚类模块，用于针对预处理结果，对各网格采用基于密度峰值和距离属性的聚类方式分别在三个投影平面中进行聚类，在聚类结束后，将每一类对应的点序号存入相应的动态链表中；

[0025] 杆状物提取模块，用于根据三个投影平面的聚类结果，用规则的空间立方体包围盒对对同一类的点云限定其空间范围，将每一类的立方体与立方体内的地物及构成地物的点云建立映射关系，根据先验知识对空间立方体包围盒内的杆状物进行提取，得到杆状物特征参数；所述用规则的空间立方体包围盒对对同一类的点云限定其空间范围，包括对各网格中每一类分别根据三个投影平面中所有点的X、Y、Z坐标最大最小值求交得到对应的包围立方体，同时获得该包围立方体对应的所有内部点序号索引，然后对将邻近的处理网格进行相近类别合并，并更新得到最终的空间立方体包围盒；

[0026] 所述先验知识为，杆状物在XOY平面的投影面能够用参数椭圆进行最小二乘拟合，在XOZ或者YOZ平面的投影面能够用平行四边形进行最小二乘拟合；

[0027] 所述对空间立方体包围盒内的杆状物进行提取，通过紧致性分析和连通域分析实现；

[0028] 杆状物建模模块，用于根据杆状物特征参数，进行建模，还原杆状物。

[0029] 本发明从最原始的车载点云数据入手，经过一系列的处理步骤后，可以对绝大部分环境下的杆状物做到快速、高效、准确的提取，并与数字城市集成，实现数字城市中的杆状物精细化和真实化建模。从而本发明的技术特点也体现了出来：

[0030] 1、首次运用多种特征实现杆状物特征的精细化提取与分类。结合国内外多篇文献中的特征提取算法，再依据本项目的特色发展，最终形成了一套利用扫描点高度值波动范围、不同水平面投影点密度与投影形状、竖直面投影特征、基于密度峰值和距离属性的聚类等多种方法实现杆状物点云的标准、快速、精细化的聚类、分离及归类的算法，并可同时获取其精确的位置信息，具有快速、高效、准确、鲁棒性等优点。

[0031] 2、规则化三维建模。有别于以往对城市杆状地物采用的统一化处理方式，本项目将针对不同属性的杆状物分别建立精细化三维模型的模板。最终按照获取的分类属性和尺寸信息对应相应的模板自动生成对应的三维模型，并按相应的位置信息安置于数字城市模型中。

[0032] 3、利用分布特性填补缺失杆状物。针对点云缺失问题，利用城市杆状地物在地域上规则化分布的特点，将城市地物中具有明显杆状特点但因附近存在干扰而难以识别的杆状物加入到数字城市中。

附图说明

[0033] 图1是本发明实施例的流程图。

[0034] 图2是本发明实施例的点云预处理流程图。

具体实施方式

[0035] 本发明利用杆状物点云的空间分布特性提取树木等城市杆状地物，并提出利用杆状物规则化分布特性，将城市地物中具有明显杆状特点但因附近存在干扰而难以识别的杆状物加入到提取过程，并最终集成到数字城市中。以下结合附图和实施例详细描述本发明的技术方案。

[0036] 参见图1，本发明实施例所提供基于密度峰值聚类的杆状物规则化三维建模方法的具体实施流程如下：

[0037] 步骤一：点云数据的预处理。

[0038] 从原始的车载点云数据入手到对点云进行聚类需要进行一系列的预处理工作，预处理的目的是为了尽可能地去除非杆状地物点。

[0039] 为了减少复杂地物空间结构中的干扰信息，先对点云数据进行预处理，突出杆状物空间分布信息。预处理包括利用高程和法线增长原理去除地面点，并利用进行点云的重采样、离群点的去除、点云高程滤波等操作，具体实施时可以利用PCL库(Point Cloud Library：现有功能最完善的点云处理预封装库)。最后将点云数据投影到XOY、XOZ和YOZ三个坐标平面上(取Y方向指向正北方向、Z方向指向竖直方向，按右手规则建立的三维坐标系，竖直方向即垂直于地平面的方向)。

[0040] 参见图2，实施例的预处理流程如下：

[0041] 首先进行体素重采样，通过输入的点云数据创建一个三维体素栅格(即一个立方体)，然后在每个体素内用体素中所有点的重心来近似显示体素中的其他点，这样该体素内所有点可最终用他们的重心点表示，处理后的点云数据排列规则，当体素的大小设置合理时，也可在保留有用信息的同时大大减少数据量，具体实施时本领域技术人员可自行预设体素大小，例如2cm×2cm、1cm×1cm；

[0042] 再去除离群点：对每个点，计算它到其所有临近点的平均距离。假设得到的结果是一个高斯分布，其形状由均值和标准差决定，平均距离在标准范围(由全局距离平均值和方差定义)之外的点，可被定义为离群点，并可从数据集中去除掉，去除离群点是为了去掉不必要的噪声点，例如高层建筑顶部的离散点，这些点在扫描时就很稀疏，也不是杆状物的点，因而这些点在聚类中不会起到作用，去除掉这些噪声点后可以减小数据量，提高效率；

[0043] 接着，为了提高运行速度，本发明提出将整个场景的点云进行格网化分割，之后的步骤都将在单个网格内部进行处理。具体实施时，可以依据实际操作中杆状物的平均间距设定分割网格的尺寸，例如将分割的网格大小确定在5m×5m～10m×10m之间，使每一个网格内部的杆状物数量不超过3个。

[0044] 最后进行高程直通滤波：在垂直于地面的高程方向上进行简单的直通滤波，即除去用户指定的高程区间内部(或外部)的点。由于实际操作中，地面点占据近一半的点云数据量且分布在很窄的高度区间内，故可采用高程直方图寻找高程统计峰值以确定地面高程区间并求地面高程区间内点的加权均值(可用直方图里面的频数作为权值)，将所得地面高程均值作为高程滤波区间下限设定依据，取略高于地面高程均值(例如0.3m)作为下限。上限则可根据具体情况预设，比如该城市常见树种的树冠底层高度。例如树冠底层高度为3m，设定采用地面高程均值0.3m以上，3m以下的高程滤波区间进行滤波，如此可将大部分的地面点和高程值大于滤波区间的建筑点去除以减少数据量，同时由于杆状物通常为由地面竖直向上伸出的细长物体，此次滤波后仍可以保留杆状物的绝大部分点云以便之后的特征分析。而对于具有较大坡度的特殊地形，无法较好的单纯利用直通滤波方式快速去除地面点云，此时可以利用法线生长的方法。具体的思想是从已知的道路点出发，借助相邻道路点法线变化的连续性，设定一个法线夹角阈值，如果相邻道路点法线角度变化超过该阈值，那么便认为此处发生“突变”，即认为已经生长到道路的边缘，最终获得所有的道路点集。该方法可以去除特殊地形的道路点，扩大了各种环境下算法的普适性，在去除了道路点的同时也缩小了数据量，有利于提高程序的速度。高程直通滤波可在各网格分别进行并行处理。

[0045] 经过以上四个步骤后，所得到的数据不仅数据量相比原始数据大大减少，而且杆状物的信息更加突出，其它地物点的分布也更加具有特点，与杆状物的分布特点差别也更加明显。为了方便聚类，可将点云向三个平面投影，即将以上处理后的数据向XOY、XOZ和YOZ三个平面进行投影，步骤二将在其中的每一个平面上对点云进行聚类。平面投影可在各网格分别进行并行处理。

[0046] 步骤二：点云数据的聚类。

[0047] 因为预处理过程中已经尽可能地减少了其它地物信息和噪声的干扰，所以在各个投影方向进行聚类后可利用杆状物的空间特性进行识别。利用Alex Rodriguez和Alessandro Laio的论文中提出的基于密度峰值和距离属性聚类的思想，可以分别在三个投影平面中进行聚类，以恢复点云在三维空间内的所有聚集特征。这样针对预处理后的点云数据进行聚类，可以充分利用点云所具有的三维信息，实现杆状物提取。聚类的思想是对于点云中的每一个点，将预先设定的距离阈值带入高斯核函数(Radial Basis Function)后计算其点密度(即该点所在区域的局部密度)；再针对每一个点计算它到密度比它大的最近的一个点的距离。这两个参数便是决定该点是否为聚类中心的重要依据，密度决定了该聚类中心周围点的密集程度，距离决定了聚类中心之间相隔的距离，那么当密度和距离两个参数同时大于相应的阈值时，该点即可选为聚类中心。具体实施时，可参见文献Alex Rodriguez and Alessandro Laio，Clustering by fast search and find of density peaks[J]，Science,2014，具体实施时，本领域技术人员可自行设定密度与距离阈值乘积的经验阈值，以自动提取所有的聚类中心。

[0048] 聚类中心选择出来后，对于其它点，将该点归为到密度比它大又最近的一个点所在的类别当中，这样即可完成对每个点的分类。然而对于类与类交界处的这些点，往往很难定义它们属于哪一类。对于这些边界点的处理方法如下：如果在某点的高斯核函数距离阈值内，存在另一个从属于不同类别的点，那么此时可利用这两个点的点密度的均值与这两个点所在类的边界密度值进行比较，若该均值大于某个类的边界密度值，则用该均值作为这个类的边界密度值。接下来针对某一类中的点，如果其点密度小于该类的边界密度值，则这个点被定义在类的外环(cluster halo)区域，而该类中其它点都是类的内核(cluster core)区域，类的内核区域中的点明确属于该类，而类的外环区域中的点是不确定的，甚至有时不对它们进行分类。

[0049] 在聚类结束后，则需要将每一类对应的点序号存入相应的动态链表中，以便之后进行进一步分析时作为点索引对类内数据点进行快速的取用。

[0050] 基于以上思想，可以得到一个较为满意的分类结果，在实验中从针对XOY平面投影的聚类效果来看，杆状物的投影面通常可以用参数椭圆进行良好的拟合，而其他地物的聚类效果形状不规则，可排除其为杆状物的可能性；从针对XOZ和YOZ平面投影的聚类效果来看，杆状物投影面具有明显的平行四边形或矩形特征，同样可以与其它地物分别开。

[0051] 同样地，点云数据的聚类可在各网格分别进行并行处理。

[0052] 步骤三：杆状物的提取。

[0053] 基于分类的结果，可以用规则的空间立方体包围盒对各个类别限定其空间范围，每一类的立方体可以与立方体内的地物及构成地物的点云建立映射关系，使得在选择某一目标的同时可以快速得到其对应类别中所有的点。再利用三个投影方向的聚类结果对每一类进行紧致性分析，确定这一类杆状物的紧致集，以去除噪声干扰。由于在预处理过程中，我们得到的仅仅是一段区间内的杆状物，因此还需要借助点云生长，从该步骤提取到的部分杆状物紧致集出发，找到所有属于该杆状物的点云，以确定所有该类别杆状物在空间中的位置。最后根据提取出的杆状物可以得到它的位置、高度信息及一些其它的特征信息，这些信息将作为该杆状物精确建模所必需的参数传到3ds Max中进行精细化建模。

[0054] 对各个网格，根据三个平面的聚类结果，可以在三维空间中将同一类的点云(对应一个地物对象)限制在一个规则立方体中，而由于投影方式的限制，在某一个平面上的分类结果并不能完全体现整体的空间分布特征，例如具有相同X、Y坐标，但Z坐标不同、上下分离的两个点集在XOY面投影时会被归为一类，但在YOZ面投影时则可以被清晰地分为两类，这就需要从三个面对规则立方体的尺寸及位置进行综合的考量。在立方体构建好后，就需要将立方体与立方体内部的地物及构成地物的点云建立映射关系，这样在后期程序与3ds Max软件结合时，可以通过鼠标的点击或者阈值的设定选中对应位置所在立方体网格，并获得网格内所有内部点的三维坐标信息并进行之后的处理，为了实现这个功能，本发明进一步提出建立动态索引的方案。立方体以及点集映射索引构建主要遵循如下步骤：

[0055] 以在XOY平面内某一类中所有点的X、Y、Z坐标的最大最小值为初始值，之后将XOZ平面中所有类别的X、Y、Z坐标的最大最小值与其进行求交运算，一旦交集为非空，则将该交集带入YOZ平面中对所有类别重复该过程，即将YOZ平面中所有类别的X、Y、Z坐标的最大最小值与其进行求交运算，一旦交集为非空，两次求交运算后的交集即为网格内该类的包围立方体；与此同时，在生成交集时所利用的三个类的点集索引中寻找交集，得到点序号的交集并存入相应的动态链表中。

[0056] 根据以上过程，可获得网格中所有包含单个独立点集的规则立方体的位置及尺寸，以及立方体对应的所有内部点序号索引。立方体的个数为该网格内的点集分类数，而每一个立方体内部都包含该类对应的所有点云。

[0057] 由于之前点云预处理的点云分割过程的随机性，可能将同一杆状物分入不同的处理网格中，所以在对各网格分别的聚类提取包围盒之后，应将邻近的处理网格进行结合，分析相邻网格间的边缘处是否存在聚类中心相近且聚簇中点云形态相似的情况，如存在则将两类合并为同一个类，同时更新立方体包围盒，以便在之后进行统一分析处理。

[0058] 当立方体包围盒构建好后，下一步就是对立方体内的杆状物进行提取。对杆状物在三个方向进行投影后，根据杆状物呈现的形态，可依据先验知识认为杆状物在XOY平面的投影面可以用参数椭圆进行最小二乘拟合，在XOZ或者YOZ平面的投影面可用平行四边形进行最小二乘拟合。而由于在点云获取中存在较多的稀疏噪点导致之前获取的立方体较实际物体的尺寸存在一定的放大，因此在XOZ、YOZ和XOZ平面需要进行紧致性分析。在紧致集分析过程中可以剔除掉同属于一个立方体和同一个杆状物，但并不属于杆状物点的杂点，从而得到更精确的杆状物真实空间大小。

[0059] 紧致性分析步骤具体如下：

[0060] 在XOY平面内，从相应平面内杆状物的投影点中选取任意三点确定一个椭圆，当包含在某椭圆内的点数与总点数的比例大于一定的阈值时，该椭圆即为该平面内投影点云的紧致椭圆，之后再找出紧致椭圆的外接矩形，并利用该外接矩形对原先的空间立方体包围盒进行X、Y方向上的范围和点集映射更新，这样有利于后续数据应用。

[0061] 而在YOZ和XOZ平面，则运用相似的原理但换用平行四边形模型进行紧致性分析，同时更新空间立方体包围盒和点集映射。

[0062] 在YOZ平面，从相应平面内杆状物的投影点中选取任意三点确定一个平行四边形，当包含在某平行四边形内的点数与总点数的比例大于一定的阈值时，该平行四边形即为该平面内投影点云的紧致平行四边形，并利用该紧致平行四边形对原先的空间立方体包围盒进行Y、Z方向上的范围和点集映射更新；

[0063] 在XOZ平面，从相应平面内杆状物的投影点中选取任意三点确定一个平行四边形，当包含在某平行四边形内的点数与总点数的比例大于一定的阈值时，该平行四边形即为该平面内投影点云的紧致平行四边形，并利用该紧致平行四边形对原先的空间立方体包围盒进行X、Z方向上的范围和点集映射更新。

[0064] 经过紧致性分析之后，可以确定杆状物的大致形状与分布，然而由于之前进行了滤波，利用紧致性分析得到的杆状物是不完整的，因而接下来便是利用紧致性分析得到的数据，从26个邻域进行连通域分析，从而使得该杆状物从中间向上下两个方向进行生长，得到完整的杆状物点云。

[0065] 得到了杆状物点云之后，还可以进一步进行特征分析。首先可利用点的数目及高度分布特性进行初步的分类筛选，点数目过少以及在高程分布区域过小的候选点云都可被筛除。例如点云的数目在50个以下，或者仅在高程1m以下区域分布的点集都不会作为候选杆状物点云。之后将利用邻域分析对杆状物的上部9邻域和下部9邻域进行进一步分析，判断其具体的地物属性。例如树木点云的上部9领域内将表现为大量密集散乱的点云，而电线杆将表现为仅在包围盒的正上方领域内有较多的点云分布，正上方邻域周围的8领域内将几乎没有点分布。在得到杆状物具体的地物属性之后，将针对其具体属性提取相应的位置坐标、高度、形状特点等参数，例如树木需要同时记录树冠和树干的高度宽度，而电线杆则只需记录宽度与高度。这些参数将作为后续建模工作的铺垫。

[0066] 步骤四：杆状物的建模。

[0067] 根据上一步得到的杆状物特征参数，可以在3ds Max中对其进行精细化建模，以还原杆状物的真实情况。

[0068] 由于在杆状物提取过程中，已经获得了杆状物所具有的几何、位置等信息，此时只需要将该参数导入到3ds Max中，运用3ds Max强大的建模功能，对杆状物进行建模即可。根据所获得的位置信息，可以准确地将模型安置在数字城市的相应位置中，根据所获得的杆状物的高度、形状、半径等信息，可以准确地计算出每一个杆状物在地面的覆盖范围、在数字城市中的高度、及具体的形状。正是由于提取的每一个杆状物的各个参数都不同，因此此时建出的模型不是单一的模型，而是根据杆状物的实际特征，真实还原实物所得到的模型，因而增强了数字城市中杆状物模型的真实性。

[0069] 基于以上流程所得结果，在需要时还可以进行缺失杆状物的填补。该填补过程并非针对所有的情况，只针对于城市地物中具有明显杆状特点但因附近存在干扰而难以识别的杆状物加以填补。这一部分杆状物常常是受到遮挡，因而在利用激光进行扫描时，此类杆状物的信息往往有一定程度的缺失。

[0070] 在实际采集的点云中，难免存在杆状物被遮挡的情况，使得点云数据不全，因此在利用以上步骤进行杆状物提取时，这部分被遮挡的杆状物数据就会遗漏。为了弥补此种由点云缺失造成的地物提取遗漏现象，可以利用杆状物的规则化分布特性来解决。即在空间上，杆状物的分布是有一定的空间规律，例如每间隔一段距离就会有同一种类杆状物反复出现，如果在数据里发现其中缺少了本应有的杆状物，那么在建模过程中便可以根据这一空间规律自动添加缺少的杆状物到相应位置。此缺失杆状物的模型可完全采用其周围杆状物的模型，而它的空间位置可以根据其周围杆状物的空间位置推算出来，这也便是杆状物提取过程中获得杆状物的位置信息的另外一种理由。

[0071] 具体实施时，本发明所提供方法可采用计算机软件技术自动运行流程，其中也可以引入用户操作以进一步提高效率，例如聚类中心的选择、类别的勾选时可进行人机交互。因此本发明可以大大简化繁琐的人工劳动，在保证精度的同时大大提高了生产效率。

[0072] 本发明实施例还相应提供一种基于密度峰值聚类的杆状物规则化三维建模系统，包括以下模块：

[0073] 预处理模块，用于针对车载激光雷达所获取原始的点云数据，进行体素重采样，去除离群点，将整个场景的点云进行格网化分割，对各网格分别通过高程直通滤波去除地面点和高层建筑点，然后向三维坐标系的三个坐标平面XOY、XOZ和YOZ分别投影，所述三维坐标系的Y方向指向正北方向、Z方向指向竖直方向，按右手规则建立；

[0074] 点云数据聚类模块，用于针对预处理结果，对各网格采用基于密度峰值和距离属性的聚类方式分别在三个投影平面中进行聚类，在聚类结束后，将每一类对应的点序号存入相应的动态链表中；

[0075] 杆状物提取模块，用于根据三个投影平面的聚类结果，用规则的空间立方体包围盒对对同一类的点云限定其空间范围，将每一类的立方体与立方体内的地物及构成地物的点云建立映射关系，根据先验知识对空间立方体包围盒内的杆状物进行提取，得到杆状物特征参数；所述用规则的空间立方体包围盒对对同一类的点云限定其空间范围，包括对各网格中每一类分别根据三个投影平面中所有点的X、Y、Z坐标最大最小值求交得到对应的包围立方体，同时获得该包围立方体对应的所有内部点序号索引，然后对将邻近的处理网格进行相近类别合并，并更新得到最终的空间立方体包围盒；

[0076] 所述先验知识为，杆状物在XOY平面的投影面能够用参数椭圆进行最小二乘拟合，在XOZ或者YOZ平面的投影面能够用平行四边形进行最小二乘拟合；

[0077] 所述对空间立方体包围盒内的杆状物进行提取，通过紧致性分析和连通域分析实现；

[0078] 杆状物建模模块，用于根据杆状物特征参数，进行建模，还原杆状物。

[0079] 本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。