SC^2-PCR: A Second Order Spatial Compatibility for Efficient and Robust Point Cloud Registration
(論文的觀讀)

**1.點雲(Point Cloud)**: 三維空間中的XYZ座標，每個點也可能包含額外的屬性資訊，如顏色、斜率、法向量、反射率等。

**2.點雲配準**: 就像是把這些「不同視角的照片」**疊合在一起**，讓它們對齊，最終**得到一個更完整、更精確的物體三維模型**。

**粗**: 會尋找不同點雲中相似的**關鍵特徵（例如角落、邊緣、形狀等）**，然後根據這些特徵的對應關係，計算出一個初步的旋轉和平移，讓點雲靠近彼此。

**精**: 大致疊在一起後，會再仔細地調整它們的位置，讓邊緣、細節等完全對齊，**iteratively**尋找兩個點雲之間**最接近的點對**，然後計算一個**更精確的變換**，使得這些對應點之間的距離越來越小，最終實現高精度的對齊。

| 粗配準 | 精配準 |
|:----------:|:----------:|
| 先大致對齊 | 再精細調整(反覆) |

**3. 二階空間相容性SC^2(核心方法)**: 它是用來衡量幾何結構(2以上之點雲)的相似性，的一種方法，用在**點雲配準**or **Object Detection**很好用，考慮到空間與空間之間的關係。

SC^2 的核心思想是：
**首要目的是為了找到那些在局部幾何結構上表現出細微關係、相似性的點(in-lier)，之後再用一系列的流程，去建構出對應的關係**

- 1. 如果**兩個潛在的對應點對都是正確**的（即屬於真正的內點），那麼它們應該與**許多相同的其他潛在對應點對也保持一致性**。

- [重要] 2. 它強調分析的是**局部鄰域的形狀**和**結構模式**，而不僅僅是單個點的屬性。
- [重要] 3. SC^2考慮點與點之間的**空間關係**(二階空間分布)，譬如: 球體、方體的法向量一致，但是本質上不同啊!

- 4. 基於 SC² 的相似性度量可以**幫助識別在幾何結構上更相似的局部區域**，從而建立更可靠的初始對應關係

-------
所以說，這篇論文主要是使用了**第二階空間相容性**，來**抓出點雲配對**

# 流程一
a. 全局譜分解 (Global Spectral Decomposition)，把它想像成一種很厲害的偵探工具，它可以從一大堆數據裡面，**找出一些整體看起來比較突出、比較有代表性的點**。就像在一群人中，先找出幾個看起來比較像是核心人物的感覺。這些點之所以被選出來，是因為它們**在整體數據的結構中扮演著比較重要的角色**。

b. 非最大抑制 (Non-Maximum Suppression)，這個步驟就像是從我們剛剛選出來的「種子選手」中，**去除掉一些太過相似、靠得重複**。非最大抑制就是要**確保我們選出來的「種子點」彼此之間有足夠的代表性**，不會過於冗餘 ! 它會比較這些「種子點」的重要性（例如，它們在全局譜分解中有多突出），然後保留最重要的那個，抑制掉周圍比較弱的。

---
a. 內點、外點是什麼?
內點: 真正**符合我們所要建立的模型**或關係的數據點
外點: 不符合模型或關係的**雜訊或錯誤數據點**

=>找到盡可能多的內點，並排除掉外點的干擾，這樣才能得到一個準確可靠的模型。

b. 種子點，又可以看做**內點適合者**，利用這些種子點，**更進一步地去尋找和確認更多的內點**，並形成所謂的「共識集」

**第一階段：從種子點擴展**
1. 先以seed為圓心去擴展抽樣，結合起來成為**候選共識集合**---猜它們都是某個特徵的

2. 評估共識集合，
**第二階段：形成多個共識集**，對於每一個候選共識集，會用它們來**擬合一個模型**（例如，如果我們在做影像匹配，這個模型可能是一個描述兩張圖片之間幾何關係的轉換矩陣）。然後，我們會**檢查原始數據中有多少其他的點**也符合這個模型。
# 流程二

1.**重複取樣**和評估: 從**不同的種子點出發**，並在它們周圍進行不同的**隨機取樣**，這樣就能產生多個不同的候選共識集。

2.**評估共識程度**: 有多少其他的點也像是內點一樣符合這個模型

3.選擇最佳共識集: **選擇那些共識程度最高的幾個集合作為最終的共識集**。這些共識集就包含了我們找到的比較可靠的內點。

# 流程三
要解釋: "對每個共識集，通過**局部譜匹配**（local spectral matching）生成**剛性轉換**的估計"。

