CVPR2023 | 如何設(shè)計(jì)一個更快更魯棒的P3P求解器？（2）

（11）中三次方程的通解可能有四種情況： 三個實(shí)根，一個實(shí)根和兩個復(fù)根，一個實(shí)根和一個重根、一個實(shí)三重根。 這四種可能性對應(yīng)于直線和交點(diǎn)的不同情況。在本文的例子中，第一個圓錐曲線（4）是不定的，第二個圓錐曲線（5）是雙曲線（b>0）。不失一般性，假設(shè)第一個是橢圓，并在圖3中展示兩個圓錐曲線的可能相對位置。 簡要起見，以圖3b作為示例。兩個圓錐曲線有四個實(shí)交點(diǎn)，特征三次方程有三個實(shí)根，每個實(shí)根對應(yīng)于一對實(shí)直線。每對實(shí)直線在四個實(shí)交點(diǎn)處與兩個圓錐曲線中的任何一個相交（圖3b）。在其他情況下也存在類似的情況。

圖3：雙曲線和橢圓相對位置的八種可能情況的圖解。具有不同顏色的一對線對應(yīng)于不同的三次根。(a)-(c): 兩個圓錐曲線分別具有零、四和兩個實(shí)交點(diǎn)的一般情況。(d)-(f): 兩個圓錐曲線相切的臨界情況，分別有一個二重交點(diǎn)、兩個二重交點(diǎn)、一個二重交點(diǎn)和兩個交點(diǎn)。(g)-(h): 兩個圓錐曲線彼此密切（兩個圓錐在切點(diǎn)具有相同的曲率），分別有一個三重交點(diǎn)和一個四重交點(diǎn)

三次方程的根、線的數(shù)量和交點(diǎn)之間的關(guān)系如表1所示。

表1：三次方程的根、退化圓錐曲線的直線數(shù)和兩個圓錐曲線交點(diǎn)之間的關(guān)系。1D、1T和1Q分別表示一個二重交點(diǎn)、一個三重交點(diǎn)和一個四重交點(diǎn)

假設(shè)三次方程（11）可以寫成

進(jìn)行變量替換可得關(guān)于的沮喪三次方程(沒有二次項(xiàng))

其中

(30)的判別式為：

• 若,（30）有三個不同的實(shí)根，其對應(yīng)于情況（a）和（b）。對于情況（a），由于所有的實(shí)根都不對應(yīng)于任何實(shí)交點(diǎn)，我們可以選擇三個根中的任何一個。使用三角解找到根,該根可以對應(yīng)于一對實(shí)線，也可以不對應(yīng)于實(shí)線。如果選擇的實(shí)根給出一對實(shí)線，可以在驗(yàn)證第一條直線沒有實(shí)交點(diǎn)后跳過第二條直線。對于情況（b），三個根中的任何一個都將產(chǎn)生一對實(shí)線和四個實(shí)交點(diǎn)。
• 若,（30）具有一個實(shí)根和兩個共軛復(fù)根，這對應(yīng)于情況（c）。使用Cardano公式可以找到實(shí)根，并且可以得到一對實(shí)直線。如果其中第一條直線與圓錐曲線有實(shí)交點(diǎn)，則可以跳過第二條直線。否則，如果第一條直線沒有實(shí)交點(diǎn)，就需要檢查第二條直線。
• 若且,則（30）有一個單實(shí)根和一個重實(shí)根，這對應(yīng)于情況（d）、（e）和（f）。對于情況（d），可以看到重實(shí)根在虛直線中產(chǎn)生。因此，對于這種情況，可以使用單實(shí)數(shù)根。
• 若且，則。在這種情況下，方程（30）有三重根γ，這對應(yīng)于情況（g）和（h）。三次方的實(shí)根給出了一對實(shí)線，并且可以很容易地找到實(shí)交點(diǎn)。

基于以上分析和表1，可以注意到，可以使用任何一對實(shí)線來恢復(fù)實(shí)交點(diǎn)，并且除了情況（d）之外，三次方程的任何實(shí)根都對應(yīng)于一對實(shí)直線。只需要在且時避免使用重實(shí)根。 另一方面，如果，則這對直線和圓錐曲線之間一定有雙重交點(diǎn)。為了避免重復(fù)的解，需要檢查直線和圓錐曲線之間的交點(diǎn)。整個過程如算法1所示。