Figure 1. 激光雷達(dá)沿著方位角(淺藍(lán))與放射方向（黃）的Bin分割 [1]

Figure 2. Scan Context示意圖 [1]

淺讀文章Scan Context，從英文字面理解就是“掃描上下文”。類比于我們閱讀的時(shí)候，需要理解上下文，才能明白其意，LidarSLAM在進(jìn)行回環(huán)檢測的時(shí)候，也需要將“上下文” （之前的數(shù)據(jù)）進(jìn)行比較，方才知道我們是不是又走到了之前的同一個(gè)地方（回環(huán)）。Scan Context這篇文章由韓國KAIST大學(xué)的Giseop Kim和Ayoung Kim所寫，它的主要特點(diǎn)是提出了Scan Context這個(gè)非直方圖的全局描述符，來幫助我們對“上下文”（當(dāng)前/之前的數(shù)據(jù)）進(jìn)行更快速、有效地搜索。典型的應(yīng)用就是在LiDAR SLAM中進(jìn)行回環(huán)檢測和Place Recognition。

提出的方法?The representation that preserves absolute location information of a point cloud in each bin （如圖2所示）?Efficient bin encoding function? Two-step search algorithm

算法流程

3.1 Scan Context的創(chuàng)建

(1) 與Shape Context的淵源

Scan Context這個(gè)算法其實(shí)一開始是由Shape Context [2] 所啟發(fā)的，而Shape Context是把點(diǎn)云的 local Keypoint 附近的點(diǎn)云形狀 encode 進(jìn)一個(gè)圖像中。Scan Context的不同在于，它不僅僅是count the number of points,而是采用了maximum height of pointsin each bin（簡單來說，就是取每一個(gè)bin中的所有point的z軸最高點(diǎn)的value作為這個(gè)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進(jìn)行分割：? Nr: number of rings （黃色圈圈）? Ns: number of sectors （淺藍(lán)色/綠色？的格子）? Lmax: 雷達(dá)每一個(gè)射線的最遠(yuǎn)距離? Radial Gap between rings =

? Sector弧度 =

? 文章中: Nr=20, Ns=60

(4) 給每個(gè)Bin進(jìn)行賦值：Bin Encoding

公式解讀： ?

就是指the set of points belonging to the bin where the ith ring and jth sector overlapped。? z(?)是指

中一個(gè)pointP的Z坐標(biāo)。? 直接使用最大z坐標(biāo)值 z(p)，作為這個(gè)bin的value。

(5) Scan Context Matrix

A scan context I is finally represented as a Nr × Ns matrix as:

3.2 Similarity Score的計(jì)算

假設(shè)我們得到了一對Scan Context的矩陣，我們要計(jì)算他們倆(

)之間的相似度，文章中采用了columnwise (按列) 的距離計(jì)算。

:Query Point Cloud (簡言之，我們當(dāng)前用來query的點(diǎn)云)

:Candidate Point Cloud （咱們的“數(shù)據(jù)庫”中儲存的用來匹配的candidate點(diǎn)云）

:Column j of Query Point Cloud （列向量）

:Column j of Candidate Point Cloud （列向量）

小紅薯：且慢，大師兄！小紅薯：古希臘哲學(xué)家赫拉克利特說，“人不能兩次踏進(jìn)同一條河流”。小紅薯：這樣來比較兩個(gè)點(diǎn)云，而沒考慮每次不可能在exactly同一個(gè)位置和角度觀察，是不是too young, too simple了呢！
–
大師兄：恩，這是個(gè)好問題。假設(shè)咱們回到同一個(gè)地方，那有可能是沿著相反的方向回來的，那咱們的Viewpoint就發(fā)生了變化，這個(gè)Scan Context矩陣就會發(fā)生偏移！這樣就會導(dǎo)致Column順序發(fā)生變化。大師兄：所幸的是，只要location是在同一個(gè)地方，不管你的方向朝著哪里，至少row order不會發(fā)生太大變化。咱們只需要關(guān)心column shift這個(gè)問題。在文章中，上面大師兄和小紅薯對話中的問題，如下圖所示：

Figure 3. Column Shift示意圖 [1]咱們可以看到在column方向發(fā)生了水平位移，但是豎著的row方向沒有變化。為了解決這個(gè)問題，文中采用了一個(gè)“地球人都能想到的方法”，那就是不斷嘗試各種角度的column shift。注意的是，旋轉(zhuǎn)candidate point cloud有個(gè)resolution，那就是之前提到的

。我們使用公式(7)進(jìn)行最佳shift的選擇，找到最好的 n?后，用公式(6)進(jìn)行distance計(jì)算。

注意：這里咱們通過找最好的 n?，還有一個(gè)意想不到的好處，那就是可以給ICP提供一個(gè)Good initial rotation value! (就是ICP代碼中的predicted pose)

3.3 Two-phase Search Algorithm

文中提到，有三種主流的Place Recognition的Search Algorithm:? Pairwise Similarity Scoring? Nearest Neighbor Search搜索? Sparse Optimization本文中采用了pairwise scoring和nearest search來實(shí)現(xiàn)有效的Hierarchical Search。

(1) Ring Key

在3.2節(jié)中我們提到的公式(6)進(jìn)行最短距離計(jì)算時(shí)，要先找到最佳旋轉(zhuǎn)n? ，計(jì)算量很大，所以在本文中提出了一種"Two-phase Search"，并提出了Ring key這個(gè)Descriptor（描述子）來進(jìn)行匹配搜索：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

Figure 4. Ring key示意圖 [1]由內(nèi)而外，一圈一圈的ring key通過對Scan Context Matrix的每一行row r 進(jìn)行ψ ( ? )的encoding就變成了一個(gè)N r 維度的Vector k：

