基于马尔科夫随机场的散乱点云全局特征提取

张靖　　周明全，2　　张雨禾　　耿国华

基于马尔科夫随机场的散乱点云全局特征提取

张靖1周明全1，2张雨禾1耿国华1

为了精确提取点云数据中的特征信息，针对激光扫描获取的三维散乱点云数据，提出一种基于马尔科夫随机场（Markov random field，MRF）的散乱点云特征提取方法.首先，根据散乱点的曲率估计及阈值初始化点标号并判定稳定点，将稳定点标记存储在数组中；然后，将优化不稳定点的标号问题转化为随机场标号的能量函数问题，引用贝叶斯估计求后验概率分布函数及MAP-MRF（Maximum a posteriori-Markov random field）框架归约得到目标函数；最后，根据图割法α-expansion算法，利用标号调整过程中标号集相对能量变化得到不稳定点的最优标号集，将其与存储稳定点的数组综合，根据点标号提取特征点.实验结果表明，该方法简单、高效、无需人工调参，能够依据全局能量的变化自适应提取特征，特征提取结果令人满意.

散乱点云，特征提取，马尔科夫随机场，标号

引用格式张靖，周明全，张雨禾，耿国华.基于马尔科夫随机场的散乱点云全局特征提取.自动化学报，2016，42（7）: 1090-1099

随着三维扫描技术的快速发展，通过激光扫描技术获得点云模型成为近几年几何模型的通用表示形式.一个物体的表达是通过精确描述该物体尖锐特征实现的，特征是反应模型几何外观的最小基元，也是模型外观准确表达的关键因素，因此，特征提取技术也成为数字几何处理中备受关注的热点话题，是后续模型分析、数据配准、曲面重建的底层技术之一.如何有效地提取点云模型的特征点成为点云数据处理的关键问题.

目前，已有诸多学者展开了针对三维模型特征提取的研究，而大部分方法是针对网格曲面等含有较多拓扑信息的模型进行处理.由于点云模型缺少顶点间的拓扑邻接关系，且不包含任何曲面和体积的信息，难以计算其物理性质和几何性质，因此，针对点云数据的处理方法较少，大致可以分为三类：基于局部拟合或聚类的方法、基于多尺度的思想以及基于特征检测算子的方法.

1）基于局部拟合或聚类的方法进行特征提取：Daniels等［1］提出了一种基于鲁棒移动最小二乘的特征线提取方法，利用鲁棒移动最小二乘拟合曲面并计算一点到拟合曲面对应点的残差，设置阈值提取潜在特征点，将潜在特征点投影在最近曲面交线上，利用协方差分析对投影点进行平滑处理.该方法在噪声幅度较大或者稀疏采样时算法性能较差. Demarsin等［2］提出了一种三维点云数据封闭特征线提取方法，首先，使用主成分分析计算点法向；然后，基于局部邻域的法向变化将点聚类，形成不同的簇.在进行特征点的判断时，是通过两点的法向夹角同可接受最大角度阈值进行比较，而此时的特征点是以一个聚类为单位进行判断.庞旭芳等［3］提出了一种点云模型谷脊特征的提取与增强算法，采用多步逼近策略提取特征点.通过局部最小二乘拟合曲面多项式计算主曲率，选取绝对值较大的主曲率同阈值比较，识别潜在谷脊特征点［4］，再将特征点投影到离其最近的潜在特征线上，得到增强的特征点并对其平滑处理.该算法需要用最小二乘进行曲面多项式的拟合，计算方法复杂；潜在特征点的提取不仅计算拟合曲面多项式的微分性质，而且要调整法向，时间耗费大；且传播阈值的设置需要根据经验人工设置，不能自适应调整.

