一種基於形狀分析的樹冠外形提取方法

2023-05-29 12:20:56 2

專利名稱：：一種基於形狀分析的樹冠外形提取方法
技術領域：
：本發明屬於模式識別與科學計算可視化相結合的交叉學科
技術領域：
，涉及點雲處理、形狀分析、植物形體(簡稱形體)和分級骨架的提取技術。
背景技術：
：隨著虛擬環境的建立，產品設計，數字娛樂，古物保護以及城市規劃的發展，三維幾何模型的重建和處理成為了一個研究熱點。可以說三維幾何建模可以看作是除了數字音頻，數字圖像，數字視頻後的第四個數字多媒體。三維的幾何模型可以表示物體的表面，因而可以鑑別外在的形狀和外表的一些性質。而隨著數據採集技術的快速發展，越來越多的三維數字掃描儀得到了普及並應用到越來越多的領域。在計算機圖形學，計算機輔助設計技術中所使用的數據解析度越來越高，數據量也越來越大。通過對物體進行密集的掃描，可以獲得關於物體外形更多的細節，獲得的是數據點雲，並且沒有拓撲連接信息。所以發展新的方法來表示，處理，重建甚至是繪製這些複雜幾何體就變得相當的重要。而幾何模型的重建是在現代虛擬實境中比較重要的一個研究主題。骨架化作為一種特徵提取和特徵表示方法，可以有效地刪除冗餘信息和保留特徵信息。在虛擬實境中，骨架化可以從數據中提取出路徑以指導漫遊，防止在漫遊中迷路。對於林業的可視化和測量，骨架可以精確的表示形體的拓撲結構以便進行樹木的識別，並且可以精確地對樹木的長度和半徑進行測量。對於文字、工程圖、指紋中的"細莖"狀圖像等都是長而窄的帶狀圖像，也常常需要通過計算它們的骨架來進行識別或重構等處理。在視頻處理中，通過骨架提取圖像中主要特徵，可以精確地對運動形體進行跟蹤。很多形體，如醫學中的血管、氣管、林業中的各種樹木，以及人體的骨架，都可以表示成為形體，因此形體的骨架提取得到了廣泛的重視，Ogniewicz利用計算幾何中的重要工具-Voronoi圖來提取骨架。對於平面中的點，可以得到該點的Voronoi多邊形，而Voronoi圖就是這些Voronoi多邊形的集合。Voronoi圖中形體邊界的點所產生的Voronoi邊或Voronoi面靠近形體的中心，因此這些邊可認為是形體的骨架。但是該方法一般只能適用於三角網格模型，而且生成的骨架包含很多雜枝。Rosenfeld提出了拓補細化的骨架化方法。該算法首先定義那些刪除以後不影響拓補性質的點為簡單點。然後從這個概念出發，考慮體素點的8-鄰域或者26-鄰域的拓補關係，設計出一些刪除模板，使得模板中的體素點滿足簡單點的定義。然後利用這些刪除模板一層層地剝開形體，直到得到骨架為止。但是這種方法計算量太大，運行時間太長。Ma改進了刪除模板，並對刪除操作進行並行處理以加快運行速度。但細化的結果經常包含很多雜枝。Borgefors提出了基於距離變換的骨架化方法。距離變換方法的主要根據是其骨架定義立體的骨架是立體內部到立體邊界距離最大的點的集合。Zhou提出的體素編碼和聚類圖方法，可以有效地分解形體，但其骨架的拓撲結構與形體的拓撲結構在分叉處不一致。Wan方法是先對體數據進行距離變換，然後將變換後的距離圖看成一個有向中心性加權圖，使用以邊界距離值的倒數建立極小擴張樹的方法來改進Dijkstra最短路徑生成算法，從而使得到的骨架點儘量的不偏離中心，但是會出現中心線的"擾動"現象。在虛擬實境中，樹木是比較典型的事物，所以重建和表示一個真實的樹木就變得相當的重要。而且樹木的重建可以用在相當多的領域得到應用，包括植被場景的數位化，新場景的設計，以及數字娛樂中等等。樹冠外形的重建對於真實樹木的建模是非常有用的，並且在一些科研領域得到關注，譬如虛擬光照對植物生長的模擬，樹木生物量的估計等等。目前很多的研究人員已經在曲面重建方面取得了一定的成果，但是樹冠外形比一般的固體外形更難重建，因為樹木的葉子和樹枝間的相互遮擋，以及樹木在幾何和拓撲方面的高度複雜性。對散亂分布點雲數據求取其外在形狀在計算幾何領域一直是個具有挑戰性的工作，在三維空間中，點雲數據的凸包外形是唯一的，但是這個凸包外形只提供了較少的數據外形信息。沒有關注數據中的大量細節。所以研究人員希望能找到更好的求取外形的方法。Jarvis是第一個將二維平面上的點集凸包形狀推廣到一般形狀的研究人員。Edelsbru皿er首先給出了關於形狀的數學上的精確定義。對於三維空間的點集，Boissonnat提出應該用Delaunay三角剖分來"刻出"點集的相互連接的形狀。Hoppe的方法是從散亂的點雲重建出曲面，他利用一個距離場函數來重建出一個隱式曲面，然後再三角剖分這個隱式曲面。Crust方法可以在二維和三維空間中重建光滑的閉合的流形體，但是它需要用到計算幾何中的重要工具Voronoi圖，並且需要計算Voronoi圖兩次，這個計算是相當耗時的，而且這個方法不能處理拐點和角點，並且需要點雲的採樣密度是很大的。Alphash即e方法首先是Delaunay三角剖分點集，然後需要用戶去選擇參數的大小，通過這個參數的不同，最後獲得的點集外形的具體細節也是不同的，當然這個Delaunay計算量太大，也是相當的耗時的。
發明內容現有的技術不能很好的計算樹形物體點雲數據的外在形狀，因此不能解決樹的表示，測量和識別。為了解決現有技術的不足，本發明的目的是求取樹的掃描數據的外在形狀，提供一種基於樹的骨架分類技術的計算樹的外在形狀的方法。為了實現本發明的目的，本發明提供的一種基於形狀分析的樹冠外形提取方法，該方法的步驟包括步驟SI:用雷射掃描儀掃描植物的單面，獲得的掃描數據稱為點雲數據；步驟S2:從點雲數據中找到根節點，用K近鄰的方法對整個點雲數據進行距離變換，構造這些點雲數據中的點到根節點的權圖，計算點雲數據的每個點到根節點的最小距離，利用這個最小距離從整個點雲數據中分離出位於主枝上的點雲數據；步驟S3:對位於主枝上的點雲數據進行聚類分析，生成樹狀聚類圖，用於尋找形體的分叉位置和末梢位置，在每個聚類中，根據距離再次聚類，得到聚類中的子聚類，對每個子聚類，用算術平均的方法計算每個子聚類的代表點，作為主枝骨架點；步驟S4:將所有子聚類的代表點形成集合，再用所有代表點集合構造具有中心性、分叉性和拓撲連接性的主枝骨架；步驟S5:從主枝骨架上部的葉子節點或稱末梢位置開始，對骨架的各個分支進行分類，使分類後的每個分支長度達到一定標準；對主枝骨架進行分類的基礎上，對點雲數據中的位於樹冠的葉子點雲數據進行分類；步驟S6:對每個分類後的葉子點雲數據分別計算它們的形狀，首先對其中的一個分類後的點雲進行三維的德朗奈三角剖分，建立點雲中每個數據點的拓撲結構，得到三角面片和四面體，對這些四面體和三角面片分別計算它們的外接球和外接圓的半徑，得到包含這些半徑的最小區間[A，B]，取阿爾法形狀方法中的參數阿爾法為區間[A，B]的中間點，把求得的四面體和三角面片進行分類，四面體分類為外部的四面體和內部的四面體，而三角面片分類為內部的三角面片、外部的三角面片以及邊界的三角面片，若邊界的三角面片組成的是個閉合的體，那麼將參數阿爾法取成[A，B]下部區間的中點繼續這個過程，直到相鄰的兩個參數之差小於給定的充分小的值，該充分小的值是取掃描數據中兩點間最小距離的百分之一，這時候這兩個參數中，較大的一個對應的邊界三角面片的集合，就是整個樹冠的外在形狀。其中，所述從點雲數據中找到根節點，是按照數據點中Y坐標最小的方法找到根節點。其中，所述構造這些點雲數據中的點到根節點的權圖，是通過K近鄰的方法，找到K個距離數據點最近的點，將這些距離數據點最近的點和數據點連接起來形成權圖，而權圖中的權就是兩點間的距離。其中，所述的計算點雲數據的每個點到根節點的最小距離，是在已知權圖的基礎上，計算從根節點到數據點路徑中權和最小的路徑，這個權和就是這個數據點到根節點的最小距離。其中，所述的聚類分析是根據主枝點雲數據中的每個數據點p到根節點的已知最小距離進行聚類分析，形成大的聚類，每個大的聚類中的點屬於一定的距離範圍。其中，所述的再次聚類是在得到的每個大的聚類中，應用距離變換再次進行聚類分析，得到子聚類。其中，所述構造分類骨架，是將每個子聚類選出中心點，然後將這些中心點中Y坐標最小的點作為根節點，計算這些中心點中的其它點到這個根節點的最小距離路徑，按照順序連接路徑上的點構造出這個主枝骨架。其中，所述的對骨架的各個分支進行分類，首先找到主枝骨架各個末梢代表點，選取Y坐標最大的末梢點作為起始點，沿著主枝骨架根節點到這個起始點的最短路徑的反方向進行移動，當到達第一個分叉點的時候計算，計算目前路徑的長度，若目前路徑的長度大於給定的值l，則目前經過路徑上的點歸為一類，然後選取下一個未處理過的並且Y坐標是最大的末梢點進行同樣的回溯路徑，否則計算以第一個分叉點為初始點的所有子枝的長度和；若初始點的所有子枝的長度和大於給定的值l，則以第一個分叉點為初始點的所有子枝上的代表點歸為一類，否則從目前分叉點，沿著最小路徑繼續回溯到下一個分叉點，將上面的所有子枝的長度和加上第一個分叉點與目前分叉點間的距離得到目前路徑長度和，若這個目前路徑長度和大於給定的值，則目前路徑上的所有代表點歸為一類，否則計算所有以目前的分叉點為初始點的所有子枝的長度和，若這個所有子枝的長度和大於給定的值1，則將目前路徑經過的代表點歸為一類，否則就繼續上面的過程，沿著最短路徑繼續回溯直到子枝的長度和大於給定的值1。其中，所述的對點雲數據中的位於樹冠的葉子點雲數據進行分類，在已經將主枝骨架分類的基礎上，依據葉子點雲數據中的每個數據點到主枝骨架距離最近的原則，將整個的葉子點雲數據進行分類，到主枝骨架同一類分支最近的葉子數據點歸為一類，否則就分屬不同的類。其中，所述外部的四面體和內部的四面體，是四面體有唯一的外接球，這個外接球半徑若大於預先給定的參數阿爾法，則是外部的四面體，否則就是內部的四面體。其中，所述內部的三角面片、外部的三角面片以及邊界的三角面片，每個三角面有唯一的外接圓，而這個外接圓半徑是這個三角面的特徵之一，三角面分成兩類位於凸包上和位於凸包內部；對於位於凸包上的三角面，若其所在的四面體是外部的四面體，則這個三角面是外部的三角面，否則其為邊界的三角面；對於位於凸包內部的三角面，其為兩個四面體所共享，這兩個相鄰四面體若其都是外部的四面體，則這個三角面上就是外部的三角面，若這兩個四面體都是內部的四面體，則這個三角面就是內部的三角面，否則這個三角面就是邊界的三角面。本發明的有益效果本發明解決的技術問題是求取樹木單面掃描數據的形狀。本發明的方法是通過對整個樹木的掃描數據進行分類，將其劃分為樹葉點雲和枝幹點雲，針對枝幹點雲我們提取相應的分級骨架，然後對這個分級骨架首先進行聚類，聚類後的骨架應用距離來對樹葉點雲進行分類，最後是對每個分類後的樹葉點雲求取其相應的形狀。骨架主用要於形體的識別和跟蹤、形體形狀的表示和測量。三維樹狀形體的骨架廣泛應用於植物生長建模中的樹木形體表示(description)、可視化和樹木形狀的測量、醫學圖像中的虛擬內窺漫遊和器官形狀表示、以及計算機視覺中的目標跟蹤等。圖1示出本發明算法流程圖圖2示出本發明採用的單面掃描數據圖3a、圖3b、圖3c示出本發明分離出來的位於枝幹上的點雲數據圖4示出本發明基於聚類方法得到的每個聚類的代表點圖5示出本發明得到的枝幹的骨架圖6示出骨架節點分類流程圖7本發明基於枝幹的骨架分類樹葉點雲的結果圖8a、圖8b和圖8c示出本發明將分類後的樹葉點雲分別求取的形狀圖9a、圖9b和圖9c示出本發明基於自動alpha-sh即e方法得到的整個掃描數據的形狀圖10a、圖10b和圖10c示出本發明對青桐數據的形狀的求取圖lla和圖10b示出本發明得到的位於邊界上的點雲數據和相應的外形圖12示出自動的阿爾法形狀(alpha-shape)方法流程圖13a至圖13h示出基於枝幹骨架分類結果的樹冠形狀的細節信息。圖13a至圖13h樹冠形狀的網格表示；圖13-1至圖13-8樹冠形狀的點雲表示。具體實施例方式下面將結合附圖對本發明加以詳細說明，應指出的是，所描述的實施例僅旨在便於對本發明的理解，而對其不起任何限定作用。1方法概述(overviewofapproach)本發明算法的核心在於基於距離變換提取樹木掃描數據的枝幹骨架、基於枝幹骨架對樹葉點雲進行立體分類、基於分類後的每個樹葉點雲用alpha-shape方法求取相應的形狀。如圖1示出本發明本發明算法流程圖，具體算法包括6個步驟(1.圖1中僅有6個步驟，請做好步驟標記，同時對每幅圖進行清楚的描述；2.對每幅流程圖中有的文字務必在文中出現，保證文圖一致)1、首先，對真實樹木的掃描數據(如圖2示出採用的單面掃描數據)通過交互式的觀察，選取Y坐標最小的點作為根節點，並對掃描數據中除這個根節點外的其它數據點進行距離變換，其中我們應用的是K近鄰的方法來完成這個任務，即將每個數據點和距離這個數據點最近的K個點相連接組成相應的邊，這樣這些邊和點就組成了一個權圖，每個邊的權是相應的兩個端點之間的歐式距離。這樣這個掃描數據中的任意兩點間的距離就是這個權圖中連接這兩個點的所有路徑中的最短路徑長度。而由根節點到其它掃描數據點的最短距離是非常有用的，一般點雲的數量是巨大的，傳統的迪傑斯特拉最短距離方法需要一個足夠大的二維矩陣，這是計算機一般承受不了的，所以我們只計算根節點到其他掃描數據點的最短距離，我們稱之為R距離。2、其次，由距離變換構造的權圖，我們將整個數據中位於主枝上的點進行分離。由步驟一，每個數據點都有相應的R距離，這樣我們可以選取適當的閾值A，若R距離小於閾值A，則相應的點我們就定義其在主枝上。如圖3a、圖3b和圖3c示出相對應的閾值取為1.6，1.4和0.5。由結果可以看出其中的圖3c比較好的分離出樹木的主枝部分。輸入的掃描數據是單面的，也就是不完全的，所以我們應用K近鄰方法時候，若參數K太小的話，則計算出來的權圖是不連接的，即產生若干個連接的子圖。若參數K太大，就會產生不正確的拓撲連接信息。譬如將屬於不同枝幹的點連接起來，實驗中我們選取K為100。3、再其次，計算主枝的骨架點。對於得到的位於主幹上的數據點，通過局部連接關係把它們轉化為一個樹狀聚類圖，提取每個聚類的代表點，從而構造一個兼顧分叉性和拓撲連接性的分類骨架(classificationskeleton)，此骨架的價值在於為位於樹木掃描數據上部的樹葉點雲進行分類。目前整個的掃描數據分成了兩個部分位於主枝上的點和位於樹木冠層的樹葉上的點。我們選取圖3c中最能代表主幹點雲的來計算骨架點。由於我們知道主枝上點到根節點的最短距離，所以我們應用聚類的方法將這些主枝上的點進行分類。我們首先計算這些主枝上的點到根節點的最短距離中的最大值rmax和最小值rmin，然後將區間[rmin，rmax]等分成50份，根據每個點到根節點的最小距離，將位於主幹上的這些點分成50類。正如我們所見，位於樹幹上的一個類中的點數據，彼此間的距離很小，但是位於主幹上的一個類中的點數據，由於可能分屬於不同的主幹，彼此間距離可能很大，為獲得相對真實的骨架，我們需要將分類後位於一個大類中的點數據，再次進行分類，將其分成不同的子類。即將一個大類中的分屬於不同主枝的點區別開。針對每個大類，首先取出一點，標記其屬於一個新的子類，遍歷這個點的K個近鄰，其中屬於這個大類的點，我們標記其屬於這個子類，然後對新加入這個子類的點同樣進行上面的這個過程，這是一個寬度優先的遍歷過程。直到新加入點的相應的K個近鄰都被處理完畢或者不屬於這個大類。然後我們從這個大類的剩餘點中取出一個未被處理過的新點，並標記其屬於另外一個新的子類，並開始一個新的寬度優先的遍歷過程來找到這個大類中屬於這個新子類的其它的點數據。直到這個大類中的點全部處理完畢，即它們全部子類所標記完畢。當我們用不同的大類和不同的子類標記了主幹的點數據後，為得到最後的骨架，需計算每個子類的代表點，這裡我們計算每個子類的中點作為代表點，表示未來的骨架點，當然我們也需對這個骨架點進行提煉，若子類中的點太少，譬如少於5個，那麼我們就拋棄這個子類相應的骨架點，認為這個骨架點對整個的骨架不會有太大的影響。如圖4所示基於聚類方法得到的每個聚類的代表點。在已知骨架點後，骨架點的數量已經大為減少，我們就可以應用傳統的迪傑斯特拉方法來計算這些骨架點到根節點的最小距離，同時也就得到了這些骨架點到根節點的最短的路徑，也就得出來這個樹幹的骨架(如圖5示出得到的枝幹的骨架)。4、然後，我們就可以應用這個枝幹骨架對位於整個數據上部的樹葉點雲進行分類。即根據樹葉點雲到骨架枝幹的距離將其聚類。在植物學中，不同的枝幹屬於不同的等級，即使相同等級的枝幹可能長度也是不同的，而恰恰是這些不同的枝幹影響了樹木外在的冠形的形狀，因此，我們首先將骨架點進行聚類，然後再聚類樹葉點雲。上一步我們得到的是骨架的有向圖，這裡我們先取出骨架的有向圖的一個葉子節點pl，要求這個葉子節點的y坐標是所有骨架節點中最大的，然後從這個葉子節點回溯到第一個分叉點p2，如果這兩個節點Pl和p2間的R距離大於l，那麼我們將這兩個節點pl和p2以及它們路徑上的節點都歸為一類，並停止尋找屬於這個類的其它節點，否則的話我們計算以這個分叉點p2為起始點的所有分支路徑的長度，如果所有分支路徑的長度和不小於l，那麼我們將位於這些分支路徑上的所有節點歸為一類，並且停止尋找屬於這個類的其它節點。否則的話若這個長度和小於l，那麼我們從目前這個分叉點p2繼續回溯去找下一個分叉點p3，並計算以目前這個分叉點p3為起始點的枝幹的總長度，直到這個枝幹的長度和大於l，我們將枝幹上的所有節點歸為一類，並標記其為處理過。然後我們取出目前未處理過並且y坐標是最大的一個葉子節點，繼續上面的過程，直到所有的葉子節點都處理過；這個算法的流程如圖6。我們將骨架節點分類後，計算樹葉點雲中的每個點到骨架節點的距離，並且以最近距離的骨架節點的類別來標記這個樹葉數據點，這樣我們就可以將樹葉點雲中的每個點進行聚類；本發明基於聚類的骨架分類葉子云的結果如圖7。5、隨後，用自動的阿爾法形狀(alpha-shape)方法計算每個聚類後的樹葉點雲形狀。首先我們不用骨架對整個的單面掃描數據P={Pi}進行分類，將整個掃描數據看作一個整體，對其進行德朗奈(Dela皿ay)三角剖分，剖分後，整個數據就獲得了一種拓撲信息，獲得了四面體T二{Tj}和三角面片F二{Fk}的集合，從外部看，這個四面體的集合組成了這個數據的凸包，數據的凸包是唯一的，但是這個凸包看上去沒有更多的細節。所以我們進一步處理它，計算每個四面體的外接球半徑R(Tj)和每個四面體的三角面片F二{Fk}的外接圓半徑r(Fk)，然後對四面體{Tj}進行分類，依據就是其相應的外接球半徑，我們先指定參數alpha值，然後所有的四面體可以分成兩類若R(Tj)>a，那麼Tj就是外部四面體；否則它就是內部四面體。所有的四面體的面{Fk}被分成三類對於位於凸包上的面，若它屬於外部四面體，那麼它就是外部面；否則，若它屬於內部四面體，那麼它就是邊界面。對於非凸包上的面，若它是兩個外部四面體的交集，則它是外部面；若它是兩個內部四面體的交集，則它是內部面；否則的話就是邊界面。而所有的邊界面會組成一個網格，這個網格就是對樹冠外形的近似。其中令r^是所有R(Tj)和r(Fk)的最大值，r^是所有R(T》和r(F。的最小值，令A=Armin，B=iirmax，A=0.9，ancU=1.1.我們得到一個區間[A，B]，阿爾法(alpha)形狀方法中的參數alpha在這個區間取值。顯然若阿爾法alpha>B，則網格M就是凸包，若alpha<A，則網格M將不是一個固體。找到合適的參數alpha是一個迭代的過程，我們先初始化alpha為區間[A，B]的中點，在每個迭代步驟，我們都驗證所有的邊界面是否組成了一個流形面，若是這樣，參數值就減少，否則的話參數值就增加，具體的流程見圖12。結果為圖10a、圖10b和圖10c、圖11a和圖llb，圖10a是桐樹的原始數據。圖10b圖是自動的阿爾法形狀方法的結果，圖10c圖是局部的特寫。圖lla是楓樹的位於邊界上的點，圖lib圖是計算的結果。這兩個數據的實驗細節如下表1所示。表1實驗數據tableseeoriginaldocumentpage10我們另外的方法是用樹木的骨架對樹葉點雲進行分類，如圖7所示，然後針對每個分類後的集合應用上面的方法，計算其相應的外形。結果如圖8a、圖8b和圖8c所示是同一實驗結果的不同角度展示。圖9a、圖9b和圖9c是單用自動的阿爾法形狀(ahpha-sh即e)方法計算的結果對比。圖13是樹冠外形的細節圖。本發明的方法的特色和創新在於根據樹木的特點，先選取根節點，利用距離變換方法求得其它點到根節點的最短距離，然後應用這個最短距離將整個的點雲數據分兩類，主幹數據和樹葉數據。利用到根節點的最短距離求對主幹數據進行聚類分析，先分出大類，對每個大類中的數據，再次聚類，分出子類，這個子類代表屬於不同的分枝。求出每個子類的代表點，並形成骨架，用這個估計分類樹葉點雲數據，然後對分類後的每個點雲數據求出其相應的形狀，得到整個樹的外在形狀。在很多樹木的建模中，這個樹冠的外在形狀可以有效的提供信息，表達樹木的結構和幾何特徵，輔助建模的準確性，並且樹冠的外在形狀對於研究樹木的資源，測量樹木的幾何尺度，為樹木建模軟體提供更多的數據。以上所述，僅為本發明中的具體實施方式，但本發明的保護範圍並不局限於此，任何熟悉該技術的人在本發明所揭露的技術範圍內，可理解想到的變換或替換，都應涵蓋在本發明的包含範圍之內，因此，本發明的保護範圍應該以權利要求書的保護範圍為準。權利要求一種基於形狀分析的樹冠外形提取方法，其特徵在於，該方法的步驟包括步驟S1用雷射掃描儀掃描植物的單面，獲得的掃描數據稱為點雲數據；步驟S2從點雲數據中找到根節點，用K近鄰的方法對整個點雲數據進行距離變換，構造這些點雲數據中的點到根節點的權圖，計算點雲數據的每個點到根節點的最小距離，利用這個最小距離從整個點雲數據中分離出位於主枝上的點雲數據；步驟S3對位於主枝上的點雲數據進行聚類分析，生成樹狀聚類圖，用於尋找形體的分叉位置和末梢位置，在每個聚類中，根據距離再次聚類，得到聚類中的子聚類，對每個子聚類，用算術平均的方法計算每個子聚類的代表點，作為主枝骨架點；步驟S4將所有子聚類的代表點形成集合，再用所有代表點集合構造具有中心性、分叉性和拓撲連接性的主枝骨架；步驟S5從主枝骨架上部的葉子節點或稱末梢位置開始，對骨架的各個分支進行分類，使分類後的每個分支長度達到一定標準；對主枝骨架進行分類的基礎上，對點雲數據中的位於樹冠的葉子點雲數據進行分類；步驟S6對每個分類後的葉子點雲數據分別計算它們的形狀，首先對其中的一個分類後的點雲進行三維的德朗奈三角剖分，建立點雲中每個數據點的拓撲結構，得到三角面片和四面體，對這些四面體和三角面片分別計算它們的外接球和外接圓的半徑，得到包含這些半徑的最小區間[A，B]，取阿爾法形狀方法中的參數阿爾法為區間[A，B]的中間點，把求得的四面體和三角面片進行分類，四面體分類為外部的四面體和內部的四面體，而三角面片分類為內部的三角面片、外部的三角面片以及邊界的三角面片，若邊界的三角面片組成的是個閉合的體，那麼將參數阿爾法取成[A，B]下部區間的中點繼續這個過程，直到相鄰的兩個參數之差小於給定的充分小的值，該充分小的值是取掃描數據中兩點間最小距離的百分之一，這時候這兩個參數中，較大的一個對應的邊界三角面片的集合，就是整個樹冠的外在形狀。2.如權利要求1所述樹冠外形提取方法，其特徵在於，所述從點雲數據中找到根節點，是按照數據點中Y坐標最小的方法找到根節點。3.如權利要求1所述樹冠外形提取方法，其特徵在於，所述構造這些點雲數據中的點到根節點的權圖，是通過K近鄰的方法，找到K個距離數據點最近的點，將這些距離數據點最近的點和數據點連接起來形成權圖，而權圖中的權就是兩點間的距離。4.如權利要求1所述樹冠外形提取方法，其特徵在於，所述的計算點雲數據的每個點到根節點的最小距離，是在已知權圖的基礎上，計算從根節點到數據點路徑中權和最小的路徑，這個權和就是這個數據點到根節點的最小距離。5.如權利要求1所述樹冠外形提取方法，其特徵在於，所述的聚類分析是根據主枝點雲數據中的每個數據點P到根節點的已知最小距離進行聚類分析，形成大的聚類，每個大的聚類中的點屬於一定的距離範圍。6.如權利要求1所述樹冠外形提取方法，其特徵在於，所述的再次聚類是在得到的每個大的聚類中，應用距離變換再次進行聚類分析，得到子聚類。7.如權利要求1所述樹冠外形提取方法，其特徵在於，所述構造分類骨架，是將每個子聚類選出中心點，然後將這些中心點中Y坐標最小的點作為根節點，計算這些中心點中的其它點到這個根節點的最小距離路徑，按照順序連接路徑上的點構造出這個主枝骨架。8.如權利要求1所述樹冠外形提取方法，其特徵在於，所述的對骨架的各個分支進行分類，首先找到主枝骨架各個末梢代表點，選取Y坐標最大的末梢點作為起始點，沿著主枝骨架根節點到這個起始點的最短路徑的反方向進行移動，當到達第一個分叉點的時候計算，計算目前路徑的長度，若目前路徑的長度大於給定的值1，則目前經過路徑上的點歸為一類，然後選取下一個未處理過的並且Y坐標是最大的末梢點進行同樣的回溯路徑，否則計算以第一個分叉點為初始點的所有子枝的長度和；若初始點的所有子枝的長度和大於給定的值l，則以第一個分叉點為初始點的所有子枝上的代表點歸為一類，否則從目前分叉點，沿著最小路徑繼續回溯到下一個分叉點，將上面的所有子枝的長度和加上第一個分叉點與目前分叉點間的距離得到目前路徑長度和，若這個目前路徑長度和大於給定的值，則目前路徑上的所有代表點歸為一類，否則計算所有以目前的分叉點為初始點的所有子枝的長度和，若這個所有子枝的長度和大於給定的值1，則將目前路徑經過的代表點歸為一類，否則就繼續上面的過程，沿著最短路徑繼續回溯直到子枝的長度和大於給定的值l。9.如權利要求1所述樹冠外形提取方法，其特徵在於，所述的對點雲數據中的位於樹冠的葉子點雲數據進行分類，在已經將主枝骨架分類的基礎上，依據葉子點雲數據中的每個數據點到主枝骨架距離最近的原則，將整個的葉子點雲數據進行分類，到主枝骨架同一類分支最近的葉子數據點歸為一類，否則就分屬不同的類。10.如權利要求1所述樹冠外形提取方法，其特徵在於，所述外部的四面體和內部的四面體，是四面體有唯一的外接球，這個外接球半徑若大於預先給定的參數阿爾法，則是外部的四面體，否則就是內部的四面體。11.如權利要求1所述樹冠外形提取方法，其特徵在於，所述內部的三角面片、外部的三角面片以及邊界的三角面片，每個三角面有唯一的外接圓，而這個外接圓半徑是這個三角面的特徵之一，三角面分成兩類位於凸包上和位於凸包內部；對於位於凸包上的三角面，若其所在的四面體是外部的四面體，則這個三角面是外部的三角面，否則其為邊界的三角面；對於位於凸包內部的三角面，其為兩個四面體所共享，這兩個相鄰四面體若其都是外部的四面體，則這個三角面上就是外部的三角面，若這兩個四面體都是內部的四面體，則這個三角面就是內部的三角面，否則這個三角面就是邊界的三角面。全文摘要本發明公開一種基於形狀分析的樹冠外形提取方法。本發明處理的數據是用雷射掃描儀對整個植物單面掃描，獲得植物的單面掃描點雲數據，首先在這個點雲數據中找到根節點，然後應用最短距離的方法將點雲數據分成樹枝點雲和樹葉點雲。從樹枝點雲提取相應的骨架，依據樹的分支特點將骨架分成若干個部分，然後用分類後的樹枝骨架將樹葉點雲分類。對每個分類後的樹葉點雲進行德朗奈三角剖分，獲得的是四面體和三角面片，將三角面片分成外部，內部和邊界等三類，其中位於邊界的三角面片就組成了閉合體，用這個閉合體來表示這個分類樹葉點雲的形狀。而每個分類樹葉點雲的形狀合集就表示了整個樹冠的外形。文檔編號G06T7/00GK101783016SQ200910242750公開日2010年7月21日申請日期2009年12月16日優先權日2009年12月16日發明者張曉鵬,朱超,李紅軍申請人:中國科學院自動化研究所