ScanContext論文詳解：Lidar SLAM 回環檢測、空間描述符
Figure 1. 激光雷達沿著方位角(淺藍)與放射方向（黃）的Bin分割 [1]
Figure 2. Scan Context示意圖 [1]
1
淺讀文章Scan Context，從英文字面理解就是“掃描 上下文”。類比于我們閱讀的時候，需要理解上下文，才能明白其意，LidarSLAM在進行回環檢測的時候，也需要將“上下文” （之前的數據）進行比較，方才知道我們是不是又走到了之前的同一個地方（回環）。Scan Context這篇文章由韓國KAIST大學的Giseop Kim和Ayoung Kim所寫，它的主要特點是提出了Scan Context這個非直方圖的全局描述符，來幫助我們對“上下文”（當前/之前的數據）進行更快速、有效地搜索。典型的應用就是在LiDAR SLAM中進行回環檢測和Place Recognition。2
提出的方法?The representation that preserves absolute location information of a point cloud in each bin （如圖2所示）?Efficient bin encoding function? Two-step search algorithm3
算法流程
3.1 Scan Context的創建
(1) 與Shape Context的淵源
Scan Context這個算法其實一開始是由Shape Context [2] 所啟發的，而Shape Context是把點云的 local Keypoint 附近的點云形狀 encode 進一個圖像中。Scan Context的不同在于，它不僅僅是count the number of points,而是采用了maximum height of pointsin each bin（簡單來說，就是取每一個bin中的所有point的z軸最高點的value作為這個bin的value）。(2) 為什么選擇Maximum height？
a. The reason for using the height is to efficiently summarize the vertical shape of surrounding structures.b. In addition, the maximum height says which part of the surrounding structures is visible from the sensor.c. This egocentric visibility has been a well-known concept in the urban design literature for analyzing an identity of a place(3) Partition a 3D scan
首先，對每一次Scan進行分割：? Nr: number of rings （黃色圈圈）? Ns: number of sectors （淺藍色/綠色？的格子）? Lmax: 雷達每一個射線的最遠距離? Radial Gap between rings =
? Sector弧度 =
? 文章中: Nr=20, Ns=60
(4) 給每個Bin進行賦值：Bin Encoding
就是指the set of points belonging to the bin where the ith ring and jth sector overlapped。? z(?)是指
中一個pointP的Z坐標。? 直接使用最大z坐標值 z(p)，作為這個bin的value。(5) Scan Context Matrix
A scan context I is finally represented as a Nr × Ns matrix as:
3.2 Similarity Score的計算
假設我們得到了一對Scan Context的矩陣，我們要計算他們倆(
)之間的相似度，文章中采用了columnwise (按列) 的距離計算。
:Query Point Cloud (簡言之，我們當前用來query的點云)
:Candidate Point Cloud （咱們的“數據庫”中儲存的用來匹配的candidate點云） 
:Column j of Query Point Cloud （列向量）
:Column j of Candidate Point Cloud （列向量）
–
大師兄：恩，這是個好問題。假設咱們回到同一個地方，那有可能是沿著相反的方向回來的，那咱們的Viewpoint就發生了變化，這個Scan Context矩陣就會發生偏移！這樣就會導致Column順序發生變化。大師兄：所幸的是，只要location是在同一個地方，不管你的方向朝著哪里，至少row order不會發生太大變化。咱們只需要關心column shift這個問題。在文章中，上面大師兄和小紅薯對話中的問題，如下圖所示：
。我們使用公式(7)進行最佳shift的選擇，找到最好的 n?后，用公式(6)進行distance計算。
3.3 Two-phase Search Algorithm
文中提到，有三種主流的Place Recognition的Search Algorithm:? Pairwise Similarity Scoring? Nearest Neighbor Search搜索? Sparse Optimization本文中采用了pairwise scoring和nearest search來實現有效的Hierarchical Search。(1) Ring Key
在3.2節中我們提到的公式(6)進行最短距離計算時，要先找到最佳旋轉n? ，計算量很大，所以在本文中提出了一種"Two-phase Search"，并提出了Ring key這個Descriptor（描述子）來進行匹配搜索：Ring key is a rotation-invariant descriptor, which is extracted from a scan context. Each row of a scan context, r, is encoded into a single real value via ring encoding function . The first element of the vector k is from the nearest circle from a sensor, and following elements are from the next rings in order as illustrated in Fig. 4
(2) KD-Tree
? 在得到ring key向量 k 之后，文章用了 k 構建KD Tree。
? 用ring key of the query到這個KD Tree中搜索K個最相似的scan indexex（K是個heuristic number）
? 得到最相似的K個scan后，用上文中公式(6)進行Similarity Score計算.
? 滿足條件的最近的candidatec?這個位置被選為revisited place，也就是loop的地方:
4
Scan Context算法延伸
4.1 ICP Initial Value中的應用
由上文3.2節的公式（7）需要找到一個n ? 旋轉，使得兩個點云之間的距離最小。這里其實也可以作為ICP的一個初始值，即predicted pose，來加快converge的過程。文章的Experiment部分對此進行了試驗，發現用Scan Context進行ICP初始化效果確實更好：
如果加入ScanContext進行全局重定位，效果如下圖:
4.3Future Works在文章最后，作者提到可以使用更好的bin encoding function (eg., a bin’s segmantic information)來提升性能，目前咱們只是用了一個很簡單的max Z(p)來找Z軸高度上的最高點。對于有夢想的讀者，也期待你的貢獻！
審核編輯 ：李倩
聲明：本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人，不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用，如有內容侵權或者其他違規問題，請聯系本站處理。
舉報投訴
-
算法
+關注
關注
23文章
4616瀏覽量
93027 -
SLAM
+關注
關注
23文章
425瀏覽量
31860
原文標題：ScanContext 論文詳解 - 用途：Lidar SLAM 回環檢測、空間描述符
文章出處：【微信號：3D視覺工坊，微信公眾號：3D視覺工坊】歡迎添加關注！文章轉載請注明出處。
發布評論請先 登錄
相關推薦
esp32-s2-soala-v1.2如何獲取攝像頭描述符？
descriptors from PC side,eg. run `lsusb -v` in linux,
請問我該如何獲得所需usb描述符？
發表于 06-27 06:48
二維PDMA可以使用描述符鏈嗎？
我正在嘗試使用二維描述符連鎖。 編寫了一些二維描述符鏈的代碼。 但我有一些疑問，比如
1.二維 PDMA 可以使用描述符鏈嗎？
2.如果 1 是，請附上一些代碼 我們是否可以使用 2 個結構或只使用 1 個結構即可。
發表于 05-31 08:16
FX3無法設置最小/最大比特率描述符值，為什么？
我正試圖通過 FX3 以 5200*3900 分辨率、15fps 的速度從我的 fpga 傳輸視頻數據流，但無法設置最小/最大比特率描述符值，因為描述符大小只有 32 位。
描述符的預期值應該是
發表于 05-21 06:36
如何將每個框架插入到SLAM框架中
LinK3D的核心思想和基于我們的LinK3D的兩個LiDAR掃描的匹配結果。綠色線是有效匹配。當前關鍵點（黑色，CK）的描述符用其相鄰關鍵點來表示。描述符的每個維度對應于扇區區域。
STM32 USB的字符串描述符不能顯示是哪里的問題？
最近用STM32做了一個USB 的HID類設備，設備描述符中有指定廠商字符串索引、產品字符串索引、序列號索引。在獲取字符串的代碼部分也發現確實執行了，但是插上電腦后卻沒有我想要的字符串，有哪位高手能指點一下。
發表于 04-30 08:13
STM32CUBEMX配置生成的一個HID設備，電腦提示設備描述符請求失敗，為什么？
如題，win10下。
用最新的 STM32CUBEMX 配置生成的 一個HID設備編譯正常。時鐘48MHz 也正常
電腦提示 設備描述符請求失敗
有沒有遇到類似問題的朋友？
發表于 04-10 06:05
STM32F103在官方USB的MSC程序基礎上修改為CDC+MSC的組合設備，出現設備描述符請求失敗的原因？
STM32F103在官方USB的MSC程序基礎上修改為CDC+MSC的組合設備，出現設備描述符請求失敗問題；抓包發現PC主機配置描述符數據和設置的數據不一致
發表于 04-07 06:34
CDC+MSC設備連接不了PC，顯示設備描述符請求失敗的原因？
USB組合設備：CDC+MSC，設備連接不了PC，顯示設備描述符請求失敗；用網上其它成功的例程測試，不是該情況就是只能使用U盤無法用虛擬串口，請問這是什么問題呢
發表于 04-03 06:44
USB OTG發送設備描述符失敗是什么原因呢？
能收到SETUP包，并解析數據跑到發送設備描述符，給FIFO寫數據也正確，但波形上就發了一個數據出去，這會是什么原因呢？
發表于 03-11 06:29
CYUSB3014設備描述符一路變成2路，windows不識別是怎么解決？
使用CyUSB3014+WM8960(音頻Codec)，來實現USB聲卡的功能，通過修改的USB設備描述符， 變成兩路音頻，發現windows不識別。之前的1路是沒問題。（見附件one channel and two channels）
發表于 02-28 07:38
為FX3應用程序實現可變USB配置描述符，開始編譯程序時報錯怎么解決？
我正在嘗試為我的 FX3 應用程序實現可變 USB 配置描述符，以允許在不同條件下包含不同的功能。 為此，我創建了一個 uint8_t 指針并使用 malloc 分配正確的內存量，然后
發表于 02-26 06:58
Traveo II上的P-DMA描述符總線錯誤是為什么？
DMA，我就會收到\"描述符總線錯誤\"中斷，由 CH_STATUS 寄存器識別，但我不確定為什么。 如果出現這個錯誤，也許你可以給我更多關于背景的信息？
我正在按照應用手冊中的說明
發表于 01-31 07:03
USB字符串描述符里面的序列號字符串到底是什么東西？
在設備描述符里面，有一個表示序列號字符串描述符的編號，請問這個序列號字符串的描述符是什么東西呢？
廠商字符串和設備字符串都能理解，而且在電腦的“設備與打印機”里面都找到了。但請問這個序列號字符串有什么用呢？在哪里能看到呢？
發表于 01-24 08:06
請問SPI DMA描述符列表如何單次觸發？
要求如下：
定義兩個個描述符類型的數組，如
SpiTxDesptr[3]= {{ SpiTxDesptr[1], X, X,X,X},{ SpiTxDesptr[2], X, X,X,X
發表于 01-12 08:07
工商網監
評論