點雲配準論文閱讀筆記--(4PCS)4-Points Congruent Sets for Robust Pairwise Surface Registration

目錄

• 點雲配準系列
• 寫在前面
• Abstract摘要
• 1 Introduction引言
• 2 Background研究背景
• • RANSAC
  • Randomized Alignment
• 3 Approximate Congruent 4-Points近似共面四點
• • 3.1overview 概述
  • 3.2 Affine Invariants of 4-Points Sets四點集的仿射不變
  • 3.3 Extracting Congruent 4-points in 3D三維中提取全等4點集
• 4 The 4PCS Algorithm 4PCS算法
• • further enhancement進一步提高
• 5 Results結果
• • 局限性
• 總結
• • 算法：
  • 問題/疑惑：
• 參考及感謝
• 完

點雲配準系列

點雲配準1：配準基礎及icp算法

點雲配準2：icp算法在PCL1.10.0上的實作+源碼解析

點雲配準3：3d-ndt算法在pcl上的實作以及參數設定

點雲配準4：cloudcompare的使用以及點雲配準功能

點雲配準5：4pcs算法在pcl上的實作

點雲配準6：tricp算法在pcl上的實作

點雲配準論文閱讀筆記–Efficient Variants of the ICP Algorithm

點雲配準論文閱讀筆記–Comparing ICP variants on real-world data sets

點雲配準論文閱讀筆記–(4PCS)4-Points Congruent Sets for Robust Pairwise Surface Registration

點雲配準論文閱讀筆記–3d-dnt博士論文

寫在前面

論文4-Points Congruent Sets for Robust Pairwise Surface Registration閱讀筆記

下載下傳位址：share_noel/papers/reg-4-Points Congruent Sets for Robust Pairwise Surface Registration.pdf

https://pan.baidu.com/s/1IsN2Ze2FNts-3v4ZH1m-9A 提取碼: mack

該論文是比較出名的4pcs點雲配準算法原文，本篇部落格為論文閱讀筆記，對關鍵内容進行提取、翻譯、解釋，并包含個人了解，如有錯漏敬請指正。

Abstract摘要

本文提出4PCS(4-Points Congruent Sets)算法進行點雲配準。允許原始噪聲，離群值，無需濾波去噪，無需初始配準。我們的方法基于一種新的技術，即從一個三維點集中提取所有共面4點集，這些點集在剛性變換下與給定的共面4點集近似全等。這個過程時間大緻消耗 O ( n 2 + k ) O(n^2+k) O(n2+k)，其中n是候選點的數目，k是得到的4點集的數目。實際上，當噪聲低和重疊度足夠高時，使用局部描述子可以将時間複雜度減至 O ( n + k ) O(n+k) O(n+k).

知道icp算法的同學都知道，icp算法精度高，但是對資料的要求也相對較高，噪聲離群值都會對算法産生影響，并且需要點雲進行粗配準（或初始配準）防止算法陷入局部最優。

1 Introduction引言

剛體變換可以由3對已知的點對恢複。我們把這樣的點內建為基集（base）。剛體變換下不變的局部描述子經常用來提取 可以産生良好候選點對的 點集。

給定在任意初始姿态下的兩個個點集P和Q，比對的基集（一個來自P，另一個來自Q）生成一組可以将P和Q進行配準的候選變換。

目标質心和PCA(object centroids and Principal Component Analysis (PCA))常用來粗配準。在部分重疊的情況下，PCA等粗配準方法不太好（原文是breakdown）。

局部特征描述是很好的工具。雖然在噪聲下也可能魯棒地計算出這些局部特征描述子,但是在噪聲和離群點很嚴重的時候，定義可信的描述子仍然是挑戰。

在這種情況下，一個有效的替代方法是依賴大數原理（principle of large numbers），而不是使用局部描述子。該方法需要求解最大公共點集（LCP）問題：給定兩個點集P和Q，在 δ \delta δ 一緻( δ \delta δ-congruence，此處不知怎樣翻譯最好)下的LCP來求解P的一個子集P’（P’有最大的基數），使得在适當的距離測度下T（P’）和Q之間的距離小于 δ \delta δ，其中T是一個剛性變換。

