局部形状特征概率混合的半自动三维点云分类

2017-02-07李红军刘欣莹张晓鹏严冬明

浙江大学学报（理学版） 2017年1期

关键词：柱面曲率形状

李红军，刘欣莹，张晓鹏，严冬明

(1.北京林业大学理学院，北京 100083； 2.中国科学院自动化研究所模式识别国家重点实验室，北京 100190)

局部形状特征概率混合的半自动三维点云分类

李红军1，刘欣莹2，张晓鹏2，严冬明2

(1.北京林业大学理学院，北京 100083； 2.中国科学院自动化研究所模式识别国家重点实验室，北京 100190)

三维激光扫描获取的点云数据可用于数字城市建设、三维模型获取、场景分析与物体测量等领域.但因遮挡和噪声的影响，加之扫描场景复杂，采样精度受限，使得不能直接运用经典的曲面和三维空间理论对点云数据进行有效分析和处理.分类是点云数据预处理的重要方式之一.提取近邻四面体体积、近邻法向量差异度、主方向差异度和主曲率值4个局部形状特征，采用概率混合策略构建了一种点云数据的半自动分类方法，可实现平面点集、柱面点集和其他点集的有效区分.其中，概率混合策略是依据近邻点平均距离和单指标类别一致程度估计每个特征推断形状的概率，通过混合加权，依据概率赋权函数最大值准则进行局部形状推断.可实现用户交互，以便处理不同扫描尺度和精度的点云数据.采用本文方法对模拟生成的点云、单棵树木点云、街道场景点云、旷野自然场景扫描点云以及航空机载扫描点云等多组数据进行了实验，结果表明，基于局部形状特征的概率混合方法对各种点云数据均具有良好的分类效果.

点云分类；局部形状推断；概率混合；法向量差异；主曲率；大规模场景分析

A semi-automatic 3D point cloud classification method based on the probability mixture of local shape features. Journal of Zhejiang University(Science Edition), 2017,44(1):001-009

三维激光扫描仪和雷达等硬件设备及其操控软件的快速发展，使得三维点云数据的获取变得方便而快捷.只需几分钟便可完成一个场景的稠密采样,而稀疏采样可通过车载或者机载设备从移动设备上快速获取.数据获取的成本不断降低,目前小型三维扫描仪的报价仅为几万元.设备日趋智能,经过简单培训即可学会数据采集与预处理.三维点云数据的快速积累及其蕴含的准确三维采样信息,使得相关理论和应用研究日益广泛和深入.在林业研究中,可用于无损测量和森林调研;在计算机图形学[1]中,可用于三维场景模型的重建;在数字娱乐中,可用于虚拟场景构建;在建筑领域,则可用于数字文物保护和建筑测量等.此外,在数字城市建设和地理信息系统中也有应用.

点云数据有2个基本特点.一是准确的三维位置信息,主要包括采样点的x,y,z三维空间相对坐标,有些数据还包括点的颜色信息和反射强度,但是没有关联关系信息;二是数据量大,一个场景包含几千万的离散采样点，而多站点组合的扫描数据则构成大数据的规模.研究的挑战来自于点集数据量的庞大、没有拓扑结构和形状信息以及由于遮挡造成数据的残缺,此外还有噪声的干扰.这些问题对采样点集的形状结构分析和进一步的场景理解造成了困难.

点云数据分类是语义标注和场景分析处理的基础.从分类目的看,大致分为以语义标注为目的[2-4]和以形状结构分析为目的2类.前者是场景理解的主要目标,后者依据点云形状进行分类,侧重于线和线段、平面、柱面、球面、锥面等形状基元的识别,是实现前者的一个重要途径,亦是本文的侧重点.

形状提取的2种经典方法:霍夫变换(Hough transform)[5]和随机抽样一致算法(RANdom SAmple Consensus,RANSAC)[6],在点云数据形状提取方面已有广泛应用.文献[7]应用RANSAC算法从深度数据中提取了圆柱；CHAPERON等[8]则用RANSAC算法从三维点云数据中提取圆柱.德国波恩大学SCHNABEL等[9]认为,早期的这2种算法及其变式在基本形状识别上有所欠缺,并开展了一系列工作,比如通过改进RANSAC算法，有效解决三维点云数据中的平面、球面、柱面和锥面的分类.但由于许多点云数据的法向量很难准确估计,仅依赖于点云法向量进行形状推断的方法有其局限性.当然,若能准确提取基元,则基于基元空间关系形成的图结构,就能进行有语义信息的形状推断[10-11].

