Nothing Special   »   [go: up one dir, main page]

CN110348478B - 一种基于形状分类与组合的室外点云场景中树木提取方法 - Google Patents

一种基于形状分类与组合的室外点云场景中树木提取方法 Download PDF

Info

Publication number
CN110348478B
CN110348478B CN201910481805.5A CN201910481805A CN110348478B CN 110348478 B CN110348478 B CN 110348478B CN 201910481805 A CN201910481805 A CN 201910481805A CN 110348478 B CN110348478 B CN 110348478B
Authority
CN
China
Prior art keywords
points
point
data
scattering
characteristic information
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201910481805.5A
Other languages
English (en)
Other versions
CN110348478A (zh
Inventor
宁小娟
田戈
王映辉
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Xian University of Technology
Original Assignee
Xian University of Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Xian University of Technology filed Critical Xian University of Technology
Priority to CN201910481805.5A priority Critical patent/CN110348478B/zh
Publication of CN110348478A publication Critical patent/CN110348478A/zh
Application granted granted Critical
Publication of CN110348478B publication Critical patent/CN110348478B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/16—Matrix or vector computation, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/22—Matching criteria, e.g. proximity measures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/24—Classification techniques
    • G06F18/241—Classification techniques relating to the classification model, e.g. parametric or non-parametric approaches
    • G06F18/2413—Classification techniques relating to the classification model, e.g. parametric or non-parametric approaches based on distances to training or reference patterns
    • G06F18/24133—Distances to prototypes
    • G06F18/24137—Distances to cluster centroïds
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V20/00—Scenes; Scene-specific elements
    • G06V20/10—Terrestrial scenes
    • G06V20/188—Vegetation

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Mathematical Physics (AREA)
  • General Engineering & Computer Science (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Evolutionary Biology (AREA)
  • Evolutionary Computation (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Mathematical Analysis (AREA)
  • Computational Mathematics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Artificial Intelligence (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Computing Systems (AREA)
  • Software Systems (AREA)
  • Databases & Information Systems (AREA)
  • Algebra (AREA)
  • Health & Medical Sciences (AREA)
  • General Health & Medical Sciences (AREA)
  • Multimedia (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Image Analysis (AREA)

Abstract

本发明公开了一种基于形状分类与组合的室外点云场景中树木提取方法，利用最优特征集，使用分类算法来提高对室外场景分类的准确性，得到分类之后的数据，通过定位，过滤，匹配等步骤来完成室外场景点云数据中单棵树木提取问题，如果在数据中存在树冠重叠问题，再通过进一步优化处理，对最后的结果进行优化改善，完成单棵树木提取。本发明解决了室外点云场景中树冠重叠树木不可分问题。

Description

一种基于形状分类与组合的室外点云场景中树木提取方法
技术领域
本发明属于计算机图形学和虚拟现实相结合的交叉学科技术领域，具体涉及一种基于形状分类与组合的室外点云场景中树木提取方法。
背景技术
随着虚拟现实、人工智能以及计算机视觉技术的发展，对各种三维室外场景的分析已经成为一个具有重要研究意义和应用价值的研究课题。3D采集技术的发展可为研究员提供精准的数据，例如：地面激光扫描仪(Terrestrial Laser Scanners，TLS)和移动激光扫描仪(Mobile Laser Scanner，MLS)可以获得高密度、高精度城市场景点云数据。对城市场景数据的分析已成为计算机图形学，计算机视觉和摄影测量领域的主要研究内容。大多数研究工作集中在对点云场景数据中特定对象(建筑物，道路，汽车，或者树木的标记和提取。
树木作为城市场景中的重要元素之一，近年来提取单棵树木并获取树木的属性(例如树高，树干直径，树冠直径)已被广泛应用于城市规划建设，3D树木建模和城市树木检测等领域。对于城市而言，树木是城市生态系统和景观的重要组成部分，对城市中街道树的分析在提高环境质量，保持城市景观美感和为居民提供社会服务方面发挥着重要作用。如何自动有效的提取树木信息对于绿色城市管理以及智慧化城市的建设有着重要的意义。然而由于树叶密集性，树木种类多样性以及由于遮挡带来的数据缺失性，都毫无疑问增加了从城市场景中提取树木元素的难度，因此，针对城市场景中树木的提取与分割研究，仍然是非常富有挑战性。目前树木提取方法主要包括以下几种：
(一)基于机器学习的树木提取方法
基于机器学习的单棵树木提取方法是通过机器学习中经典的分类算法或者聚类算法来处理室外点云场景数据。分类算法旨在将室外点云场景数据进行分类分割，提取分类结果中的目标物，达到缩小提取范围的效果。聚类算法旨在将场景中相似特征的点云数据聚类到一起，从而可以将室外点云场景数据中的树木进行单棵提取。
基于机器学习的单棵树木提取方法能够很好地从室外点云场景中提取出单棵树木。但是存在一些问题，比如：使用的分类方法比较简单，存在分类结果中出现比较多的非目标点；如果聚类方法比较简单，在聚类的过程中出现过聚类或者聚类不足等问题。
(二)基于区域增长的树木提取方法
基于区域增长的方法被广泛应用于场景分割，包括建筑物分割，树木分割，车辆分割等。它主要是对点云数据中特征比较相似的点通过一种区域生长的方式来对数据进行聚类。主要分为两种：一种是自上而下的区域增长方式，另一种是自下而上的区域增长方式。该方法一般会先选取种子点，根据计算种子点与其邻域点的特征向量，曲率等特征，将特征比较相似所对应的点进行合并，以此类推，直到没有可以合并的点云数据为止，这些特征相似的数据点通过这样的方式被聚类到一起形成一个簇，然后再重新在剩余的点云数据中选取种子点，进行区域增长，直到所有的点云数据都通过区域增长的方式被分类到某一个簇中，结果整体循环。
基于区域增长的单棵树木提取方法能够很好地将特征相似的点云数据聚类到一起形成一棵棵树，但是此方法在必须要选择种子点，另外光滑边界难以区分，准则函数不太好确定，受阈值影响太大，特别是室外点云场景，点云数据量大，场景比较复杂，故使用这种方法存在缺陷。
(三)基于体素化的单棵树木提取方法
基于体素的单棵树木提取方法，旨在通过对室外场景点云数据进行体素化之后，可以根据体素化之后每个点云数据的颜色、强度、以及数据的空间等对场景进行分割。
使用体素化的时候虽然实验结果还是不错，但是存在如果室外点云场景中的树木与点云场景中的其他物体太靠近时，实验结果就不能将它们分离开来，从而在最终的实验结果中存在非目标物的点云数据。
(四)基于模型拟合的树木提取方法
基于模型拟合的方法旨在提取具有特定形状的对象，包括平面，圆柱体和球体。对特定形状的对象数据中属于目标物的数据进行保留，再通过合并呈现出一棵完整的树。
基于模型拟合的方法可以在某些特定的情况下提取单棵树，但是在复杂几何形状中表现出比较差的性能，尤其是室外点云场景数据，存在数据庞大，场景复杂等情况，导致实验结果不是很理想。
发明内容
本发明的目的是提供一种基于形状分类与组合的室外点云场景中树木提取方法，解决了在提取室外场景点云数据中树冠重叠，导致无法提取单棵树木问题。
本发明所采用的技术方案是，一种基于形状分类与组合的室外点云场景中树木提取方法，具体包括以下步骤：
步骤1)基于室外场景点云数据的特征，得到室外场景的最优特征集；
步骤2)根据最优特征集对室外场景点云数据进行分类，分类具体包括线状点、平面点、圆柱点和散射点；
步骤3)由于树木的树干和树冠对应的室外场景点云数据为圆柱点和散射点，因此提取分类后的圆柱点和散射点，通过对圆柱点和散射点定位、过滤、匹配、优化，来完成室外场景点云数据中单棵树木提取。
本发明的特点还在于，
步骤1)具体按照以下步骤实施：
步骤1.1)手动在室外场景点云数据中选取线状数据点、平面数据点、圆柱数据点和散射数据点共四部分数据点，该四部分数据点依次记为T1、T2、T3和T4，求出所选每部分数据点中各数据点的所有特征信息值，所有特征信息包括维度特征、法向量、主方向、特征值、特征值之和、特征熵、全方差、点的异向性、点局部表面变化、局部点密度、点的高度；
步骤1.2)求出T1中各特征信息值的平均值，并由大到小排列，选取排列后前三位特征信息值的平均值所对应的特征信息，前三位的特征信息值的平均值所对应的特征信息分别为V1(T1)、V2(T1)、V3(T1)，T2、T3和T4同理得到V1(T2)、V2(T2)、V3(T2)、V1(T3)、V2(T3)、V3(T3)、V1(T4)、V2(T4)、V3(T4)；
步骤1.3)若T1、T2、T3和T4所选取的特征信息均不相同，则将T1、T2、T3和T4所选取的特征信息组成集合，得到最优特征集；若T1、T2、T3和T4所选取的特征信息存在相同的特征信息，则删除相同的特征信息，选取相同特征信息所对应部分排列后第四位特征信息值的平均值所对应的特征信息，判断T1、T2、T3和T4重新选取的特征信息是否有相同的特征信息，按照该方式以此类推，若每次T1、T2、T3和T4重选取的特征信息均存在相同的特征信息，则将T1、T2、T3和T4中保留的特征信息组成集合，得到最优特征集，若T1、T2、T3和T4重新选取的特征信息不存在相同的特征信息，则将T1、T2、T3和T4重新选取的特征信息组成集合，得到最优特征集。
步骤1.1)中求出数据点所有特征信息值具体按照以下步骤实施：
步骤1.1.1)假设室外场景点云数据P＝{p0,p1,p2,…,pi,…,pn}，i和n均为自然数，数据点pi为T1、T2、T3、T4任一部分中的数据点，数据点pi的k个相邻点及其空间坐标为qj(xj,yj,zj)，j＝1,2,…,k，k≠0，则点pi的协方差矩阵如下：
Figure BDA0002084088260000051
式(1)中，
Figure BDA0002084088260000052
是k个pi相邻点的中心，且
Figure BDA0002084088260000053
W为半正定对称矩阵，其特征值均为非负值，且不同特征值对应的特征向量是正交的，构成所在空间的一组单位正交基，且
Figure BDA0002084088260000054
式(3)中，W的特征值大小关系为λ1≥λ2≥λ3≥0；
步骤1.1.2)令pi的邻域ki由小到大为kmin到kmax，并且使ki的增量为Δk，通过下式(4)计算香农熵函数值以确定每个点的最佳邻域值，求出每个邻域ki对应的香农熵函数值，从这些香农熵函数值中选取最小值，这个最小值所对应的邻域ki即为pi的最佳邻域值。
Entropy＝-pro1Dln(pro1D)-pro2Dln(pro2D)-pro3Dln(pro3D) (4)
式(4)中，Entropy表示香农熵函数，pro1D表示线状数据点，pro2D表示平面数据点，pro3D表示柱状数据点或散乱数据点；
比较每个邻域ki相应的香熵值，选择具有最小香熵值的邻域作为最佳邻域ki'，则令ki'＝ki+Δk，通过主成分分析算法计算pi的协方差矩阵W的特征向量e1、e2、e3和特征值λ1、λ3、λ3，；
步骤1.1.3)根据特征值可以计算数据点pi的全方差、异向性、特征熵、特征值之和、局部表面变化、高度特征以及局部表面密度，数据点pi的法向量
Figure BDA0002084088260000064
可以由λ3对应的特征向量确定，主方向
Figure BDA0002084088260000065
可以由λ1对应的特征向量确定，即得到数据点所有特征信息值。
式(4)中，
Figure BDA0002084088260000061
式(5)中，1D表示维度特征为线性，2D表示维度特征为平面，3D表示维度特征为散射状，δ1、δ2、δ3表示三个正交方向的拟合残差，令
Figure BDA0002084088260000062
Figure BDA0002084088260000063
当δ1分别远大于δ2、δ3时，该点为线状点，表示该拟合区域仅在一个方向上存在较大的拟合残差，同理δ1、δ2均远大于δ3时，该点为面状点，此时λ3对应特征向量即为该点法向量，当δ1≈δ2≈δ3时，该点为散乱点或柱状点。
步骤2)具体按照以下步骤实施：
通过支持向量机得到高斯核函数及其参数，通过随机森林方法构件决策树，将最优特征集输入决策树生成多个训练集，并由高斯核函数计算每个点云数据与各训练集的相似程度，通过比较相似程度将室外点云场景数据进行分类，分类具体包括线状点、平面点、圆柱点和散射点。
步骤3)具体按照以下步骤实施：
步骤3.1)提取分类后的圆柱点和散射点，通过光谱聚类算法对圆柱点和散射点进行聚类，得到了不同种类的圆柱点和散射点点集，即得到不同的树干和树冠；
步骤3.2)通过分别设置圆柱点和散射点筛选点数阈值，将点数小于对应筛选点数阈值的点集剔除，即移除一些离室外场景比较远或者不属于真正树干、树冠、的点集，得到可匹配的圆柱点和散射点的点集；
步骤3.3)通过求取可匹配的圆柱点点集与各散射点点集的相似性，根据相似性将对应的散射点集进行匹配；
步骤3.4)若同一散射点点集对应多个圆柱点点集，求出所对应的每个圆柱点点集的质心mi(i＝1,2,…,n)，从该散射点点集随机选取一个数据点，计算该数据点到质心mi(i＝1,2,…,n)的距离，通过比较将该数据点分配给距离最短的质心所对应的圆柱点点集进行合并，按照此方式，知道该散射点点集中的数据点分配完为止，并且将其他一一对应的散射点点集和圆柱点点集进行合并，每个合并后的点集即为单棵树木对应的点集，单棵树木提取完成；若不存在同一散射点点集对应多个圆柱点点集，直接将一一对应的散射点点集和圆柱点点集进行合并，每个合并后的点集即为单棵树木对应的点集，单棵树木提取完成。
步骤3.1)具体按照以下步骤实施：
步骤3.1.1)令提取分类后的圆柱点和散射点为簇Clucy和Clusc，分别为簇Clucy和Clusc构造无向图G(V,E)，其中V即为各簇中所有的数据点(v1,v2,…,vn)，集合E表示各簇中数据点之间的边，边的权重为两点之间的距离值；
步骤3.1.2)定义簇Clucy和Clusc对称相似矩阵W＝{Wij}i,j＝1,…,n，表示每条边的权重(i,j)∈E，即权重Wij为点Vi和点Vj之间的权重，因为G是无向图，所有Wij＝Wji；
步骤3.1.3)采用全连接的方式，对提取分类后的圆柱点和散射点求取如下度量矩阵D，
Figure BDA0002084088260000081
式(6)的度量矩阵D中对角线表示对于任意一个点Vi，它的度量di定义为和它相连的所有边的权重之和，且
Figure BDA0002084088260000082
步骤3.1.4)拉普拉斯矩阵L＝D-W，对拉普拉斯矩阵进行标准化得到下式，
L＝D-1/2LD1/2＝I-D-1/2WD1/2 (8)
根据Ncut分割准则，求出L的t个特征向量，L的特征向量归一化后组成一个特征矩阵R，将特征矩阵R的每一行看做一个的样本，使用K均值算法对特征矩阵R进行聚类，即先随机选取一个样本所对应的点云数据标记，把与该样本特征相似的样本所对应的点云数据标记为同一类，将标记之后的点云数据从提取分类后的圆柱点和散射点中剔除，如果没有与该样本特征相似的样本，则重新随机选取一个样本，直至提取分类后的圆柱点和散射点中每个点云数据都进行了标记，最后得到不同种类的圆柱点和散射点点集。
步骤3.3)具体按照以下步骤实施：
步骤3.3.1)将可匹配的圆柱点点集和散射点点集分别记为
Figure BDA0002084088260000083
和
Figure BDA0002084088260000084
假设Gi(xi,yi,zi)和Qi(xi,yi,zi)分别为
Figure BDA0002084088260000085
和
Figure BDA0002084088260000086
的质心，Cij是
Figure BDA0002084088260000087
和
Figure BDA0002084088260000088
在三维空间中质心Gi(xi,yi,zi)和Qi(xi,yi,zi)之间的距离，则
Cij＝Dist(Gi,Qj)3D (9)
Cij的值被归一化，取值范围在0到1之间；
步骤3.3.2)令Tij表示
Figure BDA0002084088260000091
和
Figure BDA0002084088260000092
投影在2D中的质心Gi(xi,yi,zi)和Qi(xi,yi,zi)之间的距离，则
Tij＝Dist(Gi,Qj)2D (10)
Tij的值被归一化，取值范围在0到1之间；
步骤3.3.3)令Aij表示树干成为候选树干匹配上树冠的概率，则
Figure BDA0002084088260000093
步骤3.3.4)计算每个
Figure BDA0002084088260000094
和每个
Figure BDA0002084088260000095
之间的相似性Pro(i,j)的值，
Pro(i,j)＝1-(w1Min(Cij)+w2Min(Tij)+w3Aij) (12)
式(12)中，w1、w2、w3、w4为比例系数，w1＝w2＝0.2,w3＝0.6，若Pro(i，j)大于0.9，则将相应的两个点集匹配，若存在多个Pro(i,j)的值大于0.9，则对于同一个可匹配的圆柱点点集将相似性Pro(i,j)值最大的散射点点集进行匹配。
本发明的有益效果是：
本发明一种基于形状分类与组合的室外点云场景中树木提取方法，可操作性强，解决了在提取室外场景点云数据中树冠重叠，导致无法提取单棵树木问题，将树干与树冠在二维空间与三维空间的拓扑关系以及树干与树冠一一对应的关系，对树干与树冠进行最优合并，能够自动的完成室外场景点云数据中的树木提取，提高了单棵树木提取的准确性。
具体实施方式
下面结合具体实施方式对本发明进行详细说明。
本发明一种基于形状分类与组合的室外点云场景中树木提取方法，具体包括以下步骤：
步骤1)基于室外场景点云数据的特征，得到室外场景的最优特征集；
步骤2)根据最优特征集对室外场景点云数据进行分类，分类具体包括线状点、平面点、圆柱点和散射点；
步骤3)由于树木的树干和树冠对应的室外场景点云数据为圆柱点和散射点，因此提取分类后的圆柱点和散射点，通过对圆柱点和散射点定位、过滤、匹配、优化，来完成室外场景点云数据中单棵树木提取。
步骤1)具体按照以下步骤实施：
步骤1.1)手动在室外场景点云数据中选取线状数据点、平面数据点、圆柱数据点和散射数据点共四部分数据点，该四部分数据点依次记为T1、T2、T3和T4，求出所选每部分数据点中各数据点的所有特征信息值，所有特征信息包括维度特征、法向量、主方向、特征值、特征值之和、特征熵、全方差、点的异向性、点局部表面变化、局部点密度、点的高度，全方差、点的异向性、特征熵、特征值之和、点局部表面变化、点的高度、局部点密度的计算式如表1所示；
表1特征求取公式
Figure BDA0002084088260000101
Figure BDA0002084088260000111
步骤1.2)求出T1中各特征信息值的平均值，并由大到小排列，选取排列后前三位特征信息值的平均值所对应的特征信息，前三位的特征信息值的平均值所对应的特征信息分别为V1(T1)、V2(T1)、V3(T1)，T2、T3和T4同理得到V1(T2)、V2(T2)、V3(T2)、V1(T3)、V2(T3)、V3(T3)、V1(T4)、V2(T4)、V3(T4)；
步骤1.3)若T1、T2、T3和T4所选取的特征信息均不相同，则将T1、T2、T3和T4所选取的特征信息组成集合，得到最优特征集；若T1、T2、T3和T4所选取的特征信息存在相同的特征信息，则删除相同的特征信息，选取相同特征信息所对应部分排列后第四位特征信息值的平均值所对应的特征信息，判断T1、T2、T3和T4重新选取的特征信息是否有相同的特征信息，按照该方式以此类推，若每次T1、T2、T3和T4重选取的特征信息均存在相同的特征信息，则将T1、T2、T3和T4中保留的特征信息组成集合，得到最优特征集，若T1、T2、T3和T4重新选取的特征信息不存在相同的特征信息，则将T1、T2、T3和T4重新选取的特征信息组成集合，得到最优特征集。
步骤1.1)中求出数据点所有特征信息值具体按照以下步骤实施：
步骤1.1.1)假设室外场景点云数据P＝{p0,p1,p2,…,pi,…,pn}，i和n均为自然数，数据点pi为T1、T2、T3、T4任一部分中的数据点，数据点pi的k个相邻点及其空间坐标为qj(xj,yj,zj)，j＝1,2,…,k，k≠0，则点pi的协方差矩阵如下：
Figure BDA0002084088260000121
式(1)中，
Figure BDA0002084088260000122
是k个pi相邻点的中心，且
Figure BDA0002084088260000123
W为半正定对称矩阵，其特征值均为非负值，且不同特征值对应的特征向量是正交的，构成所在空间的一组单位正交基，且
Figure BDA0002084088260000124
式(3)中，W的特征值大小关系为λ1≥λ2≥λ3≥0；
步骤1.1.2)令pi的邻域ki由小到大为kmin到kmax，并且使ki的增量为Δk，通过下式(4)计算香农熵函数值以确定每个点的最佳邻域值，求出每个邻域ki对应的香农熵函数值，从这些香农熵函数值中选取最小值，这个最小值所对应的邻域ki即为pi的最佳邻域值。
Entropy＝-pro1Dln(pro1D)-pro2Dln(pro2D)-pro3Dln(pro3D) (4)
式(4)中，Entropy表示香农熵函数，pro1D表示线状数据点，pro2D表示平面数据点，pro3D表示柱状数据点或散乱数据点；
比较每个邻域ki相应的香熵值，选择具有最小香熵值的邻域作为最佳邻域ki'，则令ki'＝ki+Δk，通过主成分分析算法(PCA)计算pi的协方差矩阵W的特征向量e1、e2、e3和特征值λ1、λ3、λ3，；
步骤1.1.3)根据特征值可以计算数据点pi的全方差、异向性、特征熵、特征值之和、局部表面变化、高度特征以及局部表面密度，数据点pi的法向量
Figure BDA0002084088260000131
可以由λ3对应的特征向量确定，主方向
Figure BDA0002084088260000132
可以由λ1对应的特征向量确定，即得到数据点所有特征信息值。
式(4)中，
Figure BDA0002084088260000133
式(5)中，1D表示维度特征为线性，2D表示维度特征为平面，3D表示维度特征为散射状，δ1、δ2、δ3表示三个正交方向的拟合残差，令
Figure BDA0002084088260000134
Figure BDA0002084088260000135
当δ1分别远大于δ2、δ3时，该点为线状点，表示该拟合区域仅在一个方向上存在较大的拟合残差，同理δ1、δ2均远大于δ3时，该点为面状点，此时λ3对应特征向量即为该点法向量，当δ1≈δ2≈δ3时，该点为散乱点或柱状点。
步骤2)具体按照以下步骤实施：
通过支持向量机(SVM)得到高斯核函数及其参数，通过随机森林方法(RF)构件决策树，将最优特征集输入决策树生成多个训练集，并由高斯核函数计算每个点云数据与各训练集的相似程度，通过比较相似程度将室外点云场景数据进行分类，分类具体包括线状点、平面点、圆柱点和散射点。
使用SVM在于对核函数，核函数的参数g和最佳的惩罚参数c的选取。本发明的室外点云场景中树木提取方法采用高斯核函数(RBF)，其表达式如下，
Figure BDA0002084088260000141
高斯核函数(RBF)是将初始的空间映射成为无穷维度的空间上，上式σ＞0表示RBF的带宽，xi、xj分别表示选取的样本数据点。
对于选取最佳的核函数参数g和惩罚参数c，本发明的室外点云场景中树木提取方法是通过交叉验证的方法找到准确率最高的c和g。在准确率相同的条件下，先选取最小的c对应的那组c和g作为最佳的惩罚参数和核函数参数。
随机森林的分类方法，指的是利用决策树生成的多个训练集对样本进行训练并对整体数据进行预测的一种分类方法。使用Iterative Dichotomiser 3算法构建随机森林决策树，将最优特征集输入决策树生成多个具有标签的数据点训练集。IterativeDichotomiser 3算法以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。
通过高斯核函数计算所有数据点与各数据点训练集的相似程度，通过比较同一数据点与各数据点训练集的相似程度，对其进行分类，把室外点云场景数据分类为线状点、平面点、圆柱点和散射点。
步骤3)具体按照以下步骤实施：
步骤3.1)提取分类后的圆柱点和散射点，通过光谱聚类算法对圆柱点和散射点进行聚类，得到了不同种类的圆柱点和散射点点集，即得到不同的树干和树冠；
步骤3.2)通过分别设置圆柱点和散射点筛选点数阈值，将点数小于对应筛选点数阈值的点集剔除，即移除一些离室外场景比较远或者不属于真正树干、树冠、的点集，得到可匹配的圆柱点和散射点的点集；
步骤3.3)通过求取可匹配的圆柱点点集与各散射点点集的相似性，根据相似性将对应的散射点集进行匹配；
步骤3.4)若同一散射点点集对应多个圆柱点点集，求出所对应的每个圆柱点点集的质心mi(i＝1,2,…,n)，从该散射点点集随机选取一个数据点，计算该数据点到质心mi(i＝1,2,…,n)的距离，通过比较将该数据点分配给距离最短的质心所对应的圆柱点点集进行合并，按照此方式，知道该散射点点集中的数据点分配完为止，并且将其他一一对应的散射点点集和圆柱点点集进行合并，每个合并后的点集即为单棵树木对应的点集，单棵树木提取完成；若不存在同一散射点点集对应多个圆柱点点集，直接将一一对应的散射点点集和圆柱点点集进行合并，每个合并后的点集即为单棵树木对应的点集，单棵树木提取完成。
步骤3.1)具体按照以下步骤实施：
步骤3.1.1)令提取分类后的圆柱点和散射点为簇Clucy和Clusc，分别为簇Clucy和Clusc构造无向图G(V,E)，其中V即为各簇中所有的数据点(v1,v2,…,vn)，集合E表示各簇中数据点之间的边，边的权重为两点之间的距离值；
步骤3.1.2)定义簇Clucy和Clusc对称相似矩阵W＝{Wij}i,j＝1,…,n，表示每条边的权重(i,j)∈E，即权重Wij为点Vi和点Vj之间的权重，因为G是无向图，所有Wij＝Wji；
步骤3.1.3)采用全连接的方式，对提取分类后的圆柱点和散射点求取如下度量矩阵D，
Figure BDA0002084088260000151
式(6)的度量矩阵D中对角线表示对于任意一个点Vi，它的度量di定义为和它相连的所有边的权重之和，且
Figure BDA0002084088260000161
步骤3.1.4)拉普拉斯矩阵L＝D-W，对拉普拉斯矩阵进行标准化得到下式，
L＝D-1/2LD1/2＝I-D-1/2WD1/2 (8)
根据Ncut分割准则，求出L的t个特征向量，L的特征向量归一化后组成一个特征矩阵R，将特征矩阵R的每一行看做一个的样本，使用k-means算法对特征矩阵R进行聚类，即先随机选取一个样本所对应的点云数据标记，把与该样本特征相似的样本所对应的点云数据标记为同一类，将标记之后的点云数据从提取分类后的圆柱点和散射点中剔除，如果没有与该样本特征相似的样本，则重新随机选取一个样本，直至提取分类后的圆柱点和散射点中每个点云数据都进行了标记，最后得到不同种类的圆柱点和散射点点集。
步骤3.3)具体按照以下步骤实施：
步骤3.3.1)将可匹配的圆柱点点集和散射点点集分别记为
Figure BDA0002084088260000162
和
Figure BDA0002084088260000163
假设Gi(xi,yi,zi)和Qi(xi,yi,zi)分别为
Figure BDA0002084088260000164
和
Figure BDA0002084088260000165
的质心，Cij是
Figure BDA0002084088260000166
和
Figure BDA0002084088260000167
在三维空间中质心Gi(xi,yi,zi)和Qi(xi,yi,zi)之间的距离，则
Cij＝Dist(Gi,Qj)3D (9)
Cij的值被归一化，取值范围在0到1之间；
步骤3.3.2)令Tij表示
Figure BDA0002084088260000168
和
Figure BDA0002084088260000169
投影在2D中的质心Gi(xi,yi,zi)和Qi(xi,yi,zi)之间的距离，则
Tij＝Dist(Gi,Qj)2D (10)
Tij的值被归一化，取值范围在0到1之间；
步骤3.3.3)令Aij表示树干成为候选树干匹配上树冠的概率，则
Figure BDA0002084088260000171
步骤3.3.4)计算每个
Figure BDA0002084088260000172
和每个
Figure BDA0002084088260000173
之间的相似性Pro(i,j)的值，
Pro(i,j)＝1-(w1Min(Cij)+w2Min(Tij)+w3Aij) (12)
式(12)中，w1、w2、w3、w4表示比例系数，w1＝w2＝0.2,w3＝0.6，若Pro(i，j)大于0.9，则将相应的两个点集匹配，若存在多个Pro(i,j)的值大于0.9，则对于同一个可匹配的圆柱点点集将相似性Pro(i,j)值最大的散射点点集进行匹配。
本发明一种基于形状分类与组合的室外点云场景中树木提取方法，利用最优特征集，使用分类算法来提高对室外场景分类的准确性，得到分类之后的数据，通过定位，过滤，匹配等步骤来完成室外场景点云数据中单棵树木提取问题，如果在数据中存在树冠重叠问题，在通过进一步优化处理，对最后的结果进行优化改善，完成单棵树木提取。

