一種基於地面雷射雷達點雲數據自適應構建三維樹木骨架的方法

2023-06-09 14:32:46

專利名稱：一種基於地面雷射雷達點雲數據自適應構建三維樹木骨架的方法
技術領域：
本發明涉及一種基於地面雷射雷達點雲數據自適應構建三維樹木骨架的方法，屬於空間信息技術領域。
背景技術：
植物生長的研究涉及到眾多的科學研究領域，如植被遙感、生態等。地面雷射雷達能夠快速、精確的獲取植被三維點雲信息，從點雲數據可以提取樹木上的點集，利用該點集能夠重建物體的表面結構。但是樹木的幾何結構較為複雜，尤其樹木較多時，樹木間相互遮擋，造成雷射點雲數據部分缺失。如何從地面雷射點雲甚至數據缺失的雷射點雲中重建樹木的幾何結構信息是空間信息技術領域亟待需要解決的問題之一。 本發明的目的是在單一方向地面雷射雷達掃描的情況下，採用物體表面點受力平衡的假設建立優化方程，讓點雲能夠自動的填充被遮擋的部分，並且遠離一些可能錯誤相交的部分，並且用距離最小生成樹(DMst)構建的樹型結構，既反映局部的點密度又兼顧點到根部的距離。目前基於點雲對樹三維骨架建模方面，常用的有基於啟發式方法，該方法用單方向的雷射點雲重建樹的主要樹枝，在構建初始的樹以後，用福射傳輸模型對樹被遮蔽的地方進行模擬，結合L系統來填充這些地方，但該方法建模效率較低，並且難以處理點雲缺失的情況。也有學者採用八叉樹的數據結構，通過設置假設，去除那些不符合假設的邊，最後獲得樹形結構。但樹結構複雜和相互遮擋，並且雷射點雲往往存有噪聲，不能剛性的設置條件來獲取樹的結構，而是儘可能用可變形的方法來對樹進行建模。本發明採用單方向的雷射點雲來構建樹的三維結構，主要特色體現在針對樹的相互遮擋等原因造成點雲數據缺失，甚至缺失比較嚴重的情況，基於物體表面連續且粒子在物體表面是受力平衡的思想，提出了優化方法，構建優化函數，可以較好的表達點雲在樹表面的特徵，實現樹木三維骨架的建模，而以往樹建模方法幾乎沒有涉及過數據有較大缺失的情況。