除了这2种经典算法外,其他算法需提取特定几何形状基元,本质上都属于二类分类问题.较为常用的是对局部近邻点集进行平面拟合[12-13],然后根据拟合度判断形状,此类方法较适合平面片的提取.采用模板匹配技术,也有助于快速获得近似的重建结果[14].采用离散微分几何量进行点云分类,主要是利用近邻法向量方向差异度进行平面提取[15-16],此法适用于地面或者墙面的识别.利用近邻点的主方向差异度进行圆柱面提取,可应用于树干识别和树木扫描点云枝叶分类[17].

除平面、柱面、球面、锥面外,线或者线段也是常用基元.根据激光扫描原理,通过分析扫描线提取线段并逐步形成多边形,有利于建筑等对象的快速分割[18].提取的线段再结合其他信息对于点云分析和处理也有显著作用,比如2015年普林斯顿大学关于点云对齐的工作[19]、法国DEMANTKE等[20]的关于点云维度分析的工作，他们依据局部几何特征,主要是近邻点之间的空间位置关系,采用主成分分析法将点云分为3类:线(1D)、平面(2D)和体(3D).

从上述已经公开的方法可知,近几年利用法向量、主方向、平面拟合等方法提取特定形状基元,实现2种分类的比较多,且都取得了一定效果.可见这些几何量在局部形状推断上是起作用的.

受以上研究的启发,笔者认为这些几何量对形状推断是一个综合的效果,因此利用法向量和主方向的差异度,并结合局部点云主曲率的基本性质,提出了多个局部形状特征概率混合的半自动点云分类方法,实现平面、柱面和其他点的3种分类.另外,注意到在同一设备同一次扫描中,可能由于遮挡,有些地方的点比较稀疏,受空中粒子的阻挡,引起水面或者玻璃等的采样误差,因此,笔者认为同一场景中,点云的疏密蕴含着形状推断的可靠性大小.将这种疏密用概率进行描述,再用加性混合策略实现基于多特征的3种分类.实践中,大规模的点云数据有可能超过计算机的内存限制,因此本文从局部特征分析入手,通过对局部的研究进行全局推断,为大数据的并行算法设计和核外算法设计提供参考.

1 局部形状特征及其概率混合方法

1.1 局部形状特征计算

不同于机器学习方法，局部形状特征计算基于三维空间位置、回波强度、颜色等特征[21]进行点云分类,首先研究有利于区分平面(plane)、柱面(cylinder)、球面(sphere)和空间体(volumetric)等形状的4个特征:近邻四面体体积、法向量差异度、主方向差异度和主曲率阈值.

1.1.1 近邻四面体体积

(1)

式(1)具有较明显的几何形状度量含义.从直观理解,若四面体的4个顶点来自同一平面点集,则v=0;若来自于柱面、球面,则v值略大于0;若来自于立方体内,则v值比较大.

1.1.2 k-近邻点的法向量差异度

(2)其中,nP表示点P处的单位法向量,nQi表示P的近邻点Qi处的单位法向量.显然,对于平面上的点集,各点处的法向量垂直于平面,且都共线,|nP·nQi|=1,即ηP=0.而柱面的法向量则共面.

1.1.3 k-近邻点的主方向差异度

(3)

其中,mP表示点P处的单位最小主曲率方向,mQi表示P的近邻点Qi处的单位最小主曲率方向.显然,理想情况下，柱面上点集各点处的最小主曲率方向都共线,离散数据测试表明,mP值最接近0.而来自于立方体内各点的主曲率方向比较杂乱,其差异度也比较大.需要注意的是，由于球面点集和平面点集中任意一点各方向的法向曲率值相等,因此其最大主曲率和最小主曲率值相等,导致最大和最小主曲率方向不能唯一确定,若随机指定一个方向,则会造成第二主曲率方向的差异度较大.由于主方向的不确定性,利用主方向进行球面或者平面的推断变得很不方便.

1.1.4 主曲率阈值

加入主曲率值特征是本算法框架区别于其他算法的特征之一.经典微分几何表明,曲面上点的主曲率(设为κ1与κ2)组合有如下性质[22]:

•柱面上每个点都是抛物点(parabolic point),其最小主曲率为0，另一个主曲率值与柱面横截面大小相关;