2）基于多尺度的思想进行特征提取：Pauly等［5］提出了一种多尺度点云特征点提取方法，它是将局部邻域的大小作为离散尺度参数的协方差分析，计算一点在不同尺度下成为特征点的可能性，从而提取特征点.该方法对噪声敏感，即不具有鲁棒性［6［8］提出了一种在多尺度的思想下基于曲率的方法提取特征，在多尺度的思想上采用一个刚体运动不变量曲度提取特征点，并用置信值评估特征点的稳定性.该方法根据多尺度空间曲面点的局部拟合计算曲度（点的最大最小主曲率的算术平方根），实现特征点的提取.判断特征点的原则：曲面上一点不仅在当前尺度下曲度是局部极值，而且在该尺度相邻的两个尺度上曲度依然是局部极值.该算法要在不同的尺度下进行局部拟合并计算点的曲度，尺度愈多，提取的特征点准确率越高，但时间耗费越大.而部分显著特征只能在高尺度下提取出来，因此该算法是以时间为代价提高算法准确率.

3）基于特征检测算子的方法：Gumhold等［9］通过构造黎曼树表示点云的连接信息，基于局部邻域协方差矩阵的特征值计算判断一点是特征点的可能性.Jia等［10］和Tang等［11］提出一种基于张量投票的鲁棒的曲面、几何特征线及角点提取算法，该算法需要对空间进行规格网格划分，并且对每一个网格节点用张量投票的方法累加周围节点对该节点的影响，由此判断该点是否为特征点.吾守尔·斯拉木等［12］提出了一种基于平均曲率运动的散乱点云尖锐特征提取算法，它主要是通过采样点和其对应的加权邻域重心的距离标志尖锐特征候选点，然后将该距离投影到采样点的法向方向进行平滑，比较投影距离和阈值，提取尖锐特征点.王丽辉等［13］提出了一种基于曲率和密度的特征点检测算法，通过点到邻居点的平均距离、点的法向与邻居点法向夹角及数据点曲率三部分定义一个特征参数；然后，通过数据点密度与模型到中心点的最大距离相除得到特征阈值；最后，将特征参数与特征阈值进行比较，提取特征点.

基于局部拟合或重建的方法，计算复杂度高且时间耗费较大；而基于多尺度思想的方法，尺度愈大，时间耗费愈多，提取的特征点准确率越高，且部分显著特征只能在高尺度下提取出来，因此，该算法是以时间为代价提高算法准确率的；而基于局部检测算子的方法，大多依赖于全局固定的阈值，这种依赖人工调参的半交互式特征提取方法要求用户对模型有一些先验知识的累积，阈值较大，可能造成冗余特征，而阈值较小，则只能提取出较尖锐的特征，忽略较平滑的特征.

马尔科夫随机场（Markov random field，MRF）方法建立在MRF图像模型和贝叶斯估计的基础上，结合观测图像求解.在国内，传统的马尔科夫随机场模型起初仅用在图像处理领域，其中包括二值图像复原、图像分割及目标单帧检测等.其中最热门的应用是图像分割.近几年，有些学者将马尔科夫随机场模型引用在三维模型处理方面，但局限在三维网格模型的分割以及点云模型的识别方面，例如文献［14-15］.针对点云模型的特征提取技术，还未出现引用MRF的相关文献.

针对上述问题，本文提出一种基于马尔科夫随机场模型［16-17］的全局特征提取方法，直接对点云进行处理.特征提取问题的本质是分类问题，即根据设定的准则，将点云上的点划分为特征点和非特征点两类且将点标号并分类，不需要局部曲面拟合或重建.同时，无需人工调参，能自适应地提取特征点，首先，对散乱点进行曲率估计并设定阈值，将点的曲率估计的绝对值同阈值比较，初始化点标号；再根据点的k近邻中k个点的标号与该点标号是否相同识别稳定点，并将其标记存储在数组中；然后，求解不稳定点的最优标号集.用多个高斯分布拟合不稳定点的属性信息直方图分布，并求高斯分布各自的均值和标准差，当点的观测信息已知时，计算该点取对应标号的联合概率分布.依据马尔科夫—吉布斯随机场等价定理可得马尔科夫随机场状态分布函数.由联合分布和状态分布函数求出目标函数；接着由目标函数计算不稳定点的最优标号集.采用图割法α-expansion算法，通过随机场全局能量变化解目标函数，得到不稳定点的最优标号集；最后，综合不稳定点的最优标号集与存储稳定点的数组，得到散乱点云的最优标号集.根据点集与最优标号集间存在一一对应的关系，提取特征点.

