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

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

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

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

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

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

立木識別； 點云數據；K-均值聚類算法； 窗口濾波算法； 哈夫曼樹法

引言

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

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

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

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

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

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

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

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

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

其中i為激光測距的采樣編號，即第i次掃描(i為正整數，且i>1)；j為對應某次掃描的不同測量點編號(j為正整數，且j>1)。

以上9個測量值具有時間與空間的最大相關性，在該矩陣窗口中計算ρi,j與鄰近測量值之差Δρmin。

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

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

(1)

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

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

聚類為濾波后進行的數據處理，如圖2所示，掃描數據點為完全投影于樹干上的點云。對于精準對靶施藥而言，首先需對濾波后的點云進行分簇，進而對屬于同一樹干的點云簇進行擬合。針對所述當前聚類方式的不足，本文根據目標樹干的具體情況提出提前確定聚類簇數及初始聚類中心的K-均值算法。

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

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

算法流程：

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

(2)根據簇中對象的均值，將每個對象分配到最相似的簇。

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

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

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

1.2.1 基于斜率變化的聚類數確定方法

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

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

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

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。n個權值分別設為w1、w2、…、wn，則哈夫曼樹的構造規(guī)則為：

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

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

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

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

由哈夫曼樹帶權路徑長度之和最小的性質，可將該方法應用于K-均值聚類初始中心的選取上，根結點的合并方法基于對象間的相異性度量，數據間的相異性度量采用相異性矩陣表示。相異性矩陣采用存放n個對象兩兩之間的鄰近度，通常用一個n×n矩陣表示。

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

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

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

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

2 試驗設計與方法

2.1 試驗系統(tǒng)

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

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

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

2.2 濾波試驗

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

完成混合像素數據濾波后，運用距離閾值法濾去遠距離的點云噪聲，獲得僅屬于樹干部分的掃描點云。

2.3 聚類分析

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

3 結果分析與討論

3.1 濾波實驗結果分析

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

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

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

3.2 聚類試驗結果分析

3.2.1 聚類數確定試驗結果分析

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

3.2.2K-均值聚類算法試驗結果分析

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

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

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

表2 Ⅱ型、Ⅲ型分布下基于隨機抽樣法(RSM)與哈夫 曼樹法(HTM)的K-均值算法對比分析(聚類數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時采樣X的聚類結果Fig.6 Clustering result of sampling X at distance of 3 m

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

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

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

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

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

4 結束語

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

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 姜紅花，白鵬，劉理民，等. 履帶自走式果園自動對靶風送噴霧機研究[J/OL].農業(yè)機械學報，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激光探測的立木胸徑幾何算法優(yōu)化[J/OL].農業(yè)機械學報，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 屈洋，周瑜，王釗，等. 苦蕎產區(qū)種質資源遺傳多樣性和遺傳結構分析[J].中國農業(yè)科學，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 梁俊山，王慧琴，胡燕，等. 基于模糊聚類的圖像型火災檢測[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].植物分類與資源學報，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ū)銀杏苗木質量分級標準[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, 裴健. 數據挖掘概念與技術[M].3版.北京：機械工業(yè)出版社，2014：288-319.

10 王典，劉晉浩，王建利. 基于系統(tǒng)聚類的林地內采育目標識別與分類[J].農業(yè)工程學報，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/OL].農業(yè)機械學報，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-均值算法的農業(yè)超綠圖像分割方法[J].農業(yè)機械學報，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-均值聚類的綠色蘋果識別技術[J].農業(yè)機械學報，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 周世兵，徐振源，唐旭清. 一種基于近鄰傳播算法的最佳聚類數確定方法[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最佳聚類數確定算法[J].計算機應用，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 王建，姚振強，尹明德，等. 用于距離圖像2D掃描線的極速邊緣檢測器[J].電子學報，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 于金霞，蔡自興，鄒小兵，等. 基于動態(tài)自適應濾波的移動機器人障礙檢測[J].自然科學進展，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 熊軍華，王彩玲，贠超. 自動配料遠程監(jiān)控系統(tǒ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].測繪科學，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 特日跟，江晟，李雄飛，等. 基于整數數據的文檔壓縮編碼方案[J].吉林大學學報：工學版，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è)大學. 基于哈夫曼樹法確定初始聚類中心的林用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è)科學技術推廣項目(2016-29)和中央高?；究蒲袠I(yè)務費專項資金項目(2015ZCQ-GX-01)

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

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

S24

A

1000-1298(2017)03-0230-08