[發明專利]基于邊長比約束的離散點區域拓撲邊界追蹤方法

無效

• 申請號: 200810237435.2
• 申請日: 2008-12-26
• 公開（公告）號: CN101477691A
• 公開（公告）日: 2009-07-08
• 發明（設計）人: 黃先鋒;程曉光;張帆
• 申請（專利權）人: 武漢大學
• 主分類號: G06T7/60
• 分類號: G06T7/60;G01S7/48;G01S17/02
• 代理公司: 武漢華旭知識產權事務所
• 代理人: 劉 榮

技術領域

本發明涉及一種基于邊長比約束的離散點區域拓撲邊界追蹤方法，特別是涉及如何從離散點中追蹤出外邊界、內部空洞邊界以及在存在不同區域時追蹤出區域邊界的方法，屬于離散點云分析處理領域。?

背景技術

機載激光掃描(Airborne?Laser?Scanner，簡稱ALS；又稱機載激光雷達，Airborne?Light?Detection?And?Ranging，簡記LiDAR)是近十幾年來快速發展的一種新型的測量技術，廣泛用于地面數據探測和模型的恢復、重建等應用中，顯示出了巨大的前景(Vosselman，Kessels?et?al.2005)。機載激光掃描測距系統是集激光、全球定位系統(GPS)和慣性導航系統(INS)三種技術與一身的空間測量系統(Li，Li?et?al.2000)，能夠快速、精確獲取地面信息。儀器通過反射鏡快速而有序地旋轉，將激光脈沖發射體發出的窄束激光脈沖依次掃過被測區域，測量每個激光脈沖從發出經被測物表面再返回儀器所經過的時間(或者相位差)來計算距離，同時掃描控制模塊控制和測量每個脈沖激光的角度，結合傳感器所攜帶的POS系統，最后計算出激光點在被測物體上的三維坐標。這些激光點即為對象表面的采樣點，一般數量巨大，被稱為“點云”。新型的LiDAR系統可以接收多次反射，記錄每次反射的強度信息，提供水平間距小于1m、垂直精度在15～20cm左右的密集點陣數據(Hu?2003)，在獲取點陣數據的同時，其附帶的高精度CCD相機可以同時獲取高清晰影像數據。LiDAR數據經過相關軟件處理后，可以生成高精度的數字地面模型DEM、等高線圖及正射影像圖，通過將LiDAR數據獲取的建筑物模型與影像配準，可以得到高精度的三維建筑物模型。目前，LiDAR在農業、水利電力設計、林業、公路鐵路設計、國土資源調查、交通旅游與氣象環境調查、災害防治、城市規劃等各大領域中得到廣泛應用。?

發明內容

本發明的目的是提供一種基于邊長比約束的離散點區域拓撲邊界追蹤方法，該方法通過提出一個建立在三角網基礎，基于三角形邊長比約束的離散點區域拓撲邊界搜索算法，實現從離散點中追蹤出外邊界、內部空洞邊界以及在存在不同?區域時追蹤出區域邊界。?

實現本發明目的采用的技術方案是基于邊長比約束的離散點區域拓撲邊界追蹤方法，該方法包括以下步驟：?

(1)對離散點利用逐點插入法建立不規則三角網(TIN)；?

(2)利用不規則三角網找出初始邊界得到包圍數據的外環，轉入步驟(4)；?

(3)在三角網內部尋找至少有一條邊長度大于空洞長度閾值的三角形，設三角形的三條邊組成一個環，轉入步驟(4)；?

(4)對環中每條長度超過閾值的線段向內細化(在尋找內部空洞邊界時為向外細化)，獲得粗外邊界；?

(5)對粗邊界按照邊長比進行擴展逐步細化，并采用邊長比例作為限制條件，搜索到更準確的凹邊界；?

(6)在點云中的點存在區域屬性的時候，分割點云外部邊界，得到邊界點連續且右鄰域相同的邊界段；?

(7)在整個點云中搜索三個頂點的區域標志不完全相同的三角形或者直接利用外部邊界上區域標志不同的前后兩點所在的內部三角形，內插出邊界點，確定下一步搜索方向；?

(8)根據邊界段起點和終點，連接邊界段，獲得每個區域的邊界。?

本發明具有如下的優點：?

(1)避免了采用圖像的方法進行內插帶來的精度損失，保持了原始點的特性。?

(2)可以較為準確地追蹤出點云的凹邊界。?

(3)可以在閾值合適的情況下追蹤出空洞邊界。?

(4)在離散點有區域屬性的時候可以追蹤出各個區域的邊界。?

(5)適應性好，尤其是凹多邊形邊界對閾值設定不敏感。?

(6)對點密度的依賴不大。?

附圖說明

圖1為本發明流程圖。?

圖2為在追蹤點云外邊界時利用三角形找出點云的初始邊界的示意圖。?

圖3為三角網內部存在空洞時的特征示意圖。?

圖4為根據初始邊界上的組成線段長度進行細化內縮的示意圖。?

圖5是只利用邊界組成線段邊長閾值進行追蹤，可能出現的追蹤到不穩定三角形的示意圖。?

圖6是在點有區域屬性的時候點云內部不同區域邊界的示意圖。?

圖7是點云內部的三角形有兩個頂點區域屬性相同，另一個不同的示意圖。?

圖8是點云內部的三角形三個頂點區域屬性均不同的示意圖。?