史旭棟，高岳林

(1.寧夏大學(xué)數(shù)學(xué)統(tǒng)計(jì)學(xué)院，寧夏銀川 750021；2.北方民族大學(xué)信息與系統(tǒng)科學(xué)研究所，寧夏銀川 750021)

隨著3D激光技術(shù)的發(fā)展，點(diǎn)云在3D形狀中有許多應(yīng)用[1-2]。然而，現(xiàn)代3D激光掃描儀能產(chǎn)生包括數(shù)百萬的采樣點(diǎn)的點(diǎn)云集[3],但是要求超大存儲(chǔ)空間和長(zhǎng)時(shí)間的后處理。因此，必須簡(jiǎn)化冗余數(shù)據(jù)來提高精度和曲面重構(gòu)的效率。研究者一直致力于點(diǎn)云的簡(jiǎn)化。一般來說，點(diǎn)云簡(jiǎn)化包括傳統(tǒng)和自適應(yīng)的簡(jiǎn)化方法。點(diǎn)云掃描線類型的傳統(tǒng)簡(jiǎn)化方法主要包括平均距離、最小距離、角偏差和弦偏差方法[4-7]，但這些方法效率較低。

最近，3D激光掃描儀被用于掃描糧倉、煤堆和礦井等大型物體[8-11]。由于曲率變化小和細(xì)節(jié)變化小等特性，大型物體的點(diǎn)云簡(jiǎn)化方法與中小型物體的方法不同。 此外，不可能用上述提到的單一傳統(tǒng)方法。因此，學(xué)者們開始研究自適應(yīng)簡(jiǎn)化的方法。對(duì)于空間維數(shù)較低的點(diǎn)云數(shù)據(jù)，F(xiàn)errari等[12]采用一種指定減少率來自動(dòng)地簡(jiǎn)化矢量點(diǎn)云數(shù)據(jù)。對(duì)于指定減少率，Song等[13]用原始輸入數(shù)據(jù)集搜索子集的方法來簡(jiǎn)化點(diǎn)云數(shù)據(jù)。Yu等[14]提出一種基于模糊k-均值聚類法的自適應(yīng)3D點(diǎn)云簡(jiǎn)化方法。Shi等[15]提出一種自適應(yīng)簡(jiǎn)化方法，這種方法保證點(diǎn)云數(shù)據(jù)邊界的完整性和分布的合理性。也有研究者提出一種基于Akima插值的簡(jiǎn)化方法[16],針對(duì)存儲(chǔ)糧堆，點(diǎn)云數(shù)據(jù)的簡(jiǎn)化方法有待進(jìn)一步研究。筆者針對(duì)一種智能實(shí)用的點(diǎn)云數(shù)據(jù)簡(jiǎn)化算法，提出了一種基于雞群優(yōu)化(CSO)的自適應(yīng)點(diǎn)云簡(jiǎn)化算法，將CSO引入平均距離方法根據(jù)原始點(diǎn)的密度自適應(yīng)地調(diào)整點(diǎn)集而縮小掃描線的間隔，并通過使用3D點(diǎn)云掃描糧倉中糧堆表面驗(yàn)證了算法的有效性。

1 材料與方法

1.13D激光掃描儀的測(cè)量原則3D激光掃描儀由水平調(diào)節(jié)模塊、數(shù)據(jù)采集單元、中央控制器、旋轉(zhuǎn)控制模塊和掃描器設(shè)計(jì)的。激光掃描儀上安裝了一個(gè)波長(zhǎng)為905 nm的一流安全激光裝置，其掃描誤差為7 mm/50 m，掃描直徑為100 m。激光掃描儀安裝在糧倉的橫梁上，從上面掃描大塊的谷物表面。另外，發(fā)動(dòng)機(jī)可以讓掃描儀進(jìn)行270°旋轉(zhuǎn)，所以掃描儀可以一次掃描谷堆表面完整的圖像。之后激光掃描發(fā)射激光信號(hào)來測(cè)量目標(biāo)，在被測(cè)物體上出現(xiàn)漫反射后立即返回接收器。根據(jù)上述過程所需要的時(shí)間，掃描儀可以從掃描儀本身計(jì)算到掃描點(diǎn)的距離P,同時(shí)可以測(cè)量水平掃描角φ和垂直掃描角ω,利用上述變量，按以下公式計(jì)算三維坐標(biāo)的掃描點(diǎn)：

