chapter08-地面三维激光雷达点云分割与分类

18地面三维激光雷达点云分割与分类海量空间数据的快速、可靠、自动化处理是当前测绘领域研究的前沿。融合了空间信息、激光强度信息和物体色彩信息的三维激光点云数据，可以真实描述目标的空间结构、形态特性和光谱特征，三维激光点云为测量目标的识别分析提供了丰富信息，但由于其数据量大以及受到当前计算机硬件的限制，其快速、可靠、自动化的数据处理仍难难以实现，其中点云数据的自动分割是其中的一个难点，也是进行特征提取和曲面重建的前提和关键。正确进行点云分割和识别点云特征不仅有助于点云数据的管理，提高数据处理效率，还能对目标的三维重建提供可靠信息。在点云数据挖掘技术的研究中，点云分割技术的研究处在首要和优先的地位，是技术核心和基础。未来点云数据分割算法的研究则更多地集中在智能分割领域，如神经网络、群智能、遗传算法等。因此，研究三维激光点云的自动分割方法，对提高点云数据处理效率，三维目标的可靠重建和点云数据信息的充分挖掘与应用具有重要意义。8.1点云分割点云分割是确定点云中具有相同属性（空间位置、几何形状、激光强度、光谱特征等）区域的过程。点云分割的目的是从点云数据中获取更高层次的信息，是进行三维重建的基础。基于面的方法是根据微分几何中曲面的某些特征参数(如高斯曲率)的性质，来确定属于一个面的所有点，而上述特征参数的求取在曲面光滑连续的情况下才有效。实际中的物体不可能完全光滑连续而只可能是分片连续的，所以如何准确地估算出分片连续曲面的曲率是基于面的激光点云分割方法的瓶颈。基于平面度的直接分割方法是基于面的分割方法之一。该方法在计算过程中回避了种子点的选取，利用曲面上点及其邻域点的最小二乘拟合平面法矢量夹角的均方差值，来检测曲面上给定点邻域的弯曲程度，通过提取曲面之间的过渡曲面来分割曲面。基于边的方法首先根据点的局部几何特性在点邻域中估计出点的法向量或曲率，然后将法向量或曲率的突变处判定为边界位置，并经过边界跟踪和拟合等处理方法形成封闭的边界，再将封闭边界的区域作为最终的分割结果。以上两种方法都可以归结为对曲面之间过渡曲面的搜索过程。基于边的方法是通过搜索过渡曲面的边界，将过渡曲面及主要曲面分开；基于面的方法直接搜索过渡曲面和主要曲面，将过渡曲面作为独立的曲面分离出来。基于特征识别的分割的关键是各表面类型的辨识及其几何参数计算。表面2类型辨识是一个智能程度较高的过程,目前还难以由计算机自动完成,必须借助于人机交互,由人完成表面特征的辨识,由计算机完成几何参数的计算,再根据该被识别表面的类型和几何参数将该表面上的数据点群从整个三维点云中分离出来,实现三维点云分割。基于群簇的方法是通过向量量化(VQ，Vectorquantization)技术把局部几何特征参数相似的数据点聚集为一类。Hoffman和Jain通过提取数据点的坐标和法矢六维特征向量，来辨识数据点的特征；JeanK通过自组织特征映射神经网络实现聚类，取坐标、法矢和平均曲率、高斯曲率八维特征向量，来处理单视图的呈行列分布的数据。目前国际国内对点云分割问题的研究，多数是面对具体应用问题，从图像分割技术推广而来，例如分水岭法、区域增长法、Mean-shift法、聚类分析方法等。目前还没有一个有效的点云分割评价标准，多数工作仅仅致力于进一步提高分割质量。这些方法主要只考虑点云空间几何属性，而对点云的光谱特征信息利用较少。结合几何特征和光谱特征的方法将是点云分割的发展趋势。8.1.1基于邻近点空间拓扑结构的分割方法基于邻近点空间拓扑结构分割方法的基本思想是对不同的分割区域A和B，相比较B中的点而言，在A中的点更接近于A中的其他点。算法首先给点初始化一个属性表，属性表中不满足邻接准则的边界被逐个确定并剔除，最后的邻接图就表达了分割结果。邻接图的构造方法有：最小生成树（MST），Delaunay三角网、相对邻接图（RNG）和Gabriel图。8.1.2基于边缘检测的分割方法该方法的研究对象是点云数据对应深度图像、强度图像或者光谱图像，利用梯度算子检测图像中的不连续性区域，进行图像分割，分割结果所对应的区域即为不同类点云。图8.1边缘检测分割方法38.1.3基于点云表面生长的分割方法该方法首先在点云中选择种子面片或者种子点，然后以种子为中心，向周围以法向量、坡度或者曲率差异等临近准则扩张，形成连接集合，不同的集合即代表了不同的分割区域。图8.2平面生长图8.3圆柱面生长8.1.4基于模式识别的分割方法该方法是对点云中的每个点提取n个几何或者光谱特征，形成n维特征向4量空间，那么点云中连续和非连续的区域在特征空间中被视为不同的部分。可用的特征有坐标、法向量、平均曲率、高斯曲率、激光强度和光谱值等。在特征空间中进行分类的方法主要有聚类方法和神经网络方法。聚类（Clustering）分析也叫群分析，是用来研究未知样本空间的分类问题，即在没有任何先验知识的前提下，根据数据内部的特征空间分布，在给定的相似性测度的约束下将数据聚合成不同的簇或类。点云数据具有数据量大、空间分布不规则、特征量丰富等特点，因而可以将聚类分析技术应用到点云分割问题中。(1)K-均值聚类。其思想是多模式点到该类别的中心的距离的平方和最小。其目标函数为：错误！不能通过编辑域代码创建对象。(式8-1)(2)模糊C-均值聚类。传统聚类分析实质上都是一种硬性划分，对每个待识别目标都进行严格的非此即彼的归类，分类的界限明确。由于空间信息本身具有模糊性，一个事物是否属于某一类，并不是泾渭分明的。模糊聚类是将模糊集的概念应用到传统聚类分析中，将数据集的对象在分组中的可能性大小用隶属度来表达，因此这种分类的类别界限是“模糊”的。模糊聚类的优点在于能适应那些分离性不是很好的数据和类，并且对聚类初始化不敏感，具有较强的抗噪性。由于模糊聚类得到了样本属于各个类别的不确定性程度，表达了样本类别属性的模糊性，建立了样本对于类型的不确定性描述，因此得到的聚类结果往往更符合实际。模糊聚类中的代表性方法是模糊C-均值聚类（FCM），其思想是基于最小化目标函数：min112=−=∑∑==NiCjjimijcxuJ(式8-2)其中，Xxi∈是特征空间X中的第i个元素，jc是第j个聚类的类中心。{}1[0,1],1Cijijijjuuu=∈=∑表示隶属度，是特征空间的模糊划分矩阵。),1[∞∈m是权系数，控制着模式在模糊分类中的分享程度。⋅是距离测度，表征特征空间中样本与聚类中心的相似程度。模糊聚类的目标函数就是由参数集合{}⋅,,,,,mucxJijii共同决定。聚类中心jc和隶属度iju分别由(式8-3)式和(式8-4)式确定：5∑∑==⋅=NimijNiimijjuxuc11)((式8-3)()∑=−−−=pkmkijiijcxcxu1121(式8-4)一般地，模糊聚类的算法可表述为：1)确定划分的类数C，设置迭代阈值ε；2)初始化模糊划分矩阵)(tijµ；3)根据模糊划分矩阵计算各类的类中心)(tjc；4)根据目标函数J的约束，更新模糊划分矩阵)1(+tijµ，并调整类中心)1(+tjc；5)判定εµ−+)()1(tijtiju，如果不是则返回第3)步继续迭代。通过反复迭代，聚类中心自动调整到最佳位置，此时模糊划分矩阵趋于稳定，然后按照“最大隶属原则”对个体进行分类，即元素隶属度最大值所对应的类就是该元素所属的类。图8.4模糊C-均值聚类(3)均值飘移聚类（Mean-Shift）。6均值飘移聚类是基于密度的聚类算法，它没有假定聚类中心，均值漂移过程不需要预先给出类别数目，而是根据点集自身的密度分布探测获得类簇，发现任意形状的簇，在聚类过程中自动确定类别数。对于一个欧式空间内的点集，无参密度估计方法根据一个点周围一个小区域内点的分布情况来估计点集中该点位置的密度；类似的，均值飘移聚类对空间中某一位置密度梯度的估计采用统计该位置周围小区域内的点的分布状况。空间中任意位置梯度的方向即是密度增加最快的方向。均值飘移聚类根据梯度将空间中的点沿梯度方向不断移动，直到梯度为零。最终散布在整个空间的点移动到模式点的地方。每个这样的点是所有移动到它的点所覆盖的区域内密度最大的点，该处的梯度为零。Mean-shift的定义为：给定的d维欧式空间dR，对于点数据集12{}iSxin==…，，，，，带有核函数()Kx和核窗口范围h的多元核密度估计函数为：()∑=−=niidhxxKnhxf11(式8-5)其中h称为带宽(Bandwidth)，它表明在多大的x邻域内估计x点处的密度；()Kx被称为密度核函数：()()2,xkcxKdk=(式8-6)其中ck，J为规一化常量，以确保()Kx积分为h对式(式8-5)进行微分可以得到x处的梯度，从而得到Mean-Shift迭代向量。()xhxxghhxxghxxMniidniidiv−−−=∑∑=+=+1221221(式8-7)其中()()gxKx=−。上式的意义是，如果要将x向带宽h范围内密度最大的地方移动，则沿()Mx方向移动是最快的。这样不断迭代的过程会最终收敛，即()Mx最终为0。我们把差值()Mvx称为Mean-shift，而点到该采样平均值点的重复移动的过程称为Mean-shift算法。7图8.5深度图像的均值飘移聚类(4)神经网络方法自组织特征映射SOFM（SelfOrganizeFeatureMap）神经网络是芬兰Helsink大学的T.Kohonen教授1980年提出的。T.Kohonen认为一个神经网络在接受外界输入时，将会分为不同区域，每个区域对输入模式具有不同的响应特征。神经网络中邻近的各个神经元通过侧向交互作用彼此相互竞争，自适应地发展成检测不同信号的特殊检测器，这就是自组织特征映射的含义。自组织特征映射算法是一种非监督聚类方法，它能将任意输入模式在输出层映射成一维或二维离散图形，并保持其拓扑结构不变,通过对输入模式的自组织学习，在竞争层将分类结果表示出来。自组织特征映射模型可以用二维阵列表示如下图8.6图8.6自组织特征映射二维阵列神经网络由输入层和竞争层组成。输入层是一维的神经元，竞争层是二维的神经元，输入层的神经元和二维阵列竞争层的神经元每个都相互连8接，二维阵列竞争层也就是输出层。Kohonen网络就是利用其自组织特点，将N个输入向量组成的一维序列映射到二维的神经元阵上，通过自我调整从而进行信息的聚类。这种自组织的聚类过程是系统自主且无导师指导的条件下完成的。Kohonen网络的学习过程分为两步：竞争学习过程和输出层神经元的侧交互过程。对于每一个输入向量，通过输入向量值与权系数之间的比较，在神经元之间产生竞争，权系数向量与输入向量最相近的神经元被认为对输入向量反映最强，认为是获胜的神经元，并称此神经元为输入向量的象。显然，相同的输入向量在输出层产生相同的象。对于每个输入向量，都会导致与之相邻近的神经元按如下规则产生侧反馈：一方面，以获胜的神经元为圆心，对近邻的神经元表现为兴奋性侧反馈；另一方面，以获胜的神经元为圆心，对远邻的神经元表现为抑制性侧反馈。侧反馈的结果是，在每个获胜神经元附近形成一个聚类区。学习的结果使聚类区内各神经元的权系数向量保持向输入向量逼近的趋势，从而使具有相近特性的输入向量聚集在一起，这一过程是自组织的。Kohonen网络正是利用输出层神经元的侧反馈过程而实现聚类。对于输出神经元j，其外部输入信号可以用jI来表示：iiijjXWI∑=(式8-8)其中，ijW是输入神经元i到输出神经元j之间的权系数，iX是外部输入信号。在神经网络中，随外部环境的输入，神经元的权系数是自适应变化的；这一过程就是神经网络自学习的过程。其神经元自适应过程，一般用如下方程表示：()()()∉=∈−=tNjdtdWtNjWXdtdWcijcjij0α(式8-9)其中，jW是权系数向量，()Tnjjjj=，α是一常量，X是输入向量，()TnxxxX,,,21=，cN是以c为中心的某一邻域。在神经网络的SOFM模型中，每一个权系数向量都可以