实验结果表明，本文算法计算方法简单、容易理解且速度相对较快，具有自适应性，不需要人工调参.通过计算每一次调整标号对应的随机场全局能量选取标号集，直到全局能量达到稳定，最小能量对应的标号集就是最优标号集，进而提取特征点.

我国是一个古老文明的国家.然而，时间流逝，许多文物保存不当，造成文物的破碎残缺.因此，借助计算机复原破碎文物是顺应科技发展的必然趋势，而特征提取是借助计算机复原破碎文物的初始阶段，是碎片匹配、拼接等后续工作的基础.本文算法广泛应用在非真实感渲染以及线画图的绘制方面，是复原的后续工作的基石.

1　基于马尔科夫随机场的点云特征提取算法

马尔科夫随机场模型描述的是一个时间序列的问题，即一个时间的某一状态只与它前一时间的状态有关，和其他任何状态都没有关系.马尔科夫随机场模型性质符合特征点判定的问题.在特征点检测问题中，它的前一状态指该点邻域内的点.因此，本文将提取特征点的问题建模为贴标签问题，共有两个标签：特征点和非特征点，通过对散乱点贴标签实现点分类并减少计算量：1）若一个点邻域内点的标号均为特征点，将该点标记为特征点；2）若一个点邻域内点的标号均为非特征点，将该点标记为非特征点；3）若一个点的邻域内点的标号既有特征点又有非特征点，构造目标函数—能量函数，计算该点取哪一个标号的概率大，将该点标记为概率大的标号. 图1所示为本文方法的流程图.

1.1初始化散乱点云标号场

曲率的大小可以反映模型表面的凹凸程度，所以曲率是进行特征提取的重要信息.本文通过对数据点的m 个邻居点进行协方差分析［18-19］估算数据点的曲率，初始化数据点标号：对于给定点pi的球邻域邻居点进行协方差分析，根据协方差矩阵的特征值估计曲率（本文认为点的曲率近似等于曲率估计）.设协方差矩阵特征值为且满足，则曲率估计di为

然后对曲率估计求平均值并设定阈值θ，本文选取一个较为宽松的阈值以保留尽可能多的潜在特征点，并在后续的标号优化时精确提取特征点.阈值为

根据阈值初始化点标号，得到初始标号场，曲率绝对值大于阈值的点标记为特征点，其标号置为1；否则，标记为非特征点，标号置为2：

由此得到初始标号场f=｛f1，f2，···，fN｝，其中fi是指第i个点的标号.

为减少计算量，在优化标号前先判定稳定点，若是稳定点将其标记存储在数组内，然后对不稳定点进行能量优化.判定稳定点时，首先计算每一个点的k近邻（该点邻域内距离它最近的k个点），若这k个点的标号和该点的标号相同，该点是稳定点；否则，是不稳定点.

图1　本文方法流程图Fig.1　The flowchart of our method

1.2建立最优标号目标函数建立最优标号目标函数主要分为两步：1）建立马尔科夫随机场的标号场模型时，首先用K个高斯分布拟合三维散乱点云中不稳定点集P的属性信息di的直方图分布，这K个高斯分布是分别对K个标号的点集属性信息进行拟合.用最大期望算法（Expectation-maximization，EM）求这K个高斯分布各自的均值和标准差得到当马尔科夫随机场的状态f给定时，观测随机变量即属性信息为d的联合概率：

其中，N1是不稳定点的数目.最大期望算法EM：

b）由当前的参数估计每个数据与每个类之间的相关性：

d）利用式（6）～（8）给出的参数计算似然函数的对数，判断似然函数取对数之后的函数式是否满足收敛的条件，若是，算法终止；否则，转步骤b）.

2）然后根据Hammersley-Clifford定理求得马尔科夫随机场的状态分布函数：

其中，Z为归一化常数，β为交互系数，用来决定先验信息在马尔科夫随机场中所占的权重，本文中取β=8.0.δi指点i的球邻域，U（f）为能量函数，是子团势能函数Vc（f）的和，即