Claims (5)

1.一种基于形状分类与组合的室外点云场景中树木提取方法，其特征在于，具体包括以下步骤：
步骤1)基于室外场景点云数据的特征，得到室外场景的最优特征集；
所述步骤1)具体按照以下步骤实施：
步骤1.1)手动在室外场景点云数据中选取线状数据点、平面数据点、圆柱数据点和散射数据点共四部分数据点，该四部分数据点依次记为T1、T2、T3和T4，求出所选每部分数据点中各数据点的所有特征信息值，所述所有特征信息包括维度特征、法向量、主方向、特征值、特征值之和、特征熵、全方差、点的异向性、点局部表面变化、局部点密度、点的高度；
步骤1.2)求出T1中各特征信息值的平均值，并由大到小排列，选取排列后前三位特征信息值的平均值所对应的特征信息，前三位的特征信息值的平均值所对应的特征信息分别为V1(T1)、V2(T1)、V3(T1)，T2、T3和T4同理得到V1(T2)、V2(T2)、V3(T2)、V1(T3)、V2(T3)、V3(T3)、V1(T4)、V2(T4)、V3(T4)；
步骤1.3)若T1、T2、T3和T4所选取的特征信息均不相同，则将T1、T2、T3和T4所选取的特征信息组成集合，得到最优特征集；若T1、T2、T3和T4所选取的特征信息存在相同的特征信息，则删除相同的特征信息，选取相同特征信息所对应部分排列后第四位特征信息值的平均值所对应的特征信息，判断T1、T2、T3和T4重新选取的特征信息是否有相同的特征信息，按照该方式以此类推，若每次T1、T2、T3和T4重选取的特征信息均存在相同的特征信息，则将T1、T2、T3和T4中保留的特征信息组成集合，得到最优特征集，若T1、T2、T3和T4重新选取的特征信息不存在相同的特征信息，则将T1、T2、T3和T4重新选取的特征信息组成集合，得到最优特征集；
步骤2)根据最优特征集对室外场景点云数据进行分类，分类具体包括线状点、平面点、圆柱点和散射点；
所述步骤2)具体为，通过支持向量机得到高斯核函数及其参数，通过随机森林方法构件决策树，将最优特征集输入决策树生成多个训练集，并由高斯核函数计算每个点云数据与各训练集的相似程度，通过比较相似程度将室外点云场景数据进行分类，分类具体包括线状点、平面点、圆柱点和散射点；
步骤3)由于树木的树干和树冠对应的室外场景点云数据为圆柱点和散射点，因此提取分类后的圆柱点和散射点，通过对圆柱点和散射点定位、过滤、匹配、优化，来完成室外场景点云数据中单棵树木提取；
所述步骤3)具体按照以下步骤实施：
步骤3.1)提取分类后的圆柱点和散射点，通过光谱聚类算法对圆柱点和散射点进行聚类，得到了不同种类的圆柱点和散射点点集，即得到不同的树干和树冠；
步骤3.2)通过分别设置圆柱点和散射点筛选点数阈值，将点数小于对应筛选点数阈值的点集剔除，即移除一些离室外场景比较远或者不属于真正树干、树冠、的点集，得到可匹配的圆柱点和散射点的点集；
步骤3.3)通过求取可匹配的圆柱点点集与各散射点点集的相似性，根据相似性将对应的散射点集进行匹配；
步骤3.4)若同一散射点点集对应多个圆柱点点集，求出所对应的每个圆柱点点集的质心mi(i＝1,2,…,n)，从该散射点点集随机选取一个数据点，计算该数据点到质心mi(i＝1,2,…,n)的距离，通过比较将该数据点分配给距离最短的质心所对应的圆柱点点集进行合并，按照此方式，知道该散射点点集中的数据点分配完为止，并且将其他一一对应的散射点点集和圆柱点点集进行合并，每个合并后的点集即为单棵树木对应的点集，单棵树木提取完成；若不存在同一散射点点集对应多个圆柱点点集，直接将一一对应的散射点点集和圆柱点点集进行合并，每个合并后的点集即为单棵树木对应的点集，单棵树木提取完成。
2.根据权利要求1所述的一种基于形状分类与组合的室外点云场景中树木提取方法，其特征在于，所述步骤1.1)中求出数据点所有特征信息值具体按照以下步骤实施：
步骤1.1.1)假设室外场景点云数据P＝{p0,p1,p2,…,pi,…,pn}，i和n均为自然数，数据点pi为T1、T2、T3、T4任一部分中的数据点，数据点pi的k个相邻点及其空间坐标为qj(xj,yj,zj)，j＝1,2,…,k，k≠0，则点pi的协方差矩阵如下：
Figure FDA0003821843430000031
式(1)中，
Figure FDA0003821843430000032
是k个pi相邻点的中心，且
Figure FDA0003821843430000033
W为半正定对称矩阵，其特征值均为非负值，且不同特征值对应的特征向量是正交的，构成所在空间的一组单位正交基，且
Figure FDA0003821843430000034
式(3)中，W的特征值大小关系为λ1≥λ2≥λ3≥0；
步骤1.1.2)令pi的邻域ki由小到大为kmin到kmax，并且使ki的增量为Δk，通过下式(4)计算香农熵函数值以确定每个点的最佳邻域值，求出每个邻域ki对应的香农熵函数值，从这些香农熵函数值中选取最小值，这个最小值所对应的邻域ki即为pi的最佳邻域值。
Entropy＝-pro1Dln(pro1D)-pro2Dln(pro2D)-pro3Dln(pro3D) (4)
式(4)中，Entropy表示香农熵函数，pro1D表示线状数据点，pro2D表示平面数据点，pro3D表示柱状数据点或散乱数据点；
比较每个邻域ki相应的香熵值，选择具有最小香熵值的邻域作为最佳邻域ki'，则令ki'＝ki+Δk，通过主成分分析算法计算pi的协方差矩阵W的特征向量e1、e2、e3和特征值λ1、λ3、λ3，；
步骤1.1.3)根据特征值可以计算数据点pi的全方差、异向性、特征熵、特征值之和、局部表面变化、高度特征以及局部表面密度，数据点pi的法向量
Figure FDA0003821843430000041
可以由λ3对应的特征向量确定，主方向
Figure FDA0003821843430000042
可以由λ1对应的特征向量确定，即得到数据点所有特征信息值。
3.根据权利要求2所述的一种基于形状分类与组合的室外点云场景中树木提取方法，其特征在于，所述式(4)中，
Figure FDA0003821843430000043
式(5)中，1D表示维度特征为线性，2D表示维度特征为平面，3D表示维度特征为散射状，δ1、δ2、δ3表示三个正交方向的拟合残差，令
Figure FDA0003821843430000044
Figure FDA0003821843430000045
当δ1分别远大于δ2、δ3时，该点为线状点，表示该拟合区域仅在一个方向上存在较大的拟合残差，同理δ1、δ2均远大于δ3时，该点为面状点，此时λ3对应特征向量即为该点法向量，当δ1≈δ2≈δ3时，该点为散乱点或柱状点。
4.根据权利要求1所述的一种基于形状分类与组合的室外点云场景中树木提取方法，其特征在于，所述步骤3.1)具体按照以下步骤实施：
步骤3.1.1)令提取分类后的圆柱点和散射点为簇Clucy和Clusc，分别为簇Clucy和Clusc构造无向图G(V,E)，其中V即为各簇中所有的数据点(v1,v2,…,vn)，集合E表示各簇中数据点之间的边，边的权重为两点之间的距离值；
步骤3.1.2)定义簇Clucy和Clusc对称相似矩阵W＝{Wij}i,j＝1,…,n，表示每条边的权重(i,j)∈E，即权重Wij为点Vi和点Vj之间的权重，因为G是无向图，所有Wij＝Wji；
步骤3.1.3)采用全连接的方式，对提取分类后的圆柱点和散射点求取如下度量矩阵D，
Figure FDA0003821843430000051
式(6)的度量矩阵D中对角线表示对于任意一个点Vi，它的度量di定义为和它相连的所有边的权重之和，且
Figure FDA0003821843430000052
步骤3.1.4)拉普拉斯矩阵L＝D-W，对拉普拉斯矩阵进行标准化得到下式，
L＝D-1/2LD1/2＝I-D-1/2WD1/2 (8)
根据Ncut分割准则，求出L的t个特征向量，L的特征向量归一化后组成一个特征矩阵R，将特征矩阵R的每一行看做一个的样本，使用k均值算法对特征矩阵R进行聚类，即先随机选取一个样本所对应的点云数据标记，把与该样本特征相似的样本所对应的点云数据标记为同一类，将标记之后的点云数据从提取分类后的圆柱点和散射点中剔除，如果没有与该样本特征相似的样本，则重新随机选取一个样本，直至提取分类后的圆柱点和散射点中每个点云数据都进行了标记，最后得到不同种类的圆柱点和散射点点集。
5.根据权利要求1所述的一种基于形状分类与组合的室外点云场景中树木提取方法，其特征在于，所述步骤3.3)具体按照以下步骤实施：
步骤3.3.1)将可匹配的圆柱点点集和散射点点集分别记为
Figure FDA0003821843430000061
和
Figure FDA0003821843430000062
假设Gi(xi,yi,zi)和Qi(xi,yi,zi)分别为
Figure FDA0003821843430000063
和
Figure FDA0003821843430000064
的质心，Cij是
Figure FDA0003821843430000065
和
Figure FDA0003821843430000066
在三维空间中质心Gi(xi,yi,zi)和Qi(xi,yi,zi)之间的距离，则
Cij＝Dist(Gi,Qj)3D (9)
Cij的值被归一化，取值范围在0到1之间；
步骤3.3.2)令Tij表示
Figure FDA0003821843430000067
和
Figure FDA0003821843430000068
投影在2D中的质心Gi(xi,yi,zi)和Qi(xi,yi,zi)之间的距离，则
Tij＝Dist(Gi,Qj)2D (10)
Tij的值被归一化，取值范围在0到1之间；
步骤3.3.3)令Aij表示树干成为候选树干匹配上树冠的概率，则
Figure FDA0003821843430000069
步骤3.3.4)计算每个
Figure FDA00038218434300000610
和每个
Figure FDA00038218434300000611
之间的相似性Pro(i,j)的值，
Pro(i,j)＝1-(w1Min(Cij)+w2Min(Tij)+w3Aij) (12)
式(12)中，w1、w2、w3、w4表示比例系数，w1＝w2＝0.2,w3＝0.6，若Pro(i,j)大于0.9，则将相应的两个点集匹配，若存在多个Pro(i,j)的值大于0.9，则对于同一个可匹配的圆柱点点集将相似性Pro(i,j)值最大的散射点点集进行匹配。
CN201910481805.5A 2019-06-04 2019-06-04 一种基于形状分类与组合的室外点云场景中树木提取方法 Active CN110348478B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201910481805.5A CN110348478B (zh) 2019-06-04 2019-06-04 一种基于形状分类与组合的室外点云场景中树木提取方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201910481805.5A CN110348478B (zh) 2019-06-04 2019-06-04 一种基于形状分类与组合的室外点云场景中树木提取方法

