基于鸡群优化算法的点云简化算法在粮堆检测中的应用

史旭栋，高岳林

(1.宁夏大学数学统计学院，宁夏银川 750021；2.北方民族大学信息与系统科学研究所，宁夏银川 750021)

随着3D激光技术的发展，点云在3D形状中有许多应用[1-2]。然而，现代3D激光扫描仪能产生包括数百万的采样点的点云集[3],但是要求超大存储空间和长时间的后处理。因此，必须简化冗余数据来提高精度和曲面重构的效率。研究者一直致力于点云的简化。一般来说，点云简化包括传统和自适应的简化方法。点云扫描线类型的传统简化方法主要包括平均距离、最小距离、角偏差和弦偏差方法[4-7]，但这些方法效率较低。

最近，3D激光扫描仪被用于扫描粮仓、煤堆和矿井等大型物体[8-11]。由于曲率变化小和细节变化小等特性，大型物体的点云简化方法与中小型物体的方法不同。 此外，不可能用上述提到的单一传统方法。因此，学者们开始研究自适应简化的方法。对于空间维数较低的点云数据，Ferrari等[12]采用一种指定减少率来自动地简化矢量点云数据。对于指定减少率，Song等[13]用原始输入数据集搜索子集的方法来简化点云数据。Yu等[14]提出一种基于模糊k-均值聚类法的自适应3D点云简化方法。Shi等[15]提出一种自适应简化方法，这种方法保证点云数据边界的完整性和分布的合理性。也有研究者提出一种基于Akima插值的简化方法[16],针对存储粮堆，点云数据的简化方法有待进一步研究。笔者针对一种智能实用的点云数据简化算法，提出了一种基于鸡群优化(CSO)的自适应点云简化算法，将CSO引入平均距离方法根据原始点的密度自适应地调整点集而缩小扫描线的间隔，并通过使用3D点云扫描粮仓中粮堆表面验证了算法的有效性。

1 材料与方法

1.13D激光扫描仪的测量原则3D激光扫描仪由水平调节模块、数据采集单元、中央控制器、旋转控制模块和扫描器设计的。激光扫描仪上安装了一个波长为905 nm的一流安全激光装置，其扫描误差为7 mm/50 m，扫描直径为100 m。激光扫描仪安装在粮仓的横梁上，从上面扫描大块的谷物表面。另外，发动机可以让扫描仪进行270°旋转，所以扫描仪可以一次扫描谷堆表面完整的图像。之后激光扫描发射激光信号来测量目标，在被测物体上出现漫反射后立即返回接收器。根据上述过程所需要的时间，扫描仪可以从扫描仪本身计算到扫描点的距离P,同时可以测量水平扫描角φ和垂直扫描角ω,利用上述变量，按以下公式计算三维坐标的扫描点：

(1)

1.2数据收集试验是在玉米仓库中进行的，粮食存储的环境温度为16 ℃，湿度为61%。用水平调节模块调节扫描仪避免了扫描仪内的坐标系和粮仓的坐标系的交叉角和扫描精度下降。扫描仪的默认设置是将初始扫描点归零，来保证在同一标准下测量粮食的体积，从而易于比较和分析。利用点云数据的测试结果来选择扫描速度和点击细分设置。具体的扫描参数如下；扫描速度10°/s;扫描最初位置为零刻度点；电机细分设置1/4；扫描旋转角度为270°。扫描仪与远程主机相连，在扫描整个粮仓之后，将扫描数据存储在上位机的缓冲存储器中。共进行8组试验。每组扫描3次，共获得24个点云数据。

1.3基于CSO的简化算法描述

1.3.1鸡群算法的简单描述。鸡群优化算法是一个新的智能优化算法，它模拟鸡群的行为和等级制度。在该算法中，鸡群被分为若干个组，每个组是由1只公鸡、若干个母鸡和小鸡组成。假设Ng、NH、NC、NM分别表示公鸡、母鸡、小鸡和母鸡妈妈的数量。最好的NR假设为公鸡，最差的Nc假设为小鸡，其余的都是母鸡。在N只鸡的鸡群中，用xij(t)表示第t代中第i只鸡的第j维分量，pxij表示第i只鸡的最优位置[16]。