本文仅考虑双点势团的能量［12］.

定义子团势能函数V（i，j）（f），计算势能函数时，本文相邻顶点是：一个点邻域内距离该点欧氏距离最短的点.因此，子团势函数如下：

其中，CurvDist（i，j）为点 i，j的曲率距离，max（CurvDist）和min（CurvDist）分别为在散乱点云模型中的最大值和最小值，为了避免分母为零的状况及保证V（i，j）（·）的正定性，α取一个很小的正数，本文中取0.00001.曲率距离为

其中，Cmin为三维散乱点云模型的各个顶点的最小离散曲率，本文引用Cohen-Steiner等［20］和Alexa等［21］提出的算法来计算各个顶点的最小离散曲率.

3）根据前面求得的p（d|f）和p（f），定义目标函数.由MAP-MRF（Maximum a posteriori-Markov random field）框架可知，当点云模型中点的相关属性给定时，即观测随机变量的值给定时，散乱点云的马尔科夫随机场模型的最优状态f∗为

使用MAP的实质就是将标记分类的概率误差最小化，即当观测随机变量即点的相关属性给定时，每一个点属于哪一个标号的概率最大，就将该标号赋予这个点，最后这些散乱点的标号组成的集合即为最优标号集.

定义U（f|d）为

其中，U（d|f）为

由贝叶斯定理可知：

然而，由于p（f|d）∝exp（-U（f|d）），故

最大后验概率的问题转化为最小能量的问题.则由式（17）将式（13）改写成：

那么，马尔科夫随机场求最优标号问题实质是由先验概率求最大后验概率的问题.当点的属性信息已知时，每一个点取目前对应的标号的概率越大，对应的随机场的全局能量就越小，即后验概率同能量函数成反比，因此求最优标号集就是求最小能量.因此采用能量最小化原理求解最优标号的问题.

最后得到目标函数：

1.3散乱点云标号场的优化

根据前一部分的目标函数，进一步知道最优标号集为

其中，f∗为目标函数的解，即最优标号集.对于目标函数，本文引用图割法α-expansion算法解优化问题：f∗=minf∈F（E（f）），求得最优状态f∗.最终的最优状态就是三维散乱点云中不稳定点的最优标号集，将其与存储稳定点的数组综合，得出散乱点云的标号集f1∗.

由第1.2节可知，当点的观测信息给定时，求最优标号的问题实质就是求最大概率的问题—每一个点取标号集中哪一个标号概率最大，即每一个点被正确划分为特征点与非特征点的概率最大.由于每一个点的状态都和它的邻点紧密相关，将求最大概率的问题转化为求最小能量的问题（本文能量是考虑双点势团的能量，用来描述邻点之间的相关性）—点集取当前对应的标号集全局能量最小.因此，求最优标号的问题就是求最小能量的问题，能量越小，提取特征点的准确率越高.

α-expansion算法的主要思想是通过对标号执行α-expansion move操作来寻找基于α的一个局部最优解.即在标记f的所有一次α扩展变换所得的标记过程f′中，找到一个f2，使得f2=argminE（f′），若E（f2）＜E（f），则f=f′.其中，一个标号集是否优于前一个标号集是由该标号集与前一个标号集之间全局能量的大小界定.

α-expansion算法的具体步骤为

1.4提取特征点

根据第1.3节得到不稳定点的最优标号集，即散乱点中不稳定点的最优分类标号.将不稳定点的最优标号集同存储稳定点的数组综合，得到散乱点云的最优标号集f∗.其中，最优标号集f1∗= ｛f1，f2，···，fN｝与散乱点集P=｛p1，p2，···，pN｝之间存在一一对应的关系，即点p1的标号对应的是f1，以此类推，得到所有点的标号，根据标号类型直接判断该点是否为特征点，得到特征点集.判断一个点是否为特征点：

2　实验结果与分析

本文算法在Visual Studio 2010环境下实现了特征点的提取，硬件平台为2.8GHz Intel Core i5处理器、4GB内存的PC机.本文算法的参数列表如表1所示.其中，将球形邻域半径δ取值为0.01ldb～0.03ldb（ldb表示图形的包围盒的对角线长度）.