•平面上每个点都是平面脐点(umbilic point),其κ1和κ2都为0;

•球面上的点,κ1与κ2同号,是椭圆点(elliptical point);又因κ1=κ2,所以又是脐点;

根据上述主曲率性质,可以设计基于2个主曲率阈值的点云局部形状判定算法：

算法X 基于主曲率阈值的离散点形状类型推断算法.

输入：点P的主曲率κ1与κ2，且|κ2|≤|κ1|， ε.

输出：P点所处的局部形状类型.

该算法基于局部主曲率组合规则,将采样点全部进行了分类,具有类型完备性.但是,由于受近似计算或者噪声影响,接近阈值时或许容易误判,因此,算法中若增加一类无法判定的类型也有其工程应用价值．算法中没有直接采用解析曲面类型中的双曲点,而是把此类型的点归结到空间体内,以便于识别树冠层内的点云．

1.2 概率混合分类算法设计

考虑到主曲率阈值法能把点云分为4类,加上接近阈值的情况对类别不作判断,因此,所设计的算法把点云暂时分为平面、柱面、球面、空间体和类型不确定5类.将用单独一种特征对点云分类的结果称为初始分类,因此,4种特征对应4种初始分类.

1.2.1 浇灌液制备准确称取A物质0.005 g溶于100 mL蒸馏水中作为母液，将母液平均分为4份，第1份不加蒸馏水，标为浓度0.050 g/L的浇灌液，第2份加蒸馏水25 mL，标为浓度0.025 g/L的浇灌液，第3份加蒸馏水50 mL，为浓度0.010 g/L的浇灌液，第4份加蒸馏水125 mL，为浓度0.005 g/L的浇灌液。用同样的方法制备B、C、D不同浓度的浇灌液。

接下来的重点是将这4个特征综合到一个指标中,这种综合方法称为概率混合法.概率的引入基于以下假设:受遮挡和噪声的影响,局部近邻关系估计的体积、法向量、主方向和主曲率都可能存在误差.这些误差与采样密度相关.另一方面,在k个近邻点中,类别标号越一致,其类别的可信度就越高.反之，类别标号越杂乱,则类别的可信度就越低.于是,定义任意一点P属于类别j的概率为

(4)

其中,pα,j,j=1,2,…,5表示用α特征分类时,点分别属于平面、柱面、球面、空间体和不确定类的概率.其中，α∈{ν,η,m,κ}.示性函数

(5)

其中,l(Qi)表示点Qi的初始类别标号.缩放因子Ω为扫描点云最近邻4个点平均距离的2k倍.该缩放因子的设定使得概率计算免受场景大小和扫描分辨率对参数设定的影响.

由式(4)可以计算每一个点对应于分类方法的概率向量,记为

pα=(pα,1,pα,2,pα,3,pα,4,pα,5).

(6)

设混合策略以权向量w表示为

w=(wν,wη,wm,wκ)，

(7)

其中每个分量分别为4种特征分类权系数.则由概率向量式(6)和策略权向量式(7)通过加性组合形成概率混合函数,使得这个函数取得最大值的类别标号就是该点的最终类别.则本文的概率混合决策式为

(8)

由式(8)进行决策,确定该点最可能的类别.需要说明的是,混合权向量体现用户对选取的分类特征的偏好.若混合权向量的某分量为0,则该分类结果不进入混合计算;若各个分类结果相同,则混合后的分类结果也不变;若各个分类结果不同,则由概率较大且权系数较大的混合结果决定最终的分类标号.本文算法的半自动方法主要指权向量的设定.

作为一个完整的点云分类算法,本文的概率混合点云分类算法流程如图1所示.算法中的kd树构建和近邻查询参见文献[23],法向量、主曲率和主方向的计算参考文献[24].由于kd树的构建是O(n)级,近邻点查询为O(log(n))级,而法向量、主曲率计算都是O(nlog(n))级,概率融合为O(n)级,所以算法为线性对数级,即O(nlog(n)).算法中主要是近邻点的个数k、共面性和零阈值参数ε的选取.其中参数k的精细选取可以参考文献[25],由于空间体的确定，k至少大于6,通常在9～25间选1个数,比如k=20.而ε的选取与数据有关,需通过实验调试确定.

图1 算法流程图Fig.1 The algorithm flowchart

2 点云分类实验

