PMVS：多視圖匹配經(jīng)典算法

導語：Multi-View Stereo(MVS)多視圖立體匹配與三維重建的任務是：以已知內(nèi)外參數(shù)的多幅圖像(SfM的結果)為輸入，重建出真實世界中物體/場景的三維模型。

本文作者提出了PMVS的經(jīng)典算法，深入了解傳統(tǒng)算法的實現(xiàn)效果，可以幫助我們與基于深度學習的方法進行對比，對“如何評估多個視圖間相似性”這一問題有更深刻的認識，希望能對相關研究人員有一定的參考幫助。

論文題目：Accurate, Dense, and Robust Multiview Stereopsis

論文地址：https://ieeexplore.ieee.org/document/5226635

代碼地址：https://github.com/pmoulon/CMVS-PMVS

該論文提出的方法可以分解為三個主要的部分：1. 重建出若干可以完整覆蓋目標物體/場景的面片；2. 將面片模型轉換為多邊形漁網(wǎng)模型；3. 優(yōu)化多邊形漁網(wǎng)模型。這里重點分析文中提出的“匹配-擴張-剔除”策略，這也是PMVS算法的核心內(nèi)容。

圖 1 算法流程

算法效果如下圖所示，從左到右依次為輸入圖像(不同角度共48張)，特征點提取，特征匹配結果，擴張?zhí)蕹?次后效果，轉換為網(wǎng)狀模型效果。

圖 2 算法效果總覽

1、基本模型

基本模型中提及的符號含義

1.1、面片模型

先來了解什么是面片模型 (Patch Model)，所謂面片，是指三維物體表面的局部切平面，可以近似地表示某一局部范圍內(nèi)的三維物體表面，與數(shù)學中在某一范圍內(nèi)用切線研究曲線的做法一致，都是“將非線性函數(shù)線性化來近似處理”的思想。本質(zhì)上看，一個面片是三維空間中的一個矩形，由其中心點、單位法向和參考圖像三者共同確定，中心點c(p)是其對角線交點的坐標，單位法向n(p)是從中心點指向參考圖像R(p) 對應的攝影中心的單位向量，這里之所以要引入?yún)⒖紙D像的概念，是因為一個面片會在多幅圖像中出現(xiàn)，選定其中的某一圖像作為該面片的參考圖像，將包含該面片的所有圖像組成的集合V(p)稱為該面片的可視集。

（思考：如何確定一個面片的可視集并從中指定其參考圖像？）

圖 3 面片模型

1.2、成像差異函數(shù)

接著作者在面片可視集的基礎上引入了成像差異函數(shù) (Photometric Discrepancy Function) 的概念，或者叫灰度差異函數(shù)。

圖 4 成像差異函數(shù)

1.3、圖像模型

基于面片的表面表示方式最大的優(yōu)勢是其靈活性，但缺少面片與面片之間的連接信息，這使得尋找鄰近面片，面片規(guī)整等操作實現(xiàn)起來較復雜，為此引入圖像模型(Image Model)，建立起重建出的面片和其可視圖像上投影間的聯(lián)系。具體的講，將每張圖像分割為β×β的網(wǎng)格單元Ci(x,y)，在第i張圖像的(x,y)處存儲一個數(shù)組Qi(x,y)，其中包含投影在該網(wǎng)格單元上的所有面片信息。

圖 5 圖像模型

2、初始面片生成

該論文提出的多視圖匹配三維重建方法，可以分為初始面片生成、面片加密、面片剔除三部分，經(jīng)過初始特征匹配得到一組稀疏的面片集合，然后通過反復加密、剔除面片的過程得到最終的結果。每幅圖像通過Harris和DoG算子提取出特征點后，進入到特征匹配階段，這是PMVS算法的核心內(nèi)容，思路如下：

圖 6 特征匹配算法偽代碼

圖 7 特征匹配后的效果

3、面片加密