(1)

1.2數(shù)據(jù)收集試驗(yàn)是在玉米倉庫中進(jìn)行的，糧食存儲(chǔ)的環(huán)境溫度為16 ℃，濕度為61%。用水平調(diào)節(jié)模塊調(diào)節(jié)掃描儀避免了掃描儀內(nèi)的坐標(biāo)系和糧倉的坐標(biāo)系的交叉角和掃描精度下降。掃描儀的默認(rèn)設(shè)置是將初始掃描點(diǎn)歸零，來保證在同一標(biāo)準(zhǔn)下測(cè)量糧食的體積，從而易于比較和分析。利用點(diǎn)云數(shù)據(jù)的測(cè)試結(jié)果來選擇掃描速度和點(diǎn)擊細(xì)分設(shè)置。具體的掃描參數(shù)如下；掃描速度10°/s;掃描最初位置為零刻度點(diǎn)；電機(jī)細(xì)分設(shè)置1/4；掃描旋轉(zhuǎn)角度為270°。掃描儀與遠(yuǎn)程主機(jī)相連，在掃描整個(gè)糧倉之后，將掃描數(shù)據(jù)存儲(chǔ)在上位機(jī)的緩沖存儲(chǔ)器中。共進(jìn)行8組試驗(yàn)。每組掃描3次，共獲得24個(gè)點(diǎn)云數(shù)據(jù)。

1.3基于CSO的簡(jiǎn)化算法描述

1.3.1雞群算法的簡(jiǎn)單描述。雞群優(yōu)化算法是一個(gè)新的智能優(yōu)化算法，它模擬雞群的行為和等級(jí)制度。在該算法中，雞群被分為若干個(gè)組，每個(gè)組是由1只公雞、若干個(gè)母雞和小雞組成。假設(shè)Ng、NH、NC、NM分別表示公雞、母雞、小雞和母雞媽媽的數(shù)量。最好的NR假設(shè)為公雞，最差的Nc假設(shè)為小雞，其余的都是母雞。在N只雞的雞群中，用xij(t)表示第t代中第i只雞的第j維分量，pxij表示第i只雞的最優(yōu)位置[16]。

不同的雞遵循不同的運(yùn)動(dòng)規(guī)律，適應(yīng)度較好的公雞比較差的公雞更接近食物，其位置更新公式如下：

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

(2)

(3)

式中，randn(0,σ2)是均值為0，方差為σ2的高斯分布;ε是一個(gè)極小量;k是公雞群中不為i的隨機(jī)數(shù);f是x所對(duì)應(yīng)的適應(yīng)度值。

母雞的更新公式如下：

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]之間的隨機(jī)數(shù)；r1表示第i只母雞所在子雞群的公雞;r2表示隨機(jī)從雞群中挑選1只，并且r1≠r2。

小雞的更新公式如下：

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

(7)

式中，m是第i只小雞的母雞;F是[0,2]之間的隨機(jī)數(shù)。

1.3.2基于CSO的簡(jiǎn)化算法描述。在每次掃描過程中，掃描儀的安裝位置、糧倉的形狀和糧堆的表面都沒有改變。 掃描儀和測(cè)量點(diǎn)的距離和角度不同，可能會(huì)導(dǎo)致點(diǎn)云數(shù)據(jù)測(cè)出得糧食堆兩邊稀疏、中間密集。然而，對(duì)于谷堆表明這種大的物體而言，平均距離法不能根據(jù)原始點(diǎn)云數(shù)據(jù)的密度而縮小點(diǎn)的間隔。因此，該研究將CSO引入平均距離法。

CSO是元啟發(fā)式的群智能優(yōu)化算法?；贑SO的簡(jiǎn)化算法可以自適應(yīng)地調(diào)節(jié)掃描線的間隔。它隨時(shí)根據(jù)點(diǎn)云數(shù)據(jù)的密度更新掃描線的縮減間隔，最后輸出簡(jiǎn)化后的點(diǎn)云數(shù)據(jù)集。其算法步驟如下。

步驟1：提取點(diǎn)云數(shù)據(jù)的坐標(biāo)信息(xi,yi,zi),i=1,2,3,…,m。