为了验证本文提出的4个局部形状特征概率混合进行点云分类算法的可行性,用模拟数据和多个公开数据进行实验,并与相关工作比较.除了主曲率方法能区分球面和空间体点云外,其他3个特征对这些形状的区分效果不明显,因此,实验中重点进行平面、柱面和其他点云等的3种分类.

2.1 模拟数据分类实验

首先，用一个解析曲面随机采样的离散点集进行实验.该点集从平面、柱面、球面和正方体中简单随机采样(见图2(a)).每种形状采样3 000个点,共12 000个点.

图2 4种基本形状合成点云分类Fig.2 Point cloud synthesized with 4 kinds of shapes

采用本文算法,得到的分类情况如图2(b)所示.图中黄色为平面点,蓝色为柱面点,绿色为其他点.从分类结果可以看出,在叠合区域,对点的形状判断较为困难.但通过准确的点的类型信息,并与分类结果相比较,可以得到混淆矩阵及其对应的百分率,结果见表1.三类的平均准确率为90.96%.

表1 分类点数以及对应百分比的混淆矩阵

事实上,4种形状特征可以组合成15种分类方式,各种混合方式的准确率如图3所示,其中v,n,d,k分别表示基于体积、法向量、主方向和主曲率的分类.从图3可以看出,依据法向量一致性分类的准确率约为70%,这与文献[9]的结论一致;而主曲率参与的分类效果最好,最好的是4种特征(kndv)的概率混合结果.

图3 不同混合算法分类结果的准确率Fig.3 Accurate rates of different mix methods

2.2 单棵树木点云分类

对于实际扫描点云,首先以树干检测为例,测试本文算法与主方向一致性判断方法[17]在柱面识别上的效果.

图4 松树点云枝叶分类比较Fig.4 A pine point cloud classified into leaves and branches points using two different methods

一般而言,对于单棵树木点云,其枝干点云局部呈圆柱形[26];而树冠点云则呈立方体或者球形;少有平面点集.实验数据(见图4(a))采集于北京大学校园,包含116 940个采样点,树高约8.24 m,点云的枝叶以及地面的分类效果如图4(b)所示.对比树干提取结果(图4(d),16 452个点)与基于主方向投票技术的树木枝叶分割结果(图4(c),14 076个点)[17],本文算法提取枝干点多出2 376个,其结果更有利于树干的准确测量和重建.

2.3 城市街道场景点云分类

在数字城市建设过程中,城市街道的扫描是一项主要工作.街道场景中的对象一般包括道路、建筑、行道树、车、人和广场等.由于道路和广场都近似为平面形状,而建筑往往由平面近似组合而成,以往的文献侧重于提取这类建筑面.本文方法则还能进一步获得柱面形状对象.

一个来源于美国卡内基梅隆大学(Carnegie Mellon University, CMU)的三维点云数据库[27]的城市街道场景数据(见图5(a))包含196 811个点.用本文方法,点云数据分为3类:平面，包括地面和部分建筑面(黄色)；柱面，主要是建筑柱子、棱角和树干(蓝色)；其他点，即城市植被等(绿色),如图5(c)所示.2015年德国Karlsruhe Institute of Technology(KIT)提出通过优化最近邻数实现点云最优聚类方法[27],其分类效果如图5(b)所示.

表2 街道场景点云分类的混淆矩阵

对比2个结果可以看出,本文方法能区分建筑物的平面墙和柱面墙(见图5(d));更多地保留了一些细节,比如左侧建筑前面的小汽车和摩托车，可看到右侧建筑物门口更多的台阶等.表2为本文的概率混合方法的混淆矩阵与文献[27]的对比,本文方法的平均准确率为82.13%.

数据来源：http://www.cs.cmu.edu/～vmr/datasets/oakland-3d/cvpr09/doc/

图5 城市街道场景点云分类Fig.5 Street point cloud classification

2.4 旷野自然场景点云分类

对复杂自然场景进行点云分类有助于环境监测和地理信息分析.以法国Brodu N主页的自然场景及数据(图6(a))为例.该场景包含1 908 271个点,局部空白处是由遮挡造成的点云缺失.图6(b)是本文方法的分类结果,沙地和植被大致可区分.图6(c)是图6(b)左下区域的局部放大图,对比Canupo软件的计算结果[28](见图6(d))可以看出，本文4个特征概率混合方法能将沙漠地形较好地分离,且地上的绿植明显比Canupo软件多.考虑是远距离大场景的扫描,故对点的位置敏感性要求有所降低,仅测试了用法向量差异度进行的分割,即其余的特征权重皆为零,所得结果如图6(d)所示,则点云分类效果与该软件分类结果相当,分类结果的混淆矩阵如表3所示,准确率为94.86%.