Publications (2)

Publication Number Publication Date
CN110348478A CN110348478A (zh) 2019-10-18
CN110348478B true CN110348478B (zh) 2022-10-11

Family

ID=68181495

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201910481805.5A Active CN110348478B (zh) 2019-06-04 2019-06-04 一种基于形状分类与组合的室外点云场景中树木提取方法

Country Status (1)

Country Link
CN (1) CN110348478B (zh)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN111428784B (zh) * 2020-03-23 2024-06-18 湖南工学院 采用机载激光雷达对落叶林树级参数测定的鲁棒分割方法
CN111986223B (zh) * 2020-07-15 2024-02-06 西安理工大学 一种基于能量函数的室外点云场景中树木提取方法
CN112347894B (zh) * 2020-11-02 2022-05-20 东华理工大学 基于迁移学习和高斯混合模型分离的单株植被提取方法
CN114972743A (zh) * 2022-03-18 2022-08-30 西安理工大学 一种基于半径扩展的层次级单棵树木提取方法

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101877128A (zh) * 2009-12-23 2010-11-03 中国科学院自动化研究所 一种三维场景中不同物体的分割方法
CN104463856A (zh) * 2014-11-25 2015-03-25 大连理工大学 基于法向量球的室外场景三维点云数据的地面提取方法
WO2015149302A1 (zh) * 2014-04-02 2015-10-08 中国科学院自动化研究所 基于点云与数据驱动的树木模型重建方法

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101877128A (zh) * 2009-12-23 2010-11-03 中国科学院自动化研究所 一种三维场景中不同物体的分割方法
WO2015149302A1 (zh) * 2014-04-02 2015-10-08 中国科学院自动化研究所 基于点云与数据驱动的树木模型重建方法
CN104463856A (zh) * 2014-11-25 2015-03-25 大连理工大学 基于法向量球的室外场景三维点云数据的地面提取方法

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
基于LiDAR点云的单棵树木提取方法研究;林怡等;《计算机测量与控制》;20170625(第06期);全文 *
局部形状特征概率混合的半自动三维点云分类;李红军等;《浙江大学学报(理学版)》;20170115(第01期);全文 *