(8)

步驟3：取掃描線k，得到這些點(diǎn)減少間隔的闕值ηk(3δk>ηk-1>0.3δk)，最后判斷平均減少間隔是否超過間隔闕值。如果超過轉(zhuǎn)步驟4，否則，轉(zhuǎn)步驟7。

步驟4：建立最優(yōu)化的數(shù)學(xué)模型，利用CSO確定最優(yōu)平均下降間隔。

步驟5：計(jì)算適應(yīng)度，根據(jù)每只雞的適應(yīng)度求得gbest。

步驟6：如果滿足終止條件，則輸出最優(yōu)解gbest，否則轉(zhuǎn)步驟5。

步驟7：利用自適應(yīng)最優(yōu)減少間隔來減少掃描線上的點(diǎn)，輸出減少后點(diǎn)云數(shù)據(jù)。

步驟8：如果掃描線全部簡(jiǎn)化，則跳出程序，否則轉(zhuǎn)步驟2。

最優(yōu)化的適應(yīng)度函數(shù)可以由以下公式計(jì)算：

fitness(X)=

(9)

算法的初始參數(shù)如下：雞群規(guī)模N為40；公雞、母雞和小雞的比例為2∶6∶2；媽媽母雞的比例為0.1；小雞跟隨系數(shù)FL為(0,2)；最大迭代次數(shù)為500；初始減少間隔(η0/mm)為0.1。

2 結(jié)果與分析

簡(jiǎn)化的糧堆表面點(diǎn)云數(shù)據(jù)反映了糧堆表面的特征。為了得到糧堆表面，該研究使用Delaunay triangulation方法來重建點(diǎn)云數(shù)據(jù)。由于Delaunay triangulation是使用一系列連通但不重疊的三角形集合來重建，所以該方法適用于數(shù)據(jù)密集分布、數(shù)據(jù)冗余較小并且存儲(chǔ)效率較高的點(diǎn)云數(shù)據(jù)。

利用CSO簡(jiǎn)化點(diǎn)云數(shù)據(jù)的方法的平均時(shí)間為1 523 s。然而用平均簡(jiǎn)化方法簡(jiǎn)化的點(diǎn)云數(shù)據(jù)時(shí)間的平均值為5 871 s。 結(jié)果表明，點(diǎn)云數(shù)據(jù)簡(jiǎn)化性能在后期表面重建上效果較好，特別是數(shù)據(jù)較大時(shí)。更少的數(shù)據(jù)和更均勻的點(diǎn)云數(shù)據(jù)將得到更短的時(shí)間和更好的表面重建性能。這也說明需要為密集點(diǎn)云數(shù)據(jù)設(shè)計(jì)一種更有效簡(jiǎn)化算法。

相比平均距離法，該研究所提出的算法計(jì)算出的糧堆體積更接近實(shí)際糧堆體積，表1給出了結(jié)果。均方根誤差反映了個(gè)體離散度，由式(10)給出：

(10)

表1不同算法對(duì)糧堆體積估算的比較

Table1Comparisonofgrainvolumeestimationbydifferentalgorithms

算法Algo-rithm組號(hào)GroupNo.簡(jiǎn)化點(diǎn)的數(shù)目Thenumberofsimplifiedpoint計(jì)算玉米的體積Thevolumeofcalculatedcorn∥m3相對(duì)誤差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 結(jié)論

提出了一種基于CSO的點(diǎn)云簡(jiǎn)化算法，該算法能夠自適應(yīng)地調(diào)節(jié)掃描線的平均距離，解決了原始點(diǎn)云數(shù)據(jù)量大和分布不均勻的問題。利用該算法可使分布更加均勻、簡(jiǎn)化。該研究所提出的算法是一種可以代替平均距離法解決存貯糧食體積問題的簡(jiǎn)單和實(shí)用的方法。

[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] 陳璋雯,達(dá)飛鵬.基于模糊熵迭代的三維點(diǎn)云精簡(jiǎn)算法[J].光學(xué)學(xué)報(bào),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] 徐偉恒,馮仲科,蘇志芳,等.一種基于三維激光點(diǎn)云數(shù)據(jù)的單木樹冠投影面積和樹冠體積自動(dòng)提取算法[J].光譜學(xué)與光譜分析,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.