据文献[3],本文算法具有阶层式分类的特征.可满足用户的多阶层分类需求.

表3 Canupo数据分类的混淆矩阵

数据来源：http://nicolas.brodu.net/en/recherche/canupo/

图6 旷野自然场景点云分类Fig.6 A nature scene point cloud classification

2.5 机载扫描点云数据分类

上面几组数据都由地面扫描仪采集.本节将测试由空中机载扫描仪获得的数据,并进行分类准确率的量化分析.数据来源于莫斯科国立罗蒙诺索夫大学的图形与媒体实验室(Graphics and Media Lab, GML),他们曾用朴素贝叶斯方法[29]和非联合马尔科夫网方法[30]进行了点云分类.数据包含1 002 668个点,并附有一个点云分类准确结果,如图7(a)所示.原始数据分7类,本文将地面单独作为一类(黄色),建筑和汽车等归为第2类(蓝色),其余为第3类(绿色).这3类点的数量分别为439 989,22 880和539 799.这样便于与本文分类结果相比较,也便于计算混淆矩阵,见表4.

数据来源：http://graphics.cs.msu.ru/en/node/922

图7 空中扫描场景点云分类Fig.7 An airborne LIDAR scan point cloud classification

形状平面柱面其他平面/%柱面/%其他/%地面2822444545911228664．20．325．5建筑117614670644951．420．428．2其他506505614885889．40．190．5

表4中,由于原数据标签是地面和建筑,而本文的分类是平面与柱面,比较图7(c)与(d)可知,屋顶平面点不在建筑类而大量地被分到平面点集中.通过增大与地面的距离或许能识别屋顶,但这不是本文的当前目标,而是基于物体提取的目标.即便如此,参考GML的类型标示，本文方法的平均准确率也达到了77.34%.

从上述实验可以看出,本文算法能够达到现有优化方法的点云分类效果.在保证效果的前提下,本文算法的优势主要有:(1)对点云类别结果给出了类别判定的概率;(2)方法直观、逻辑明确、容易实现;(3)用户半自动设定特征融合方式,便于适应不同点云采样分辨率和满足用户的阶层式分类需求.上述数据的实验耗时如表5所示,主要耗时通过主曲率计算.

表5 实验时间

3 结论与讨论

针对以形状结构分析为目的的点云分类,提出了一种将近邻四面体体积、近邻法向量方向差异度、主方向差异度和主曲率阈值4种局部形状特征概率进行混合的半自动分类方法.该方法将点云数据分为平面点、柱面点和其他点3个基本类，为赋权加性混合方式，其概率基于点的分散程度和近邻点类型的一致程度定义.工程应用中,用户可根据经验和实验情况调整混合方式和权重.实验数据包含模拟以及4个不同来源的扫描数据,即自己采集的松树扫描点云和来自美国、法国、俄罗斯的数据.实验结果表明,本文方法能较好地进行点云分类,准确率达77%以上.

一般而言,语义层面的点云分类主要有2条途径:计算统计特征或采用机器学习方法判断语义层面的点云分类；先从点云中获取基本形状,再根据基本形状的位置关系进行语义层面的点云分类.本文采用的是后一种分类方法,其分类结果可作为面向语义形状标注的预处理工作之一.

点云分类的准确性尚有很大的提升空间,涉及的工作包括噪声识别与处理、缺失数据补全、分类准确性评估和有标注的点云对象库的构建等.基于本文工作,还可就以下问题展开研究：提取更加丰富的形状基元,研究各个基元之间的空间结构关系;参考网格曲面的形状分析[31],研究一般二次曲面级别的点云分类问题;结合有效的地面识别方法[32],完成建筑侧立面和屋顶面的提取;将这些结果应用于基于点云的形状查询、三维重建以及室内外点云场景理解等.

