面向立木識(shí)別的有效K-均值聚類算法研究

王亞雄 康 峰 李文彬 文 劍 鄭永軍

(1.北京林業(yè)大學(xué)工學(xué)院， 北京 100083； 2.中國農(nóng)業(yè)大學(xué)工學(xué)院， 北京 100083)

面向立木識(shí)別的有效K-均值聚類算法研究

王亞雄1康 峰1李文彬1文 劍1鄭永軍2

(1.北京林業(yè)大學(xué)工學(xué)院， 北京 100083； 2.中國農(nóng)業(yè)大學(xué)工學(xué)院， 北京 100083)

針對(duì)林區(qū)自動(dòng)對(duì)靶施藥過程中，當(dāng)立木生長密集時(shí)，獲取的點(diǎn)云數(shù)據(jù)聚類準(zhǔn)確率低、效率低的問題，提出優(yōu)化后的K-均值聚類算法，數(shù)據(jù)獲取方式基于2D激光掃描。針對(duì)立木點(diǎn)云信息聚類前需對(duì)相關(guān)數(shù)據(jù)進(jìn)行濾波，提出窗口濾波算法，選取產(chǎn)生混合像素點(diǎn)的樹干邊緣，提取3次連續(xù)掃描的混合像素及其近鄰點(diǎn)組成濾波窗口，進(jìn)行最大閾值濾波，結(jié)果顯示50次試驗(yàn)中僅有2個(gè)混合像素點(diǎn)未被濾除，混合噪聲的濾除率高。在K-均值算法優(yōu)化方面，針對(duì)算法需預(yù)先確定聚類數(shù)和初始聚類中心的不足，提出利用斜率變化確定聚類數(shù)的方法，試驗(yàn)對(duì)5個(gè)不同距離下5組立木分別進(jìn)行100次測(cè)量，結(jié)果顯示錯(cuò)誤測(cè)量次數(shù)僅為3次，并可在試驗(yàn)前期通過人工方式去除，算法合理有效；對(duì)哈夫曼樹法確定立木掃描點(diǎn)聚類中心的性能進(jìn)行了試驗(yàn)分析，3種不同樹干分布類型下分別運(yùn)用隨機(jī)抽樣法和哈夫曼樹法進(jìn)行K-均值聚類，前者平均正確率僅為76.4%，后者則為95.5%；同時(shí)分析了Ⅰ型分布下2種算法聚類的迭代次數(shù)和耗時(shí)，5個(gè)不同距離下，隨機(jī)抽樣法的平均迭代次數(shù)明顯高于哈夫曼樹法，平均運(yùn)行耗時(shí)上，哈夫曼樹法則高于隨機(jī)抽樣法，前者變化范圍為120～220 ms，后者為50～85 ms，該范圍為林區(qū)測(cè)繪的可接受范圍。試驗(yàn)證明，基于斜率變化確定聚類數(shù)和基于哈夫曼樹法確定聚類中心的K-均值算法是林區(qū)立木點(diǎn)云聚類的有效算法，可應(yīng)用于林區(qū)的立木檢測(cè)。

立木識(shí)別； 點(diǎn)云數(shù)據(jù)；K-均值聚類算法； 窗口濾波算法； 哈夫曼樹法

引言

林區(qū)立木信息的采集與前期處理是林業(yè)領(lǐng)域的重要研究內(nèi)容，如精準(zhǔn)對(duì)靶施藥[1-2]、林木采伐[3]、林業(yè)測(cè)繪[4]、植株信息分類[5]、森林火災(zāi)預(yù)測(cè)[6]、森林植物地帶劃分[7]、苗木質(zhì)量分級(jí)[8]等。其中對(duì)獲取的立木信息如何進(jìn)行有效聚類是該過程的關(guān)鍵環(huán)節(jié)，對(duì)確定立木的形態(tài)與位置信息具有重要意義。聚類是把一個(gè)數(shù)據(jù)對(duì)象(或觀測(cè))劃分成子集的過程，每個(gè)子集是一個(gè)簇，使得簇中的對(duì)象彼此相似[9]。目前立木信息聚類的常用方法主要有毗連點(diǎn)距離法、系統(tǒng)聚類法[10]、區(qū)域分割法[11]以及K-均值算法等。毗連點(diǎn)距離法算法簡(jiǎn)單，僅在數(shù)據(jù)量較小且分布簡(jiǎn)單時(shí)適用，且對(duì)異常點(diǎn)敏感；系統(tǒng)聚類法可根據(jù)不同距離類別實(shí)現(xiàn)具體聚類要求，并且可生成直觀聚類譜系圖，但分類過程需人工干預(yù)；區(qū)域分割法依據(jù)概率方法進(jìn)行樹干簇?cái)?shù)判定，算法簡(jiǎn)便可行，但準(zhǔn)確性不高，可能導(dǎo)致誤判和漏判。相比上述3種算法，K-均值算法作為聚類分析中的經(jīng)典算法，具有簡(jiǎn)單、高效、時(shí)間復(fù)雜度低等特性[12-13]，除了應(yīng)用于農(nóng)林業(yè)方面[14-15]外，也常用于文檔聚類[16]、圖像分割[17]等領(lǐng)域。

但K-均值算法同時(shí)存在缺點(diǎn)：需要預(yù)先確定聚類數(shù)和初始聚類中心，且對(duì)初始聚類中心敏感，易陷入局部極小。在聚類數(shù)的確定方面，周世兵等[18]提出的聚類數(shù)法原理較為復(fù)雜，運(yùn)用到樹干點(diǎn)云數(shù)據(jù)分析時(shí)時(shí)間開銷大；王勇等[19]通過樣本數(shù)據(jù)分層得到聚類數(shù)搜索范圍的上界，并設(shè)計(jì)聚類有效性指標(biāo)來評(píng)價(jià)聚類后類內(nèi)與類間的相似性程度，從而在聚類數(shù)搜索范圍內(nèi)獲得最佳聚類數(shù)，該方法能夠快速、高效地獲得最佳聚類數(shù)，對(duì)數(shù)據(jù)集聚類效果良好，適用于數(shù)據(jù)量較大時(shí)的聚類分析，但運(yùn)用于樹干點(diǎn)云數(shù)據(jù)的分簇上耗時(shí)較多。在初始聚類中心選取上，當(dāng)林區(qū)立木生長較密集時(shí)，常用的隨機(jī)抽樣法由于其隨機(jī)性而使選取的聚類中心理想情況較少，導(dǎo)致結(jié)果不穩(wěn)定，使算法陷入局部最優(yōu)。

本研究探索運(yùn)用K-均值算法對(duì)林區(qū)二維立木橫截面點(diǎn)云進(jìn)行高效聚類的優(yōu)化，服務(wù)于林區(qū)自動(dòng)對(duì)靶施藥系統(tǒng)[1]。針對(duì)K-均值算法上述的不足，當(dāng)林區(qū)立木生長較密集時(shí)對(duì)其進(jìn)行如下優(yōu)化：提出基于斜率變化的聚類數(shù)確定方法；運(yùn)用哈夫曼樹法(Huffman tree method)確定初始聚類中心。此外，在前期數(shù)據(jù)濾波部分提出窗口濾波算法。對(duì)以上優(yōu)化方案分別進(jìn)行室內(nèi)試驗(yàn)驗(yàn)證，以期在可接受的耗時(shí)范圍內(nèi)對(duì)樹干截面點(diǎn)云進(jìn)行準(zhǔn)確濾波及聚類，以便精確確定立木截面形態(tài)及位置，從而進(jìn)行精準(zhǔn)施藥。

1 優(yōu)化模型建立

本研究利用二維激光掃描儀獲取林區(qū)立木信息，獲取的點(diǎn)云數(shù)據(jù)信息量較大，但這些數(shù)據(jù)并非完全包含有用信息，需首先對(duì)數(shù)據(jù)進(jìn)行濾波，濾波后得到的數(shù)據(jù)為包含有用信息的數(shù)據(jù)集。對(duì)該數(shù)據(jù)集運(yùn)用優(yōu)化后的K-均值聚類算法分成不同的簇，繼而在分簇后的數(shù)據(jù)上進(jìn)行擬合，提取出樹干有效定位識(shí)別信息。

1.1 林區(qū)立木信息的濾波

對(duì)獲取的立木掃描數(shù)據(jù)進(jìn)行聚類處理前，首先需要對(duì)點(diǎn)云數(shù)據(jù)集進(jìn)行濾波，以消除異常點(diǎn)對(duì)聚類精確度的影響，從而可相對(duì)準(zhǔn)確地獲取立木特征(直徑和相對(duì)中心位置)。二維激光掃描儀獲取的數(shù)據(jù)需要最終保留完全投影于樹干上的點(diǎn)。圖1所示為濾波前的點(diǎn)云數(shù)據(jù)圖，掃描數(shù)據(jù)中的噪聲點(diǎn)主要由2部分構(gòu)成：因距離產(chǎn)生的噪聲，如區(qū)域A，通常為背景障礙物；混合像素產(chǎn)生的噪聲，如區(qū)域B所示6個(gè)掃描點(diǎn)(標(biāo)號(hào)1～6)。混合像素產(chǎn)生機(jī)理詳見文獻(xiàn)[4]，此處不再贅述。本研究主要濾除上述2部分噪聲數(shù)據(jù)，此外，在測(cè)試過程中還可能產(chǎn)生環(huán)境噪聲，一般采用人工方式去除，如選擇適宜天氣、加裝濾光鏡等。對(duì)于區(qū)域A，可通過距離閾值法濾除[20]，而區(qū)域B，部分文獻(xiàn)運(yùn)用弦高閾值法[21]濾除，但該方法無法確定兩次相鄰掃描時(shí)刻的關(guān)聯(lián)性，即在連續(xù)掃描過程中，某次掃描的返回?cái)?shù)據(jù)無法與其相鄰兩次掃描數(shù)據(jù)進(jìn)行對(duì)比，導(dǎo)致處理結(jié)果不理想。

圖1 掃描3株樹干濾波前的點(diǎn)云Fig.1 Point cloud before filtering when scanning three tree trunks

針對(duì)該問題，本文運(yùn)用一種動(dòng)態(tài)自適應(yīng)濾波算法對(duì)混合像素點(diǎn)進(jìn)行濾除[22-23]。該方法原理如下： 激光掃描儀對(duì)立木數(shù)據(jù)的采集為連續(xù)多次掃描。同一掃描角度上，相鄰掃描時(shí)刻的測(cè)量值具有相關(guān)性；同一次掃描中，相鄰掃描角度的測(cè)量值也具有相關(guān)性。對(duì)任一距離下測(cè)量值ρ和掃描角度λ組成的極坐標(biāo)(ρi, j，λi, j)建立矩陣窗口

其中i為激光測(cè)距的采樣編號(hào)，即第i次掃描(i為正整數(shù)，且i>1)；j為對(duì)應(yīng)某次掃描的不同測(cè)量點(diǎn)編號(hào)(j為正整數(shù)，且j>1)。

以上9個(gè)測(cè)量值具有時(shí)間與空間的最大相關(guān)性，在該矩陣窗口中計(jì)算ρi,j與鄰近測(cè)量值之差Δρmin。

