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

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

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

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

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

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

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

圖 1 算法流程

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

圖 2 算法效果總覽

1、基本模型

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

1.1、面片模型

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

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

圖 3 面片模型

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

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

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

1.3、圖像模型

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

圖 5 圖像模型

2、初始面片生成

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

圖 6 特征匹配算法偽代碼

圖 7 特征匹配后的效果

3、面片加密

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

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

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

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

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

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

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

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

3.2、擴(kuò)張策略

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

圖 9 擴(kuò)張策略的偽代碼

4、面片剔除

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

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

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

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

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

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

參考文獻(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.