[1] 伍龙华,黄惠.点云驱动的计算机图形学综述[J].计算机辅助设计与图形学学报,2015,27(8):1341-1353. WU L H, HUANG H. Survey on points-driven computer graphics[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(8): 1341-1353.

[2] 李慧盈,李文辉,陈圣波.一种机载雷达点云数据的快速分类方法[J].吉林大学学报:地球科学版，2010(5):1205-1210. LI H Y, LI W H, CHEN S B. A method for classify point clouds of airborne laser scanning[J]. Journal of Jilin University: Earth Science Edition, 2010(5): 1205-1210.

[3] 李文宁,张爱武,王书民,等.地面激光点云阶层式分类方法[J].计算机辅助设计与图形学学报,2015,27(8):1555-1561. LI W N, ZHANG A W, WANG S M, et al. Hierarchical classification method for terrestrial laser point clouds[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(8): 1555-1561.

[4] 吴永华,胡以华,顾有林,等.激光点云分类算法的探讨与展望[J].红外与激光工程,2010,39(增刊):147-151.WU Y H, HU Y H, GU Y L, et al. Discussion and prospect for classification algorithm of laser point cloud[J]. Infrared and Laser Engineering,2010,39(supp):147-151.

[5] HOUGH P. Method and means for recognizing complex patterns: 3069654[P].1962-12-18.

[6] FISCHLER M A, BOLLES R C. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM,1981,24(6):381-395.

[7] BOLLES R C, FISCHLER M A.A ransack-based approach to model fitting and its application to finding cylinders in range data[C]// Proceedings of the 7th International Joint Conference on Artificial Intelligence, San Francisco: Morgan Kaufmann Publishers Inc,1981:637-643.

[8] CHAPERON T, GOULETTE F.Extracting cylinders in full 3-d data using a random sampling method and the gaussian image[C]// VMV01.Stuttgart: Aka Gmbh，2001:35-42.

[9] SCHNABEL R, WAHL R, KLEIN R. Shape detection in point clouds[J]. Computer Graphics Technical Reports,2006,CG-2006/2.

[10] SCHNABEL R, WESSEL R, WAHL R, et al. Shape recognition in 3d point-clouds[C]//The 16th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision. Plzen： UNION Agency-Science Press，2008, 8.

[11] NIEUWENHUISEN M, STÜCKLER J, BERNER A, et al. Shape-primitive based object recognition and grasping[C]//Proceedings of 7th German Conference on Robotics. Munich：VDE, 2012: 1-5.

[12] LARI Z, HABIB A, KWAK E. An adaptive approach for segmentation of 3D laser point cloud[J]. ISPRS Workshop Laser Scanning, Remote Sensing and Spatial Information Sciences，2011,XXXVIII-5/W12:103-108.

[13] NING X, ZHANG X, WANG Y, et al. Segmentation of architecture shape information from 3D point cloud[C]// Proceedings of the 8th International Conference on Virtual Reality Continuum and Its Applications in Industry. New York: ACM, 2009: 127-132.

[14] NAN L, XIE K, SHARF A. A search-classify approach for cluttered indoor scene understanding[J]. ACM Transactions on Graphics (TOG), 2012, 31(6): 137.

[15] RABBANI T, VAN DEN HEUVEL F, VOSSELMANN G. Segmentation of point clouds using smoothness constraint[J]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2006, 36(5): 248-253.

[16] LI H, ZHANG X, JAEGER M, et al. Segmentation of forest terrain laser scan data[C]// Proceedings of the 9th ACM SIGGRAPH Conference on Virtual-Reality Continuum and its Applications in Industry. New York: ACM, 2010: 47-54.

[17] DAI M, LI H, ZHANG X. Tree modeling through range image segmentation and 3d shape analysis [C]//Advances in Neural Network Research and Applications. Springer /Berlin/ Heidelberg: Springer, 2010: 413-422.

[18] HEBEL M, STILLA U. Pre-classification of points and segmentation of urban objects by scan line analysis of airborne LIDAR data[J]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2008, 37(B3a): 105-110.

[19] YU F, XIAO J, FUNKHOUSER T. Semantic alignment of LIDAR data at city scale[C]//Computer Vision and Pattern Recognition (CVPR). Los Alamitos: IEEE Computer Society,2015:1722-1731.

[20] DEMANTKE J, MALLET C, DAVID N, et al. Dimensionality based scale selection in 3D lidar point clouds[J]. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2011, 38(Part 5): W12.

[21] 李海亭,肖建华,李艳红,等.机器学习在车载激光点云分类中的应用研究[J].华中师范大学学报:自然科学版,2015,49(3):460-464. LI H T, XIAO J H, LI Y H, et al. Application of machine learning in the vehicle-borne laser point cloud extraction[J].Journal of Central China Normal University: Natural Sciences, 2015, 49(3): 460-464.

[22] TOPONOGOV V A. Differential Geometry of Curves and Surfaces: A Concise Guide[M]. Boston：Springer Science & Business Media,2006.

[23] MOUNT D M. ANN Programming Manual[EB/OL].[2009-12-14]. http link: http://www. cs. umd. edu/～ mount/ANN/Files/1.1,2006,1.

[24] CHENG Z L, ZHANG X P. Estimating differential quantities from point cloud based on a linear fitting of normal vectors[J]. Science in China(Ser F): Information Sciences,2009,52(3):431-444.

[25] WEINMANN M, JUTZI B, HINZ S, et al. Semantic point cloud interpretation based on optimal neighborhoods, relevant features and efficient classifiers[J]. ISPRS Journal of Photogrammetry and Remote Sensing,2015,105:286-304.

[26] YAN D M, WINTZ J, MOURRAIN B, et al. Efficient and robust reconstruction of botanical branching structure from laser scanned points[C]// CAD/Graphics, Los Alamitos: IEEE Computer Society,2009:572-575.

[27] MUNOZ D, BAGNELL J A, VANDAPEL N, et al. Contextual classification with functional max-margin markov networks[C]// Computer Vision and Pattern Recognition(CVPR2009).Los Alamitos: IEEE Computer Society,2009:975-982.

[28] AIJAZI A K, CHECCHIN P, TRASSOUDAINE L. Segmentation based classification of 3D urban point clouds: A super-voxel based approach with evaluation[J]. Remote Sensing,2013,5(4):1624-1650.

[29] BRODU N, LAGUE D. 3D terrestrial lidar data classification of complex natural scenes using a multi-scale dimensionality criterion: Applications in geomorphology[J]. ISPRS Journal of Photogrammetry and Remote Sensing,2012,68:121-134.

[30] SHAPOVALOV R, VELIZHEV A, BARINOVA O. Non-associative markov networks for point cloud classification[C]// Photogrammetric Computer Vision and Image Analysis. Paris:出版社，2010.

[31] SHAPOVALOV R, VELIZHEV A. Cutting-plane training of non-associative markov network for 3D point cloud segmentation[C]// 3D Imaging, Modeling, Processing, Visualization and Transmission (3DIMPVT). Paris: ISPRS,2011:1-8.

[32] YAN D M, LIU Y, WANG W. Quadric surface extraction by variational shape approximation[M]//Geometric Modeling and Processing-GMP 2006. Berlin: Springer,2006:73-86.

LI Hongjun1, LIU Xinying2, ZHANG Xiaopeng2, YAN Dongming2

(1.CollegeofScience,BeijingForestryUniversity,Beijing100083,China; 2.NLPR-LIAMA,InstituteofAutomation,CAS,Beijing100190,China)

Point clouds captured by three dimensional scanner have been used in many fields, including modeling of digital cities, acquisition of three dimensional shapes, scene analysis and object measuring. However, due to the limitation of the sampling process and the complexity of scanned scenes, most traditional methods of surface modeling and three dimensional space analysis cannot work effectively when dealing with the point cloud data. Classification is therefore an important way for point cloud preprocess. Four features, namely the volume of a tetrahedron constructed by 4 neighboring points, the deviation of normal directions of neighboring points, the deviation of principal directions of neighboring points, and the values of principal curvature, are mixed with probabilities for semi-automatic classification of the three dimensional point cloud data. With the new method, a point cloud is to be divided into three classes: plane points, cylinder points and other points. The initial classification result is labeled according to its single shape feature value. The probability mixture is completed by estimating the probability of inferring a shape from a local point set with respect to each feature, generating a mixture with weighted sum, and maximizing the mixture probability function, while the probability is estimated with the average distance between a point and its neighbor points together with the consistency ratio of initial labels of the point to its neighbors. User interactions are invoked to make the choice of classification thresholds and the setting of weights, which is helpful when dealing with point cloud with different space scale and scanning point resolution. Experiments show that the proposed method works well for various kinds of point cloud data sets, including point clouds generated by simulation, and those corresponding to a single pine tree, a street scene, a country scene, and an airborne big scene.

point cloud classification; local shape inference; probability mixture; normal difference; principal curvature; large scale scene analysis