CVPR2023 | 如何設(shè)計(jì)一個(gè)更快更魯棒的P3P求解器?(1)
1 什么是P3P問題P3P 問題是經(jīng)典的多視圖幾何問題之一,其中標(biāo)定的相機(jī)的絕對(duì)位姿由三個(gè) 2D-3D 對(duì)應(yīng)關(guān)系決定。由于這是許多視覺系統(tǒng)的關(guān)鍵(例如定位和SfM),因此過去有很多研究關(guān)注于如何開發(fā)更快、更穩(wěn)定的P3P算法。雖然當(dāng)前SOTA的求解器既非??煊址€(wěn)定,但仍然存在可能崩潰的配置。 本文將問題代數(shù)化為尋找兩個(gè)圓錐的交點(diǎn)。通過這個(gè)方式,我們能夠分析表征多項(xiàng)式系統(tǒng)的實(shí)根,并為每個(gè)問題實(shí)例采用量身定制的解決方案。這導(dǎo)出了一個(gè)快速穩(wěn)定的P3P求解器,它能夠正確解決其它方法可能會(huì)失敗的情況。實(shí)驗(yàn)評(píng)估表明,該方法在速度和成功率方面都優(yōu)于當(dāng)前的SOTA方法。
PnP是指根據(jù)2D-3D對(duì)應(yīng)關(guān)系集合估計(jì)相機(jī)絕對(duì)位姿,集合最小的情況是P3P問題。P3P是將2D-3D對(duì)應(yīng)關(guān)系通過相機(jī)內(nèi)參轉(zhuǎn)換為3D-3D對(duì)應(yīng)關(guān)系進(jìn)行求解。 給定世界坐標(biāo)系中的3個(gè)3D點(diǎn)以及它們對(duì)應(yīng)的歸一化圖像點(diǎn),兩個(gè)點(diǎn)集通過剛體變換關(guān)聯(lián):
其中是某個(gè)正數(shù)。P3P的目標(biāo)是求解其中的旋轉(zhuǎn)和平移。
2 P3P問題發(fā)展史P3P作為一個(gè)幾何問題歷史悠久,比計(jì)算機(jī)視覺領(lǐng)域的出現(xiàn)都要早很久。早在1773年Lagrange就在研究這個(gè)問題,Lagrange證明該問題最多可能有4個(gè)實(shí)數(shù)解,可以轉(zhuǎn)化為4次多項(xiàng)式問題求解。大約1個(gè)世紀(jì)后,1841年德國數(shù)學(xué)家Grunert重新研究了該問題,給出了一種直接求解方法。20世紀(jì)早期,該問題在攝影測(cè)量領(lǐng)域內(nèi)受到關(guān)注,但主要關(guān)注點(diǎn)在于精調(diào)而不是從頭求解。Finstenvalder和Scheufele在1937年證明P3P問題只需要找到1個(gè)三次多項(xiàng)式的1個(gè)根和2個(gè)二次多項(xiàng)式的根。該問題后來在1981年Fischler和Bolles的RANSAC論文重新露面,由于RANSAC的成功,該問題也開始受到很大的關(guān)注。
根據(jù)最后需要求解的一元多項(xiàng)式的階次,P3P問題可分為兩大類:求解1個(gè)四次方程和求解1個(gè)三次方程。
最近的大多數(shù)工作關(guān)注于將P3P問題轉(zhuǎn)化為求解四次方程問題。Gao等人在2003年用吳零點(diǎn)分解法第一次給出了P3P的完成解析解。Kneip等人2011年提出了一種直接由計(jì)算相機(jī)絕對(duì)位置和旋轉(zhuǎn)的方式求解P3P問題的方法,避免了特征值分解或奇異值分解。Ke等人2017年提出用相應(yīng)的幾何約束確定相機(jī)的旋轉(zhuǎn)。Banno和Nakano分別于2018和2019提出了P3P的直接求解法,通過估計(jì)中間坐標(biāo)系中的距離,使得旋轉(zhuǎn)矩陣可以形式化為距離的線性表示。
與基于四次方程的方法不同,基于三次方程的方法在P3P問題的文獻(xiàn)中沒有得到太多關(guān)注。自Finstenvalder和Scheufele在1937年的工作以來,Grafarend等人在1989年也使用了三次方程,他們?cè)噲D將(3)簡(jiǎn)化為齊次形式,然后使用與Finstenvalder和Scheufele相同的技術(shù)求解。Haralick等人在1991年回顧了P3P問題的主要基于三次方程的解法,并討論了數(shù)值精度。最近,Persson和Nordberg在2018年展示了關(guān)于尋找旋轉(zhuǎn)和平移的更多細(xì)節(jié),并提出了一種使用三次方程的一個(gè)根的有效算法,該方法比以前的方法有更好的數(shù)值精度,并且更快。
3 P3P問題轉(zhuǎn)化為兩個(gè)圓錐曲線相交問題參照Persson和Nordberg在2018年的解法,為了消除旋轉(zhuǎn)和平移參數(shù),如圖1所示,有如下約束:
根據(jù)余弦定理,
其中。我們的目標(biāo)是找到的解,從而求解旋轉(zhuǎn)和平移。我們可以假設(shè),不然3D點(diǎn)就和相機(jī)中心一樣了。將(3)中前兩個(gè)式子除以第三個(gè)式子,并通過變量替換,可以得到以下二元二次方程組:
其中
現(xiàn)在問題變?yōu)榍髢蓚€(gè)二次方程的實(shí)數(shù)解,也就是說找到兩個(gè)圓錐曲線的實(shí)數(shù)交點(diǎn)。
4 本文的方法本文的方法的基本思路也是求解兩個(gè)圓錐曲線的相交問題。 (4)和(5)的兩個(gè)二次方程可以重寫為:
其中為的矩陣。為了找到交點(diǎn),首先構(gòu)造一個(gè)矩陣
交點(diǎn)可通過構(gòu)建一個(gè)與真正的解相交的退化圓錐曲線找到。退化圓錐曲線由以下命題給出:
命題1(退化圓錐曲線,見《計(jì)算機(jī)視覺中的多視圖幾何》)如果矩陣 不滿秩,則圓錐曲線退化。退化點(diǎn)的圓錐曲線是兩條線(秩為2)或一條重復(fù)線(秩為1),可以寫為:
其中。
退化圓錐曲線被構(gòu)造出來后,可以被分解為(至多)兩條直線(和),可以進(jìn)一步很容易地與原來的兩個(gè)圓錐曲線相交。
4.1 尋找退化圓錐曲線根據(jù)定理1,退化圓錐曲線需要非滿秩,即行列式為0:
得到關(guān)于的三次方程。求解(11)可以得到的值,并得到矩陣。注意原始方程組的任何解(同時(shí)屬于圓錐曲線)也在退化圓錐曲線上。
對(duì)于(11)中的每個(gè)解,都可以得到一個(gè)退化圓錐曲線。根據(jù)(10),退化圓錐曲線是兩條直線和的組合。那么如何將退化圓錐曲線分解為兩條直線呢?
4.1.1 方法一:直接求解直線這里展示一種尋找直線的直接方法。假定已經(jīng)找到了一個(gè)退化圓錐曲線,寫為如下形式:
由于,假設(shè),矩陣也可以寫為:
假定,令,則
\tilde{p}_2+\tilde{q}_2& =2c_{12}/c_{11}, \\ \tilde{p}_2\tilde{q}_2& =c_{22}/c_{11}, \\ \tilde{p}_3+\tilde{q}_3& =2c_{13}/c_{11}, \\ \tilde{p}_2\tilde{q}_3+\tilde{p}_3\tilde{q}_2& =2c_{23}/c_{11},
根據(jù)(14)和(15)可以解出, 進(jìn)而根據(jù)(16)和(17)可求得。在這種情況下,可以得到一對(duì)直線和。為了避免的情況,可以找到的絕對(duì)值最大的對(duì)角線元素,更穩(wěn)定地計(jì)算出直線對(duì)。
4.1.2 方法二:通過求兩直線相交求解直線由于兩直線參數(shù)的叉乘可得交點(diǎn),可以進(jìn)而從中提取出兩直線。對(duì)于交點(diǎn),這里展示兩種求法:
(1) 零空間法: 根據(jù)(10)可知, 交點(diǎn)在的零空間內(nèi), 對(duì)于的任意零空間向量,有。我們現(xiàn)在必須找到,使得的尺度與(以及)一致。由于,我們有
結(jié)合(12),(13)和(18),可以推導(dǎo)出的范數(shù)和的元素之間的關(guān)系:
因此,可以將以正確的尺度適當(dāng)?shù)刂匦驴s放得到交點(diǎn)。
(2) 伴隨矩陣法:矩陣的伴隨矩陣應(yīng)滿足:
證明:通過(13)可以得到
與相等。
給定一個(gè)矩陣,可以得到。為了避免0元素,可以找到其對(duì)角線最大的元素和對(duì)應(yīng)的列,交點(diǎn)可以通過將該列除以對(duì)角線的平方根得到。
恢復(fù)直線:得到交點(diǎn)之后,根據(jù)其反對(duì)稱矩陣
定義一個(gè)新的矩陣
結(jié)合(22)和(10)可得。直線對(duì)可以通過的行和列得到。
秩為1的情況: 如果退化圓錐曲線包括一對(duì)重復(fù)的直線,則矩陣的秩為1。在這種情況下,可以直接從一行或一列中恢復(fù)重復(fù)的直線。
4.2 P3P問題求解退化圓錐曲線中獲得的直線過原二次方程組(7)與(8)的解(交點(diǎn)),因此可以通過求直線與兩個(gè)圓錐曲線的交點(diǎn)進(jìn)行求解。 假設(shè)第一條直線為:
將(23)代入(5)可得一個(gè)關(guān)于的二次方程,至多有2個(gè)解。需要注意的是,我們只關(guān)心正的實(shí)數(shù)解。得到后,根據(jù)(23)可以得到。由可得。代入(3)可得關(guān)于的二次方程
由于, 可以得到的解。這種情況下,可以得到的值。由于有一對(duì)直線,的解有4種可能。知道后,可以用Gauss-Newton優(yōu)化(3)的平方和對(duì)結(jié)果進(jìn)行細(xì)化。之前的工作也使用了類似的細(xì)化方法。
求解旋轉(zhuǎn)和平移:對(duì)于每個(gè),首先用(1)消除平移,得到以下方程組
為了找到另一個(gè)非共面向量量對(duì)應(yīng)關(guān)系,與前人工作一樣,可以使用由三個(gè)3D點(diǎn)和圖像點(diǎn)定義的平面的法線(見圖2)。法向量也滿足
其中
結(jié)合(25)和(26),可以解得旋轉(zhuǎn)
得到旋轉(zhuǎn)后由(1)可以求解平移。
圖2:從向量對(duì)應(yīng)關(guān)系到旋轉(zhuǎn)
4.3 可能解的配置分析以及魯棒算法以上展示了P3P問題求解的一個(gè)通用算法,主要包括2個(gè)步驟:
- 求解構(gòu)建退化圓錐曲線(式(9));
- 將退化圓錐曲線分解為兩條直線,進(jìn)而代入(4)(5)的圓錐曲線求交點(diǎn)
*博客內(nèi)容為網(wǎng)友個(gè)人發(fā)布,僅代表博主個(gè)人觀點(diǎn),如有侵權(quán)請(qǐng)聯(lián)系工作人員刪除。