文章目錄
- 1 背景
-
- 1.1 問題描述
- 1.2 相似性測度（Similarity Measure）
- 1.3 随機采樣一緻性（Random Sample Consensus，RANSAC）
- 1.4 Randomized Alignment
- 1.5 4PCS算法概述
- 2 4點一緻性
-
- 2.1 概述
- 2.2 4點集的仿射不變性
- 2.3 在3D空間中提取一緻的4點
- 3 4PCS算法
-
- 3.1 算法描述
- 3.2 實驗結果
- 參考
1 背景
1.1 問題描述
給定任意初始位置的兩個點集 P P P和 Q Q Q，找到一個最佳變換（通常是剛性變換），使得 P P P、 Q Q Q中距離小于 δ \delta δ的點數最多。
1.2 相似性測度（Similarity Measure）
在點雲配準問題中，我們通常會用相似性測度來衡量兩組點雲之間的比對程度，常見的相似性測度有均方誤差（Root Mean Square Error（RMSE）、最大公共點集（Largest Common Pointset，LCP） 等。
4PCS算法中所使用的相似性測度即為LCP測度。由LCP測度的原理我們可以看出，4PCS算法最終并不一定能夠得到一個非常精确的變換矩陣，是以它常被用作點雲配準問題中粗配準（Coarse Registration）步驟中的方法，配合ICP等精配準（Fine Registration）算法共同實作精确的點雲比對。
1.3 随機采樣一緻性（Random Sample Consensus，RANSAC）
RANSAC是一種被廣泛使用的通用性算法，用于對因噪聲和異常值破壞的資料進行模型的魯棒拟合。
基于RANSAC的點雲比對過程可以歸納為：
- 從點集 P P P和 Q Q Q中分别随機選取3個不同的點（友善起見，下文中我們把這3個不同的點稱作“基底/base”）對作為基礎的比對點對；
- 計算所選取3組對應點對的變換矩陣 T i T_i Ti；
- 計算點集 P P P和 Q Q Q的LCP測度 k i k_i ki，即點集 P P P中的點與點集 Q Q Q中的點距離在 δ \delta δ範圍内點的個數；
- 如果 k i k_i ki足夠大，則直接接受 T i T_i Ti作為最佳的變換矩陣，否則重複以上步驟；
- 這個過程将被重複 L L L次，并選擇 k i k_i ki最大時的變換矩陣 T i T_i Ti作為最終的結果。
1.4 Randomized Alignment
Randomized Alignment是Irani和Raghavan在1996年提出的RANSAC算法的一種變體，用于在相似性變換下解決2D對齊問題。其基本步驟為：
- 從點集 P P P中随機選取一組基底；
- 計算該基底與 Q Q Q中所有可能的基底得到的變換矩陣；
- 驗證得到的變換矩陣，這也是随機的：首先，僅随機抽取 P P P中固定數量的點進行驗證，隻有當該子集中大部分的點比對上（即在點集 Q Q Q中存在與其距離在 δ \delta δ内的點）時，才測試其餘點；
- 與RANSAC中一樣，為了達到一定的成功率，以上過程将被重複 L L L次。
與基本的RANSAC不同的是，4PCS算法從 P P P中随機選擇基底，然後使用某種配準算法在 Q Q Q中尋找對應的基底，下面将詳細介紹4PCS算法。
1.5 4PCS算法概述
我們知道，3個不共線的點對即可計算空間變換矩陣，而作者認為，尋找特殊的4點作為基底會使問題變得更加容易。4PCS算法就是使用一組來自 P P P的4個共面點作為基底 B B B，并從 Q Q Q中快速找到與 B B B大緻一緻的所有4點基底的子集，即允許剛性變換将兩個4點集對齊且距離在 δ \delta δ範圍内。
2 4點一緻性
2.1 概述
仿射變換遵循以下規則：給定3個共線的點 { a , b , c } \{a,b,c\} {a,b,c}，它們之間的比例關系 r = a − b a − c r=\frac{a-b}{a-c} r=a−ca−b是不變的。給定一組共面的4點集，在給定的點雲資料中查找與其在距離限制（ δ \delta δ）下具有仿射變換關系的4點集的集合。
2.2 4點集的仿射不變性
定義非共線的共面4點 X ≡ { a , b , c , d } X\equiv\{a,b,c,d\} X≡{a,b,c,d}， a b ab ab和 c d cd cd相交于點 e e e，則以下2個比率在仿射變換下是不變的：
r 1 = ∣ ∣ a − e ∣ ∣ ∣ ∣ a − b ∣ ∣ r 2 = ∣ ∣ c − e ∣ ∣ ∣ ∣ c − d ∣ ∣ r_1=\frac{||a-e||}{||a-b||} \\ r_2=\frac{||c-e||}{||c-d||} r1=∣∣a−b∣∣∣∣a−e∣∣r2=∣∣c−d∣∣∣∣c−e∣∣
給定含有 n n n個點的點集 Q Q Q，以及兩個由點集 P P P得到的仿射不變性比率 r 1 r_1 r1和 r 2 r_2 r2，對于 Q Q Q中的每對點 q 1 , q 2 ∈ Q q_1,q_2 \in Q q1,q2∈Q，可以計算兩個中間點：
e 1 = q 1 + r 1 ( q 2 − q 1 ) e 2 = q 1 + r 2 ( q 2 − q 1 ) e_1 = q_1 + r_1 (q_2-q_1) \\ e_2 = q_1 + r_2 (q_2-q_1) \\ e1=q1+r1(q2−q1)e2=q1+r2(q2−q1)
任意兩對中間點 e 1 e 2 e_1 e_2 e1e2在允許範圍内重合的點，都可以被看作與 P P P中基礎點對可能的仿射對應點。
2.3 在3D空間中提取一緻的4點
給定點集 P P P中不共面的4點作為基底 B B B，以及另外一個點集 Q ∈ R 3 Q \in \mathbb{R}^3 Q∈R3，我們的目标是從 Q Q Q中找到所有在允許範圍（ δ \delta δ）内與 B B B一緻的4點的集合。基本步驟為：
- 計算給定 B B B的兩個放射不變比率，即 r 1 r_1 r1和 r 2 r_2 r2；
- 利用2.2中描述的方法，從 Q Q Q中查找所有通過放射變換能與 B B B相比對的點集；
- 通過距離限制（ δ \delta δ），過濾掉不符合要求的比對（主要針對仿射變換中存在尺度縮放的一部分點集）；
- 利用最小二乘法，計算餘下每對點與 B B B的最佳變換。
事實上，對于大的點集，上述過程的計算量是相當大的。考慮到我們尋求的是剛性變換的解，對于一個基底 B ≡ { a , b , c , d } B\equiv\{a,b,c,d\} B≡{a,b,c,d}，首先計算兩點間的距離 d 1 = ∣ ∣ a − b ∣ ∣ d_1=||a−b|| d1=∣∣a−b∣∣， d 2 = ∣ ∣ c − d ∣ ∣ d_2=||c−d|| d2=∣∣c−d∣∣，然後僅考慮點集 Q Q Q中兩點距離與 d 1 d_1 d1或 d 2 d_2 d2相差在一定範圍内（ δ \delta δ）的點對。
3 4PCS算法
3.1 算法描述
給定兩個點集 P P P和 Q Q Q，不确定性度量（ δ > 0 \delta > 0 δ>0），以及預估的兩點集的重疊率 f f f，我們的目标是找到一個剛性變換，使 P P P中的點到 Q Q Q中的點距離小于 δ \delta δ的個數最多。
- 首先選擇由4個共面點組成的基底 B ⊆ P B\subseteq P B⊆P。實際上我們不一定能到找到完全共面的4個點，是以先随機選擇3個點，再查找第4個點組成近似共面的基底。理論上來說，點之間的距離越遠得到的比對結果越精确，然而若距離過遠，可能導緻所選擇的點不在兩個點集的重疊部分，也就無法計算得到理想的比對對。是以使用重疊率 f f f來估計這個最大距離（ f f f的預設值為1）；
- 得到基底 B B B後，我們可以定義仿射不變比。從 Q Q Q中查找所有與 B B B在距離限制（ δ \delta δ）下的對應點對集合 U ≡ { U 1 , U 2 , . . . , U s } U\equiv\{ U_1,U_2,...,U_s \} U≡{U1,U2,...,Us}。利用最小二乘法計算 B B B與 U i U_i Ui的最佳變換 T i T_i Ti；
- 驗證所得到的 T i T_i Ti的準确性，該過程以随機方式進行。計算 P P P經過 T i T_i Ti變換後與 Q Q Q的相似性測度（在 δ \delta δ限制下的最大公共點集）。為了提高效率，最近點的查找使用近似最近鄰算法（Approximate Nearest Neighbor，ANN）。具體來說，首先從 P P P中選擇固定數量的點，計算這些點經過 T i T_i Ti變換後與 Q Q Q中的點距離在 δ \delta δ内的點的個數，如果足夠多的話則對餘下的點也做這樣的計算。比對點數最多的變換将被作為本次比對中最佳的變換矩陣 T T T；
- 對于重複 L L L次不同的基底 B i B_i Bi，均按照上述步驟找到最佳變換 T i T_i Ti，并最終得到總體的最佳變換矩陣 T o p t T_{opt} Topt作為最終結果。
3.2 實驗結果
幾組作者論文中給出的實驗結果，所有結果都是經過ICP微調後的效果。
（1）不同重疊率
（2）不同噪聲程度
其餘的大家直接看論文吧。
參考
[1] https://sci-hub.tw/10.1145/1360612.1360684
[2] http://graphics.stanford.edu/~niloy/research/fpcs/fpcs_sig_08.html