當P和Q分别是m和n點時，最原始的方法的時間複雜度是 O ( m 3 n 3 ) O(m^3n^3) O(m3n3)（因為3個點對就能求解剛體變化，從P中選3個點需要 m 3 m^3 m3，從Q中選3個點需要 n 3 n^3 n3）。該算法的随機版本從P開始嘗試适當數量的随機基，進而将複雜度降低到 O ( m n 3 l o g n ) O(mn^3logn) O(mn3logn)[Irani和Raghavan 1996]。通過随機驗證，這種複雜度可以進一步降低到 O ( n 3 l o g n ) O(n^3logn) O(n3logn)。然而，對于較大的點集，這樣仍然是很耗時的。

本文算法的關鍵是選取一個寬基集（wide-base），如圖2。（就是選取的點的距離相對大些，算法才更穩定，明顯上面的配準效果比下面的好，因為上面的點隔得遠，但是最遠距離要受重疊度的限制）

寬基集（wide-base）和LCP讓我們的配準算法能适應噪聲和離群點，是以算法能對原始資料進行直接配準。即使在低重疊度和沒有初始配準的情況下，算法也能成功配準點雲，如圖1。

2 Background研究背景

問題定義：

給定任意初始位置的兩個點集P和Q，從一個指定的變換族中找到最佳變換，通常是剛體變換，它能最好地配準P和Q。對最佳變換，我們指的是這個變換，能将P配準至Q，P’是P的子集，此時P’中的點數量最大且P’中的點（可認為是重疊部分的點） 與 Q的距離 均小于 δ \delta δ。在剛體變換的情況下，三個點對足以唯一地确定一個空間變換。

RANSAC

RANSAC大量用于拟合被噪聲和離群值污染的模型。

基于RANSAC的配準如下：

随機從P、Q中各選擇3個點（P中3個，Q中3個），組成3個點對，計算變換矩陣 T i T_i Ti​;

将P使用 T i T_i Ti​變換後，計算P中與Q的距離小于 δ \delta δ的點數，記為 k i k_i ki​；

如果 k i k_i ki​足夠大，将 T i T_i Ti​視為一個好的結果，否則重新選擇3個點對進行計算；

上述過程将會執行L次，最終選擇 k i k_i ki​最高的結果作為最佳結果。從P和Q中随機選取基點的過程重複L次，選出最佳解，即 k i k_i ki​值最高的解。

RANSAC原文：

[share_noel/papers/RANSAC原文-Random sample consensus–a paradigm for model fitting with applications to image analysis and automated cartography.pdf]https://pan.baidu.com/s/1IsN2Ze2FNts-3v4ZH1m-9A 提取碼: mack

關于RANSAC算法的了解和其他應用可參考以下部落格：

RANSAC算法詳解

RANSAC

RANSAC算法了解

深度解析RANSAC算法

Randomized Alignment

Randomized Alignment是RANSAC的一種變體算法。

設 p g p_g pg​是從P中随機選擇的一個點也存在于Q中的機率（即，在重疊區域中），基(base)的大小為N， p f p_f pf​是在L嘗試找到存在的良好拟合後算法退出的機率。由于我們随機從P中選擇點，我們得到： p f = （ 1 − p g N ） L p_f=（1-p^N_g）^L pf​=（1−pgN​）L。

是以， p s p_s ps​為大于成功的機率，則有疊代次數L:

L > l o g ( 1 − p s ) / l o g ( 1 − p g N ) (1) L>log(1-p_s)/log(1-p^N_g)\tag{1} L>log(1−ps​)/log(1−pgN​)(1)

對于剛體變換，N=3已經足夠。

對于這個公式，下面給出我的了解：

失敗的機率 p f p_f pf​等于1減去成功的機率 p s p_s ps​： p f = 1 − p s p_f=1-p_s pf​=1−ps​

則：

