基于雞群優化算法的點云簡化算法在糧堆檢測中的應用

史旭棟，高岳林

(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是元啟發式的群智能優化算法?；贑SO的簡化算法可以自適應地調節掃描線的間隔。它隨時根據點云數據的密度更新掃描線的縮減間隔，最后輸出簡化后的點云數據集。其算法步驟如下。

步驟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.