表1参数列表Table 1　The parameter list

2.1本文方法实验

兵马俑碎片的点云模型是通过非专业人员使用Creaform VIU 718手持式扫描仪扫描获得.扫描分辨率是3.91mm，这有利于扫描速度，但扫描精度粗糙.在该部分应用本文特征提取方法提取兵马俑碎片的特征点.特征检测的结果如图2～图4所示.为了说明本文方法能够准确地提取尖锐特征及细微特征点，同时能够保留较平滑的特征，本文选取三种具有不同特征的兵马俑碎片进行实验.

图2　兵马俑1号碎片特征提取Fig.2　Feature extraction of Terracotta Army 1

图2是兵马俑1号碎片模型图及特征提取结果图.该碎片是一个仅有尖锐特征的简单碎片模型，特征线比较突出，图2（b）表明本文方法能够完整准确地提取出碎片的尖锐特征点.

图3、图4是一个相对图2较为复杂的兵马俑碎片模型，这两个模型既包含尖锐特征，也包含相对平滑的特征，既有采样比较好的区域，也存在采样不均的区域，甚至还包含特征强度逐渐减弱的特征线.从图3（b）和图4（b）中可以看出，本文方法不仅提取到尖锐特征，同时也完整地保留了相对平滑的特征，例如碎片表面较为平滑的凸起，该方法能够识别并提取出特征点.

图3　兵马俑2号碎片特征提取Fig.3　Feature extraction of Terracotta Army 2

图4　兵马俑3号碎片特征提取Fig.4　Feature extraction of Terracotta Army 3

2.2对比实验

为了验证本文方法的优越性，本文对文献［9］及文献［13］的方法进行了实现.其中，文献［9］的方法实质是基于张量投票提取特征，主要是通过采样点和其对应的加权邻域重心的距离标志尖锐特征候选点，然后将该距离投影到采样点的法向方向进行平滑，比较投影距离和阈值，提取尖锐特征点.文献［13］的阈值检测法首先通过点到邻居点的平均距离、点的法向与邻居点法向夹角和数据点曲率三部分定义一个特征参数，然后将特征参数与特征阈值进行比较，提取特征点.该两个方法均涉及特征参数及特征阈值的选取设置，因此它们不能很好地识别逐渐平滑的特征及细微特征.

图5为本文方法、张量投票法以及阈值检测法在Bunny模型上的特征提取效果对比.Bunny模型既包含尖锐特征，也包含相对平滑的特征.张量投票的特征提取方法不能很好地检测出相对平滑的特征，阈值检测法对于头部的眼睛嘴巴的细微特征不能完整的识别.而本文方法能够较好地提取尖锐特征，同时尽可能地保留较平滑的特征点.

图6为本文方法、张量投票法以及阈值检测法在Fandisk模型上的特征检测对比.Fandisk模型既包含显著特征，也包含相对较弱的特征，既包含直线特征，也带有曲线型特征强度连续变化的特征.图6（c）为张量投票方法提取出尖锐特征，对于底部较为平滑的特征不能很好地识别.特征阈值检测法能够检测出尖锐特征，但是不能识别逐渐平滑的特征. 图 6（b）为本文方法提取特征的结果图，从中可以看出，本文方法不仅提取到显著特征，同时也保留了较平滑的特征.

图 7为 Dragon模型的算法效果对比图. Dragon模型复杂，点数量大，且其头部细小特征较多.通过对比图7（b）～（d）可以发现，本文算法检测出该模型的尖锐特征点以及一些细微的特征点；其余两种方法同样能够检测出尖锐特征点，但是不能很好地识别一些细微特征点.

本文方法首先通过曲率估计确定稳定点，然后通过计算能量函数使不稳定点以一定的概率接受该点是否是特征点，使特征点的判断具有灵活性，减少特征点的误判.从实验结果图可以看出，本文方法能够更加精确地提取出尖锐特征点，并尽可能多地保留相对平滑的特征.

图5　Bunny模型特征提取Fig.5　Feature extraction of Bunny model

