[發明專利]基于空間網格劃分的快速點云配準方法、裝置和設備

有效

• 申請號: 202110795806.4
• 申請日: 2021-07-14
• 公開（公告）號: CN113706587B
• 公開（公告）日: 2022-12-09
• 發明（設計）人: 趙宏;劉發恒;張春偉;胡敏;鮑勍慷;張天宇;張振洋
• 申請（專利權）人: 西安交通大學
• 主分類號: G06T7/30
• 分類號: G06T7/30;G06T7/11
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 王艾華

本發明公開了基于空間網格劃分的快速點云配準方法、裝置和設備，所述方法根據點云數據的空間范圍，構建能容納完整視角點云的三維立體空間，將立體空間依據點云密度劃分為多個子空間網格，確立空間網格的序列坐標，將點云序列轉化為空間網格序列，解決了點云無序性問題。在點云精配準算法中，ICP方法要依據點云序列查找最近鄰點，現有構建點云序列的方法如K?D樹時間復雜度較高，并且迭代求解耗時，影響點云配準效率。通過劃分空間網格，借助網格序列的鄰域信息獲得點云序列的鄰域信息，降低構建點云序列的時間復雜度，加快點云鄰域信息的搜索，并且各個網格之間查詢互不干擾，可以借助GPU并行處理，極大提高了點云配準速度。

技術領域

本發明屬于視覺測量技術領域，具體涉及基于空間網格劃分的快速點云配準方法、裝置和設備。

背景技術

在三維測量中，由于測量設備視場有限，加之被測物體外形復雜，單次測量往往無法將物體待測區域覆蓋完整，因此需要從不同視角對物體分別進行測量，然后通過點云配準的方式還原被測物體的全視角三維形貌。點云配準可以分為粗配準和精配準兩步。粗配準指的是在兩幅點云之間的變換完全未知的情況下進行較為粗糙的配準，目的主要是為精配準提供較好的變換初值；精配準則是給定一個初始變換，進一步優化得到更精確的變換。目前應用最廣泛的點云精配準算法是迭代最近點算法(Iterative Closest Point,ICP)及其優化算法。

ICP算法中查找最近點對的過程是整個ICP算法的速度瓶頸，ICP方法要依據點云序列查找最近鄰點，目前最主流的ICP算法是將目標點云用K-D樹的形式組織，利用K-D樹的空間分割特性來加速查找。將目標點云中所有點作為K-D樹的節點，其中每輸出一個節點都要進行一次排序，且所有節點串行輸出，時間復雜度較高。對于數量龐大的點云來說，需要進行高密度計算，迭代求解耗時，在CPU上運行時計算速度慢，影響點云配準效率，無法保證算法的低延時，無法滿足實時場景的速度要求。這是ICP算法的一個缺陷，有待針對性研究進行補足。

發明內容

本發明提供了基于空間網格劃分的快速點云配準方法、裝置和設備，解決了點云無序性問題，避免了構建K-D樹的時間復雜度，借助硬件并行計算為快速實現ICP點云精配準提供了解決方案。

為達到上述目的，本發明所述基于空間網格劃分的快速點云配準方法，包括以下步驟：

步驟1：根據全視角的點云數據的空間范圍，構建能容納所有視角點云數據的三維立體空間；

步驟2：確立三維立體空間的坐標原點，依據點云密度，將三維立體空間沿X、Y、Z三個坐標軸劃分為多個空間網格，并對每個空間網格進行編號；

步驟3：將所有視角的點云數據填入空間網格，計算每個視角的點云數據中的每個點落入的空間網格編號；

步驟4：用落入一個空間網格內的所有點的重心近似代替其他點，保證一個空間網格中至多含有一個點；

步驟5：對多視角點云數據進行粗配準，得到精配準的位置初值；

步驟6：對粗配準后的點云數據進行精配準，以最近鄰點為點云匹配點，借助空間網格編號的鄰域信息獲得點云編號的鄰域信息，查詢到最近鄰點，得到源點云和目標點云之間的最近鄰點對；

步驟7：并行處理計算最近鄰點對的協方差矩陣，求解得到源點云的位姿變換矩陣，根據位姿變換矩陣進行位姿調整，得到更新后的源點云，用更新后的源點云進行迭代，當迭代結果達到配準精度或者達到迭代次數上限時，停止迭代，輸出配準結果。

進一步的，步驟3中，計算每個點(x,y,z)落入的空間網格編號(i,j,k)公式為: