從三視圖到多視圖的完整計算機視覺重建之路

基礎矩陣是計算機視覺中連接二維圖像與三維重建的神秘橋梁。當我們擁有多個相機拍攝的圖像時，如何確保這些相機之間的關系能夠在三維空間中和諧共存？這就是基礎矩陣兼容性問題的核心。長期以來，研究者們錯誤地認為三視圖的兼容性足以保證全局兼容性。本文揭示了這一錯誤觀念，并展示了從三視圖到四視圖及更多視圖的完整理論框架。通過精確的代數條件，我們不僅能判斷一組基礎矩陣是否兼容，還能重建出原始相機的位置與朝向。這些發現不僅具有理論意義，更為計算機視覺中的實際應用打開了新的可能性大門。

圖像的幾何語言

計算機視覺中的基礎矩陣是連接不同視角相機之間的重要紐帶。想象一下，你拿著手機圍繞一個物體拍攝多張照片，每兩張照片之間都存在某種幾何關系，這種關系就由基礎矩陣描述?；A矩陣在數學上是一個33的矩陣，它編碼了兩個相機之間的所有點對應關系。

基礎矩陣的特點是它總是一個秩為2的矩陣。這意味著它有一些特殊的代數性質，使得我們可以從中提取關于相機位置的有用信息。對于任何一個秩為2的33矩陣F12，我們總能找到一對相機P1和P2，使得F12成為它們的基礎矩陣。這對相機在投影變換下是唯一的，這就是為什么基礎矩陣成為三維重建的基石。

兼容性問題的核心在于：給定n個相機之間的多個基礎矩陣（通常是n（n-1）/2個），是否存在n個相機，使得每對相機之間的基礎矩陣都與給定的基礎矩陣一致？這聽起來似乎很直觀，但實際上并非如此簡單。

這個問題的研究歷史可以追溯到上世紀90年代。早期的多視圖結構運動方法通常從估計點對應關系的基礎矩陣開始。這些方法在當時已經相當成熟，但在理論上，人們對多個基礎矩陣之間的兼容條件卻知之甚少。

視圖圖（viewing graph）的概念被引入來描述相機之間的連接關系。在這個圖中，每個節點代表一個相機，節點之間的邊表示我們知道這兩個相機之間的基礎矩陣。完整視圖圖意味著我們知道所有可能的n（n-1）/2個基礎矩陣。

在實際應用中，兼容性條件的研究具有重要意義。Kasten等人在2019年提出了一種投影結構運動算法，該算法應用了他們發現的兼容性必要充分條件。該算法能處理完整或部分的基礎矩陣集合，目標是找到相機矩陣，使它們對給定的基礎矩陣集合產生最小的全局代數誤差。

在理論領域，Angst等人利用兼容性條件對臨界配置進行了分類。臨界配置是指在特定的相機和場景點分布下，三維重建可能變得不穩定或不唯一的情況。這些研究深化了我們對多視圖幾何學的理解。

兼容性問題的主要挑戰在于找到明確的代數條件，這些條件必須是必要且充分的，能夠判斷一組基礎矩陣是否兼容。過去的研究主要集中在特定情況下，如三視圖或所有相機中心共線的情況，而對一般情況下的完整條件則知之甚少。

基礎矩陣與相機之間的關系可以通過一個理論映射ψ來描述。對于兩個34的相機矩陣P1和P2，ψ（P1， P2）返回它們的基礎矩陣F12。這個映射只有在P1和P2的核（代表相機中心）有交集時才會退化為零矩陣。

在接下來的部分中，我們將詳細探討三視圖情況下的兼容性條件，這是理解更一般情況的基礎。

三視圖的代數條件

三視圖情況下的兼容性問題是最基本也是最早被系統研究的情況。在這個設置中，我們有三個相機P1、P2和P3，以及它們之間的三個基礎矩陣F12、F13和F23。問題是：給定這三個基礎矩陣，它們是否兼容？即是否存在三個相機使得它們產生給定的基礎矩陣？

在Hartley和Zisserman的經典著作《Multiple View Geometry》中，他們提出了三視圖情況下的必要充分條件。這些條件分為兩種情況：非共線相機和共線相機。

對于非共線相機（即三個相機中心不在同一直線上），兼容性的必要充分條件是：

1. 每個圖像中的兩個極點必須不同。極點是指一個相機中心在另一個相機圖像上的投影。

2. 三個所謂的＂三重約束＂必須成立：（e?）?F??e? = （e?）?F??e? = （e?）?F??e? = 0

這里，e??表示第k個相機中心在第i個相機圖像上的投影（極點）。這些條件在幾何上有清晰的解釋：它們確保了三個相機中心和任何一個場景點都在同一個平面上。

有趣的是，長期以來，人們錯誤地認為這些三重約束對于任何相機配置都是充分的。這個誤解甚至出現在一些學術文獻中。例如，在2007年，Angst等人聲稱這些條件對于共線相機也是充分的，但這一說法后來被證明是錯誤的。

