1.引言

多視圖立體技術(shù)是一種從已知相機(jī)內(nèi)外參數(shù)的多個視角的彩色影像中，利用立體匹配算法恢復(fù)立體結(jié)構(gòu)的三維視覺技術(shù)。本篇文章將帶來MVS的傳統(tǒng)方法PatchMatch Stereo和源碼實踐。

注1：文末附【三維重建】交流群

注2：計算機(jī)視覺書籍匯總

注3：整理不易，請點贊支持！

作者：視覺企鵝 | 來源：3D視覺工坊微信公眾號

作為立體視覺的經(jīng)典之作，PatchMatchStereo[1](以下簡介為“PMS”)重述了DSI以及視差平面等概念。本文作為這一系列的引論，先拋磚引玉，主要介紹PMS的基本思路和創(chuàng)新點，再帶來李迎松大佬的代碼進(jìn)行代碼供大家參考，快速上手。

PatchMatchStereo主要提出了更早以前的視差估計方法中的兩種做法：

1）以前的視差平面采樣都假設(shè)各個視差平面前向平行(圖1)，并且垂直與深度維度，即以光心為原點，以光軸為法線方向垂直均勻采樣。

圖1 視差平面示意圖

2）視差采樣是整數(shù)值采樣。前向垂直的采樣方式(圖2-a)不能很好地貼合物體平面，圖2-b)則是傾斜視窗地采樣策略，會極大地提升采樣精度。

圖2 視差采樣策略，a) 原始整數(shù)值采樣以及垂直視窗策略 b) 子像素級采樣以及傾斜視窗策略，

以上兩種做法雖然可以得到正確的視差估計結(jié)果，但會導(dǎo)致一下視差估計結(jié)果出現(xiàn)階梯現(xiàn)象(圖3-b)，視差結(jié)果斷續(xù)不接，仿佛是上臺階一樣。

這是因為，首先前向平行窗口模型下視差采樣是整型采樣，無法達(dá)到子像素級的精度，其次，該模型之前需要對立體像對進(jìn)行核線糾正，使得左右立體像對中同名特征點位于平行核線上，這一步一般在攝影測量中會作為圖像預(yù)處理進(jìn)行，而計算機(jī)視覺中并不會做這一步，因此，對于大部分自然影像，前向平行窗口模型（fronto-parallel window model）無法得到令人滿意的結(jié)果。

1. 原圖與視差真值 b) 前向平行窗口模型下視差估計的階梯效果

圖3 早期視差估計方法

2.PatchMatchStereo原理

針對上述問題，PMS算法提出一種新的窗口模型——傾斜支持窗口(圖2-b)，該模型不僅可以估計子像素級的視差（Q點），更重要的是，該模型可以更好地模擬物體傾斜、光滑弧面（R、S點）。

2.1視差平面建模

2.2基于隨機(jī)算法的優(yōu)化搜索算法

如果直接暴力搜索最佳平面以求解式3)，那么是NP問題無法求解。為了保證求解效率以及考慮后期GPU加速的可能性，PMS利用PatchMatch算法進(jìn)行同名窗口快速匹配，以求得視差值。

PatchMatch[2]算法是通過初始化、代價傳播、隨機(jī)搜索等迭代步驟快速找到匹配像素塊。例如，我們需要找到藍(lán)色塊在另一張圖上的匹配塊(圖4-a)，我們就先在另一張圖隨機(jī)采樣，完成初始化。然后我們會檢查藍(lán)色塊的左邊、上邊的紅色塊和綠色塊與藍(lán)色塊的匹配代價，如果匹配代價小于藍(lán)色塊本身的代價，說明匹配塊靠近代價小的像素塊(圖4-b)。這樣經(jīng)過代價傳播，我們大概就知道了一個藍(lán)色匹配塊的搜索區(qū)域(圖4-c)，在這個區(qū)域中隨機(jī)搜索會很快得到最優(yōu)匹配，而且速度很快。

圖4 PatchMatch算法原理