不同的鸡遵循不同的运动规律，适应度较好的公鸡比较差的公鸡更接近食物，其位置更新公式如下：

xij(t+1)=pxij(t)×[1+randn(0,σ2)]

(2)

(3)

式中，randn(0,σ2)是均值为0，方差为σ2的高斯分布;ε是一个极小量;k是公鸡群中不为i的随机数;f是x所对应的适应度值。

母鸡的更新公式如下：

xij(t+1)=pxij(t)+c1·rand·[xr1j(t)-xij(t)]+

c2·rand·[xr2j(t)-xij(t)]

(4)

(5)

c2=efr2-fi

(6)

式中，rand是[0，1]之间的随机数；r1表示第i只母鸡所在子鸡群的公鸡;r2表示随机从鸡群中挑选1只，并且r1≠r2。

小鸡的更新公式如下：

xij(t+1)=pxij(t)+FL·(pxmj-xij)

(7)

式中，m是第i只小鸡的母鸡;F是[0,2]之间的随机数。

1.3.2基于CSO的简化算法描述。在每次扫描过程中，扫描仪的安装位置、粮仓的形状和粮堆的表面都没有改变。 扫描仪和测量点的距离和角度不同，可能会导致点云数据测出得粮食堆两边稀疏、中间密集。然而，对于谷堆表明这种大的物体而言，平均距离法不能根据原始点云数据的密度而缩小点的间隔。因此，该研究将CSO引入平均距离法。

CSO是元启发式的群智能优化算法。基于CSO的简化算法可以自适应地调节扫描线的间隔。它随时根据点云数据的密度更新扫描线的缩减间隔，最后输出简化后的点云数据集。其算法步骤如下。

步骤1：提取点云数据的坐标信息(xi,yi,zi),i=1,2,3,…,m。

(8)

步骤3：取扫描线k，得到这些点减少间隔的阙值ηk(3δk>ηk-1>0.3δk)，最后判断平均减少间隔是否超过间隔阙值。如果超过转步骤4，否则，转步骤7。

步骤4：建立最优化的数学模型，利用CSO确定最优平均下降间隔。

步骤5：计算适应度，根据每只鸡的适应度求得gbest。

步骤6：如果满足终止条件，则输出最优解gbest，否则转步骤5。

步骤7：利用自适应最优减少间隔来减少扫描线上的点，输出减少后点云数据。

步骤8：如果扫描线全部简化，则跳出程序，否则转步骤2。

最优化的适应度函数可以由以下公式计算：

fitness(X)=

(9)

算法的初始参数如下：鸡群规模N为40；公鸡、母鸡和小鸡的比例为2∶6∶2；妈妈母鸡的比例为0.1；小鸡跟随系数FL为(0,2)；最大迭代次数为500；初始减少间隔(η0/mm)为0.1。

2 结果与分析

简化的粮堆表面点云数据反映了粮堆表面的特征。为了得到粮堆表面，该研究使用Delaunay triangulation方法来重建点云数据。由于Delaunay triangulation是使用一系列连通但不重叠的三角形集合来重建，所以该方法适用于数据密集分布、数据冗余较小并且存储效率较高的点云数据。

利用CSO简化点云数据的方法的平均时间为1 523 s。然而用平均简化方法简化的点云数据时间的平均值为5 871 s。 结果表明，点云数据简化性能在后期表面重建上效果较好，特别是数据较大时。更少的数据和更均匀的点云数据将得到更短的时间和更好的表面重建性能。这也说明需要为密集点云数据设计一种更有效简化算法。

相比平均距离法，该研究所提出的算法计算出的粮堆体积更接近实际粮堆体积，表1给出了结果。均方根误差反映了个体离散度，由式(10)给出：

(10)

表1不同算法对粮堆体积估算的比较