p f = （ 1 − p g N ） L = 1 − p s p_f=（1-p^N_g）^L=1-p_s pf​=（1−pgN​）L=1−ps​

取對數，并把L放前面：

l o g ( 1 − p g N ) L = l o g ( 1 − p s ) log(1-p^N_g)^L=log(1-p_s) log(1−pgN​)L=log(1−ps​)

L = l o g ( 1 − p s ) / l o g ( 1 − p g N ) L=log(1-ps)/log(1-p^N_g ) L=log(1−ps)/log(1−pgN​)

這是成功實作的情況下的L，那麼實際使用時，L肯定隻能大于上述結果，是以：

L > l o g ( 1 − p s ) / l o g ( 1 − p g N ) L>log(1-ps)/log(1-p^N_g ) L>log(1−ps)/log(1−pgN​)

文章的算法基于 randomized alignment。但是，我們并沒有測試Q中的所有可能基集合，我們使用共面點集來選取一個小的基集合來和P的基集比對。

3 Approximate Congruent 4-Points近似共面四點

與上面的隻選取3點不同，我們的方法是從P中選擇一個共面4點集，記為B，然後在Q中快速查找與B近似全等（approximately congruent to B）的所有子集。後面将闡述如何高效地從P中提取一個B子集。兩點集近似全等（approximate congruence），意味着兩個四點集可以使用剛體變換進行配準。下文将闡述如何在 O ( n 2 + k ) O(n^2+k) O(n2+k)時間内在Q中提取所有這樣的全等子集。

3.1overview 概述

仿射變換具有如下屬性：

給定三個共線點 { a , b , c } \{a,b,c\} {a,b,c}，比值 ∥ a − b ∥ / ∥ a − c ∥ \parallel{a-b}\parallel/\parallel{a-c}\parallel ∥a−b∥/∥a−c∥不變。

對于給定的一個共面的4點基集，我們在另一個給定點雲中尋找（近似）與其仿射等價的4點集。

3.2 Affine Invariants of 4-Points Sets四點集的仿射不變

如圖4，共面點集 X ≡ { a , b , c , d } X\equiv\{a,b,c,d\} X≡{a,b,c,d}，并不全部共線， e e e是 a b ab ab和 c d cd cd的交點，定義兩個獨立的比值 r 1 , r 2 r_1, r_2 r1​,r2​：

r 1 = ∥ a − e ∥ / ∥ a − b ∥ r_1=\parallel{a-e}\parallel/\parallel{a-b}\parallel r1​=∥a−e∥/∥a−b∥

r 2 = ∥ c − e ∥ / ∥ c − d ∥ (2) r_2=\parallel{c-e}\parallel/\parallel{c-d}\parallel\tag{2} r2​=∥c−e∥/∥c−d∥(2)

r 1 , r 2 r_1, r_2 r1​,r2​在仿射變換下具有不變性，并且在唯一地定義了仿射變換的4個點。現在給定一個 n n n個點的集合Q，以及兩個仿射不變比 r 1 , r 2 r_1, r_2 r1​,r2​，我們可以在 O ( n 2 + k ) O(n^2+k) O(n2+k)時間内有效地提取由這兩個不變量定義的所有4點集，其中 k k k是所提取的4點集的個數。對于每個點對 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_1=q_1+r_1(q_2-q_1) e1​=q1​+r1​(q2​−q1​)

e 2 = q 1 + r 2 ( q 2 − q 1 ) (3) e_2=q_1+r_2(q_2-q_1)\tag{3} e2​=q1​+r2​(q2​−q1​)(3)

任何兩對中間點（一個來自 r 1 r_1 r1​，另一個來自 r 2 r_2 r2​）重合，可能對應于一個仿射變換4點集（見圖5）。由于點 e 1 − s e_1-s e1​−s和 e 2 − s e_2-s e2​−s都在同一個坐标系中，是以可以使用鄰域搜尋結構快速搜尋重合點。

在實際中，由于噪聲的影響，中間點不是完全重合的，最終成為附近的點。為了允許對鄰近點進行快速範圍查詢，我們在 R 3 \mathbb{R}^3 R3中使用标準資料結構。