Rigid Transformation: 能夠在3D空間中保持物體的形狀大小不變的運動，包含旋轉、平移；Point Cloud Registration之目的，就是要找出這種，將一個點雲移動到另一個點雲對齊的位置(可以用4x4 homogeneous 齊次變換矩陣表達)

共識集: Consensus Set
(被認為是**一致性較高**的一組對應點對)

**局部譜匹配(Local Spectral Matching)**:
1. 譜方法(Spectual): 這個是廣泛使用在圖形狀分析中，會用到譜信息，like Laplace矩陣的特徵值/向量

2. 在這個Point Cloud配對中，LSM不是對一整個點雲做譜分析，**而是對每個共識集中的局部圖，以估計Rigid 剛性轉換**。

3.描述流程:
a.在共識集中選取局部鄰域
b.建構局部圖
c.計算局部譜信息(圖形的特徵分析)
d.圖匹配(比較特徵大小之類的)
e.估計局部的rigid transformation

在點雲配準的**粗配準階段**，通常會使用一些**隨機採樣的方法**（例如RANSAC）來尋找不同點雲之間潛在的對應關係。由於初始的點雲**可能存在噪聲、異常值或不完全重疊**，如果假設這些對應是正確的，那麼計算出的變換應該能夠較好地對齊這些點對

# 流程四
後續的步驟通常會對這些**初步的剛性轉換進行評估和優化**，以得到最終的、最佳的Rigid Transformation配準結果。

## 以上是大致上的Abstract + Conclusion整理
## ---------------------------------------------------------

## 接下來是introduction

前言: PCR點雲配準是大量用在機器人、AR、SLAM(及時座標化與映射)
典型方法: 1.先建立特徵對應 2. 估算3D旋轉與translation，以求得最好的對其方式

(這是理想上，但困難點是: 重疊部分、模糊的特徵，導致參考過多outliers，變成是不好的對應)

剛開始有幾種方法:

* -RANSAC: 精度高，一直跌代抽樣去套在模型上看看合不合適，但是會花很大時間去做收斂，當outlier變多，無法保證他的表現->適用無outlier
(Random Sample Consensus)
* -Spatial Compatibility: 是用來**衡量兩個對應關係**的度量方法，**若對應關係是內點**，則點雲間的空間**距離差異會比較小**，**他只考慮了兩兩點對之對應關係**

但由於外點**可能會與某些內點有較高的相容性分數**，會有較高的模糊性，難以有效區分內外點，(恩恩，所以SC^2有考慮相容性問題了!)

(b 第一階) c6, c7兩個outliers，但是在SC中卻**接近內點的相容值**，增加模糊程度
(d 第二階) outliers是小的，可以被區分出來的
- 
- 這一邊是先將數值給二元化，再來針對: 相容性的對應點，會再用其他的相容對應點(等於是拿第三者來指認這對點)

相容: 對應的在空間結構上是否基本一致，最主要的衡量標準是它們內部點之間的距離在兩個點雲中是否近似相等


綠色: inliers ... 紅色: outliers

---------------------------------
# Related Work
點雲對應點選擇的深度學習方法
近年來，越來越多使用DL技術，來找出對應點的分類
- 3DRegNet 將 CN-Net 概念拓展到3D場景，設計回歸模塊估計剛性變換。

- DGR 利用全卷積網路捕捉全局上下文信息，提高配準準確度。

- PointDSC 通過基於空間一致性的非局部模塊及神經譜匹配，加速模型生成與選擇。

- DetarNet 通過孿生網絡解耦平移與旋轉的估計過程。

- DHVR 利用深度霍夫投票空間來辨識共識集合，改進變換預測。

---------------------------------

# Problem Formulation

Source: X
Target: Y - **匹配對建立**
首先從Source的每個點在**特徵空間**中找到其在**目標點雲**的**最近鄰**，進而形成 N 組候選對應點 (putative correspondences)。

我們會為來源點雲和目標點雲中的每一個點都提取一個特徵向量 (feature vector)

Feature Space: 我們會為每個點**提取**一個描述其**局部幾何特徵的特徵向量**

**目標**
從這些候選對應點中推估**剛性變換**（剛性轉換矩陣）
RX + t

- 這個是ambiguity的機率
- M 是用來**衡量匹配對相似度**的特定度量方法
- M(in, out) :一正一錯的相似程度
- M(in, in) :兩個皆為正的相似程度
- 所以，這張圖，機率值須越小越好->採樣不易失敗

# Second Order Spatial Compatibility

先以Spatial Compatibility出發
- d(x1,x2) :距離關係
- ϕ :單調遞減核函數
- 所以是匹配對i, j兩點；求出距離，再通過這個函數
- **d(in, in) = 0, length consistency**
- **模糊性問題必然存在於某些域值之下**