Table1Comparisonofgrainvolumeestimationbydifferentalgorithms

算法Algo-rithm组号GroupNo.简化点的数目Thenumberofsimplifiedpoint计算玉米的体积Thevolumeofcalculatedcorn∥m3相对误差Relativeerror∥%RMSESACSO165.1814105.1540.1225.709260.8834103.1090.073365.5904090.6360.244455.6924091.9420.220565.4224096.3410.170655.5164098.7740.085766.4824105.9030.122862.3464098.9110.085ADM197.8964079.0320.51215.9102100.3684113.2570.3173112.6234120.0390.488498.8324089.7110.2685115.5294119.9060.463698.8424088.0210.2937103.5304110.4030.2448104.1824117.4010.415

3 结论

提出了一种基于CSO的点云简化算法，该算法能够自适应地调节扫描线的平均距离，解决了原始点云数据量大和分布不均匀的问题。利用该算法可使分布更加均匀、简化。该研究所提出的算法是一种可以代替平均距离法解决存贮粮食体积问题的简单和实用的方法。

[1] FLEISHMAN S,COHEN-OR D,ALEXA M,et al.Progressive point set surfaces[J].ACM Transactions on Graphics,2003,22(4):997-1011.

[2] KIL Y J,AMENTA N.Defining point-set surfaces[J].ACM Transactions on Graphics,2004,23(3):264-270.

[3] LEVOY M,PULLI K,CURLESS B,et al.The digital Michelangelo project:3D scanning of large statues[C]//Proceedings of SIGGRAPH.New York:ACM Press,2000.

[4] LIU H,TAO Y L,FU J W.Data processing of scanning beam point-cloud based measuring freeform surface[J].Modular machine tool & automatic manufacturing techique,2011(5):77-80.

[5] FANG Y M,XIA Y H,CHEN J.Study on point cloudy data simplification of goal based on improved angular deviation method[J].Journal of earth sciences and environment,2012,34(2):106-110.

[6] WANG G F,LV Y M,HAN N,et al.Simplification method and application of 3D laser scan point cloud date[C]//Mechanical engineering and material science:2012 international conference on mechanical engineering and material science(MEMS 2012).France:Atlantis Press,2012:266-268.

[7] 陈璋雯,达飞鹏.基于模糊熵迭代的三维点云精简算法[J].光学学报,2013,33(8):153-159.

[8] MCCAFFREY K J W,JONES R R,HOLDSWORTH R E,et al.Unlocking the spatial dimension:Digital technologies and the future of geoscience fieldwork[J].Journal of the geological society,2005,162(6):927-938.

[9] QIN J.Open access publishing of scientific scholarly journals in China[M].Tianjin:Tianjin University of Technology,2011:63.

[10] 徐伟恒,冯仲科,苏志芳,等.一种基于三维激光点云数据的单木树冠投影面积和树冠体积自动提取算法[J].光谱学与光谱分析,2014,34(2):465-471.

[11] ZHU L L,HYYPPA J.The use of airborne and mobile laser scanning for modeling railway environments in 3D[J].Remote sensing,2014,6(4):3075-3100.

[12] FERRARI S,FERRIGNO G,PIURI V,et al.Reducing and filtering point clouds with enhanced vector quantization[J].IEEE Transactions on Neural Networks,2007,18(1):161-177.

[13] SONG H,FENG H Y.A global clustering approach to point cloud simplification with a specified data reduction ratio[J].Computer-aided design,2008,40(3):281-292.

[14] YU Z W,WONG H S,PENG H,et al.ASM:An adaptive simplification method for 3D point-based models[J].Comprter-aided design,2010,42(7):598-612.

[15] SHI B Q,LIANG J,LIU Q.Adaptive simplification of point cloud using k-means clustering[J].Computer-aided design,2011,43(8):910-922.

[16] FENG H M.Particle swarm optimization learning fuzzy system design[C]//Proceedings of the third international conference on information technology and applications.[s.l.]:ICITA,2001:101-106.