我們使用近似範圍樹，它可以在 O （ n l o g n ） O（n logn） O（nlogn）内由大小為 n n n的點集建構，并支援在 O （ l o g n + k ） O（logn+k） O（logn+k）時間内查詢任何矩形内的所有點， k k k是要報告的點數。一旦所有的中間點都插入到範圍樹中，我們将查詢與 r 1 r_1 r1​相關聯的所有點，這些點位于與 r 2 r_2 r2​相關的點的 δ − \delta- δ−鄰域( δ − \delta- δ−neighborhood)中。

計算所有中間點需要 O （ n 2 ） O（n^2） O（n2）時間，建構和查詢相鄰點需要 O （ n 2 l o g n + k ） O（n^2 logn+k） O（n2logn+k），其中k是報告的總點數。稍後我們将進一步改善這種複雜性。

3.3 Extracting Congruent 4-points in 3D三維中提取全等4點集

給定一個（近似）共面4點集B（B從P中選擇），和另一個點集 Q ∈ R 3 Q\in\mathbb{R}^3 Q∈R3，我們的目标是從Q中提取與B近似全等的所有4點的集合。首先給定B，我們計算它在這個平面上的兩個仿射不變量比率，如前所述。然後從點Q中，使用3.2節中描述的方法，通過仿射變換提取與B相關的所有點集。

為了去除非全等基（non-congruent bases），我們觀察它們在 R 3 \mathbb{R}^3 R3中的原始位置，并驗證相應的集合是否在某個門檻值内與基集B一緻。然後利用基集B和Q中的每個潛在可能的基集，利用Horn[1987]提出的閉式解計算最小二乘意義下的最佳剛體變換。對于寬基，由于基點之間的距離接近Q的直徑，是以子集的典型數目為 O ( n ) O(n) O(n)加上一個小常數（這裡的 O ( n ) O(n) O(n)表示空間複雜度而不是時間複雜度）。在這種情況下，我們可以從大小為n的點集中提取所有的全等4點集。

上述過程需要計算和存儲 O ( n 2 ) O(n^2) O(n2)中間點，這對于大點集是不允許的。然而，當尋找剛性變換時，一個保守的 O ( n ) O(n) O(n)子集就足夠了，因為以下原因：剛性變換保持點間歐幾裡德距離。給定基 B ≡ { a , b , c , d } B\equiv\{a,b,c,d\} B≡{a,b,c,d}，我們首先計算距離 d 1 = ∥ a − b ∥ d_1=\parallel{a-b}\parallel d1​=∥a−b∥和 d 2 = ∥ c − d ∥ d_2=\parallel{c-d}\parallel d2​=∥c−d∥。現在我們隻考慮Q中相距 d 1 d_1 d1​或 d 2 d_2 d2​的點對，誤差為 δ \delta δ。對于具有大緻均勻采樣的點集，我們隻需要在距離資料結構中插入 O ( n ) O(n) O(n)對。是以，整個算法在 O ( n 2 ) O(n^2) O(n2)時間内運作，包括距離樹構造的時間。隻考慮線性數量的此類對，而不是它們的二次數，會導緻顯著的加速和可管理的空間，即使對于大型點集，也可以實作剛體變換配準。

4 The 4PCS Algorithm 4PCS算法

我們給出了兩個點集P和Q，點的位置精度的一些不确定度( δ > 0 \delta>0 δ>0)，以及對P中部分點 f f f的估計， f f f裡面的點能與Q比對。我們的目标是找到一個剛性變換，使P中最大數量的點到Q的距離小于門檻值 δ \delta δ。我們提出了一個算法（見algorithm 1），其運作取決于給定點集之間的最大比對點的數量，并被随機化，以很高的機率找到正确的解。