發明內容
I、目的本發明的目的是從地面雷射點雲數據中自動重建三維樹木骨架。由於樹木幾何形態比較複雜，待處理的點雲數據往往不完整或存有噪聲，本發明在單一方向的地面雷射雷達掃描的情況下，採用物體表面點受力平衡的假設建立優化方程，自動填充缺失的區域，用距離最小生成樹構建三維樹骨架結構。本發明在植被遙感、生態等領域具有很好的應用價值。2、技術方案本發明一種基於地面雷射雷達點雲數據自適應構建三維樹木骨架的方法，具體步驟如下(如圖I):步驟一初步建立樹木三維幾何結構
對於包含多棵樹的地面雷射點雲，需要先識別樹的株數及其對應的底部。獲取一定高度層的點，然後聚類提取單棵樹的點雲集合。計算每棵樹點雲集合的中點，作為該樹的底點。對於複雜的區域需要交互式指定底部來確定樹的棵數和底點。在樹木點雲中,利用k-Nearest Neighbor (KNN)算法計算每個點最鄰近的n個點，一般的，n = 50 ;設其中兩點分別為i點和j點，KNN算法計算出的最鄰近點i的最相鄰點包含j，而j的最鄰近不包括i，所以讓i的最相鄰點包含j，且點的相鄰點包含i，點與點連線形成邊的長度作為該邊的權重，以此構建一個無向圖，通過該無向圖構建最小生成樹(MST)。用Dijkstra算法計算每個底點到MST各點的最短距離,把每個點歸屬到離所對應底點最近的樹上去。這樣就獲得了一株樹的點雲以及其連接方式。步驟二 構建距離最小生成樹從樹木點雲中用Di jkstra算法獲得樹的三維結構缺乏相鄰點的信息，而MST也不能很好描述樹的伸展形狀。樹枝通常是向上生長的，小範圍內樹幹的分布應該是相對光滑的，樹上的點被認為是以離根節點最近的方式連接，並且越相臨的點在同一樹枝上的可能性越大。本發明提出距離最小生成樹方法(DMst)來構建子樹。DMst的方法流程如下(I)對單株樹的點雲構建無向圖，其中頂點集合為V。設每個頂點到根節點的距離Ddij,每個頂點到當前DMst (此時,DMst為空)的最小距離為Dmst,每個頂點指向為P,每個頂點的MST指向為Pmst,每個頂點Dijkstra樹的指向為Pdij ；(2)把底點做為DMst的根節點，初始化V，除底點以外的所有頂點放入V中，計算所有點的Ddu和Dmst，把根節點相鄰點的P、Pdij和Pmst指向根節點。(3)在V中，選取Dmst+Ddij之和最小的點，把該點從V中移出。(4)更新Pnist和Dnist，設點i、j之間的距離為Clij，如果Dnist [ i ] > Cli」，那麼Pnist指向 j，Dmst [i] = (Iij,更新 Pdij 和 Ddij ;如果 Ddij[i] > DdijOdij,那麼 Pmst 指向 j，Ddij [i]=Ddij[j]+Clij ;當 Dmst [i] +(Dmst [i]+Ddij[j]) < = Ddij[i]-Ddij[k]+Ddij[i]時，P[i]指向距樹最小的位置j，否則，P[i]指向距根節點距離最小的位置。(5)重複步驟⑶和(4)，直到V中沒有點為止，通過P獲取所有點的組織結構，完成DMst構建。構建DMst時，用Dmst[i]+wXDdij[i]代替Dmst+Ddij控制入選的點。更新時，因為在DMst中每次獲取i點和j點的公共前向，計算複雜度大，而用Dmst[i] +(Dmst[i]+Ddij[j])-Ddij[k] <= wX (Ddij[i]-Ddij[k]+Ddij[i]-Ddij[k])作為判定條件，可以獲得較好效果。DMst獲得的樹形結構中，大量的樹節點點只有少量的子節點，去除那些只有少量子節點的樹節點，剩下的點構成一個近似的樹骨架。設置每個點的權值Ci,對沒有子節點的點來說，Ci = 0. I，對有子節點的點，Ci =+dy)( 1 )式⑴中，Q是i點相鄰子節點的集合，j點是i點相鄰的子節點，(Iij是i點和j點之間的距離。設閾值為S，剔除Ci 6的點。保留的點構成了樹的近似骨架，並且骨架點是樹的表面點，骨架節點之間的方向很好反映了樹枝的伸展方向。DMst構成樹的連接方式具有方向性，因為考慮了每個點到根部的距離，形成樹枝的方向主要是向上的，符合樹的生長特徵，這也為缺失點雲區域的修補提供了幫助。步驟三優化樹骨架結構一般的，樹的表面是連續的，樹枝的變化是平滑的，不會出現粗枝瞬間變細枝或者細枝瞬間變成粗枝的情況，所以用如下假設來描述樹的表面地面雷射雷達掃描儀掃描樹木表面形成點雲的過程可看作連續表面離散化的過程，點雲類似於粒子，它們之間有相互的斥力，所在位置對其本身有一定的束縛作用，這些粒子所構成的表面處於受力平衡的狀態，因此有點雲缺失的樹木區域，本應該存在的表面點沒有了，整個表面的受カ平衡狀態就破壞了，粒子會產生運動，最後會獲得ー個新的受カ平衡狀態，而這個平衡狀態就是修復了缺失的狀態。(I)提取枝幹主方向因為點密集分布在樹的表面，相鄰點之間的方向並不能代表樹枝的伸展方向，所以點與點之間的方向不能代表表面上姆ー個點受カ方向，用主方向來反映樹枝的伸展方向。為了獲得主方向，對去除Ci δ且所有後向點的Ci δ，這個點是樹的分叉點。在所有採樣點構成的樹骨架上，每隔距離d再採ー個點，d是點與點之間樹幹上的距離而不是直線距離，把這些點按DMst的結構連接起來，d = O. 2。設相鄰兩點為i，j，離根節點近的點設為i，另一點設為j，由i指向j的方向作為這兩點之間的方向，該方向作為i點的所有子節點的主方向；取末枝點的前向節點到末枝點的方向作為末枝點的所有子節點的主方向。(2)優化點雲缺失的樹木對於完整點雲集合來說，其中每個點處於受力平衡狀態，所以一個點所連接的所有點對該點的合力在主方向上的投影Fr與其所在位置對該點的束縛カFs之和F = Fr+Fs,作為該點所受的外力，顯然F = O時,該點處於平衡狀態。類似於同性電荷之間的力，點之間的斥力與其距離成反比，通過公式(2)計算每個點的電荷量qi;
權利要求
1.一種基於地面雷射雷達點雲數據自適應構建三維樹木骨架的方法，步驟包括 步驟一初步建立樹木三維幾何結構 對於包含多棵樹的地面雷射點雲，需要先識別樹的株數及其對應的底部，獲取一定高度層的點，然後聚類提取單棵樹的點雲集合，計算每棵樹點雲集合的中點，作為該樹的底點，對於複雜的區域需要交互式指定底部來確定樹的棵數和底點。
在樹木點雲中，利用k-Nearest Neighbor (KNN)算法計算每個點最鄰近的n個點，以此構建一個無向圖，通過該無向圖構建最小生成樹(MST),用Di jkstra算法計算每個底點到MST各點的最短距離，把每個點歸屬到離所對應底點最近的樹上去。
步驟二 構建距離最小生成樹 從樹木點雲中用Dijkstra算法獲得樹的三維結構缺乏相鄰點的信息，而MST也不能很好描述樹的伸展形狀；樹枝通常是向上生長的，小範圍內樹幹的分布應該是相對光滑的，樹上的點被認為是以離根節點最近的方式連接，並且越相臨的點在同一樹枝上的可能性越大，本發明提出距離最小生成樹方法(DMst)來構建子樹，DMst的方法流程如下 (1)對單株樹的點雲構建無向圖，其中頂點集合為V，設每個頂點到根節點的距離Ddij,每個頂點到當前DMst的最小距離為Dmst,每個頂點指向為P,每個頂點的MST指向為Pmst,每個頂點Dijkstra樹的指向為Pdij ； (2)把底點做為DMst的根節點，初始化V，除底點以外的所有頂點放入V中，計算所有點的Ddu和Dmst，把根節點相鄰點的P、Pdij和Pmst指向根節點。
(3)在V中，選取Dmst+Ddij之和最小的點，把這個點從V中移出。
(4)更新Pmst和Dmst,設點i、j之間的距離為Clij,如果Dmst[i] > Clij,那麼Pmst指向J，Dnist [i] = (Iij,更新 Pdij 和 Ddij ；如果 D⑴[i] > Ddij [ j] +dir 那麼 Pnist 指向 j，Ddij [i]=Ddij[j]+Clij ;當 Dmst [i] +(Dmst [i]+Ddij[j]) < = Ddij[i]-Ddij[k]+Ddij[i]時，P[i]指向距樹最小的位置j，否則，P[i]指向距根節點距離最小的位置。
(5)重複步驟(3)和(4)，直到V中沒有點為止，通過P獲取所有點的組織結構，完成DMst構建。
構建DMst時，用Dmst[i]+wXDdij[i]代替Dmst+Ddij控制入選的點，更新時，用Dmst[i] + (Dmst[i]+Ddij[j])-Ddij[k] <= wX (Ddij[i]-Ddij[k]+Ddij[i]-Ddij[k])作為判定條件。
DMst獲得的樹形結構中，去除那些只有少量子節點的樹節點，剩下的點構成一個近似的樹骨架，設置每個點的權值Ci,對沒有子節點的點來說，Ci = 0. 1，對有子節點的點，
全文摘要
本發明涉及一種基於地面雷射雷達點雲數據自適應構建三維樹木骨架的方法。基於Dijkstra算法和最小生成樹，提出了距離最小生成樹方法(DMst)重構樹木點雲間的幾何拓撲關係，獲得近似樹三維骨架，利用該骨架計算其上每點的主方向，採用物體表面點受力平衡的假設建立優化函數，以此修補缺失的樹木點雲信息，用DMst構建完整的樹骨架結構，基於樹異向生長特性模型計算樹幹的半徑，實現樹骨架的三維重建。本發明能很好的處理缺失點雲數據，在大量點雲缺失的情況下，仍能精確重建樹的骨架結構。本發明具有很好的魯棒性和數據自適應性。
文檔編號G06T17/00GK102682475SQ20121014390
公開日2012年9月19日 申請日期2012年5月11日 優先權日2012年5月11日
發明者張立強, 王臻, 陳棟 申請人:北京師範大學