對于共線相機情況（即三個相機中心在同一直線上），兼容性的條件有所不同。在這種情況下，三個相機中心共線意味著每個圖像中的兩個極點必須相同。具體來說，如果P1、P2、P3的中心共線，那么P1（kernel P2） = P1（kernel P3），這導致e? = e?，e? = e?，e? = e?。

然而，僅僅滿足這些條件和三重約束還不足以確保兼容性。實際上，還需要一個額外的條件：（F??）?[e?]F?? = F??，其中[e?]表示e?的叉積矩陣。這個條件確保了三個基礎矩陣在共線情況下的一致性。

為了說明三重約束在共線情況下的不足，讓我們考慮一個具體的反例。假設我們有以下三個基礎矩陣：

F?? = [[0，0，0]，[0，1，0]，[0，0，1]]

F?? = [[0，0，0]，[0，0，1]，[0，1，0]]

F?? = [[0，0，0]，[0，1，1]，[0，-1，1]]

以及對應的極點：

e? = e? = [1，0，0]

e? = e? = [1，0，0]

e? = e? = [1，0，0]

這些基礎矩陣滿足三重約束，但沒有三個相機能同時產生這三個基礎矩陣。這驗證了三重約束在共線情況下不是充分條件。

三視圖兼容性的研究不僅具有理論意義，還有實際應用。在三維重建中，我們經常需要從估計的基礎矩陣中恢復相機。了解兼容性條件可以幫助我們判斷這些估計是否合理，以及如何調整它們使它們變得兼容。

三視圖條件的局限性在于它們只適用于三個相機的情況。當我們考慮四個或更多相機時，這些條件是否足夠就成為一個重要問題。長期以來，人們認為只要每三個相機滿足三重約束（稱為三重兼容性），那么整個系統就是兼容的。這一信念在2010年代逐漸形成，甚至在一些學術文獻中被視為既定事實。然而，這一信念是錯誤的，正如我們在后續章節中將看到的那樣。

三視圖情況下的兼容性條件為我們理解多視圖幾何奠定了基礎。這些條件揭示了基礎矩陣與相機構型之間的復雜關系，并引導我們思考更一般情況下的兼容性問題。

四視圖的新發現

長期以來，計算機視覺領域的研究者普遍認為，只要三個相機之間的關系滿足了兼容性條件，那么任意多個相機之間的關系自然也會滿足兼容性。這種觀點甚至在2018年的學術文獻中仍被認為是正確的。但實際上，這種想法是錯誤的，特別是當涉及到四個或更多相機時。

為了打破這一錯誤認識，Bratelund和Rydell在2023年提供了一個反例。他們構造了六個基礎矩陣F12、F13、F14、F23、F24和F34，它們兩兩之間滿足三重約束條件，但整體上不兼容。具體來說，這六個矩陣是：

F12 = [[0，0，0]，[0，0，1]，[0，1，0]]

F13 = [[0，0，1]，[0，0，0]，[0，1，0]]

F14 = [[0，0，1]，[0，1，0]，[0，0，0]]

F23 = [[0，0，1]，[0，0，0]，[1，0，0]]

F24 = [[0，0，1]，[1，0，0]，[0，0，0]]

F34 = [[0，1，0]，[2，0，0]，[0，0，0]]

對應的極點分布如下：

在相機1中：e21 = [1，0，0]， e31 = [0，1，0]， e41 = [0，0，1]

在相機2中：e12 = [1，0，0]， e32 = [0，1，0]， e42 = [0，0，1]

在相機3中：e13 = [1，0，0]， e23 = [0，1，0]， e43 = [0，0，1]

在相機4中：e14 = [1，0，0]， e24 = [0，1，0]， e34 = [0，0，1]

盡管這些矩陣滿足三重約束，但不存在四個相機能同時產生這六個基礎矩陣。這個反例徹底打破了之前的錯誤認識。

四個相機之間的兼容性問題更為復雜，因為相機中心在三維空間中可能有多種布局。Bratelund和Rydell將這些可能的配置分為四種情況：

1. 通用情況：四個相機中心不共面，即沒有一個平面包含所有四個中心。在這種情況下，每個圖像中的三個極點不共線。

2. 所有相機中心共面，但沒有三個中心共線。在這種情況下，每個圖像中的三個極點各不相同且共線。

3. 恰好三個相機中心共線。在這三個相機的圖像中，來自其他兩個相機的極點重合，而第三個不同。在第四個圖像中，三個極點各不相同且共線。

4. 所有四個相機中心共線。在這種情況下，每個圖像中的三個極點重合。

對于通用情況，他們證明了兼容性的必要充分條件是：三重約束條件加上一個額外的方程：

e4123e2134e3142e4231e1243e2341 = e3124e4132e2143e1234e3241e1342