首先我們選擇一個共面4點組成的基集： B ⊆ P B\subseteq P B⊆P。實際上，先随機選3個點，再選第四個點，與前三個點近似在同一平面。點各自相隔較遠能讓結果更穩定，但是太遠的話可能點又不在重疊區域内了，是以得不到滿意的結果。我們使用重疊度 f f f來估計這個距離。如果 f f f沒有給定，那麼在算法上使用從1遞減的 f f f如 f = 1 , 0.5 , 0.25 , . . . f=1,0.5,0.25,... f=1,0.5,0.25,...直到得到滿意的結果。在重疊度 f f f已知情況下，我們可以選擇一個在重疊部分的3點集，再按上面的方法選擇第4個點。

在基集B的擷取階段，我們定義仿射不變比。對于近似平面的基集，我們使用 連接配接點對的線之間 最近的點 來定義不變比率。現在，我們應用第3.3節中的方法，從Q中提取所有4點子集的集合 U ≡ { U 1 ， U 2 ， … ， U s } U\equiv\{U_1，U_2，…，U_s\} U≡{U1​，U2​，…，Us​}，這些子集與B近似全等。對于每個 U i U_i Ui​，利用B和 U i U_i Ui​之間的對應資訊，我們計算最佳剛體變換 T i T_i Ti​，使B在最小二乘意義上接近 U i U_i Ui​[Horn 1987]。為了驗證 T i T_i Ti​，我們計算 T i ( P ) T_i(P) Ti​(P)并找出 T i ( P ) T_i(P) Ti​(P)中有多少點與Q的距離小于 δ \delta δ。這種驗證是以随機方式進行的。為了提高效率，我們在 R 3 \mathbb{R}^3 R3中使用ANN（近似最近鄰）[Arya等人，1998]進行鄰域搜尋。我們首先從P中選擇恒定數量的部分點集S，使用 T i T_i Ti​對這些點進行空間變換，然後對于S裡面的每個點查找其在Q中的近鄰點。如果比對到足夠多的點（S中有足夠多的點與Q的距離小于 δ \delta δ），我們再對P中剩餘的點進行相同測試，并為 T i T_i Ti​配置設定一個分數（參見[Irani and Raghavan 1996]）。設 T T T表示具有最佳得分的變換。

給定一個基 B i B_i Bi​，我們描述了如何計算與其對應的最佳變換 T i T_i Ti​。每個變換 T i T_i Ti​基于門檻值 δ \delta δ有一個分數。使用此程式，我們現在執行randomized alignment（見第2節），并根據重疊度 f f f的估計值，測試L個不同的基（ B i B_i Bi​）（見公式1）。最後我們得到得分最高的轉換 T o p t T_{opt} Topt​。

further enhancement進一步提高

局部描述子，剛體變換下具有不變性，經常用來減少配準時的搜尋空間。同樣，當局部描述子能被可靠地計算時，本算法也能通過局部描述子得到提升。在下文中，我們展示了即使使用簡單的非不變描述符（如曲面法線），也可以實作顯著的加速，同時仍然可以使用寬基保持計算變換的精度。給定一個由4個共面點組成的基 B B B和一個 Q ∈ R 3 Q\in \mathbb{R}^3 Q∈R3的集合，我們要在一個近似水準 δ \delta δ内找到Q的所有4個點子集，這些子集與 B B B是近似全等的。設 B ≡ { a , b , c , d } B\equiv\{a,b,c,d\} B≡{a,b,c,d}為P中的四個共面點（如第4節所選）， O ≡ { N a , N b , N c , N d } O\equiv \{N_a,N_b,N_c,N_d\} O≡{Na​,Nb​,Nc​,Nd​}為它們的相關法線， d 1 = ∥ a − b ∥ d_1=\parallel{a-b}\parallel d1​=∥a−b∥， d 2 = ∥ c − d ∥ d_2=\parallel{c-d}\parallel d2​=∥c−d∥。設 N ( x , y ) N(x,y) N(x,y)分别表示點x和y處兩條局部法線之間的二面角。請注意，我們不要求法線方向的全局一緻性。