- 會有這個uniform PDF之假設，原因是實際上d(in,in)不會是0，而是**有一個dthr的門檻**，故假設d(in,in)是均等分配於dthr，允許一定的誤差存在。


- din, out & dout, out
不會有像是din, in的問題存在與限制
(因為外點的**隨機分配性**)
所以兩個無關的點，我們會視為**相等分配**(identically distributed)

**dr表示din, out; dout, out的range**

- 因為dr>>dthr，所以上面圖片，可以解釋成: 逼近F(l)為一常數落在(0, dthr), ie., F(l) = f0

所以我們轉換SC的模糊機率

但是因為outlier的數量也會很龐大，這樣的機率會有**模糊性問題**，所以現在換成一個SC^2的方法
1. 建立**硬相容性矩陣**
2. 當兩個匹配對 i,j 是**相容的**（Cij=1）時，計算他們共有相容對的數量
. 

現在就來計算SC^2的模糊機率(共有N個對應)
1. **大幅降低模糊事件發生機率**
2. 使得內點之間的相似度值更高且更明顯地區分於外點相似度

這個S是Skellam Distribution，當α(inlier rate)增加時候，**模糊機率p**會趨近0
**兩個獨立的 Poisson 分布隨機變數之差**

圖片說明了SC^2這個方法會大幅降低模糊機率的值，即使inlier比率近於0也是一樣，且越大的時候，越明顯看到相差了一半的機率

# Reliable Seed Selection
並不需要找到大量的inliers，而是我們可以只要找seeds，使用的方法是spetural matching technique
1. 建立相似矩陣 + 標準化成0~1 ->取得特徵向量的max
2. **最大的特徵值**會反映了匹配對整體的相容性結構。
3. seeds的數量由對應數量，他們成比例
4. 為了確保seeds的均勻分布，**在這些候選的seeds當中要挑選最大的信賴值**

我們可以在這些內點對應集中找出共識集 但是這樣比較費力

所以要有一個方法去找到一些可靠的內點---種子點去增快它的配點速度

這邊會使用一篇論文講的是"高效率譜配對方法"去找出種子點

然後先用一個相似矩陣 將他標準化之後 想要有效地找出種子點是誰

會取得這些對應的關聯性 是來自最大的值所對應的特徵向量??

然後會被賦予一個信賴

為了使得種子點是均勻分布，

我們取這些的局部最大信賴值當作首選

# Two stage consensus set sampling
Goal: 用於從**每個種子點擴展出一個共識集**，目的是為了後續的剛性變換估計。

Step1 : 如何從已選定的種子點出發，建立起用於後續配準計算的「共識集 (consensus set)」
- 1.是藉由在 SC² 度量空間 中尋找每個種子的前 k1 個最近鄰居
- 2.因為都是內點了 所以他們的模糊機率會很小
- 3.基於每個已選定的種子點，在其全局 SC² 鄰域內尋找相關的 correspondences。種子點的選擇本身可能也利用了全局信息（例如通過譜方法），而這裡的擴展是圍繞每個種子點進行的。
- 4.所以他們鄰居的選擇會更為的平均

- 也就是說為了拓展成共識集，我們會先藉由找出他的前k1個鄰居，作為他的k1個對應，因為裡面皆為內點居多，所以模糊程度會非常的小，然後這又是建立在SC^2的全局測度之下，所以會選取的非常平均

Step2 : 想要更進一步去把潛在的外點給刪除掉

- 1.再從一個種子中k1個對應當中去取**前k2個對應**(這個是建立在重新建構**局部的SC^2矩陣**)

- 2.越高的內點比例會使得模糊比率降低

- 3.即使裡面仍然會有外點，而外點仍然會使得我們的一致性成立，因為他在這個對應裡面

但是我們會用後段的假說去設法刪去掉外點

# 3.5. Local Spectral Matching
1. 每個由種子點擴展出的共識集合，利用帶權重的奇異值分解（weighted SVD）來估計剛體變換
2. 雖然前面的方法可以大幅降低outlier，但是內點仍然會有瑕疵，所以採用權重的方法來分散這不足處
3. 
為了使SC^2更為有效地表達，用了以上的替換

- 1. 我們是利用每個種子對應的共識集來估計屬於他的剛性變換

- 2. 因為可能含有外點 所以要用權重的方式

- 3. 傳統的譜配對方法是一個個乘上權重 但這受到模糊程度影響

- 4. 所以我們改良了SC^2的公式變換

- 5. 再用局部譜分解方法得到這些的權重 以估計R .t剛性轉換

# 3DMatch 實驗測試結果圖(fpfh/fcgf)
json檔案要去更改path & descriptor 才能看到兩者之測試結果

# 3DLoMatch 實驗測試結果圖(fpfh/fcgf)

# KITTI 實驗測試結果圖(fpfh/fcgf)