Scan Context——論文學習
- 0. 前言
- 1. 摘要及引言
- 2. Scan Context建構
- 3. 雙層比對算法與Scan Context相似度打分
-
- 3.1 Ring Key
- 3.2 評分
- 4. 整體流程
0. 前言
在前一段時間深藍學院課程中，用到了Scan Context。因為時間原因，一直沒有深入了解。這裡重新對論文進行學習。
論文中描述了大量的實驗結果，這也是作者提到的關鍵貢獻之一。本篇文章主要對論文的理論部分進行學習。
在這篇文章中，有一些概念類詞彙在學習論文過程中造成了一些困擾，這裡也提前進行記錄。
perception aliasing（感覺混疊）：感覺混疊是一種在不同的地方中産生相似的視覺區域現象1，即不同位置的相似環境産生了定位錯誤。就個人了解，本文中感覺混疊主要指同一位置的因為不同光照、物體不同等産生了定位錯誤。
基于雷達的位置識别需要解決的兩個問題：需要克服
egocentric 2.5D information（自我中心的2.5D 資訊）：這個還沒有搞清楚，大概是将3維雷達資訊通過矩陣（也就是提出的Scan Context描述子）表示出來，矩陣内容含有一定的3維資訊（高度），而該描述子是以機器人自身為中心的。
L0範數： 指向量中非0的元素的個數
root shift是啥，為啥可以對平移魯棒
1. 摘要及引言
1.1 摘要
重點提煉了Scan Context 的特點，即基于3D雷射雷達的非直方圖環境描述方法。該方法的比對度計算采用雙層搜尋算法來提高效率，且與現有算法相比有了巨大提升。
1.2 引言
基于雷達的位置識别算法有兩個需要解決的問題，旋轉不變性以及噪聲處理。這也是本文所涉及到的。
本文貢獻主要在四個方面。
- 高效的桶編碼函數（Efficient bin encoding function），具有對點雲密度和法線的不變性。
- 儲存點雲内部結構（Preservation of internal structure of a point cloud），提高了scan context對不同視角的正确識别能力。
- 高效的雙層比對算法（Effective two-phase matching algorithm），先利用Ring key進行快速的上層搜尋，得到少量候選幀。随後對候選幀與目前幀進行距離計算。
- 與現有主流算法的徹底比較，大量的實驗。
2. Scan Context建構
Scan Context描述子是将單幀雷射雷達點雲資料轉換為
數值為目前桶内雷射點最大高度的二維矩陣
。
首先，對Scan Context 桶（區域劃分）進行介紹。如圖1所示，将單幀雷射雷達按兩個方向：徑向與環向進行劃分。其區域數量分别是Nr（徑向）、Ns（環向）。是以，其區域分辨率為 L max N r \frac{L_{\max }}{N_{r}} NrLmax（徑向）， 2 π N s \frac{2 \pi}{N_{s}} Ns2π（環向）。
是以，目前幀點雲為劃分的區域的并集。
P = ⋃ i ∈ [ N r ] , j ∈ [ N s ] P i j \mathcal{P}=\bigcup_{i \in\left[N_{r}\right], j \in\left[N_{s}\right]} \mathcal{P}_{i j} P=i∈[Nr],j∈[Ns]⋃Pij
是以，目前幀點雲的Scan Context描述子可以表達為Nr * Ns的矩陣，其元素值為區域點雲中高度的最大值。
即，
I = ( a i j ) ∈ R N r × N s , a i j = ϕ ( P i j ) I=\left(a_{i j}\right) \in \mathbb{R}^{N_{r} \times N_{s}}, a_{i j}=\phi\left(\mathcal{P}_{i j}\right) I=(aij)∈RNr×Ns,aij=ϕ(Pij)
其中， ϕ ( P i j ) = max p ∈ P i j z ( p ) \phi\left(\mathcal{P}_{i j}\right)=\max _{\mathbf{p} \in \mathcal{P}_{i j}} z(\mathbf{p}) ϕ(Pij)=p∈Pijmaxz(p)
圖1 Scan context 區域劃分
疑問：因為再次回到同一位置時車道不一樣而導緻的scan context 行順序不同。為了解決這個問題，将原始點雲又放入 N t r a n s N_{trans} Ntrans鄰域中，并将其與Scan context一起存下來。
–
3. 雙層比對算法與Scan Context相似度打分
論文中先講了對scan context的相似度評分，而後因其計算量過大，無法對所有矩陣進行評分，故引入了中間描述子Ring Key。首先利用Ring Key進行候選幀的挑選，而後對scan context進行評分。
3.1 Ring Key
将scan context對行進行計算，從矩陣I（scan context）得到向量k，k中每一行表示該圓環區域中的占據率（非空區域與Ns的比值）。另外，通過k建構KD樹，實作快速檢索。
即，
k = ( ψ ( r 1 ) , … , ψ ( r N r ) ) ψ ( r i ) = ∥ r i ∥ 0 N s \mathbf{k}=\left(\psi\left(r_{1}\right), \ldots, \psi\left(r_{N_{r}}\right)\right) \\ \psi\left(r_{i}\right)=\frac{\left\|r_{i}\right\|_{0}}{N_{s}} k=(ψ(r1),…,ψ(rNr))ψ(ri)=Ns∥ri∥0
圖2 Ring key示意圖
這樣，就可以根據門檻值條件擷取候選幀。
c ∗ = argmin c k ∈ C D ( I q , I c k ) , s.t D < c^{*}=\underset{c_{k} \in \mathcal{C}}{\operatorname{argmin}} D\left(I^{q}, I^{c_{k}}\right), \text { s.t } D< c∗=ck∈CargminD(Iq,Ick), s.t D<
3.2 評分
在擷取到候選幀的基礎上，分别進行評分，以擷取最終比對結果。對于目前幀Iq和候選幀Ic，其距離可以表示為。
d ( I q , I c ) = 1 N s ∑ j = 1 N s ( 1 − c j q ⋅ c j c ∥ c j q ∥ ∥ c j c ∥ ) d\left(I^{q}, I^{c}\right)=\frac{1}{N_{s}} \sum_{j=1}^{N_{s}}\left(1-\frac{c_{j}^{q} \cdot c_{j}^{c}}{\left\|c_{j}^{q}\right\|\left\|c_{j}^{c}\right\|}\right) d(Iq,Ic)=Ns1j=1∑Ns(1−∥∥cjq∥∥∥∥cjc∥∥cjq⋅cjc)
其中， c j q c_{j}^{q} cjq和 c j c c_{j}^{c} cjc是列向量。
然而，這裡仍然有個問題，就是視角變換（偏航角的改變）會引起scan context中列向量的順序，而行向量卻不變（隻有偏航角改變，隻會在環向發生變化，相對距離不變）。
是以，采用周遊的形式。 這一步也是得益于利用Ring Key找出了較少的候選幀，減少了工作量。而這裡的周遊分辨率，就是每個區域劃分的分辨率，即 2 π N s \frac{2 \pi}{N_{s}} Ns2π。
D ( I q , I c ) = min n ∈ [ N s ] d ( I q , I n c ) n ∗ = argmin n ∈ [ N s ] d ( I q , I n c ) . \begin{aligned} D\left(I^{q}, I^{c}\right) &=\min _{n \in\left[N_{s}\right]} d\left(I^{q}, I_{n}^{c}\right) \\ n^{*} &=\underset{n \in\left[N_{s}\right]}{\operatorname{argmin}} d\left(I^{q}, I_{n}^{c}\right) . \end{aligned} D(Iq,Ic)n∗=n∈[Ns]mind(Iq,Inc)=n∈[Ns]argmind(Iq,Inc).
值得注意的是，該方法還能得到可以用于ICP初始化的偏航角資訊，使ICP的速度和效果均有所提升。
4. 整體流程
對于單幀3D雷射雷達，首先對其提取Scan Context描述子。在此基礎上，利用Ring Key 描述子，通過KD樹這一快速檢索方式，找到最相似的候選幀，而後才将少數候選幀與目前幀進行相似度評分，檢測是否回環。
- 出自論文：Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models ↩︎