在近似法線的條件下，所有滿足 ∥ q 1 − q 2 ∥ ≈ d 1 \parallel{q_1-q_2}\parallel\approx d_1 ∥q1​−q2​∥≈d1​或 ∥ q 1 − q 2 ∥ ≈ d 2 \parallel{q_1-q_2}\parallel\approx d_2 ∥q1​−q2​∥≈d2​的點對 { q 1 , q 2 } ∈ Q \{q_1,q_2\}\in Q {q1​,q2​}∈Q進行進一步修剪：選擇任意一點 q ∈ Q q\in Q q∈Q，計算其近似法向 N q N_q Nq​，然後提取所有點 q i ∈ Q q_i\in Q qi​∈Q，使得 N ( Q , q i ) ≈ N ( a , b ) N(Q,q_i)\approx N(a,b) N(Q,qi​)≈N(a,b)，或 N ( Q , q i ) ≈ N ( c , d ) N(Q,q_i)\approx N(c,d) N(Q,qi​)≈N(c,d)。在近似法線（用高斯球上的點表示）上使用鄰域資料結構，可以有效地完成上述計算。是以，在實際中，這種基于法線和距離的限制沒有存儲所有 n 2 n^2 n2對點，而是輸入點的線性關系。即使使用在剛性變換下變化的無向近似曲面法線，我們也觀察到了兩倍的加速。當可靠的剛性不變描述子可用時，可以進一步加速。

5 Results結果

我們在各種輸入資料上測試了4PCS算法，這些資料具有不同的噪聲量、離群值和重疊程度。我們将展示算法準确性和和魯棒性。為了進行比較，使用了基于局部描述符的RANSAC算法，并在相同的輸入上執行。

圖7顯示了在沒有使用ICP精配準的情況下，在零均值不同方差 σ \sigma σ的高斯噪聲下配準過程的魯棒性。

在圖9中，我們展示了在存在不同數量的離群值時的配準結果，且沒有使用icp進行精配準。

在一個相關的實驗中，我們改變重疊量來評估性能（圖6）。可看到改變異常值的數量或重疊度對4PCS的運作時間有相似的影響，因為這兩種方法都會導緻兩個對象之間的全等基集更少。

在圖8中，我們列出了算法的各種性能特征。為了進行比較，我們使用結合了最先進的（state-of-the-art）局部描述子的RANSAC算法。我們使用多尺度自旋圖像[Li and Guskov 2005]和魯棒積分不變量[Pottmann等人，2007]的組合作為局部描述子。随着噪聲和離群值的增加，基于RANSAC的方法會随着局部描述子的可靠性降低而變慢，最終退化為暴力搜尋。在局部特征空間中，我們手動選擇最小搜尋半徑，使得估計誤內插補點與我們提出的算法相當。在極端條件下，基于局部描述子的結果無法進一步使用icp來收斂到正确的解，而4PCS的表現仍然令人滿意。總而言之，在存在大量異常值、低重疊或高噪聲的情況下，我們的算法總是優于LD-RANSAC（local descriptor RANSAC）。在局部描述符可以可靠計算的情況下，4PCS的工作速度甚至更快。

在表1中，我們展示了4PCS在各種測試資料集上的性能。如與局部描述符方法（圖8）的比較所示，噪聲和小的重疊度讓配準時間不是線性變換。我們使用了一個高門檻值的法線，其估計對含噪聲的資料是不可靠的，進而實作了隻有兩個加速因子。法線估計的預計算時間也包括在其中。

如圖10所示，很容易将我們的算法擴充到恢複較小的剪切(shear)變換。然而，對于這樣的仿射變換（指剪切變換），不能用P中的單個4點基唯一确定，我們必須構造一對具有兩個共同點的4點基：其餘算法保持不變。雖然這個過程可以處理較小的剪切，但對于一般的仿射變換，該算法可能會存儲輸入點數為二次方的中間點，這使得該過程不切實際。(原文：Although this procedure can handle small shears, for general affine transforms the algorithm may store intermediate points quadratic in number of input points, making the procedure impractical.

the algorithm may store intermediate points quadratic in number of input points這句話沒懂，是以給出的翻譯也是直接機器翻譯的)

