[發明專利]基于概率論的二維點云外包輪廓處理方法、裝置及介質

在審

• 申請號: 202011473619.6
• 申請日: 2020-12-15
• 公開（公告）號: CN112598799A
• 公開（公告）日: 2021-04-02
• 發明（設計）人: 趙自力;張志翱;張秀鵬;劉紀東;許亞峰;許明生;程志萍;王亞軍;張浩彬;龔祎壟
• 申請（專利權）人: 珠海市規劃設計研究院
• 主分類號: G06T17/20
• 分類號: G06T17/20;G06T7/13
• 代理公司: 廣州嘉權專利商標事務所有限公司 44205
• 代理人: 葉琦煒

本發明涉及一種基于概率論的二維點云外包輪廓處理方法、裝置及介質的技術方案，包括：S100，使用Bowyer?Watson算法處理點云數據，生成Delaunay三角網；S200，計算Delaunay三角網所有邊長并進行降序排列，通過概率論計算長度閾值；S300，采用迭代法循環刪除可退化邊，得到點云外包輪廓的多邊形。本發明的有益效果為：使用概率論方法計算核心參數，不依賴于先驗知識或人工干預，實際處理效果良好；計算結果具有良好的冪等性。

技術領域

本發明涉及計算機圖形和空間地理信息領域，具體涉及了一種基于概率論的二維點云外包輪廓處理方法、裝置及介質。

背景技術

應用于計算機圖形處理、空間地理信息等值線生成。在計算機圖形處理、空間數據分析過程中，經常需要通過離散的點集合，提取研究對象的外部輪廓，從而實現幾何建模和有效范圍界定。比如在測繪行業，為了獲取復雜環境的地形圖，一般通過人工或者無人機雷達的方式進行抽樣測量，抽樣位置點是一個個離散點，如果離散點云整體輪廓為彎曲的條帶狀，確定測量區邊界存在一定的困難。傳統方法都是采用Delaunay三角剖分等方法來處理，提取的外部輪廓存在偏差。

現有技術在二維點云外部輪廓提取和地理空間數據處理過程中，經常出現彎曲形、條帶狀的點云，其外部輪廓是凹多邊形，直接使用Delaunay三角剖分處理方法得出的結果是凸多邊形，不滿足實際需求；目前主流凹多邊形輪廓提取方法有滾邊法、滾球法、盒的邊界搜索法、行列法以及基于Delaunay三角網退化法等。目前凹多邊形輪廓提取方法都涉及到一個核心的長度參數，比如滾邊法的邊長、滾球法的半徑等，這個參數決定了生成的多邊形的凸凹程度，在實際生產處理中，這些參數依賴于先驗知識，需要人工判斷和干預，缺乏科學明確的標準；其次，現有凹多邊形提取方法不具備冪等性，計算結果有一定的隨機性，對于相同的輸入，同一個算法多次計算的結果可能不相同，不適用于某些強一致性領域。

發明內容

本發明的目的在于至少解決現有技術中存在的技術問題之一，提供了一種基于概率論的二維點云外包輪廓處理方法、裝置及介質，不依賴于先驗知識或人工干預，實際處理效果良好，計算結果具有良好的冪等性。

本發明的技術方案包括一種基于概率論的二維點云外包輪廓處理方法，其特征在于，該方法包括：S100，使用Bowyer-Watson算法處理點云數據，生成Delaunay三角網；S200，按長度計算Delaunay三角網所有邊長，并進行降序排列，通過概率論計算長度閾值；S300，采用迭代法循環刪除可退化邊，得到點云外包輪廓的多邊形。

根據所述的基于概率論的二維點云外包輪廓處理方法，其中S200包括：S210，計算Delaunay三角網中所有的邊長，加入邊長列表中；S220，按長度大小，對邊長列表中的元素進行降序排序；S230，取邊長列表第N個元素值，作為長度閾值，其中應該是N為不大于n的最大正整數，n＝0.05m，m為邊長列表的元素數量。

根據所述的基于概率論的二維點云外包輪廓處理方法，其中S300包括：S310，遍歷Delaunay三角網，建立三角形、邊、點的拓撲關系；S320，統計邊的共享關系，將不共享邊加入不共享邊列表，不共享邊的頂點加入不共享邊頂點列表；S330，遍歷不共享邊列表，如果邊的對應頂點不在不共享邊頂點中，則該邊屬于可退化邊，將可退化邊加入可退化邊列表；S340，如果可退化邊列表為空，則執行S360；如果可退化邊列表不為空，獲取其中最長邊；S350，如果最長邊的長度小于所述長度閾值，執行S360；否則，從不共享邊中移除最長邊，將最長邊所屬三角形的另外2條邊加入不共享邊列表，將最長邊的對應頂點加入不共享邊頂點列表，清空可退化邊列表，返回S330；S360，將不共享邊列表作為外部輪廓邊進行連接，得到凹包多邊形。

根據所述的基于概率論的二維點云外包輪廓處理方法，其中該方法還包括初始化Delaunay三角網。