图6　Fandisk模型特征提取Fig.6　Feature extraction of Fandisk model

图7Dragon模型特征提取Fig.7　Feature extraction of Dragon model

2.3噪声及时间效率

2.3.1本文算法噪声分析

本文在两类不同的模型上进行实验，检测本文算法的鲁棒性，即：人工添加的含有统一噪声的模型及由三维扫描获取的含有不统一噪声的模型.

本文首先对Fandisk模型人工添噪，并提取特征点.加入噪声的方式是将噪声点云位置偏移原位置某一距离.

表2　含噪声模型特征提取对比表Table 2　Comparison of feature points extracted with noise model

图8为Fandisk模型在不同尺度噪声下的特征提取结果［22］.实验结果表明，本文算法对噪声不敏感.在噪声尺度适中的情况下，该算法具有较好的鲁棒性.

2.3.2本文算法与对比实验的时间性能分析

表3中列出了本文算法、张量投票法、阈值检测法的时间效率.

由表3可知，本文算法的时间效率优于张量投票法及阈值检测法.本文算法的时间效率和采样点数及标号分类密切相关.首先，本文对于初始标号时选取曲率估计，其相对于局部拟合计算主曲率节省时间开销；接着采用马尔科夫随机场模型解决问题.针对该模型，采样点数及标号种类越多，时间开销越大.而任何模型进行特征提取，标号种类均为2（特征点、非特征点）.因此，对于采样点相同的模型，该算法的时间性能有所改善.

表3　算法时间效率对比表Table 3　Comparison table of algorithm time efficiency

2.4点采样密度敏感性

为了测试本文算法对不均匀采样的点云特征提取效果，本文将模型进行简化，得到具有相同曲面不同采样密度的模型，并对特征提取结果的不同视角进行展示分析.图5为Bunny模型提取结果，图9（a1）是将点简化到35%的Bunny模型，图9（b1）、（c1）、（d1）是对应图9（a1）的简化模型的特征提取结果，实验结果表明对于该简化模型，本文方法提取结果比较理想，即本文算法对采样密度并不敏感；而图9（a2）是简化到24%的Bunny模型，图9（b2）、（c2）、（d2）是对应图9（a2）的特征提取结果，实验结果表明该算法误将非特征点当作特征点提取出来，导致特征点的误判.因此，本文算法对于过于稀疏的点云模型效果不理想.

图8　带噪声模型提取特征点数对比Fig.8　Fandisk feature extraction with different noise amplitude

3　结论

本文针对散乱点云模型的特征提取问题提出一种基于马尔科夫随机场的特征提取方法.首先，计算每个点的曲率估计及阈值，比较点的曲率估计与阈值，初始化标号场，识别稳定点并将其标记存储在数组中；然后，由不稳定点属性信息的联合分布函数以及随机场的状态分布函数计算目标函数，求解目标函数得到不稳定点的最优标号集；最后，综合不稳定点的最优标号集与存储稳定点的数组，根据点标号提取特征点.实验结果表明本文算法能有效地提取尖锐特征并尽可能多保留较平滑的特征，同时算法简单易懂.与传统的特征检测方法相比，此方法的自适应性提高了特征提取的准确率，减少了特征点的误判率.

尽管本文方法能提取出尖锐特征点并尽可能多地保留较平滑特征，但仍存在改进空间.本文算法不适用于过度稀疏的点云模型.针对这一问题，下一步将考虑采用启发式算法解决稀疏模型的特征提取问题.

图9　Bunny简化模型特征提取结果Fig.9　Feature extraction of simplified Bunny model

References

1 Daniels J，Ha L K，Ochotta T，Silva C T.Robust smooth feature extraction from point clouds.In：Proceedings of the 2007 IEEE International Conference on Shape Modeling and Applications.Lyon，France：IEEE，2007.123-136

2 Demarsin K，Vanderstraeten D，Volodine T，Roose D.Detection of closed sharp feature lines in point clouds for reverse engineering applications.In：Proceedings of the 4th International Conference.Pittsburgh，PA，USA：Springer，2006.571-577