局限性

在圖13中，如果被掃描的底層對象是可滑動的，4PCS的性能如何——結果可能在滑動方向上是次優的（參見[Gelfand and Guibas 2004]）。由于我們是在點層次上操作的，這個問題是不可避免的。然而，消除這些歧義可能需要更多關于對象的語義資訊，而不僅僅是現在使用的點位置。

在極低重疊掃描的極端情況下，選擇寬的4點基集不太可能（choosing a 4-points wide base might not be possible）。在這種情況下，我們不得不通過選擇較窄的基集來犧牲配準的穩定性。然而，任何配準技術在輸入上都面臨類似的問題。

總結

算法：

從待配準點雲 P P P中選擇 L L L個共面4點集構成基集 B i ≡ { a , b , c , d } ( i = 1 , 2 , , , L ) B_i\equiv\{a,b,c,d\}(i=1,2,,,L) Bi​≡{a,b,c,d}(i=1,2,,,L)，實際應用中，這4點并不是嚴格共面，而是近似共面。選擇方式是先随機選3個點，然後再選一個與前3個點近似共面的點作為第4個點。我們希望這4個點越遠越好，算法越穩定，但是，必須在點雲的重疊部分。利用4個點的對角線交點（ab交cd于e），記錄對于仿射變換不變的比例關系 r 1 = ∥ a − e ∥ / ∥ a − b ∥ r_1=\parallel{a-e}\parallel/\parallel{a-b}\parallel r1​=∥a−e∥/∥a−b∥， r 2 = ∥ c − e ∥ / ∥ c − d ∥ r_2=\parallel{c-e}\parallel/\parallel{c-d}\parallel r2​=∥c−e∥/∥c−d∥，以及點間距離 d 1 = ∥ a − b ∥ d_1=\parallel{a-b}\parallel d1​=∥a−b∥， d 2 = ∥ c − d ∥ d_2=\parallel{c-d}\parallel d2​=∥c−d∥。

在參考點雲Q中尋找所有與 B i B_i Bi​近似全等的4點集 U ≡ { U 1 ， U 2 ， … ， U s } U\equiv\{U_1，U_2，…，U_s\} U≡{U1​，U2​，…，Us​}，條件是 U s U_s Us​的4點滿足 B i B_i Bi​ 的4點生成的比例關系和距離關系。計算由 U s U_s Us​和 B i B_i Bi​确定的空間變換 T i s T_{is} Tis​（4個點對求解空間變換矩陣，這裡是一個 B i B_i Bi​對應s個U）。使用 T i s T_{is} Tis​對 P P P進行變換後，統計此時 T i s ( P ) T_{is}(P) Tis​(P)中與Q的距離小于門檻值 δ \delta δ的點數 k i s k_{is} kis​，留下 k i s k_{is} kis​最大時的變換作為最優的 T i T_i Ti​。

對 L L L個 B i B_i Bi​均執行上述過程，在保留的 T i T_i Ti​中，再次選擇最優的一個作為最後的結果 T o p t T_{opt} Topt​。

問題/疑惑：

文中給出用重疊度 f f f來選擇在重疊部分的3點集，再選擇第4個點，但是沒有具體說怎麼選擇根據 f f f選擇3點集。

在未知重疊度 f f f時，從1往下遞減，每次遞減的量多少合适，太小比如每次減0.01這種會太耗時，太大像0.25這種，又得不到準确的重疊度，用2分法去試那不就增加了手動的成分？

希望懂的朋友能指教！

參考及感謝

papers:

Aiger D , Mitra N J , Cohen-Or D . 4-points congruent sets for robust pairwise surface registration[J]. Acm Transactions on Graphics, 2008, 27(3):1-10.

FISCHLER, M. A., AND BOLLES, R. C. 1981. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 6, 381–395.

blog:

文中已列出

完

邊學邊用，如有錯漏，敬請指正

--------------------------------------------------------------------------------------------諾有缸的高飛鳥202012