PMVS：多檢視匹配經典演算法
導語：
Multi-View Stereo（MVS）多檢視立體匹配與三維重建的任務是：以已知內外引數的多幅影象（SfM的結果）為輸入，重建出真實世界中物體/場景的三維模型。
本文作者提出了PMVS的經典演算法，深入瞭解傳統演算法的實現效果，可以幫助我們與基於深度學習的方法進行對比，對“如何評估多個檢視間相似性”這一問題有更深刻的認識，希望能對相關研究人員有一定的參考幫助。
論文題目：
Accurate， Dense， and Robust Multiview Stereopsis
作者：Scentea|來源微信公眾號：3D視覺工坊
論文地址：
https：//
ieeexplore。ieee。org/doc
ument/5226635
程式碼地址：
https：//
github。com/pmoulon/CMVS
-PMVS
該論文提出的方法可以分解為三個主要的部分：1。 重建出若干可以完整覆蓋目標物體/場景的面片；2。 將面片模型轉換為多邊形漁網模型；3。 最佳化多邊形漁網模型。這裡重點分析文中提出的“匹配-擴張-剔除”策略，這也是PMVS演算法的核心內容。
圖 1 演算法流程演算法效果如下圖所示，從左到右依次為輸入影象（不同角度共48張），特徵點提取，特徵匹配結果，擴張剔除迭代3次後效果，轉換為網狀模型效果。
圖 2 演算法效果總覽
1、基本模型
基本模型中提及的符號含義
1.1、面片模型
先來了解什麼是面片模型 （Patch Model），所謂面片，是指三維物體表面的區域性切平面，可以近似地表示某一區域性範圍內的三維物體表面，與數學中在某一範圍內用切線研究曲線的做法一致，都是“將非線性函式線性化來近似處理”的思想。本質上看，一個面片是三維空間中的一個矩形，由其中心點、單位法向和參考影象三者共同確定，中心點
c
（
p
）是其對角線交點的座標，單位法向
n
（
p
）是從中心點指向參考影象
R
（
p
） 對應的攝影中心的單位向量，這裡之所以要引入參考影象的概念，是因為一個面片會在多幅影象中出現，選定其中的某一影象作為該面片的參考影象，將包含該面片的所有影象組成的集合
V（p）
稱為該面片的可視集。（思考：如何確定一個面片的可視集並從中指定其參考影象？）
圖 3 面片模型
1.2、成像差異函式
接著作者在面片可視集的基礎上引入了成像差異函式 （Photometric Discrepancy Function） 的概念，或者叫灰度差異函式。
圖 4 成像差異函式
1.3、影象模型
基於面片的表面表示方式最大的優勢是其靈活性，但缺少面片與面片之間的連線資訊，這使得尋找鄰近面片，面片規整等操作實現起來較複雜，為此引入影象模型（Image Model），建立起重建出的面片和其可檢視像上投影間的聯絡。具體的講，將每張影象分割為β×β的網格單元
Ci
（
x，y
），在第i張影象的（
x，y
）處儲存一個數組
Qi
（
x，y
），其中包含投影在該網格單元上的所有面片資訊。
圖 5 影象模型
2、初始面片生成
該論文提出的多檢視匹配三維重建方法，可以分為初始面片生成、面片加密、面片剔除三部分，經過初始特徵匹配得到一組稀疏的面片集合，然後透過反覆加密、剔除面片的過程得到最終的結果。每幅影象透過Harris和DoG運算元提取出特徵點後，進入到特徵匹配階段，這是PMVS演算法的核心內容，思路如下：
圖 6 特徵匹配演算法虛擬碼
圖 7 特徵匹配後的效果
3、面片加密
經過上述的特徵匹配後，重建出了一組稀疏的面片，接下來透過已有的面片在周圍空處生成新的面片進行加密，期望達到的效果是每個影象網格單元上都至少包含有一個面片。首先，對於一個面片
p
，明確其周邊可以擴張的網格單元，然後按照某種擴充套件策略進行擴充套件，具體思路如下：
確定可擴張網格單元
存在面片
p
的網格單元
Ci
（
x，y
），根據下式，將其上下左右四個網格單元視作鄰近網格單元，但並非每個鄰近網格單元都是可擴張的網格單元，還需要滿足兩個基本條件。
圖 8 鄰近網格單元
第一個條件：該網格單元中不存在鄰近面片
p’
，鄰近面片的判定條件如下，意思是說兩個面片中心點的距離不能過大，且兩個面片的朝向不能偏差很大。
第二個條件是作者從深度方面考慮的，擴張出的面片
p’
和麵片
p
對應的實際深度不能相差過大，但是實際的深度要在完成三維重建的過程後才能知道，這裡就進入了一個“雞生蛋”的邏輯死迴圈中，該論文中作者在這裡僅做了一個簡單的處理，判斷兩者間的成像差異函式。簡單總結一下，結合下圖，在確定可擴張的網格單元時分為三種情況，沒有面片時（綠色箭頭a）進行擴張；有面片且為鄰近面片時（紅色箭頭b）沒有必要擴張；有面片但非鄰近面片時（橙色c）需要進一步判斷成像差異係數，若小於給定閾值沒必要擴張，大於給定閾值則擴張。
3.2、擴張策略
在明確了哪些網格單元可以擴張後，接下來的問題就是如何根據已有的面片構建出新的面片了，思路如下：
圖 9 擴張策略的虛擬碼
4、面片剔除
在擴張的過程中，為應對那些變化較大、較難重建的區域，調大了成像差異的閾值，但與此同時不可避免地會出現一些冗餘、灰度差異大等低質量的面片，在這一步中進行剔除，“擴張-剔除”的操作需要迭代進行若干次（該論文中統一進行3次），每次剔除分三步進行，每步的側重不同，前兩步從成像一致性/灰度一致性入手，第三步強調面片間的關聯性。第一步剔除掉出現在同一個網格單元中，但並非鄰近面片的粗差情況；第二步透過視差圖測試，剔除掉那些較少影象上能看到的面片；第三步，剔除掉在相鄰網格單元中相鄰面片個數佔總面片數小於1/4的面片。下圖表示了整個演算法過程中面片的個數變化，透過“擴張”後面片個數急劇增加，然後透過三種策略剔除較差的面片，面片數不斷減少，再進行下一次的“擴張-剔除”。
圖 10 不同階段的面片數
圖 11 最終重建出的面片（物體）
圖 12 最終重建出的面片（場景）可以看出，除了重複紋理區域（人的頭髮）、凹陷部分、深度突變區域外，重建的整體效果還是不錯的，這得益於“匹配-擴張-剔除”策略的成功，成像差異函式的提出是立體匹配從雙目走向多檢視的關鍵，可視集
V（p）
在極線約束下利用幾何資訊，更新可視集
V*（p）
進一步考慮灰度資訊，在深度學習出現後，已有論文實現透過學習的方式來評估多個面片間的相似性。
參考文獻：
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。
備註：
作者也是我們
「3D視覺從入門到精通」
特邀嘉賓：
一個超乾貨的3D視覺學習社群
本文僅做學術分享，如有侵權，請聯絡刪文。
3D視覺精品課程推薦：
1。面向自動駕駛領域的多感測器資料融合技術2。面向自動駕駛領域的3D點雲目標檢測全棧學習路線！（單模態+多模態/資料+程式碼）
3。徹底搞透視覺三維重建：原理剖析、程式碼講解、及最佳化改進
4。國內首個面向工業級實戰的點雲處理課程
5。鐳射-視覺-IMU-GPS融合SLAM演算法梳理和程式碼講解
6。徹底搞懂視覺-慣性SLAM：基於VINS-Fusion正式開課啦
7。徹底搞懂基於LOAM框架的3D鐳射SLAM： 原始碼剖析到演算法最佳化
8。徹底剖析室內、室外鐳射SLAM關鍵演算法原理、程式碼和實戰（cartographer+LOAM +LIO-SAM）
9。從零搭建一套結構光3D重建系統［理論+原始碼+實踐］
10。單目深度估計方法：演算法梳理與程式碼實現
更多幹貨
歡迎加入【3D視覺工坊】交流群，方向涉及3D視覺、計算機視覺、深度學習
、vSLAM、鐳射SLAM、立體視覺、自動駕駛、點雲處理、三維重建、多檢視幾何、結構光、多感測器融合、VR/AR、學術交流、求職交流等。工坊致力於乾貨輸出，為3D領域貢獻自己的力量！歡迎大家一起交流成長~
新增小助手微信：CV_LAB，備註學校/公司+姓名+研究方向即可加入工坊一起學習進步。