經(jīng)過上述的特征匹配后，重建出了一組稀疏的面片，接下來通過已有的面片在周圍空處生成新的面片進行加密，期望達到的效果是每個圖像網(wǎng)格單元上都至少包含有一個面片。首先，對于一個面片p，明確其周邊可以擴張的網(wǎng)格單元，然后按照某種擴展策略進行擴展，具體思路如下：

確定可擴張網(wǎng)格單元

存在面片p的網(wǎng)格單元Ci(x,y)，根據(jù)下式，將其上下左右四個網(wǎng)格單元視作鄰近網(wǎng)格單元，但并非每個鄰近網(wǎng)格單元都是可擴張的網(wǎng)格單元，還需要滿足兩個基本條件。

圖 8 鄰近網(wǎng)格單元

第一個條件：該網(wǎng)格單元中不存在鄰近面片p’，鄰近面片的判定條件如下，意思是說兩個面片中心點的距離不能過大，且兩個面片的朝向不能偏差很大。

第二個條件是作者從深度方面考慮的，擴張出的面片p’和面片p對應的實際深度不能相差過大，但是實際的深度要在完成三維重建的過程后才能知道，這里就進入了一個“雞生蛋”的邏輯死循環(huán)中，該論文中作者在這里僅做了一個簡單的處理，判斷兩者間的成像差異函數(shù)。

簡單總結一下，結合下圖，在確定可擴張的網(wǎng)格單元時分為三種情況，沒有面片時(綠色箭頭a)進行擴張；有面片且為鄰近面片時(紅色箭頭b)沒有必要擴張；

有面片但非鄰近面片時(橙色c)需要進一步判斷成像差異系數(shù)，若小于給定閾值沒必要擴張，大于給定閾值則擴張。

3.2、擴張策略

在明確了哪些網(wǎng)格單元可以擴張后，接下來的問題就是如何根據(jù)已有的面片構建出新的面片了，思路如下：

圖 9 擴張策略的偽代碼

4、面片剔除

在擴張的過程中，為應對那些變化較大、較難重建的區(qū)域，調(diào)大了成像差異的閾值，但與此同時不可避免地會出現(xiàn)一些冗余、灰度差異大等低質(zhì)量的面片，在這一步中進行剔除，“擴張-剔除”的操作需要迭代進行若干次（該論文中統(tǒng)一進行3次），每次剔除分三步進行，每步的側重不同，前兩步從成像一致性/灰度一致性入手，第三步強調(diào)面片間的關聯(lián)性。第一步剔除掉出現(xiàn)在同一個網(wǎng)格單元中，但并非鄰近面片的粗差情況；第二步通過視差圖測試，剔除掉那些較少圖像上能看到的面片；第三步，剔除掉在相鄰網(wǎng)格單元中相鄰面片個數(shù)占總面片數(shù)小于1/4的面片。

下圖表示了整個算法過程中面片的個數(shù)變化，通過“擴張”后面片個數(shù)急劇增加，然后通過三種策略剔除較差的面片，面片數(shù)不斷減少，再進行下一次的“擴張-剔除”。

圖 10 不同階段的面片數(shù)

圖 11 最終重建出的面片（物體）

圖 12 最終重建出的面片（場景）

可以看出，除了重復紋理區(qū)域（人的頭發(fā)）、凹陷部分、深度突變區(qū)域外，重建的整體效果還是不錯的，這得益于“匹配-擴張-剔除”策略的成功，成像差異函數(shù)的提出是立體匹配從雙目走向多視圖的關鍵，可視集V(p)在極線約束下利用幾何信息，更新可視集V*(p)進一步考慮灰度信息，在深度學習出現(xiàn)后，已有論文實現(xiàn)通過學習的方式來評估多個面片間的相似性。

參考文獻：

Y. Furukawa and J. Ponce, "Accurate, Dense, and Robust Multiview Stereopsis," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 32, no. 8, pp. 1362-1376, Aug. 2010, doi: 10.1109/TPAMI.2009.161.