這里的eijkl表示＂極點數＂，定義為（ei j）T Fjk ekl。這些數值在幾何上表示四個相機中心形成的四面體的體積關系。

對于其他三種情況，他們也給出了類似的必要充分條件。這些條件都可以表示為基礎矩陣和極點的多項式方程。

這些發現不僅解決了長期以來的理論爭議，還為實際應用提供了重要工具。例如，在處理噪聲數據時，我們可以利用這些條件來調整估計的基礎矩陣，使它們變得兼容，從而提高三維重建的準確性。

另一個重要發現是，四點兼容性實際上足以保證全局兼容性。具體來說，如果一組n個相機的所有四相機子集都兼容，那么整個系統必然兼容。這大大簡化了判斷大型相機系統兼容性的復雜度。

特別地，當所有相機中心共線時，三重兼容性實際上足以保證全局兼容性。在這種情況下，重建將是一組中心都位于同一直線上的相機。

這些研究還解決了兼容基礎矩陣解的唯一性問題。除非所有圖像中的極點重合（即所有相機中心共線），否則兼容的基礎矩陣集合在投影變換下有唯一解。

理論擴展與應用

基礎矩陣兼容性研究的一個重要方向是將理論擴展到任意視圖圖，而不僅僅是完整圖。Bratelund和Rydell在2023年提出了一個循環定理，它為任意視圖圖上的兼容性提供了必要充分條件。

循環定理指出，一組基礎矩陣{Fij}是兼容的，當且僅當存在矩陣Hi和非零標量λij，使得Gij = λijHiT Fij Hj滿足循環條件：對于圖中的每個有向循環C，∑（ij）∈E（C） Gij = 0。

這個定理將兼容性問題轉化為尋找合適的標量和矩陣的問題，使得變換后的基礎矩陣滿足特定的代數條件。如果這樣的標量和矩陣存在，那么原始的基礎矩陣就是兼容的。

這個定理特別適用于相機是校準的情況，此時基礎矩陣被稱為本質矩陣。在這種情況下，兼容性與平行剛性（parallel rigidity）理論密切相關，這在校準相機的可解性研究中已經得到了證實。

循環定理還可以用來導出我們之前討論的兼容性條件。例如，對于三個相機，循環定理意味著存在矩陣Hi和標量λij，使得λijHiT Fij Hj是反對稱的，且滿足λ12G12 + λ23G23 + λ31G31 = 0。從這個條件，我們可以導出三重約束e12F23e13 = 0。

同樣，對于四個相機，循環定理可以用來導出通用情況下的額外條件。通過使用循環條件和一些代數操作，我們可以得到我們之前看到的條件。

Kasten等人在2019年和Cheng等人在2022年也研究了基礎矩陣兼容性問題，他們提出了基于n視圖基礎矩陣的方法。n視圖基礎矩陣是將所有二視圖基礎矩陣拼接成一個大矩陣。

他們的結果表明，一組基礎矩陣是兼容的，當且僅當存在非零標量λij = λji，使得n視圖基礎矩陣F = （λijFij）具有特定的秩和特征值條件。對于非共線相機，F應該是秩6，并且恰好有3個正特征值和3個負特征值。對于共線相機，F應該是秩4，并且恰好有2個正特征值和2個負特征值。

Bratelund和Rydell通過計算機代數系統Macaulay2的實驗，證明了在通用情況下和所有極點在每個圖像中重合的情況下，特征值條件實際上是多余的。這大大簡化了兼容性的判斷。

這些理論發現在實際應用中有重要意義。例如，在結構運動（structure-from-motion）算法中，我們經常需要從噪聲數據中估計基礎矩陣。知道精確的兼容性條件，可以幫助我們調整這些估計，使它們變得一致，從而提高三維重建的精度。

兼容性理論也與臨界配置分類相關。臨界配置是指在特定的相機和場景點分布下，三維重建可能變得不穩定或不唯一的情況。通過理解基礎矩陣的兼容性條件，我們可以更好地識別和處理這些情況。

此外，這些研究還與可解性理論相關?？山庑匝芯康氖?，給定一組相機，它們的基礎矩陣是否有唯一解（在投影變換下）。這個問題在計算機視覺中有廣泛的研究，特別是在校準相機的情況下。

總的來說，基礎矩陣兼容性的研究為計算機視覺中的多視圖幾何提供了堅實的理論基礎。這些研究不僅解決了長期以來的理論爭議，還為實際應用提供了重要工具，幫助我們更準確地從二維圖像恢復三維結構。

參考資料

1. Martin Bratelund &； Felix Rydell （2023）. Compatibility of Fundamental Matrices for Complete Viewing Graphs， ICCV 2023

2. Hartley &； Zisserman. Multiple View Geometry in Computer Vision.

3. Kasten et al. （2019）. Algebraic-Geometric Approach to Camera Auto-Calibration.