3 Pang Xu-Fang，Pang Ming-Yong，Xiao Chun-Xia.An algorithm for extracting and enhancing valley-ridge features from point sets.Acta Automatica Sinica，2010，36（8）：1073-1083（庞旭芳，庞明勇，肖春霞.点云模型谷脊特征的提取与增强算法.自动化学报，2010，36（8）：1073-1083）

4 Tombari F，Salti S，Stefano L D.Performance evaluation of 3D keypoint detectors.International Journal of Computer Vision，2013，102（1-3）：198-220

5 Pauly M，Keiser R，Gross M.Multi-scale feature extraction on point-sampled surfaces.Computer Graphics Forum，2003，22（3）：281-289

6 Guo Y L，Bennamoun M，Sohel F，Lu M，Wan J W.3D object recognition in cluttered scenes with local surface features：a survey.IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36（11）：2270-2287

7 Guo Y L，Bennamoun M，Sohel F，Lu M，Wan J W，Kwok N M.A comprehensive performance evaluation of 3D local feature descriptors.International Journal of Computer Vision，2016，116（1）：66-89

8 Ho H T，Gibbins D.Curvature-based approach for multiscale feature extraction from 3D meshes and unstructured point clouds.IET Computer Vision，2009，3（4）：201-212

9 Gumhold S，Wang X L，MacLeod R.Feature extraction from point clouds.In：Proceedings of the 10th International Meshing Roundtable.Berlin：Springer Press，2001.293-305

10 Jia J Y，Tang C K.Tensor voting for image correction by global and local intensity alignment.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（1）：36-50

11 Tang C K，Medioni G.Inference of integrated surface，curve and junction descriptions from sparse 3D data.IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20（11）：1206-1223

12 Wushour S，Cao Ju-Ming.An extraction algorithm for sharp feature points from point clouds.Journal of Xi′an Jiaotong University，2012，46（12）：1-5（吾守尔·斯拉木，曹巨明.一种新的散乱点云尖锐特征提取方法.西安交通大学学报，2012，46（12）：1-5）

13 Wang Li-Hui，Yuan Bao-Zong.Feature point detection for 3D scattered point cloud model.Signal Processing，2011，27（6）：932-938（王丽辉，袁保宗.三维散乱点云模型的特征点检测.信号处理，2011，27（6）：932-938）

14 Longjiang E，Waseem S，Willis A.Using a MAP-MRF model to improve 3D mesh segmentation algorithms.In：Proceedings of the 2013 IEEE Southeastcon.Jacksonville，FL：IEEE，2013.1-7

15 Lavou´e，Wolf C.Markov random fields for improving 3D mesh analysis and segmentation.In：Proceedings of the 1st Eurographics Conference on 3D Object Retrieval.Switzerland，Switzerland：Eurographics Association Aire-la-Ville，2008.25-32

16 Lu Xiao-Xin.Research on 3D Mesh Segmentation Algorithms Using Markov Random Filed［Master dissertation］，Harbin Institute of Technology，China，2010（卢孝新.基于马尔科夫随机场的三维网格模型分割算法研究［硕士学位论文］，哈尔滨工业大学，中国，2010）

17 Ren Ran.Research on Image Segmentation Method Based on Markov Random Field［Master dissertation］.Anhui University of Technology，China，2013（任然.基于Markov随机场的图像分割方法研究［硕士学位论文］，安徽工业大学，中国，2013）

18 Hoppe H，DeRose T，Duchamp T，McDonald J，Stuetzle W.Surface reconstruction from unorganized points.In：Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques.New York，NY，USA：ACM，1992.71-78

19 Wang Xiao-Chao，Liu Xiu-Ping，Li Bao-Jun，Zhang Shao-Guang.Feature detection on point cloud via local reconstruction.Journal of Computer-Aided Design&Computer Graphics，2013，25（5）：659-665（王小超，刘秀平，李宝军，张绍光.基于局部重建的点云特征点提取.计算机辅助设计与图形学学报，2013，25（5）：659-665）