Δρmin=min{|ρt+i,s+j-ρi,j|，

t,s=-1,0,1 &t≠0,s=0 &t=0,s≠0}

(1)

當(dāng)Δρmin>σ(ρ)(σ(ρ)為測(cè)量值可接受的鄰近差值的閾值，依據(jù)實(shí)際環(huán)境利用不同距離范圍下的標(biāo)準(zhǔn)差估計(jì))，測(cè)量值ρi,j被視為混合像素測(cè)量噪聲，對(duì)其進(jìn)行濾除。本文所述試驗(yàn)中σ(ρ)設(shè)置為30 mm，依據(jù)相鄰掃描時(shí)刻及掃描角度下相關(guān)數(shù)據(jù)點(diǎn)的距離標(biāo)準(zhǔn)差獲取，并預(yù)先設(shè)定試驗(yàn)使用的距離范圍。

1.2 針對(duì)林區(qū)立木識(shí)別的K-均值模型優(yōu)化

聚類為濾波后進(jìn)行的數(shù)據(jù)處理，如圖2所示，掃描數(shù)據(jù)點(diǎn)為完全投影于樹干上的點(diǎn)云。對(duì)于精準(zhǔn)對(duì)靶施藥而言，首先需對(duì)濾波后的點(diǎn)云進(jìn)行分簇，進(jìn)而對(duì)屬于同一樹干的點(diǎn)云簇進(jìn)行擬合。針對(duì)所述當(dāng)前聚類方式的不足，本文根據(jù)目標(biāo)樹干的具體情況提出提前確定聚類簇?cái)?shù)及初始聚類中心的K-均值算法。

圖2 掃描3株樹干濾波后的點(diǎn)云Fig.2 Point cloud after filtering when scanning three tree trunks

K-均值算法屬于劃分聚類算法，其中每個(gè)簇的中心都用簇中所有對(duì)象的均值來表示。輸入為簇的數(shù)目(K)與包含n個(gè)對(duì)象的數(shù)據(jù)集(D)；輸出為K個(gè)簇的集合。

算法流程：

(1)從D中任意選擇K個(gè)對(duì)象作為初始聚類中心。

(2)根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象分配到最相似的簇。

(3)更新簇均值，即重新計(jì)算每個(gè)簇中對(duì)象的均值。

(4)循環(huán)步驟(2)、(3)，直到聚類不再發(fā)生變化。

提前確定聚類數(shù)和初始聚類中心是K-均值聚類法的特點(diǎn)，但在實(shí)際林區(qū)立木檢測(cè)中，依靠人工觀測(cè)確定聚類數(shù)目以及隨機(jī)抽樣法確定聚類中心的常規(guī)方法費(fèi)時(shí)多且聚類中心確定的正確率低。針對(duì)該問題本文提出基于斜率變化確定聚類數(shù)的方法，聚類中心的確定則采用哈夫曼樹法。

1.2.1 基于斜率變化的聚類數(shù)確定方法

本文的研究對(duì)象為林區(qū)活立木，斜率變化法主要在視野內(nèi)無遮擋的情況下根據(jù)樹干上相鄰掃描數(shù)據(jù)點(diǎn)斜率變化的關(guān)系得出點(diǎn)云數(shù)據(jù)的簇?cái)?shù)K。如圖2所示，各樹干上的掃描點(diǎn)云呈弧形均布于面向激光的位置，而相鄰兩點(diǎn)的斜率逆時(shí)針方向必然有從負(fù)向正的變化過程，將這樣一個(gè)過程進(jìn)行一次數(shù)據(jù)記錄，總的變化數(shù)目即為點(diǎn)云數(shù)據(jù)集的簇?cái)?shù)K。

1.2.2 基于哈夫曼樹法的聚類中心確定方法

初始聚類中心的選取采用基于哈夫曼樹的思想(簡(jiǎn)稱HTM)。HTM簡(jiǎn)單來說是帶權(quán)路徑長度之和最小的二叉樹，也稱最優(yōu)二叉樹[24]，主要應(yīng)用于通信數(shù)據(jù)編碼[25]及圖形與文檔壓縮[26-27]等技術(shù)上。算法的構(gòu)造思想如下：

假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)。n個(gè)權(quán)值分別設(shè)為w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：

(1)將w1、w2、…、wn看成有n棵樹的森林(每棵樹僅有一個(gè)結(jié)點(diǎn))。

(2)在森林中選出兩個(gè)根結(jié)點(diǎn)權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和。

(3)從森林中刪除選取的兩棵樹，并將新樹加入森林。

(4)重復(fù)步驟(2)、(3)，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

由哈夫曼樹帶權(quán)路徑長度之和最小的性質(zhì)，可將該方法應(yīng)用于K-均值聚類初始中心的選取上，根結(jié)點(diǎn)的合并方法基于對(duì)象間的相異性度量，數(shù)據(jù)間的相異性度量采用相異性矩陣表示。相異性矩陣采用存放n個(gè)對(duì)象兩兩之間的鄰近度，通常用一個(gè)n×n矩陣表示。

其中d(i,j)為對(duì)象i、j之間的相異性度量。

一般d(i,j)非負(fù)，對(duì)象i和j彼此高度相似或“接近”時(shí)，其值接近于零；而越不同，該值越大。在本研究中，數(shù)據(jù)對(duì)象為二維數(shù)據(jù)點(diǎn)，數(shù)據(jù)間的相異性距離度量采用歐氏距離。

圖3 3種不同類型的樹干位置分布Fig.3 Three different types of trunks position distribution

