[發明專利]基于格網索引和球樹的傾斜模型和激光點云融合方法

在審

• 申請號: 202110436234.0
• 申請日: 2021-04-22
• 公開（公告）號: CN113177902A
• 公開（公告）日: 2021-07-27
• 發明（設計）人: 陳澤遠;許張柱;張先文;王賓賓;李庚新;丁保才
• 申請（專利權）人: 陜西鐵道工程勘察有限公司
• 主分類號: G06T5/50
• 分類號: G06T5/50;G06T17/20;G06T17/00;G06F16/51;G06F16/53
• 代理公司: 西安新思維專利商標事務所有限公司 61114
• 代理人: 李罡

本發明涉及一種基于格網索引和球樹的傾斜模型和激光點云融合方法，針對整個測區先建立格網索引，然后在每個格網內建立Ball?Tree結構，各個Ball?Tree為各自獨立的索引結構；使用Ball?Tree快速搜索到最鄰近的模型點，并將紋理信息賦值給該點，實現融合。本發明通過生成格網索引，并行構建Ball?Tree，提升了運行效率；先對整個測區建立格網索引，然后在每個格網內建立Ball?Tree結構，大幅減少Ball?Tree的深度；此外，由于各個Ball?Tree為各自獨立的索引結構，因此，每個Ball?Tree的生成和查詢都可并行運行，效率得到大幅提升。

技術領域

本發明涉及工程測量點云數據處理技術領域，具體涉及一種基于格網索引和球樹的傾斜模型和激光點云融合方法。

背景技術

傾斜攝影測量及三維激光掃描技術是三維空間快速獲取信息的重要手段，被廣泛應用在地理信息系統、國家基礎建設規劃等眾多領域。通過該技術采集得到的傾斜模型數據和三維激光點云數據是三維地理信息空間重要的數據來源，同時，對傾斜模型和激光點云進行融合，同時對數據的三維坐標與紋理信息進行提取、綜合，是后期數據處理及應用的關鍵步驟，也是當前的研究熱點之一。

目前，國內外學者針對空間數據的組織進行了大量的研究工作，其中，廣泛應用的組織策略主要有格網索引、四叉樹索引、八叉樹索引、KD樹索引、R樹及其變種樹索引等。海量點云的空間形態千差萬別，數據量巨大，單純使用一種索引模型往往難以進行高效管理，為了充分發揮不同索引的優勢，多數學者將重心放在了兩種及以上索引的混合索引模型的研究。

KDTree的優勢是可以遞增更新，新的觀測點可以不斷地加入進來。找到新觀測點應該在的區域，如果它是空的，就把它添加進去，否則，沿著最長的邊分割這個區域來保持接近正方形的性質。這樣會破壞樹的平衡性，同時讓區域不利于找最近鄰點，我們可以當樹的深度到達一定值時重建這棵樹。

然而，KDTree也有問題。矩形并不是用到這里最好的方式。偏斜的數據集會造成我們想要保持樹的平衡與保持區域的正方形特性的沖突。另外，矩形甚至是正方形并不是用在這里最完美的幾何形狀。

為了解決沿著笛卡爾坐標進行劃分的低效率，球樹（Ball-Tree）在KDtree的二叉樹樹形結構上進行了改進，其在一系列嵌套的超球體上分割數據。也就是說：使用超球面而不是超矩形劃分區域。雖然Ball-Tree在多維數據上表現的很高效，但是，在構建數據結構的花費上要大過于KDtree，極大地影響算法效率。

發明內容

本發明的目的是提供一種基于格網索引和球樹的傾斜模型和激光點云融合方法，解決使用KDTree組織大數據量點云時存在的問題，包括：第一，由于點云具有多維屬性數據，使用KDTree進行查詢操作效率較低；第二，由于點云數據量較大，直接構建Ball-Tree結構將導致樹的深度過大，極大地降低了Ball-Tree的查詢效率。

本發明所采用的技術方案為：

基于格網索引和球樹的傾斜模型和激光點云融合方法，其特征在于：

所述方法為：

針對整個測區先建立格網索引，然后在每個格網內建立Ball-Tree結構，各個Ball-Tree為各自獨立的索引結構；

使用Ball-Tree快速搜索到最鄰近的帶坐標的傾斜模型節點，并將紋理信息賦值給該點，實現融合。

所述格網索引的建立過程為：

獲取傾斜模型數據的二維包圍盒，遍歷點云數據，使用每個包圍盒對點云數據進行裁剪，獲取落在該包圍盒內的激光點，使模型數據和點云塊一一對應。

所述Ball-Tree結構的建立過程為：

（1）遍歷每個格網，在其中找到距離最遠的兩個激光點 a 和 b，以它們為種子點；

（2）遍歷其余所有點，對每個激光點s，分別計算其與 a 和 b的距離, 離 a 近就歸到 a 的子簇, 對 b 同理；