SIMD在点云滤波处理中的应用

柳红凯　徐晓　郭浩

摘 要：为了进一步提高.NET平台数据处理能力，微软新推出基于.NET平台的新技术-SIMD。传统滤波算法大都采用单指令单数据流对点云数据进行处理，然而由于三维激光扫描获取的点云数据量极其庞大，单指令单数据的处理方式效率较低。文章在区域增长理论基础上提出基于.NET平台的单指令多数据流（SIMD）点云滤波处理新算法。该方法在对数据处理时通过一次指令同时进行多个数据并行计算的方式达到提高效率的目的。通过对大量数据的运算实例表明算法的高效性。

关键词：.NET；SIMD；点云滤波；区域增长；单指令

引言

三维激光扫描技术（LIDAR）是继GPS后又一新兴的测量新技术，能够在很短的时间内获得大量地形表面信息，这些LIDAR点云数据除了包括地面点外，还包括诸如汽车，房屋及植被等一些非地面信息。为了获得真实的地面高程模型（DEM），需要将点云数据进行滤波处理，将地面点和非地面点进行分离，得到由地面点组成的DEM模型。

多年来，国内外不少学者专注于点云的处理研究上[1-2]，并取得了不错的成果，具有代表性的有以下几种滤波算法，如以内插不规则三角形的算法[3]、基于形态学的算法[4-7]、基于多分辨率法[8]、基于坡度的算法、区域增长算法等，这些算法应用到不同情况和不同地形条件下得到一些有价值的参考价值。区域增长算法由于适应性广，即使在复杂地形条件下也有强的适应性，但是该方法是串行算法，当目标较大时，数据处理速度慢，因此在使用该方法时应该尽量提高效率。

文章在区域增长算法的基础上，提出融合SIMD技术，一次指令多个数据并行处理，使得大量点云数据时，极大的提高了效率。文章试验中，抽取大量的、不同数量的点云数据，通过计时对比，验证该理论算法的可行性和高效性。

1 区域增长滤波算法

区域生长（region growing）是指将成组的像素或区域发展成更大区域的过程。既是根据事先定义的准则将像素或者子区域聚合成更大的区域。基本方法是以“一组”种子开始，将与种子性质相似（灰度级或颜色的特定范围）的相邻像素附加到生长区域的种子上。

这种算法的关键是一类元素总有一些相似的性质，在点云数据滤波处理中就是为了分离地面点和非地面点，文章将数据元素的高程值作为同一性质的集合用作数据分离度量。

1.1 区域增长法则

（1）选取图像中的一点为种子点（种子点的选取需要具体情况具体分析）。（2）在种子点处进行8邻域或4邻域扩展（文章以8邻域搜索），判定准则是：如果考虑的像素与种子像素灰度值差的绝对值小于某个门限T，则将该像素包括进种子像素所在的区域。（3）当不再有像素满足加入这个区域的准则时，区域生长停止。

1.2 初始地面的生成

（1）确定格网尺寸L0。为了避免分割尺寸过大时数据的冗余和尺寸过小时格内无点的情况，在对点云数据分割时一般将格网尺寸L0略大于点云的平均间隔L。（2）计算网格的平均高程。在只有一个点云数据的网格内，将该点的高程值作为格网的高程值记录下来；一个网格内含有多个点时，以高程最小的点为基准，将超过阈值的其他点删除，最后记录内所有高程点的平均值；一个格网没有点时，进行8邻域搜索选取最低点作为该格子的高程值。（3）生成地面模型。选择合适种子点，按照生长准则，不断进行8邻域搜索和合并得到地面模型。区域增长算法是串行性质的算法，区域增长算法就显得效率较低，文章就是针对提高区域增长算法效率而引入多数据并行处理的新算法。

2 单指令多数据流（SIMD）

单指令多数据流（Single Instruction Multiple Data，简称SIMD），能够一次性获得多个操作数，并把它们保存成一组指令集。以同步方式，在同一时间内执行同一条指令。

