第２４卷第１期 ２０１５年１月 测绘工程
Ｅｎｇｉｎｅｅｒｉｎｇ ｏｆ Ｓｕｒｖｅｙｉｎｇ ａｎｄ Ｍａｐｐｉｎｇ Ｖ０Ｉ．２４，Ｎｏ．１
Ｊａｎ．，２０１５
一种改进的ＲＡＮＳＡＣ算法提取多模型圆弧特征点云 许烨璋 ，王鑫森 ，郑德华 ，谢波 ，王春林 （１．河海大学地球科学与工程学院，江苏南京２１００９８；２．天津市勘察院，天津３００１９１）
摘要：针对传统ＲＡＮＳＡＣ算法迭代次数无上限及只能识别单个模型的局限，提出一种适用于扫描线式点云数据 改进的ＲＡＮＳＡＣ算法。对三维激光点云数据进行二维化处理，在ＲＡＮＳＡＣ算法的基础上对局外点进行预剔除，计 算过程中对迭代次数进行自适应调整，采用分次识别法实现多模型圆弧点云的提取。实例证明，文中算法能够有效 地提取同一场景中的多模型圆弧点云，较传统算法具有明显优势。 关键词：点云二维化；改进的ＲＡＮＳＡＣ算法；多模型圆弧；特征提取 中图分类号：ＴＰ３９１．４ 文献标志码：Ａ 文章编号：１００６—７９４９（２０１５）０１—００２８—０４
Ａｎ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｏｆ ＲＡＮＳＡＣ ｔｏ ｅｘｔｒａｃｔ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｃｌｏｕｄ ｏｆ ｍｕｌｔｉ－－ｍｏｄｅｌ ａｒｃ
ＸＵ Ｙｅ－ｚｈａｎｇ ，ＷＡＮＧ Ｘｉｎ－ｓｅｎ。，ＺＨＥＮＧ Ｄｅ－ｈｕａ ，ＸＩＥ Ｉ３ｏ ，ＷＡＮＧ Ｃｈｕｎ－ｌｉｎ （１．Ｓｃｈｏｏｌ ｏｆ Ｅａｒｔｈ Ｓｃｉｅｎｃｅｓ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｏｈａｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ ２１００９８，Ｃｈｉｎａ；２．Ｔｉａｎｊｉｎ Ｅｘｐｌｏｒａｔｉｏｎ Ｉｎｓｔｉｔｕｔｅ，Ｔｉａｎｊｉｎ ３００１９１，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｇａｉｎｓｔ ｔｈｅ ｌｉｍｉｔ ｏｆ ｔｒａｄｉｔｉｏｎａ１ ＲＡＮＳＡＣ ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈ ｈａｓ ｎｏ ｃａｐｓ ｏｆ ｉｔｅｒａｔｉｏｎｓ ａｎｄ ｃａｎ ｊ ｕｓｔ ｉｄｅｎｔｉｆｙ ｏｎｅ ｍｏｄｅｌ。ｉｔ ｐｒｏｐｏｓｅｓ ａｎ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｏｆ ＲＡＮＳＡＣ ｆｏｒ ｓｃａｎ－ｗｉｒｅ ｐｏｉｎｔ ｃｌｏｕｄ ｏｆ ３－Ｄ ｌａｓｅｒ ｓｃａｎｎｉｎｇ．Ｆｉｒｓｔｌｙ ３Ｄ ｐｏｉｎｔ ｃｌｏｕｄ ｉｓ ｔｒａｎｆｏｒｍｅｄ ｉｎｔｏ ２Ｄ ｐｏｉｎｔ ｃｌｏｕｄ．Ｂａｓｅｄ ｏｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｏｆ ＲＡＮＳＡＣ，ｔｈｅ ｏｕｔｌｉｅｒｓ ａｒｅ ｅｘｃｌｕｄｅｄ ｐｒｅｖｉｏｕｓｌｙ．Ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｃａｌｃｕｌａｔｉｎｇ，ｔｈｅ ｉｔｅｒａｔｉｏｎｓ ａｒｅ ａｄｊ ｕｓｔｅｄ ａｄａｐｔｉｖｅｌｙ．Ａｔ ｌａｓｔ ｔｈｅ ｉｄｅｎｉｔｉｆｉｃａｔｉｏｎ ｏｆ ｍｕｌｔｉｐｌｅ ａｒｃｓ ｉｓ ｇｏｎｅ ｔｈｒｏｕｇｈ ｇｒａｄｅｄ ｒｅｃｏｇｎｉｔｉｏｎ ｍｅｔｈｏｄ．Ｅｘｐｅｒｉｍｅｎｔ ｓｈｏｗｓ ｔｈａｔ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｃａｎ ｅｘｔｒａｃｔ ｍｕｌｔｉｐｌｅ ａｒｃｓ ｏｆ ｐｏｉｎｔ ｃｌｏｕｄ ｂｅｔｔｅｒ ｔｈａｎ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ａｌｇｏｒｉｔｈｍ ｏｆ ＲＡＮＳＡＣ． Ｋｅｙ ｗｏｒｄｓ：ｔｗｏ ｄｉｍｅｎｓｉｏｎａｌ ｐｏｉｎｔ ｃｌｏｕｄ；ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｏｆ ＲＡＮＳＡＣ；ｍｕｌｔｉ—ｍｏｄｅｌ ａｒｃ；ａｕｔｏｍａｔｉｃａｌｌｙ ｅｘｔｒａｃｔ
目前点云数据的特征提取大多是直接在三维 空间中进行的＿１］。特征提取算法基本可分为基于边 界的算法和基于面域的算法两大类，另外还有综合 使用两种方法的混合算法＿２］。前者主要是提取点云 数据表面形态变化剧烈的点，通常利用法矢、曲率 等微分几何变量的突变来提取特征。这种方法对 噪声比较敏感，故抗差性较弱。后者主要在于寻找 点云数据中具有相同属性的点集，构造出可靠的生 长区域进行生长，最终实现分割和特征提取。这类 方法主要有ＲＡＮＳＡＣ（随机抽样一致算法）、Ｍ估 计、最小中值算法、遗传算法和霍夫变换等［３］。这些 方法本身具有良好的抗差估计性能，因此在提取特
收稿日期：２０１３—１１一Ｏｌ；修回日期：２０１４—１０—０９ 作者简介：许烨璋（１９８９一），男，硕士研究生．
征时能有效抵御噪声。 ＲＡＮＳＡＣ（Ｒａｎｄｏｍ Ｓａｍｐｌｅ Ｃｏｎｓｅｎｓｕｓ）算法是 １９８１年由Ｆｉｓｃｈｌｅｒ和ＢｏｌｌｅｓＥ ］最先提出。该方法能 够在含有大量粗差点的情况下估计出正确的模型， 较经典的最小二乘法具有明显优势。但随着局外 点的增多，算法的迭代次数会呈现指数式增长，算 法耗时急剧增加。另外ＲＡＮＳＡＣ算法只能实现单 个模型的识别。本文提出一种改进的ＲＡＮＳＡＣ算 法，能够有效地克服传统ＲＡＮＳＡＣ的不足。
１扫描线点云特点及其二维化 １．１扫描线点云特点 扫描线式点云由一组扫描线组成，每条扫描线 点云数据是按照扫描仪与激光脚点的仰角大小依 第１期 许烨璋，等：一种改进的ＲＡＮＳＡＣ算法提取多模型圆弧特征点云 ・２９・ 次存储的ｒ５］。本文采用的数据为Ｔｒｉｍｂｌｅ ＧＸ２００ 三维激光扫描仪采集的扫描线式点云数据，每条扫 描线都是扫描光刀平面与目标物体的交线。由于 本文所扫描的对象为球体目标，因此所要提取的圆 弧特征点云都位于每条扫描线上。同一条扫描线 中的扫描点基本共面，对于单独一条扫描线数据， 完全可以在二维平面内进行特征点的提取，这样就 可以把复杂的三维点云的问题简化到二维平面内 处理［６］，故本文以扫描线为单位进行圆弧点云的 提取。 １．２扫描线点云二维化 由于各项误差的存在，每条扫描线上的点云不 可能都严格位于各自的光刀平面内，而是以微小的 距离分布在光刀平面的两侧。因此将扫描线点云 二维化至其对应的光刀平面，首先须根据扫描线点 Ｄ ｙ 图１投影点的三维表达 ２ Ｒ ＬＣ算法的改进 ２．１ ＲＡＮＳＡＣ算法原理及其不足 ＲＡＮＳＡＣ算法是通过不断地选择数据集中的 一组随机子集来估计待定模型。选取的点集假设 为局内点即符合模型的数据点，不符合模型的点称 为局外点。每次用选定的随机子集去估计一个待 估模型，然后用该模型去测试数据集中其他的点， 符合该模型的点归为局内点，当局内点数量达到设 定要求时就认为该模型合理，并且将局内点归纳进 来重新估算模型。如果局内点数量不够，则认为该 模型估算的不正确，此时舍弃原模型，重新在数据 集中随机抽取一个子集来估算模型。每次估算的 模型要么因为局内点数量充足而重新生长，要么由 于局内点数量不足而遭到舍弃［７］。最终以局内点和 模型的错误率来评价模型估算的精度。 虽然传统ＲＡＮＳＡＣ算法能从含有大量局外点 的数据集中估算出高精度的模型参数，但其迭代次 数没有上限。如果设置了迭代上限，可能会导致抽 样不充分从而计算出错误的模型，如果不控制迭代 次数，便会造成算法效率低下，难以收敛。 云拟合计算出对应的光刀平面方程式。本文采用 特征值法求取平面方程式，具体解求过程不再详 述。拟合平面求出后将对应的三维点云投影上去， 完成点云的投影。 经过投影后点空间三维点虽已全部位于平面 上，但其坐标仍为（Ｉｎｄ，Ｘ，Ｙ，Ｚ）（其中Ｉｎｄ为索引 值）的三维形式，须将这些点转化为（Ｉｎｄ，Ｘ，ｙ）的二 维形式，图１所示为某拟合平面０ｔ 内的投影点集 （Ｐ０，Ｐ 一，Ｐ ）在三维直角坐标系中；图２所示为 所要得到的二维坐标。其转换过程为：①以Ｐ 点为 原点，Ｐ 连线的方向矢量为Ｘ轴，以过点Ｐ 并 垂直于Ｘ轴成右手系的向量作为ｙ轴。②计算其 他点Ｐ 到Ｐ 点的距离ｄ，以及向量Ｐ。Ｐｆ与Ｐ 之间的夹角ｙ。③根据ｄ和７，将二维极坐标向二 维直角坐标转换，求取 点的直角坐标（Ｘ，ｙ）。
图２投影点的二维表达 ＲＡＮＳＡＣ算法的另一个不足是它只能在特定的数 据集中估计出一个模型，对于数据集中存在两个或 者两个以上的模型，ＲＡＮＳＡＣ不能识别。 ＲＡＮＳＡＣ算法输入参数见表１。
表１ ＲＡＮＳＡＣ算法输入参数 参数名 含义 一组观测数据 适应于数据的模型 最少必要模型点个数 算法的迭代次数（抽样次数） 决定数据是否适用于模型的阈值 判定模型是否适用于数据集的数据数目
设 个点全部为局内点的概率为Ｐ，点集的总 点数为Ｎ，所有局外点数为№，则随机选取一个点 为局外点的概率为ｗ，且Ｗ—Ｎｔ／Ｎ。ｎ个点全部 为局内点的概率又可以表示为（１一Ｗ） ，１一（１一 Ｗ）”表示１＂１个点中至少有一个为局外点的概率，则 （１一（１一ｗ） ） 表示永远都取不到，ｚ个点全部都为
ｍ・３０・ 测绘工程 第２４卷 局内点的概率，它应该和１一Ｐ相等，即ｌ—Ｐ一 （１一（１一Ｗ） ） ，对两边取对数即可得出 走一 若 ． ㈩ 迭代时取略大于ｋ的值即可。 由式（１）可以看出，在７ｚ和Ｐ固定的情况下，局 外点率Ｗ越大，迭代次数ｋ也就越大，算法效率越 低下。因此为了减少迭代次数，提高算法效率，就 必须降低局外点所占的比例并且根据每次数据的 调整对ｋ值进行自适应调整。 ２．２局外点的预剔除 本文提取的圆弧点云为球面圆弧点云，为扫描 光刀平面在球面上截取的圆，其直径必然小于或等 于球直径（球面被光刀面所截的圆截面中，通过球 直径的截面最大），因此那些直径大于球直径的数 据点即可认为局外点。利用这一特性本文以相邻 的３个点为一组遍历整条扫描线，计算每组数据对 应圆的直径，将直径大于设定阈值的数据剔除，从 而达到降低外点率的目的。图３为局外点剔除示 意图。
图３局外点剔除示意图 ２．３ ｋ值的自适应调整 随着迭代次数的增加，内点被不断地增加到估 算模型的点集中来，即在迭代过程中内点率不断增 加，相应的外点率在不断减小，则根据式（１）迭代次 数ｋ值也在随之减小。本文算法在开始计算时将ｋ 值设置为一个较大的值，然后在每次迭代时根据外 点率重新计算ｋ的值使其趋于一个合理的值完成迭 代。为了验证ｋ值自适应调整的效果，事先针对迭 代次数ｋ值做了一组测试。将ｋ的初始值设为 １４ ０００，开始计算后每隔１０ Ｓ记录一次ｋ值，从图４ 可以看出ｋ值在前４０ Ｓ中数值下降显著，最终在第 ９０ Ｓ处自适应停止，稳定到５５ Ｓ左右，表明本文的 自适应处理能够取到良好的效果。 ｌ４ ０００ ． １２ ０００ 。■－－＼ 一 １０ ０００ ８０００ ６０００ ４０００ ２０００ Ｏ ｌ ２ ３ ４ ５ ６ ７ ８ ９ ＿．一 １４０００ ８３２０ ７ｌ７８ ３姗 ３Ｏ０６ １０１８ ８００ ｌ０ｏ ５５ －．埘Ｉ＇￣ｑｊｓ １Ｏ ２０ ３０ ４０ ５ｏ ６０ ７０ ８０ ９０ 图４ ｋ值自适应变化过程 ２．４多模型识别的改进 上文提到ＲＡＮＳＡＣ算法的另一大不足就是只 能对待估点集中的一个模型进行识别，对包含两个 及其以上的模型就无法适用。为解决这一问题，本 文采用分次识别的方法，即将第一次识别出的模型 所对应的点集剔除出二维点集后再进行下一个模 型的识别，按照这种流程直到满足某种条件为止。 综合以上３点改进，本文改进的ＲＡＮＳＡＣ算 法提取圆弧点的算法步骤如下： １）选定一组已经二维化后的扫描线点集｛Ｐ ， Ｐ ，…，Ｐ ），将相邻的３个｛Ｐ ，Ｐ斗 ，Ｐ斗２ ｌ ｉ∈Ｅ１， 一２］｝计算构成圆的半径值ｒ，按顺序无重复地遍 历点集。 ２）将半径值ｒ∈ ，Ｒ ］对应的点保留，将超 过ｒ阈值范围的对应点集剔除，构成新的点集｛Ｑ ， Ｑ ，…，Ｑ ）。 ３）将迭代次数ｋ设置为一个足够大的数值，随 机抽取一个包含３个点的样本，计算其模型参数 Ｍｏｄｅｌ ，即圆心坐标及半径（ｚ。，Ｙ。，ｒ） 。 ４）再次检验样本点计算的ｒ值是否符合ｒ∈ ＥＲ ，Ｒ ］，若是，则进入下一步，否则退出本次循环， 转回到３）。 ５）遍历点集｛Ｑ ，Ｑ，…，Ｑ ｝，判断每加入一个