提出的方法•The representation that preserves absolute location information of a point cloud in each bin （如圖2所示）• Efficient bin encoding function• Two-step search algorithm
3
算法流程
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 points in 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(⋅) 是指 中一個point P 的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 （列向量）
在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
Figure 4. Ring key示意圖 [1]由內而外，一圈一圈的ring key通過對Scan Context Matrix的每一行row r 進行ψ ( ⋅ )的encoding就變成了一個N r 維度的Vector k：
The ring encoding function ψ \psi ψ is a occupancy ratio using L0 norm:
小紅薯： 大師兄，這裡的r0是什麼意思呢？大師兄： 這是L0 norm（範數）的意思，其實L0 norm並不是一個真正的norm，它就是the total number of non-zero elements in a vector 。 比如,(2,0,1,0,9)這個vector的 L0 norm就是3，因為有3個非零數。大師兄： 這樣一來，咱們統計每一圈的row中有多少個非零數值，那這就和rotation沒啥關係啦（也就是原文中所說的rotation invariance）！ 這樣就能夠達到快速的search。
(2) KD-Tree
• 在得到ring key向量 k 之後，文章用了 k 構建KD Tree。
• 用ring key of the query到這個KD Tree中搜索K個最相似的scan indexex（K是個heuristic number）
Figure 5. SC在ICP初始化中的應用 [1]4.2 ScanContext在全局重定位中的應用在深藍學院第四章作業中，我們應用了ScanContext在全局重定位中的效果。如果初始化不在原點，且沒有全局重定位，效果如下:如果加入ScanContext進行全局重定位，效果如下圖:4.3 Future Works 在文章最後，作者提到可以使用更好的bin encoding function (eg., a bin』s segmantic information)來提升性能，目前咱們只是用了一個很簡單的max Z(p)來找Z軸高度上的最高點。對於有夢想的讀者，也期待你的貢獻！參考文獻[1] G. Kim and A. Kim, 「Scan Context: Egocentric Spatial Descriptor for Place Recognition Within 3D Point Cloud Map,」 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Madrid, 2018, pp. 4802-4809, doi: 10.1109/IROS.2018.8593953.[2] S. Belongie, J. Malik, and J. Puzicha, 「Shape matching and object recognition using shape contexts,」 IEEE Trans. Pattern Analysis and Machine Intell., vol. 24, no. 4, pp. 509–522, 2002.
就是指the set of points belonging to the bin where the ith ring and jth sector overlapped。
中一個point P 的Z坐標。
)之間的相似度，文章中採用了columnwise (按列) 的距離計算。
:Query Point Cloud (簡言之，我們當前用來query的點雲)
:Candidate Point Cloud （咱們的「數據庫」中儲存的用來匹配的candidate點雲） 
:Column j of Query Point Cloud （列向量）
:Column j of Candidate Point Cloud （列向量）
。