根據(jù)HTM的思想，基于數(shù)據(jù)相異度，在本研究中將獲取的林區(qū)立木數(shù)據(jù)樣本構(gòu)造成一棵樹。為保證數(shù)據(jù)的近鄰性，采用左右結(jié)點(diǎn)的算術(shù)平均值(本研究中指相鄰掃描點(diǎn)的中點(diǎn))作為新的二叉樹根結(jié)點(diǎn)的值。然后按構(gòu)造結(jié)點(diǎn)的逆序找到K-1個(gè)結(jié)點(diǎn)，去掉這K-1個(gè)結(jié)點(diǎn)可將該樹分為K個(gè)子樹，這K個(gè)子樹的平均值即初始的K個(gè)聚類中心點(diǎn)，對(duì)其按照K-均值算法進(jìn)行聚類。該方法可在理論上獲取全局最優(yōu)解。

2 試驗(yàn)設(shè)計(jì)與方法

2.1 試驗(yàn)系統(tǒng)

本研究采用德國SICK公司生產(chǎn)的LMS511 20100PRO型激光掃描雷達(dá)。在試驗(yàn)中激光掃描雷達(dá)作為服務(wù)器，客戶端為一臺(tái)Dell E5400型便攜式計(jì)算機(jī)，服務(wù)器與客戶端之間通過以太網(wǎng)進(jìn)行通信。該掃描雷達(dá)的掃描范圍為-5°～185°，試驗(yàn)設(shè)置為30°～150°，角分辨率設(shè)為0.333°，對(duì)應(yīng)掃描頻率為50 Hz。最大探測(cè)距離為26 m，本試驗(yàn)設(shè)定為10 m。

試驗(yàn)用到的各算法程序加載于版本號(hào)為基于哈夫曼樹法確定初始聚類中心的林用K-均值算法軟件V1.0上[28]，軟件在Windows XP環(huán)境下基于C/C++語言開發(fā)，使用MFC框架。

驗(yàn)證試驗(yàn)在室內(nèi)進(jìn)行，樹干的分布設(shè)置為3種類型，如圖3所示，分別為Ⅰ型、Ⅱ型、Ⅲ型分布。其中Ⅰ型分布為距激光掃描儀1、2、3、4、5 m 5個(gè)不同距離下對(duì)應(yīng)放置3、3、5、5、7株樹干，使其均布于激光掃描儀前，如圖3a所示，圖中樹干中心距激光掃描儀3 m，該分布類型為距離對(duì)聚類準(zhǔn)確率的定量分析；Ⅱ型、Ⅲ型分布主要驗(yàn)證不同分布類型對(duì)聚類準(zhǔn)確率的影響，如圖3b、3c所示，樹干中心距激光掃描儀分別為2.5～3.5 m、1.5～3.5 m。3種分布類型下，樹干的直徑范圍均為50～350 mm。由于傳統(tǒng)隨機(jī)抽樣確定初始聚類中心的方法在樹干生長較密集時(shí)容易導(dǎo)致聚類準(zhǔn)確率降低，為檢測(cè)該情況下基于HTM聚類的準(zhǔn)確性，本試驗(yàn)的3種分布類型需確保較小的樹間間隔(小于40 mm)。

2.2 濾波試驗(yàn)

首先對(duì)立木樹干進(jìn)行連續(xù)數(shù)據(jù)采集找到視野中出現(xiàn)混合像素的樹干邊緣，測(cè)量混合像素及其2個(gè)相鄰掃描角度返回的距離數(shù)據(jù)，重復(fù)多次(40次以上)并記錄獲取的距離數(shù)值。應(yīng)用窗口濾波器進(jìn)行濾波處理，驗(yàn)證濾波效果。

完成混合像素?cái)?shù)據(jù)濾波后，運(yùn)用距離閾值法濾去遠(yuǎn)距離的點(diǎn)云噪聲，獲得僅屬于樹干部分的掃描點(diǎn)云。

2.3 聚類分析

首先運(yùn)用斜率控制法確定樹干分簇?cái)?shù)目，測(cè)量100次，統(tǒng)計(jì)簇?cái)?shù)確定的正確率，在此基礎(chǔ)上分別運(yùn)用隨機(jī)抽樣法(Random sampling method，RSM)與HTM進(jìn)行聚類中心的選取。其中，Ⅰ型分布各檢測(cè)距離下進(jìn)行3次采樣，每次采樣的聚類數(shù)目(即樹干個(gè)數(shù))相同，樹干直徑不同，Ⅱ型、Ⅲ型分布同樣進(jìn)行3次采樣，每次采樣的聚類數(shù)相同(本試驗(yàn)設(shè)定為5次)，樹干直徑不同。運(yùn)用K-均值算法分別依據(jù)2種算法確定的聚類中心對(duì)獲得的數(shù)據(jù)點(diǎn)進(jìn)行分簇，統(tǒng)計(jì)采樣數(shù)據(jù)的分簇正確率并比較2種算法的運(yùn)行時(shí)間及迭代次數(shù)。考慮到距離變化對(duì)結(jié)果的影響，運(yùn)行時(shí)間及迭代次數(shù)的分析主要針對(duì)Ⅰ型分布。

3 結(jié)果分析與討論

3.1 濾波實(shí)驗(yàn)結(jié)果分析