Also Published As

Publication number Publication date
CN110348478A (zh) 2019-10-18

Similar Documents

Publication Publication Date Title
CN110348478B (zh) 一种基于形状分类与组合的室外点云场景中树木提取方法
Guo et al. Classification of airborne laser scanning data using JointBoost
Zhong et al. Segmentation of individual trees from TLS and MLS data
CN103839261B (zh) 基于分解进化多目标优化和fcm的sar图像分割方法
CN110992341A (zh) 一种基于分割的机载LiDAR点云建筑物提取方法
JP6621445B2 (ja) 特徴抽出装置、物体検出装置、方法、及びプログラム
CN108510516A (zh) 一种散乱点云的三维线段提取方法及系统
CN108241871A (zh) 基于多特征的激光点云与影像融合数据分类方法
CN112070769A (zh) 一种基于dbscan的分层点云分割方法
CN115205690B (zh) 基于mls点云数据的行道树单体化提取方法及装置
CN104091321A (zh) 适用于地面激光雷达点云分类的多层次点集特征的提取方法
CN112347894B (zh) 基于迁移学习和高斯混合模型分离的单株植被提取方法
Kim et al. 3D classification of power-line scene from airborne laser scanning data using random forests
JP2012088796A (ja) 画像領域分割装置、画像領域分割方法および画像領域分割プログラム
Li et al. A branch-trunk-constrained hierarchical clustering method for street trees individual extraction from mobile laser scanning point clouds
CN111414958B (zh) 一种视觉词袋金字塔的多特征图像分类方法及系统
Guo et al. Classification of airborne laser scanning data using JointBoost
CN113657216A (zh) 基于形状特征的点云场景树木树冠及木质点分离方法
CN106874421A (zh) 基于自适应矩形窗口的图像检索方法
Liu et al. A novel rock-mass point cloud registration method based on feature line extraction and feature point matching
CN116310849B (zh) 基于三维形态特征的树木点云单体化提取方法
CN111860359B (zh) 一种基于改进随机森林算法的点云分类方法
CN117893924A (zh) 一种基于树冠形态的无人机激光雷达点云单木分割方法
CN113988198B (zh) 一种基于地标约束的多尺度城市功能分类方法
Xu et al. Instance segmentation of trees in urban areas from MLS point clouds using supervoxel contexts and graph-based optimization

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant