[發明專利]一種基于分支定界法的自動切圖方法

有效

• 申請號: 202110038919.X
• 申請日: 2021-01-12
• 公開（公告）號: CN112883290B
• 公開（公告）日: 2023-06-27
• 發明（設計）人: 陳龍;高凌霄;劉坤華
• 申請（專利權）人: 中山大學
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06F16/53;G06F16/56;G01S7/48
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 陳偉斌

1.一種基于分支定界法的自動切圖方法，其特征在于，包括切圖觸發器，離線處理和分支定界法三個部分，其中，

首先，進行離線處理，用戶輸入某一地圖關聯的地圖，隨后算法通過簡單的邏輯，將地圖關系更新到數據庫中；

然后，通過切圖觸發器進行判斷是否需要切圖，一部分是判斷定位數據是否超出地圖邊界，若超出，則需要切圖，進入下一步；另一部分是判斷當前點云數據的占據柵格地圖與定位所屬子圖間的匹配得分，若得分低于設定的閾值，則需要切圖，也進入下一步；

最后，通過分支界定法尋找當前激光雷達采集到的點云屬于哪個占據柵格地圖，直到尋找到所屬的占據柵格地圖后，則進行切圖；具體步驟包括：首先，將下界定義為用戶提供的一個閾值，同時將搜索空間構造為樹形結構，內部節點代表一個子搜索空間，葉子節點代表一個精確的結果；開始搜索時從頂層節點開始往下搜索，當遇到一個節點時，根據該節點位姿變換矩陣旋轉當前幀占據柵格地圖得到新地圖，遍歷新地圖所有點，根據載入的子圖占據值更新當前子圖舊的占據值，將占據值進行加和，若小于下界，說明結果太差，該分支被剪枝，返回頂層重新查找；若大于上界，繼續往下搜索，直到葉子節點，抵達葉子節點后，使用葉子節點占據值得分更新下界，返回頂層重新查找，直到查找到適配的子圖。

2.根據權利要求1所述的一種基于分支定界法的自動切圖方法，其特征在于：使用分支定界法縮小搜索域，找出唯一一個符合要求的占據柵格地圖。

3.根據權利要求1所述的一種基于分支定界法的自動切圖方法，其特征在于：通過外置定位算法獲得定位結果，通過該定位結果判斷是否產生地圖越界情況，并以此判斷是否需要切圖。

4.根據權利要求1所述的一種基于分支定界法的自動切圖方法，其特征在于：主線程處理判斷是否產生越界。

5.根據權利要求1所述的一種基于分支定界法的自動切圖方法，其特征在于：當在數據庫中添加一個地圖時，需要添加該地圖緊鄰于哪些地圖，算法將對每一個地圖的緊鄰關系維護一個數據結構。

6.根據權利要求1所述的一種基于分支定界法的自動切圖方法，其特征在于：預先通過一個線程去載入存儲在計算機中的地圖數據，該地圖數據包括地圖的各個節點和子圖，節點即激光雷達一幀構成的占據柵格地圖，子圖即多個節點構成的數據。

7.根據權利要求1所述的一種基于分支定界法的自動切圖方法，其特征在于：定義占據值如下，占據柵格某個格點有物體的概率；求取兩占據柵格的相對位姿變換就是求取一個旋轉，使得兩占據柵格合并成的柵格地圖占據值最大。

8.根據權利要求1所述的一種基于分支定界法的自動切圖方法，其特征在于：將所有的地圖數據全部載入一個專門容器中，并提供一個閾值，以作為分支定界法的下界，當需要進行切圖時，算法讀取存儲在計算機中的數據，該數據保存有占據柵格在不同搜索空間中的預算得分；算法將當前激光雷達點云數據構造成占據柵格地圖，根據粗糙的搜索空間計算當前該搜索空間的最高得分。

9.根據權利要求8所述的一種基于分支定界法的自動切圖方法，其特征在于：根據粗糙的搜索空間計算當前該搜索空間的最高得分后，若高于閾值，則進入該搜索空間繼續搜索，若低于閾值，則進行減枝，縮小搜索域；這樣一直搜索到一個精確的沒有子搜索空間的位姿，用這個占據值得分去更新閾值。

10.根據權利要求4所述的一種基于分支定界法的自動切圖方法，其特征在于：當有越界情況發生時，開啟一個線程進行分支定界法搜索。