圖4所示為圖3中樹干B左側(cè)邊緣連續(xù)測(cè)量50次所得混合像素點(diǎn)及相鄰兩數(shù)據(jù)點(diǎn)的距離信息統(tǒng)計(jì)圖。從圖中可以得出，當(dāng)λ為62.33°時(shí)，光斑完全投影于樹干，返回值為樹干與激光掃描儀的距離；當(dāng)λ為63.00°時(shí)，光斑完全投影于背景墻壁，返回值為墻壁與激光掃描儀的距離；當(dāng)λ為62.67°時(shí)，光斑部分投射于背景墻壁，部分投射于樹干，返回的距離值界于兩者之間。由于每次掃描時(shí)激光光斑會(huì)有微小差別，因此在50次測(cè)量中，混合像素的距離不斷變化。運(yùn)用窗口濾波算法對(duì)該像素點(diǎn)進(jìn)行濾波后，獲得圖5所示數(shù)據(jù)，50次濾波中，只有2個(gè)數(shù)據(jù)點(diǎn)未被濾除，原因是2個(gè)數(shù)據(jù)點(diǎn)的距離小于閾值σ(ρ)。通過多次數(shù)據(jù)統(tǒng)計(jì)，該情況出現(xiàn)的概率小于0.5%，當(dāng)出現(xiàn)運(yùn)用濾波窗口無法濾去的噪聲點(diǎn)時(shí)，可配合弦高閾值法將其濾除。試驗(yàn)證明，運(yùn)用窗口濾波法可有效濾除混合像素點(diǎn)，濾除率大于99.5%，滿足林區(qū)測(cè)繪需求。

圖4 樹干B左側(cè)邊緣混合像素點(diǎn)濾除前的測(cè)距統(tǒng)計(jì)Fig.4 Distance statistics of mixed pixels on left edge of trunk B before they were filtered

圖5 樹干B左側(cè)邊緣混合像素點(diǎn)濾除后的測(cè)距統(tǒng)計(jì)Fig.5 Distance statistics of mixed pixels on left edge of trunk B after they were filtered

3.2 聚類試驗(yàn)結(jié)果分析

3.2.1 聚類數(shù)確定試驗(yàn)結(jié)果分析

運(yùn)用斜率變化法計(jì)算樹干聚類數(shù)目，針對(duì)Ⅰ型分布進(jìn)行，5個(gè)不同距離下均測(cè)試100次。數(shù)據(jù)顯示僅在距離為2、4 m時(shí)分別產(chǎn)生2次和1次錯(cuò)誤，原因是這些采樣中，由于樹干的布置關(guān)系，邊緣樹干在激光掃描視野中僅包含部分信息，導(dǎo)致相鄰掃描點(diǎn)斜率正負(fù)變化過程的缺失。產(chǎn)生該誤差時(shí)，只需合理調(diào)整激光的視野角度即可。

3.2.2K-均值聚類算法試驗(yàn)結(jié)果分析

表1所示為Ⅰ型分布下基于RSM與HTM的K-均值算法對(duì)比分析數(shù)據(jù)，5種不同距離不同聚類數(shù)目下RSM樣本聚類的平均正確率為72.5%，HTM為95.2%。表2所示為Ⅱ型、Ⅲ型分布下的算法對(duì)比分析數(shù)據(jù)，Ⅱ型分布RSM樣本聚類的平均正確率為77.9%，HTM為95.1%；Ⅲ型分布RSM為78.8%，HTM為96.2%。2種算法相比較，基于HTM進(jìn)行的聚類具有明顯優(yōu)勢(shì)，平均正確率為95.5%；RSM對(duì)初始聚類中心的選取具有一定的隨機(jī)性，正確選擇的概率較小，導(dǎo)致數(shù)據(jù)的錯(cuò)誤歸類，平均正確率僅為76.4%。根據(jù)表1，RSM聚類的錯(cuò)誤率隨聚類數(shù)目的增加有較明顯的增加趨勢(shì)，符合概率理論。其中采樣Y中，2 m處的正確率達(dá)到100%是由于該次抽樣恰好隨機(jī)選取了正確的聚類中心。而在本研究中HTM選取聚類中心的原理是基于數(shù)據(jù)間的歐氏距離分類，聚類中心選取的正確率較高。

提取距離為3 m時(shí)采樣X的數(shù)據(jù)樣本進(jìn)行分析，如圖6所示。5株樹干樣本點(diǎn)總量為63，T1～T5為人工聚類的5個(gè)簇，即樹干樣本點(diǎn)的真實(shí)聚類結(jié)果，與RSM、HTM 2種算法的聚類結(jié)果進(jìn)行對(duì)比。T1～T5相對(duì)應(yīng)的樣本點(diǎn)數(shù)分別為9、13、16、13、12，各簇樣本點(diǎn)分別屬于5株不同樹干，屬于不同簇的樣本點(diǎn)數(shù)量取決于樹干直徑。T′1～T′5為基于RSM的K-均值聚類結(jié)果，對(duì)應(yīng)的樣本點(diǎn)數(shù)分別為13、14、13、13、10，其中正確聚類的樣本個(gè)數(shù)為50，錯(cuò)誤聚類的樣本個(gè)數(shù)為13。對(duì)照簇T1～T5，T′1～T′5中錯(cuò)誤的聚類樣本分別為T′1簇的T′1-1～T′1-4、T′2簇的T′2-1～T′2-5、T′3簇的T′3-1～T′3-2以及T′4簇的T′4-1～T′4-2。T″1～T″5為基于HTM的K-均值聚類結(jié)果，對(duì)應(yīng)的樣本點(diǎn)數(shù)分別為9、13、15、15、11，錯(cuò)誤的聚類樣本僅為T″4簇的T″4-1和T″4-22個(gè)樣本點(diǎn)。以上數(shù)據(jù)說明對(duì)于林區(qū)立木截面二維掃描點(diǎn)云的聚類，基于HTM的K-均值聚類算法優(yōu)于基于RSM的K-均值聚類算法。

表1 Ⅰ型分布下基于隨機(jī)抽樣法(RSM)與哈夫曼樹法(HTM)的K-均值算法對(duì)比分析Tab.1 Contrastive analysis of K-means algorithm based on random sampling method (RSM) and Huffman tree method (HTM) at type I distribution

表2 Ⅱ型、Ⅲ型分布下基于隨機(jī)抽樣法(RSM)與哈夫 曼樹法(HTM)的K-均值算法對(duì)比分析(聚類數(shù)5)Tab.2 Contrastive analysis of K-means algorithm based on random sampling method (RSM) and Huffman tree method (HTM) at type Ⅱ and type Ⅲ distributions (five clusters)

圖6 距離為3 m時(shí)采樣X的聚類結(jié)果Fig.6 Clustering result of sampling X at distance of 3 m

在Ⅰ型分布下對(duì)基于RSM與HTM的K-均值聚類算法進(jìn)行3次采樣并取迭代次數(shù)的平均值進(jìn)行對(duì)比分析，如圖7所示。圖中數(shù)據(jù)說明，RSM由于選取初始聚類中心的隨機(jī)性，導(dǎo)致迭代次數(shù)的出現(xiàn)也呈隨機(jī)性，在本試驗(yàn)中，其值為4～8次；而HTM由于初始聚類中心選擇的準(zhǔn)確性較高，因而運(yùn)用K-均值算法對(duì)樣本進(jìn)行聚類時(shí)的迭代次數(shù)總體偏少，其值為1～7次，且HTM的迭代次數(shù)隨聚類數(shù)的增加呈遞增趨勢(shì)。

圖7 基于RSM與HTM的K-均值算法迭代次數(shù)Fig.7 Iterations of K-means algorithm based on RSM and HTM

圖8 基于RSM與HTM的K-均值算法耗時(shí)Fig.8 Time-consuming of K-means algorithm based on RSM and HTM

2種算法的耗時(shí)平均值如圖8所示(計(jì)算機(jī)配置：Dell E5400, Intel(R) Core(TM) 2 Duo CPU P8700 @ 2.53 GHz, 3.45 GB RAM)，基于RSM的K-均值算法耗時(shí)明顯低于HTM，前者為50～85 ms，后者為120～220 ms。由2種算法的原理可知，HTM初始聚類中心選取的耗時(shí)大于RSM，而基于RSM的K-均值聚類迭代耗時(shí)卻大于HTM，前者的差值大于后者，因而對(duì)2種算法總的耗時(shí)進(jìn)行對(duì)比時(shí)，HTM

明顯大于RSM。另外迭代次數(shù)與耗時(shí)還與樣本數(shù)量相關(guān)，由于林區(qū)環(huán)境下激光掃描儀可識(shí)別的最遠(yuǎn)距離范圍內(nèi)樣本數(shù)量相對(duì)較少，HTM的耗時(shí)在林區(qū)測(cè)繪可接受的數(shù)值范圍內(nèi)，因而本文暫不分析樣本數(shù)量與聚類數(shù)目對(duì)迭代次數(shù)與耗時(shí)的影響。

4 結(jié)束語

主要分析了林區(qū)立木生長較密集時(shí)，基于二維激光掃描的有效信息聚類方法，即基于HTM確定初始聚類中心和基于斜率變化確定聚類數(shù)的K-均值聚類算法。對(duì)激光掃描儀獲取的原始數(shù)據(jù)采用窗口濾波算法對(duì)異常點(diǎn)進(jìn)行了有效濾除，濾除率大于99.5%，進(jìn)而對(duì)比分析了HTM與RSM對(duì)初始聚類中心選取的有效性，同時(shí)分析了基于2種算法的迭代次數(shù)與耗時(shí)。分析結(jié)果顯示，基于斜率變化法確定聚類數(shù)的正確率接近100%，基于HTM的K-均值聚類正確率高于95%，而基于RSM的聚類正確率不足80%。基于HTM的K-均值聚類迭代次數(shù)較少，但是耗時(shí)較高，在本研究Ⅰ型分布的3次采樣中，數(shù)據(jù)樣本介于40～100之間，5種距離下平均耗時(shí)介于120～220 ms之間，屬于林區(qū)數(shù)據(jù)采集可接受的耗時(shí)范圍。可以得出基于斜率變化確定聚類數(shù)與基于HTM確定初始聚類中心的K-均值法為林區(qū)立木點(diǎn)云聚類分析的一種有效算法，可應(yīng)用于林區(qū)自動(dòng)對(duì)靶施藥系統(tǒng)及林業(yè)測(cè)繪等領(lǐng)域。

1 KANG F, PIERCE F J, WALSH D B, et al. An automated trailer sprayer system for targeted control of cutworm in vineyards [J]. Transactions of the ASABE, 2012, 55(5): 2007-2014.