以乘法指令为例，单指令单数据流（SISD）的CPU对乘法指令译码后，先访问内存，取得第一个操作数；之后再一次访问内存，取得第二个操作数，随后才能进行求积运算。而在SIMD中，CPU对乘法指令译码后，一次性获得所有操作数进行运算，随后进行求积运算。两者技术区别代码如下：

通过对比我们可以了解到这个特点使SIMD特别适合于大量点云数据的处理。SIMD是通过一次指令并行处理多个数据元素的方式处理数据，该方法在点云这种大数据量的处理中有独特的优势。

3 算法

由于点云数据量极大，传统单数据流算法较难提高效率，文章在区域增长思想的基础上，结合了SIMD的编程技术，提高点云处理效率。

文章算法的基本思想如下：

（1）结合经验对区域进行块划分（block）。在进行区域划分时尽量保证分割区域的连续性。而格网尺寸的大小一般以最大建筑物的尺寸为参考。并且尽量将区域分成大小不同的规则形状（如矩形，正方形等）。（2）将块格网化。根据点的平面坐标位置，将点云区域格网划分，至于格网的大小以点云的密度为参考，一般保证每个小方格内含有1、2个点即可。（3）选择适当的种子点。遍历块中的点数据选择高程值最小的点作为种子点数据。（4）以8邻域法则进行种子搜索。将邻域点与种子点的高程值作比较，当差值小于阈值时即为地面点且作为新的种子点，当差值大于阈值时就以非地面点滤除。直到没有符合条件的点数据时生长结束。在.NET Vector 数据处理时，首先利用Vector 泛型类中public static int Length { get； }只读属性获得计算机cpu支持的位数，将搜索到的数据点的高程值（文章将高程值定义为float类型）压入堆栈，然后对堆栈中的数据进行并行处理（文章计算机设计成4数值并行处理）。

4 实验

文章选取大淑村扫描的1580645个点进行对比计算，通过新算法与原算法进行对比。为了验证新算法的高效性，文章选取传统的区域增长算法与新算法对去除体外孤点进行试验对比，通过计时对比两者之间的差距。为了论证新算法的高效性，文章还通过录入不同数量的点进行比较，进一步证明新算法的高效性。

5 结束语

文章算法是针对传统算法对点云数据处理中效率性进行讨论，并对并行算法的关键技术做了详细解释。针对大量的、不同算法、不同数量的点云数据处理进行计时对比试验，结果表明新改进的算法确实可以将点云处理效率提高数倍。

参考文献

[1]王勇.地面激光扫描数据滤波研究[D].郑州：解放军信息工程大学，2012.

[2]王金亮，陈联君.激光雷达点云数据的滤波算法述评[J].遥感技术与应用，2010，25（5）：632-638.

[3]李卉，李德仁，黄先锋，等.一种渐进加密三角网LIDAR点云滤波的改进算法[J].测绘科学，2009，34（3）：39-40，216.

[4]张熠斌，隋立春，曲佳，等.基于数学形态学算法的机载LIDAR点云数据快速滤波[J].测绘通报，2009，5：16-18，65.

[5]李鹏程，王慧，刘志青，等.一种基于扫描线的数学形态学LIDAR点云滤波方法[J].测绘科学技术学报，2011，28（4）：274-277，282.

[6]张熠斌，隋立春，曲佳，等.基于数学形态学算法的机载LIDAR点云数据快速滤波[J].测绘通报，2009，5：16-18，65.

[7]孙美玲，李永树，陈强，等.基于扫描线的渐进式形态学机载LIDAR点云滤波[J].光电工程，2013，40（11）：71-75.

[8]万幼川，徐景中，赖旭东，等.基于多分辨率方向预测的LIDAR点云滤波方法[J].武汉大学学报（信息科学版），2007，32（11）：10-11.

[9]成晓倩，赵红强.基于区域生长的LIDAR点云数据滤波[J].国土资源遥感，2008，78（4）：6-8，21.

作者简介：柳红凯（1989-），男，硕士研究生，主要从事地理三维激光点云数据处理方面研究。