PMS算法利用該思路進(jìn)行視差的空間傳播、視角傳播以及序列傳播等操作，序列傳播主要應(yīng)用于視頻序列的視差估計，所以本文省去而主要介紹空間傳播和視角傳播。

PMS視差傳播的假設(shè)是，在自然立體像對中，一個大鄰域的像素集可以被近似在同一個平面。這么假設(shè)是合理的，比如一個半徑為5-10的像素塊，在像素為千萬級圖像中，往往從屬于同一物體，而那些有灰度劇烈變化的地方，在匹配代價計算過程中，也往往能很快的提取出來。在這樣的假設(shè)下，PMS對每個圖像的每個像素都會隨機(jī)化一個視差平面，并且假設(shè)隨機(jī)化的結(jié)果有少量是正確的，這是合理的隨機(jī)算法的理論假設(shè)，因為雖然搜索范圍很大，但隨機(jī)的初始平面也很多。只要有一個正確的假設(shè)，PatchMatch就能很快迭代到最優(yōu)結(jié)果。具體做法如下：

1）隨機(jī)初始化

這里大家現(xiàn)有一個這樣的概念，具體推到我們以后將結(jié)合DSI細(xì)講。

2）空間傳播

圖5 視差平面?zhèn)鞑ナ疽鈭D

3）視角傳播

視角傳播是一個對左右視差值的強(qiáng)連續(xù)性檢查，這里的假設(shè)是一個立體像對中的同名像點在此像對中擁有一樣的視差值，這是合理的，因為本來左右視差圖就是相對的，所以在立

以上就是PatchMatch中核心的創(chuàng)新點，論文后面的后處理我們不再展開，對后處理有興趣的同學(xué)可以詳細(xì)閱讀此篇文章。

3.源代碼實踐

接下來引用的是武漢大學(xué)博士李迎松的源碼進(jìn)行代碼實踐，他開源了Windows版本的代碼，可以在VS studio中直接使用。而照顧到部分讀者和筆者自身常使用Linux系統(tǒng)，故將其改成了Linux版本的，還添加了CMakeLists.txt文件，僅供大家參考，如何使用已經(jīng)在網(wǎng)頁中詳細(xì)說明。這里OpenCV并沒有具體的要求，建議安裝3.1以上3.5以下版本。

Windows和Linux版本開源代碼地址：在公眾號「3D視覺工坊」，后臺回復(fù)「PMS」，即可直接下載。

代碼實踐效果是：

圖6 視差估計結(jié)果(以左圖為參考)

4.總結(jié)

本篇文章主要講解了PatchMatchStereo的基本流程，希望大家針對此篇講解對PatchMatchStereo做一個簡單的認(rèn)識，之后就傳播算法進(jìn)行展開，最后是源碼實踐。下篇文章將會就DSI這一重要概念進(jìn)行講解，再次感謝李迎松博士開源的代碼！

參考文獻(xiàn)

[1] Bleyer M , Rhemann C , Rother C . PatchMatch Stereo - Stereo Matching with Slanted Support Windows[C]// British Machine Vision Conference 2011. 2011.

[2] Barnes, C,Finkelstein, A,Shechtman, E, et al.PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing[J].ACM Transactions on Graphics,2009,28(3):24:1-24:11.

備注：作者也是我們「3D視覺從入門到精通」知識星球特邀嘉賓：

本文僅做學(xué)術(shù)分享，如有侵權(quán)，請聯(lián)系刪文。

3D視覺工坊-三維重建交流群

已建立3D視覺工坊-三維重建微信交流群！想要進(jìn)三維重建學(xué)習(xí)交流群的同學(xué)，可以直接加微信號：CV_LAB。加的時候備注一下：三維重建+學(xué)校+昵稱，即可。然后就可以拉你進(jìn)群了。

強(qiáng)烈推薦大家關(guān)注3D視覺工坊知乎賬號和3D視覺工坊微信公眾號，可以快速了解到最新優(yōu)質(zhì)的3D視覺與SLAM論文。