2 姜紅花，白鵬，劉理民，等. 履帶自走式果園自動(dòng)對(duì)靶風(fēng)送噴霧機(jī)研究[J/OL].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2016，47(增刊)：189-195.http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=2016s029&journal_id=jcsam.DOI:10.6041/j.issn.1000-1298.2016.S0.029. JIANG Honghua, BAI Peng, LIU Limin, et al. Caterpillar self-propelled and air-assisted orchard sprayer with automatic target spray system [J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2016, 47(Supp.): 189-195. (in Chinese)

3 ZHENG Y L, LIU J H, WANG D, et al. Laser scanning measurements on trees for logging harvesting operations [J]. Sensors, 2012, 12(7): 9273-9285.

4 王亞雄，康峰，李文彬，等. 基于2D激光探測(cè)的立木胸徑幾何算法優(yōu)化[J/OL].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2016，47(6)：290-296. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20160638&journal_id=jcsam.DOI:10.6041/j.issn.1000-1298.2016.06.038. WANG Yaxiong, KANG Feng, LI Wenbin, et al. Optimization of geometry algorithm for DBH of standing tree on 2D laser detection [J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2016, 47(6): 290-296. (in Chinese)

5 屈洋，周瑜，王釗，等. 苦蕎產(chǎn)區(qū)種質(zhì)資源遺傳多樣性和遺傳結(jié)構(gòu)分析[J].中國農(nóng)業(yè)科學(xué)，2016，49(11)：2049-2062. QU Yang, ZHOU Yu, WANG Zhao, et al. Analysis of genetic diversity and structure of tartary buckwheat resources from production regions [J]. Scientia Agricultura Sinica, 2016, 49(11): 2049-2062. (in Chinese)

6 梁俊山，王慧琴，胡燕，等. 基于模糊聚類的圖像型火災(zāi)檢測(cè)[J].計(jì)算機(jī)工程，2012，38(4)：196-198. LIANG Junshan, WANG Huiqin, HU Yan, et al. Image type fire detection based on fuzzy clustering [J]. Computer Engineering, 2012, 38(4): 196-198. (in Chinese)

7 姚雪芹，張欽弟，畢潤成，等. 山西太岳山遼東櫟群落林下草本植物功能群分類[J].植物分類與資源學(xué)報(bào)，2015，37(6)：849-855. YAO Xueqin, ZHANG Qindi, BI Runcheng, et al. Plant functional group classification of herbaceous species inQuercuswutaishanicacommunities in the Taiyue mountains, Shanxi Province of China [J]. Plant Diversity and Resources, 2015, 37(6): 849-855. (in Chinese)

8 蔣冬生，唐紅蓮，覃宏明，等. 桂北地區(qū)銀杏苗木質(zhì)量分級(jí)標(biāo)準(zhǔn)[J].林業(yè)科技，2015，40(4)：29-32. JIANG Dongsheng, TANG Honglian, Qin Hongming, et al. Grading standard ofGinkgobiloba. seedling quality in the northern area of Guangxi [J]. Forestry Science & Technology, 2015, 40(4): 29-32. (in Chinese)

9 韓家煒，Micheline K, 裴健. 數(shù)據(jù)挖掘概念與技術(shù)[M].3版.北京：機(jī)械工業(yè)出版社，2014：288-319.

10 王典，劉晉浩，王建利. 基于系統(tǒng)聚類的林地內(nèi)采育目標(biāo)識(shí)別與分類[J].農(nóng)業(yè)工程學(xué)報(bào)，2011，27(12)：173-177. WANG Dian, LIU Jinhao, WANG Jianli. Identification and classification of scanned target in forest based on hierarchical cluster [J]. Transactions of the CSAE, 2011, 27(12): 173-177. (in Chinese)

11 周俊，胡晨. 密植果園作業(yè)機(jī)器人行間定位方法[J/OL].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2015，46(11)：22-28. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20151104&journal_id=jcsam.DOI:10.6041/j.issn.1000-1298.2015.11.004. ZHOU Jun, HU Chen. Inter-row localization method for agricultural robot working in close planting orchard[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(11): 22-28. (in Chinese)

12 LLOYD S P. Least squares quantization in PCM [J]. IEEE Transactions on Information Theory, 1982, 28(2): 128-137.

13 MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]∥Proceedings of the 5th Berkeley Symposium on Mathematical Statistics & Probability, 1967: 281-297.

14 趙博，宋正河，毛文華，等. 基于PSO與K-均值算法的農(nóng)業(yè)超綠圖像分割方法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2009，40(8)：166-169. ZHAO Bo, SONG Zhenghe, MAO Wenhua, et al. Agriculture extra-green image segmentation based on particle swarm optimization andK-means clustering [J]. Transactions of the Chinese Society for Agricultural Machinery, 2009, 40(8): 166-169. (in Chinese)

15 司永勝，劉剛，高瑞. 基于K-均值聚類的綠色蘋果識(shí)別技術(shù)[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2009，40(增刊)：100-104. SI Yongsheng, LIU Gang, GAO Rui. Segmentation algorithm for green apples recognition based onK-means algorithm [J]. Transactions of the Chinese Society for Agricultural Machinery, 2009, 40(Supp.): 100-104. (in Chinese)

16 KRISHNA K, ROHIT L, SHOURYA R, et al. A hierarchical monothetic document clustering algorithm for summarization and browsing search results [C]∥Proceedings of the 13th International Conference on WWW, 2004: 658-665.

17 LUO M, MA Y F, ZHANG H J. A spatial constrainedK-means approach to image segmentation[C]∥Proceedings of the 4th IEEE Pacific-Rim Conference on Multimedia, 2003: 738-742.

18 周世兵，徐振源，唐旭清. 一種基于近鄰傳播算法的最佳聚類數(shù)確定方法[J].控制與決策，2011，26(8)：1147-1157. ZHOU Shibing, XU Zhenyuan, TANG Xuqing. Method for determining optimal number of clusters based on affinity propagation clustering [J]. Control and Decision, 2011, 26(8): 1147-1157. (in Chinese)

19 王勇，唐靖，饒勤菲，等. 高效率的K-means最佳聚類數(shù)確定算法[J].計(jì)算機(jī)應(yīng)用，2014，34(5)：1331-1335. WANG Yong, TANG Jing, RAO Qinfei, et al. High efficientK-means algorithm for determining optimal number of clusters [J]. Journal of Computer Applications, 2014, 34(5): 1331-1335. (in Chinese)

20 KANG F, LI W B, PIERCE F J, et al. Investigation and improvement of targeted barrier application for cutworm control in vineyards [J]. Transactions of the ASABE, 2014, 57(2): 381-389.

21 王建，姚振強(qiáng)，尹明德，等. 用于距離圖像2D掃描線的極速邊緣檢測(cè)器[J].電子學(xué)報(bào)，2010，38(7)：1711-1715. WANG Jian, YAO Zhenqiang, YIN Mingde, et al. A rapid edge detector for 2D scan line in range image [J]. Acta Electronica Sinica, 2010, 38(7): 1711-1715. (in Chinese)

22 RODRIGUEZ-CABALLERO E, AFANA A, CHAMIZO S, et al. A new adaptive method to filter terrestrial laser scanner point clouds using morphological filters and spectral information to conserve surface micro-topography[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2016, 117: 141-148.

23 于金霞，蔡自興，鄒小兵，等. 基于動(dòng)態(tài)自適應(yīng)濾波的移動(dòng)機(jī)器人障礙檢測(cè)[J].自然科學(xué)進(jìn)展，2006，16(5)：618-624. YU Jinxia, CAI Zixing, ZOU Xiaobing, et al. Obstacle detection of mobile robot based on dynamic adaptive filtering [J]. Progress in Natural Science, 2006, 16(5): 618-624. (in Chinese)

24 CHAUDHURI D, CHAUDHURI B B. A novel multiseed nonhierarchical data clustering technique[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1997, 27(5): 871-876.

25 熊軍華，王彩玲，贠超. 自動(dòng)配料遠(yuǎn)程監(jiān)控系統(tǒng)設(shè)計(jì)[J].農(nóng)機(jī)化研究，2011(9)：128-131. XIONG Junhua, WANG Cailing, YUN Chao. Design of remote monitoring system of automatic batching[J]. Journal of Agricultural Mechanization Research, 2011(9): 128-131. (in Chinese)

26 張翔，張青峰，張莉，等. 利用哈夫曼樹的遙感影像無損壓縮方法[J].測(cè)繪科學(xué)，2015，40(4)：106-111. ZHANG Xiang, ZHANG Qingfeng, ZHANG Li, et al. Huffman tree based lossless compression method for remote sensing image [J]. Science of Surveying and Mapping, 2015, 40(4): 106-111. (in Chinese)

27 特日跟，江晟，李雄飛，等. 基于整數(shù)數(shù)據(jù)的文檔壓縮編碼方案[J].吉林大學(xué)學(xué)報(bào)：工學(xué)版，2016，46(1)：228-234. TE Rigen, JIANG Sheng, LI Xiongfei, et al. Document compression scheme based on integer date[J]. Journal of Jilin University: Engineering and Technology Edition, 2016, 46(1): 228-234. (in Chinese)

28 北京林業(yè)大學(xué). 基于哈夫曼樹法確定初始聚類中心的林用K-均值算法軟件V1.0：中國，2016SR250805[P]. 2016-06-29.

EffectiveK-means Clustering Algorithm for Tree Trunk Identification

WANG Yaxiong1KANG Feng1LI Wenbin1WEN Jian1ZHENG Yongjun2

(1.SchoolofTechnology,BeijingForestryUniversity,Beijing100083,China2.CollegeofEngineering,ChinaAgriculturalUniversity,Beijing100083,China)

In the process of automatic targeted spray in forest region at present, the accuracy and efficiency of point cloud data are all low when the tree trunks grow intensively, aimed at which the optimizedK-means clustering algorithm was put forward, and data acquisition method was based on 2D laser detection. In view of the relevant data needed to be filtered before clustering analysis for trunk scanning spots, application of window filtering algorithm was put forward. The edge of trunk which generated mixed pixels was selected, and then the mixed pixels deriving from three adjacent scans and the scanning spots deriving from two scanning angles near the mixed pixel were extracted, finally, the maximum threshold filtering processing for the neighbor spots was done. Through 50 times of extractions and analyses of test data, only two mixed pixels were not filtered, which indicated that the filtering rate of mixed noises was high. Aimed at the defects of cluster number and initial cluster centers forK-means algorithm needed to be predetermined, the method of slope variation used to determine the clustering number was firstly proposed. Five groups of trunks were respectively measured for 100 times at five different distances in the test, and results showed that the number of error measurements was only three times, which could be removed by artificial way at the early stage of the test, and it indicated that the slope variation algorithm was reasonable and effective. The performance of Huffman tree method, which was used to determine the clustering centers for the trunk scanning spots, was analyzed in another test, andK-means clustering was carried out by using random sampling method and Huffman tree method under three trunk distribution types. The average correct rate of former was only 76.4%, while that of the latter was 95.5%. Meanwhile, iterations and time-consuming using the two above-mentioned algorithms at type I distribution were analyzed, and the average number of iterations of random sampling method was obviously higher than that of Huffman tree method at five different distances, but the average time-consuming of Huffman tree method was higher than that of random sampling method. The variation range of former was 120～220 ms and it was 50～85 ms for the latter, which were all in acceptable ranges on forest surveying and mapping. Experiments proved that the determining methods for clustering number based on the slope variation algorithm and clustering centers based on Huffman tree method were effective algorithms for the clustering of trunk scanning spots in forest region during usingK-means algorithm, which could be applied to tree trunk detection for actual forest region.

tree trunk identification; point cloud data;K-means clustering algorithm; window filtering algorithm; Huffman tree method

10.6041/j.issn.1000-1298.2017.03.029

2016-11-15

2016-12-22

國家林業(yè)局林業(yè)科學(xué)技術(shù)推廣項(xiàng)目(2016-29)和中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2015ZCQ-GX-01)

王亞雄(1986—)，男，博士生，主要從事林業(yè)工程裝備及其自動(dòng)化研究，E-mail： yaxiongwang87@bjfu.edu.cn

李文彬(1962—)，男，教授，博士生導(dǎo)師，主要從事林業(yè)工程裝備自動(dòng)化及人工環(huán)境工程研究，E-mail： leewb@bjfu.edu.cn

S24

A

1000-1298(2017)03-0230-08