[發明專利]一種適用于高維散亂點云的索引查詢方法

在審

• 申請號: 201410301833.1
• 申請日: 2014-06-27
• 公開（公告）號: CN104050283A
• 公開（公告）日: 2014-09-17
• 發明（設計）人: 劉仁義;張豐;杜震洪;陳明;宣偉浩;郭綠奕
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 張法高

技術領域

本發明涉及空間索引技術領域，尤其涉及一種適用于高維散亂點云的索引查詢方法。

背景技術

空間索引是一種依據空間對象的位置、形狀或空間對象之間的某種空間關系而組織、排列的數據結構，其中包含空間對象的標識、外接矩形以及指向空間對象實體的指針等概要信息。高維散亂點云數據具有數據量大、空間分辨率高等特點，在后續的數據處理中需要對其進行頻繁地范圍查詢。為此有必要預先對其進行有效的組織和索引，以提高后續的查詢效率。目前針對點云數據采用較多的索引有2ⁿ叉樹索引、格網索引、R樹索引等。2ⁿ叉樹索引實現簡單，適用于分布相對均勻的數據；格網索引查詢效率較高，但其分辨率單一，通用性不高；R樹索引具有較高的通用性，但其中的最小外包矩形有可能交疊，造成一定的數據冗余，且隨著空間維度的擴展，其查詢用時顯著增加。

發明內容

本發明的目的是克服現有高維點云數據索引方法存在的不足，根據降維、并行處理的思想，提供一種適用于高維散亂點云的索引查詢方法。

適用于高維散亂點云的索引查詢方法包括如下步驟：

1)根據給定的高維散亂點云數據(含m個點，維度為n)構建點集P＝{p₁,p₂,...,p_m}，點集中任意一點p_i的坐標為(a_i1,a_i2,...,a_in)，存于邏輯主節點；

2)一個邏輯主節點配套n個邏輯子節點(個數與點云維數相等)，前者將點集P中每一個點p₁,p₂,...,p_m的id及其第j(j＝1,2,...,n)維坐標信息(a_1j,a_2j,...,a_mj)分別發送至編號為j的邏輯子節點，后者接收后根據各點第j維坐標的大小順序建立B⁺樹索引；

3)對于n維查詢區域R＝((s₁,t₁),(s₂,t₂),...,(s_n,t_n))，邏輯主節點將其在第j(j＝1,2,...,n)維上的投影(s_j,t_j)分別發送至編號為j的邏輯子節點，后者接收后基于之前創建的B⁺樹索引查找位于范圍(s_j,t_j)之內的點，并將點的id返回給邏輯主節點；

4)邏輯主節點計算所有邏輯子節點返回的點id的交集，該交集即為高維散亂點云針對范圍R的查詢結果。

步驟2)、3)和4)所述的n個邏輯子節點在物理上可部署于數量少于n個的機器上，即一臺機器可部署多個邏輯子節點程序。

步驟3)所述邏輯子節點查找位于范圍(s_j,t_j)之內點的方法為：獲取關鍵字s_j在B+樹索引中的位置，再順著連接B+樹葉子節點的雙向鏈表向右掃描，直到關鍵字大于t_j為止，掃描所及的葉子節點對應位于范圍(s_j,t_j)之內的點。

步驟4)所述邏輯主節點計算n個邏輯子節點返回點id交集的方法為：獲取返回點個數最少的邏輯子節點返回的點id集合K，對于其中的每一個點id，判斷它是否也在其它邏輯子節點返回的點id集合中出現。只要有一個邏輯子節點返回的點id集合不包含這個點id，就將它從K中刪除，繼續判斷K中下一個點id。K中每一個點id都經過如此判斷之后，最終剩下的點id即為n個邏輯子節點返回點id的交集。

本發明與現有高維點云數據索引方法相比具有的有益效果：

將n維空間的范圍查詢轉換為n個并行的一維空間范圍查詢，大幅提高了高維散亂點云的查詢效率，有效解決了現有索引方法存在的分辨率單一、通用性不高、數據冗余等問題。

附圖說明：

圖1為本發明索引創建階段的流程圖；

圖2為本發明范圍查詢階段的流程圖。

具體實施方式：

適用于高維散亂點云的索引查詢方法包括如下步驟：