20 Cohen-Steiner D，Morvan J M.Restricted delaunay triangulations and normal cycle.In：Proceedings of the 19th Annual Symposium on Computational Geometry.New York，USA：ACM，2003.312-321

21 Alexa M，Behr J，Cohen-Or D，Fleishman S，Levin D，Silva C T.Computing and rendering point set surfaces. IEEE Transactions on Visualization and Computer Graphics，2003，9（1）：3-15

22 Webber C，Hahmann S，Hagen H.Sharp feature detection in point clouds.In：Proceedings of the 2010 Shape Modeling International Conference.Aix-en-Provence，France：IEEE，2010.175-186

张靖西北大学信息科学与技术学院硕士研究生.主要研究方向为图像处理，可视化技术.

E-mail:zj18710812436@163.com

（ZHANG JingMaster student at the College of Information Science and Technology，Northwestern University. Her research interest covers computer graphics and visualization.）

周明全北京师范大学信息科学与技术学院教授.主要研究方向为虚拟现实与可视化技术，智能信息处理，数据库与知识库，图形图像处理.本文通信作者.

E-mail:mqzhou@nwu.edu.cn

（ZHOUMing-QuanProfessorat the College of Information Science and Technology，Beijing Normal University. His research interest covers virtual reality and visualization technology，intelligent information processing，database and knowledge base，graphics and image processing.Corresponding author of this paper.）

张雨禾西北大学信息科学与技术学院博士研究生.主要研究方向为计算机图形图像处理与可视化技术.

E-mail:zhangyuhe0601@126.com

（ZHANG Yu-HePh.D.candidate at the College of Information Science and Technology，Northwestern University.Her research interest covers computer graphics and visualization.）

耿国华西北大学信息科学与技术学院教授.主要研究方向为智能信息处理，数据库与知识库，图形图像处理.

E-mail:ghgeng@nwu.edu.cn

（GENG Guo-HuaProfessor at the CollegeofInformationScienceand Technology，Northwestern University. Her research interest covers intelligent information processing，dat abase and knowledge base，graphics and image processing.）

Global Feature Extraction from Scattered Point Clouds Based on Markov Random Field

ZHANG Jing1ZHOU Ming-Quan1，2ZHANG Yu-He1GENG Guo-Hua1

In order to extract the feature information of point clouds data accurately，a new method of feature extraction based on Markov random field（MRF）is proposed.First based on scattered point of curvature estimation and the threshold to initialize labels and determine the stability，the stable point marks stored in the array.Second，the problem of optimal unstable label transform to energy function of the label of the airport.By citing Bayesian estimation for posterior probability distribution function and the MAP-MRF（Maximum a posteriori-Markov random field）reduction，objective function is obtained.Finally according to the graph cut algorithm，using label adjustment process label set relative energy changes get optimal labels of unstable set，and the stable storage array synthesis，by labels rapidly extracts feature points. Experimental results show that the proposed method is simple and fast，and does not need manual setting of threshold. According to the change of global energy，the optimal labeling and feature points are extracted.

Scattered point cloud，feature extraction，Markov random field（MRF），label

10.16383/j.aas.2016.c150627

Zhang Jing，Zhou Ming-Quan，Zhang Yu-He，Geng Guo-Hua.Global feature extraction from scattered point clouds based on Markov random field.Acta Automatica Sinica，2016，42（7）:1090-1099

2015-10-10录用日期2016-01-19
Manuscript received October 10，2015；accepted January 19，2016
国家自然科学基金（61373117，61305032），高等学校博士学科点专项科研基金（20136101110019），陕西省教育厅科研专项（2013JK1180）资助
Supported by National Natural Science Foundation of China （61373117，61305032），Special Research Fund for the Doctoral Program of Higher Education（20136101110019），and Shaanxi Provincial Department of Education Research（2013JK1180）
本文责任编委吴建鑫
Recommended by Associate Editor WU Jian-Xin
1.西北大学信息科学与技术学院西安7101272.北京师范大学信息科学与技术学院北京100875
1.College of Information Science and Technology，Northwestern University，Xi′an 7101272.College of Information Science and Technology，Beijing Normal University，Beijing 100875