The ring encoding functionψ psiψis a occupancy ratio usingL0 norm:

小紅薯：大師兄，這里的r0是什么意思呢？大師兄：這是L0 norm（范數(shù)）的意思，其實(shí)L0 norm并不是一個(gè)真正的norm，它就是the total number of non-zero elements in a vector 。比如,(2,0,1,0,9)這個(gè)vector的 L0 norm就是3，因?yàn)橛?個(gè)非零數(shù)。大師兄：這樣一來，咱們統(tǒng)計(jì)每一圈的row中有多少個(gè)非零數(shù)值，那這就和rotation沒啥關(guān)系啦（也就是原文中所說的rotation invariance）！這樣就能夠達(dá)到快速的search。

(2) KD-Tree

? 在得到ring key向量 k 之后，文章用了 k 構(gòu)建KD Tree。

? 用ring key of the query到這個(gè)KD Tree中搜索K個(gè)最相似的scan indexex（K是個(gè)heuristic number）

? 得到最相似的K個(gè)scan后，用上文中公式(6)進(jìn)行Similarity Score計(jì)算.

? 滿足條件的最近的candidatec?這個(gè)位置被選為revisited place，也就是loop的地方:

Scan Context算法延伸

4.1 ICP Initial Value中的應(yīng)用

由上文3.2節(jié)的公式（7）需要找到一個(gè)n ? 旋轉(zhuǎn)，使得兩個(gè)點(diǎn)云之間的距離最小。這里其實(shí)也可以作為ICP的一個(gè)初始值，即predicted pose，來加快converge的過程。文章的Experiment部分對此進(jìn)行了試驗(yàn)，發(fā)現(xiàn)用Scan Context進(jìn)行ICP初始化效果確實(shí)更好：

Figure 5. SC在ICP初始化中的應(yīng)用 [1]4.2 ScanContext在全局重定位中的應(yīng)用在深藍(lán)學(xué)院第四章作業(yè)中，我們應(yīng)用了ScanContext在全局重定位中的效果。如果初始化不在原點(diǎn)，且沒有全局重定位，效果如下:

如果加入ScanContext進(jìn)行全局重定位，效果如下圖:

4.3Future Works在文章最后，作者提到可以使用更好的bin encoding function (eg., a bin’s segmantic information)來提升性能，目前咱們只是用了一個(gè)很簡單的max Z(p)來找Z軸高度上的最高點(diǎn)。對于有夢想的讀者，也期待你的貢獻(xiàn)！審核編輯：李倩

聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請聯(lián)系本站處理。舉報(bào)投訴

算法

算法

+關(guān)注

關(guān)注
23

文章
4784

瀏覽量
98088
SLAM

SLAM

+關(guān)注

關(guān)注
24

文章
457

瀏覽量
33336

原文標(biāo)題：ScanContext 論文詳解 - 用途：Lidar SLAM 回環(huán)檢測、空間描述符

文章出處：【微信號：3D視覺工坊，微信公眾號：3D視覺工坊】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

91欧美超碰AV自拍|国产成年人性爱视频免费看|亚洲日韩欧美一厂二区入|人人看人人爽人人操aV|丝袜美腿视频一区二区在线看|人人操人人爽人人爱|婷婷五月天超碰|97色色欧美亚州A√|另类A√无码精品一级av|欧美特级日韩特级

搜索歷史

ScanContext論文詳解：Lidar SLAM 回環(huán)檢測、空間描述符

算法流程

3.1 Scan Context的創(chuàng)建

(1) 與Shape Context的淵源

(2) 為什么選擇Maximum height？

(3) Partition a 3D scan

(4) 給每個(gè)Bin進(jìn)行賦值：Bin Encoding

(5) Scan Context Matrix

3.2 Similarity Score的計(jì)算

3.3 Two-phase Search Algorithm

(1) Ring Key

(2) KD-Tree

? 在得到ring key向量 k 之后，文章用了 k 構(gòu)建KD Tree。

? 用ring key of the query到這個(gè)KD Tree中搜索K個(gè)最相似的scan indexex（K是個(gè)heuristic number）

? 得到最相似的K個(gè)scan后，用上文中公式(6)進(jìn)行Similarity Score計(jì)算.

? 滿足條件的最近的candidatec?這個(gè)位置被選為revisited place，也就是loop的地方:

Scan Context算法延伸

4.1 ICP Initial Value中的應(yīng)用

評論

搜索歷史

ScanContext論文詳解：Lidar SLAM 回環(huán)檢測、空間描述符

算法流程

3.1 Scan Context的創(chuàng)建

(1) 與Shape Context的淵源

(2) 為什么選擇Maximum height？

(3) Partition a 3D scan

(4) 給每個(gè)Bin進(jìn)行賦值：Bin Encoding

(5) Scan Context Matrix

3.2 Similarity Score的計(jì)算

3.3 Two-phase Search Algorithm

(1) Ring Key

(2) KD-Tree

? 在得到ring key向量 k 之后，文章用了 k 構(gòu)建KD Tree。

? 用ring key of the query到這個(gè)KD Tree中搜索K個(gè)最相似的scan indexex（K是個(gè)heuristic number）

? 得到最相似的K個(gè)scan后，用上文中公式(6)進(jìn)行Similarity Score計(jì)算.

? 滿足條件的最近的candidatec?這個(gè)位置被選為revisited place，也就是loop的地方:

Scan Context算法延伸

4.1 ICP Initial Value中的應(yīng)用

評論

ScanContext論文詳解：Lidar SLAM 回環(huán)檢測、空間描述符

(2) 為什么選擇Maximum height？

? 在得到ring key向量 k 之后，文章用了 k 構(gòu)建KD Tree。