雙約束條件下PMVS的改進(jìn)算法

楊文博，孫博文

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

雙約束條件下PMVS的改進(jìn)算法

楊文博，孫博文+

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

PMVS（patch-based multi-view stereo）算法以其良好的表現(xiàn)，在多視立體領(lǐng)域得到廣泛應(yīng)用。然而，算法存在重建模型細(xì)節(jié)丟失與重建點(diǎn)位置不夠精確的問(wèn)題，這種情況在輸入圖片較少，重建場(chǎng)景紋理不明顯時(shí)尤為嚴(yán)重。針對(duì)這些不足，對(duì)去除候選誤匹配點(diǎn)及對(duì)種子點(diǎn)置信度的排序進(jìn)行了研究：引入U(xiǎn)SAC（Universal-RANSAC）去除候選誤匹配點(diǎn)方法；提出雙約束條件策略，篩選出候選空間點(diǎn)中置信度較高的點(diǎn)作為種子點(diǎn)。重建模型細(xì)節(jié)與原物體的契合度有了很大提高，紋理較少模型的重建點(diǎn)云數(shù)明顯增加，漏洞也明顯減少。通過(guò)在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證了改進(jìn)算法具有更強(qiáng)的有效性和實(shí)用性。

PMVS算法；Universal-RANSAC；雙約束條件；多視立體重建

1 引言

作為計(jì)算機(jī)視覺(jué)的研究熱門，三維重建技術(shù)不管是從理論方面還是從實(shí)踐方面都日臻成熟。理論上，SFM（structure from motion）技術(shù)[1-2]中Bundler算法[3]的提出及完善[4]進(jìn)一步促進(jìn)了三維重建技術(shù)的發(fā)展。實(shí)踐中，三維重建技術(shù)在諸如醫(yī)療、測(cè)量、文化遺產(chǎn)保護(hù)、3D電影娛樂(lè)、軍事以及虛擬現(xiàn)實(shí)等領(lǐng)域的廣泛應(yīng)用，使得更多的研發(fā)人員加入到開(kāi)發(fā)使用三維重建技術(shù)[5]的行列。傳統(tǒng)的三維重建技術(shù)由于其自動(dòng)化程度較低，并且開(kāi)發(fā)周期較長(zhǎng)，設(shè)備昂貴及只適用于室內(nèi)場(chǎng)景等缺陷，應(yīng)用受到了很大限制。多視立體重建技術(shù)則克服了以上缺點(diǎn)，得到了廣泛研究[6-7]。

把輸出場(chǎng)景再現(xiàn)作為基準(zhǔn)來(lái)對(duì)多視立體算法進(jìn)行分類，目前最為流行的多視立體算法分為如下4類：

（1）基于點(diǎn)云的方法[8-9]；

（2）基于深度圖的方法[10-11]；

（3）基于體積標(biāo)量場(chǎng)的方法[12-13]；

（4）基于網(wǎng)格的方法[14-15]。

在上述4類方法中，后3種方法都需要一些初始信息，如對(duì)視差范圍、表面進(jìn)行初始化等。這一要求極大地限制了它們?cè)谥亟◤?fù)雜大場(chǎng)景中的應(yīng)用，而是僅僅適用于重建單個(gè)物體，因?yàn)樵趶?fù)雜大場(chǎng)景情況下，幾乎是無(wú)法正確估計(jì)所需的初始信息的。與這3種方法有所差異，前者不會(huì)用到任何初始化信息。該方法是由Furukawa等人提出的PMVS（patchbased multi-view stereo）算法，不管是在重建精度還是在重建完整性上都具有非常好的表現(xiàn)，該算法是這類算法的代表，同時(shí)也代表了當(dāng)前多視重建所達(dá)到的水平。該算法在很多場(chǎng)景重建特別是室外大場(chǎng)景重建中都有很好的重建效果[16-17]。盡管這樣，在實(shí)際的應(yīng)用中，會(huì)發(fā)現(xiàn)該算法仍然有需要改進(jìn)的地方。本文針對(duì)原始PMVS算法的不足提出了一些改進(jìn)方法。

2 PMVS算法及其改進(jìn)

PMVS算法是一種對(duì)物體從多個(gè)角度拍攝所形成的多張圖像進(jìn)行匹配，然后依據(jù)一定幾何約束條件重建三維點(diǎn)云的算法。其核心思想可以理解為以下幾步：首先將每幅圖像中的特征點(diǎn)用Harris+DoG算子提取出來(lái)，并對(duì)特征點(diǎn)對(duì)進(jìn)行匹配，在滿足極線幾何約束的條件下，采用三角化方法生成以三維空間點(diǎn)為中心的矩形面片，該面片被稱為以法向量為具體方向的種子面片；然后以相鄰點(diǎn)云片的兩個(gè)相似特性為條件（法向量和空間點(diǎn)位置），一步步將種子點(diǎn)云片的鄰近相似點(diǎn)云片擴(kuò)散并重建出來(lái)；最后，擴(kuò)散結(jié)束后需要進(jìn)行過(guò)濾處理操作，將不滿足一致性的錯(cuò)誤面片剔除。其中PMVS在擴(kuò)散和過(guò)濾階段需要迭代運(yùn)行n次，n一般取值為3。通過(guò)這種方式，算法可以魯棒性地?cái)U(kuò)散出稠密的三維空間面片。

2.1 基本定義

按照文獻(xiàn)[7]，基本定義如下：

定義1（面片模型）面片（又稱點(diǎn)云片）p是一個(gè)小平面矩形，該平面與所重建物體表面近似相切。每個(gè)面片p對(duì)應(yīng)一個(gè)參考圖像R(p)，R(p)對(duì)p保持可見(jiàn)。

c(p)為面片p的中心；n(p)為面片p的單位法線；R(p)為面片p的參考圖像；V(p)為面片p的準(zhǔn)可見(jiàn)圖像集（所有包含面片p的圖像集合，圖像集中包含那些面片p應(yīng)該被看到但是由于運(yùn)動(dòng)模糊、遮擋、高光等而不被看到的圖像）；V*(p)為圖像集中面片p都能被看到的圖像集。其中：

式（1）中O(Ii)為參考圖像光心，不等式左邊表示面片p的單位法向量與經(jīng)過(guò)p中心與O(Ii)形成向量的單位向量的點(diǎn)積，τ=π/3。

定義2（圖像模型）將圖像集合Ii中的每一幅圖像都劃分成大小為β×β像素的圖像小塊Ci(x,y（)實(shí)驗(yàn)中β取值為2）。這里x、y是圖像塊的下標(biāo)，i表示的是第i張圖像。Qi(x,y)是用于記錄投射到V(p)中每個(gè)圖像塊Ci(x,y)的所有點(diǎn)云片的集合。

C(p)為點(diǎn)云片p在V(p)中的毗鄰塊形成的集合。

定義3（灰度一致性函數(shù)）對(duì)于一個(gè)點(diǎn)云片p，在其集合V*(p)上的灰度一致性函數(shù)g*(p)被定義為：

式（5）中，h(p,I,R(p))為R(p)和圖像I之間的灰度一致性度量函數(shù)。

2.2 重建流程

（1）特征點(diǎn)的提取、匹配以及種子面片的生成。首先使用Harris和DoG算子對(duì)圖像集合中的全部相關(guān)特征點(diǎn)進(jìn)行提取，對(duì)于每一幅圖像Ii中的每一個(gè)特征點(diǎn)，在圖像集的其余圖像中分別找到該特征點(diǎn)與R(p)光心O(Ii)所形成直線在每幅圖像中的投射直線，專業(yè)上稱這條線為極線。將極線周圍兩個(gè)像素誤差內(nèi)的所有特征點(diǎn)作為該特征點(diǎn)的潛在匹配點(diǎn)進(jìn)行匹配，從而形成該特征點(diǎn)的匹配點(diǎn)對(duì)，然后再采用三角化方法將這些匹配點(diǎn)對(duì)形成三維空間點(diǎn)，最后根據(jù)這些三維空間點(diǎn)到該特征點(diǎn)所對(duì)應(yīng)的參考圖像光心O(Ii)的距離從小到大進(jìn)行排序，依照這樣的順序，對(duì)該距離所對(duì)應(yīng)的三維空間點(diǎn)依次嘗試生成面片p，直到生成面片成功為止。其中面片的中心c(p)為能夠成功生成面片的三維空間點(diǎn)，而該有向面片的單位法向量n(p)為c(p)指向參考圖像光心O(Ii)的單位法向量。通過(guò)式（1）、（2）來(lái)確定面片的準(zhǔn)可視圖像集V(p)和可視圖像集V*(p)。然后對(duì)c(p)和n(p)進(jìn)行優(yōu)化，優(yōu)化過(guò)程是通過(guò)最小化式（5）來(lái)完成的。優(yōu)化完成后再次利用式（1）、（2）對(duì)V(p)和V*(p)進(jìn)行更新，其中τ的值保持不變，由于優(yōu)化前后面片的灰度一致性度量值會(huì)顯著提高，從而α的值變?yōu)?.3。最后，如果優(yōu)化后的可視圖像集V*(p)滿足大于等于γ（取值為3）的條件，則表示重建成功，此時(shí)將所創(chuàng)建的面片p存儲(chǔ)到V(p)和V*(p)對(duì)應(yīng)的圖像塊中，同時(shí)對(duì)集合Qi(x,y)和進(jìn)行更新。

（2）對(duì)初始種子面片進(jìn)行擴(kuò)散。對(duì)點(diǎn)云片進(jìn)行擴(kuò)散這一環(huán)節(jié)是以盡量使得Ci(x,y)中的點(diǎn)云數(shù)不小于1為目標(biāo)的。首先使用式（3）確定面片p所對(duì)應(yīng)的鄰域圖像塊集C(p)，從該圖像塊集合中選出滿足一定約束條件的圖像塊Ci(x′,y′)，對(duì)其嘗試擴(kuò)散出一個(gè)新的面片p′，這里將面片p所在平面與穿過(guò)Ci(x,y)中心的可視光線所形成的交點(diǎn)作為面片p′的初始中心值，即c(p′)。將面片p的n(p)、V(p)、R(p)作為p′的初始值分別賦值給n(p′)、V(p′)、R(p′)，用式（2）對(duì)可視圖像集V*(p)進(jìn)行初始化。然后再對(duì)c(p′)和n(p′)進(jìn)行優(yōu)化，優(yōu)化之后，根據(jù)深度測(cè)試條件來(lái)判斷面片p′對(duì)應(yīng)的準(zhǔn)可視圖像，將準(zhǔn)可視圖像加入到V(p′)中，并利用式（3）再次對(duì)V*(p′)進(jìn)行更新。最后，如果V*(p′)滿足條件V*(p′)≥γ，則新擴(kuò)散出的面片是可接受的。

（3）過(guò)濾。整個(gè)過(guò)濾過(guò)程是通過(guò)3個(gè)過(guò)濾器來(lái)實(shí)現(xiàn)的，前兩個(gè)過(guò)濾器是利用可視一致性約束條件來(lái)剔除重建表面的內(nèi)點(diǎn)和外點(diǎn)。而第三個(gè)過(guò)濾器則是通過(guò)強(qiáng)加一個(gè)較弱的規(guī)則實(shí)現(xiàn)的。整個(gè)算法流程如圖1所示。

Fig.1 Flowchart of PMVS algorithm圖1PMVS算法流程

2.3 存在問(wèn)題

PMVS算法存在以下問(wèn)題：

（1）在重建種子面片的過(guò)程時(shí)，該算法存在相對(duì)較大的匹配誤差及選取候選三維空間點(diǎn)誤差，而誤差的累積使得重建出點(diǎn)云空間位置不夠精確，累積達(dá)到一定程度，甚至?xí)霈F(xiàn)錯(cuò)誤點(diǎn)。這樣，在稠密匹配階段，如果得到的種子點(diǎn)不夠準(zhǔn)確，就會(huì)產(chǎn)生大量不準(zhǔn)確的重建點(diǎn)。這對(duì)于輸入圖像較少，提取特征點(diǎn)不多的情況，以及所重建物體表面紋理較少的情況來(lái)說(shuō)，其影響是巨大且不可忽略的。因此，減少重建過(guò)程中的各種誤差，謹(jǐn)防誤差過(guò)度積累，是重建結(jié)果進(jìn)行優(yōu)化的一個(gè)重要方面。

（2）原算法通過(guò)匹配點(diǎn)生成三維空間點(diǎn)后，會(huì)將這些點(diǎn)按照距離從小到大進(jìn)行排序，然后依次嘗試生成面片，直到成功，該方法存在一定的盲目性。

2.4 PMVS算法的改進(jìn)

本文改進(jìn)后的算法流程如圖2所示。

Fig.2 Flowchart of the proposed algorithm圖2 本文算法運(yùn)行流程圖

對(duì)于第一個(gè)問(wèn)題，本文在特征點(diǎn)檢測(cè)后使用NCC（normalized cross correlation）算法[18]對(duì)其進(jìn)行粗匹配，之后，誤匹配的消除是通過(guò)使用Universal-RANSAC[19]（該算法解決了經(jīng)典RANSAC算法在效率、精度、退化三方面上的局限性，幾乎所有比較前沿的RANSAC改進(jìn)算法都是它的一個(gè)特例，簡(jiǎn)稱USAC）來(lái)實(shí)現(xiàn)的，從而一些魯棒性較差的點(diǎn)被消除，有效地減少擴(kuò)散階段誤匹配的累積，同時(shí)該階段運(yùn)行的時(shí)間也有減少，區(qū)域的搜索范圍也有縮小，整個(gè)系統(tǒng)的計(jì)算速度也有所增加。而減少候選三維空間點(diǎn)的誤差，在問(wèn)題（2）的解決方案中得到了很好的解答。

對(duì)于問(wèn)題（2），本文提出雙約束條件來(lái)對(duì)三維空間點(diǎn)進(jìn)行選取，從而提高創(chuàng)建種子點(diǎn)的運(yùn)行速度及所創(chuàng)建種子點(diǎn)的置信度。其中，雙約束條件即去最值取平均策略和點(diǎn)的置信度策略。

（1）去最值求平均策略

用匹配點(diǎn)對(duì)使用三角化方法生成一系列三維空間點(diǎn)，然后將這些點(diǎn)按照距離O(Ii)從小到大進(jìn)行排序，假設(shè)有n個(gè)這樣的三維點(diǎn)。首先根據(jù)n值的大小來(lái)設(shè)定一個(gè)合適的閾值，該閾值的作用有兩個(gè)，判斷是否對(duì)最值點(diǎn)進(jìn)行去除以及去除兩端最值的百分比，從而解決了問(wèn)題（1）中所說(shuō)的減少選取候選三維空間點(diǎn)誤差問(wèn)題，然后求得剩余距離總和的均值d。優(yōu)先選取距離均值d最近的距離，并以其對(duì)應(yīng)的三維空間點(diǎn)為中心，開(kāi)始嘗試重建面片。

本策略依據(jù)的是正態(tài)分布原理。為了驗(yàn)證此依據(jù)的正確性，本文將由匹配點(diǎn)對(duì)集合（極線幾何一致性約束條件）生成的一系列三維空間點(diǎn)作為輸入數(shù)據(jù)，分別對(duì)這些點(diǎn)在x、y、z坐標(biāo)軸上進(jìn)行正態(tài)分布測(cè)試，其測(cè)試結(jié)果如圖3（a）所示。根據(jù)直方圖所繪制的曲線看起來(lái)很像正態(tài)分布曲線，其中高概率點(diǎn)基本都位于曲線對(duì)稱軸左右。為了進(jìn)一步證明這些點(diǎn)數(shù)據(jù)符合正態(tài)分布，本文通過(guò)正態(tài)Q-Q圖進(jìn)行檢驗(yàn)。如圖3（b）所示，可以看出各點(diǎn)近似圍繞著直線，說(shuō)明數(shù)據(jù)呈近似正態(tài)分布。

（2）點(diǎn)的置信度策略

利用上述算法對(duì)待匹配特征點(diǎn)和候選匹配點(diǎn)進(jìn)行匹配時(shí)，每一對(duì)匹配點(diǎn)對(duì)都會(huì)得到相應(yīng)的相似度匹配分?jǐn)?shù)，創(chuàng)建種子云面片時(shí)，選擇滿足一定條件的最高分，這里將該匹配點(diǎn)對(duì)所獲得的三維空間點(diǎn)附加一個(gè)閾值限制條件。本文定義該限制條件為，當(dāng)前云面片距離不小于雙約束條件（1）中所計(jì)算平均距離時(shí)，其云面片距離與平均距離之比小于等于1.3（閾值）；當(dāng)前云面片距離不大于雙約束條件（1）中所計(jì)算平均距離時(shí)，云面片距離與平均距離之比大于等于0.7（閾值）；從而提高點(diǎn)的置信度。

綜合本文提出的兩種策略作為約束條件，實(shí)現(xiàn)對(duì)三維空間點(diǎn)的選取。

2.5 原算法以及改進(jìn)算法參數(shù)尋優(yōu)策略

通過(guò)2.3節(jié)可知，原PMVS算法依次嘗試生成面片的過(guò)程具有一定的盲目性。假設(shè)能夠成功生成的空間點(diǎn)位于距離比較大的位置，那么比該距離小的所有空間點(diǎn)都得依次嘗試生成面片，并都會(huì)以失敗告終，這些操作是耗時(shí)并且沒(méi)有必要的。即使距離光心距離較小的點(diǎn)能夠成功創(chuàng)建面片，也不一定是在最優(yōu)的三維空間點(diǎn)位置創(chuàng)建的。再者，如果生成的面片點(diǎn)恰好是誤匹配點(diǎn)或者置信度不太高的匹配點(diǎn)生成的，就會(huì)產(chǎn)生錯(cuò)誤的種子點(diǎn)或者置信度不高的種子點(diǎn)。這一點(diǎn)不處理好的話，擴(kuò)散階段，誤差的累積就會(huì)產(chǎn)生錯(cuò)誤的或不準(zhǔn)確的面片，使得重建模型細(xì)節(jié)不能夠很好地重建出來(lái)，增加了區(qū)域增長(zhǎng)的運(yùn)行時(shí)間，同時(shí)也占用了不少的內(nèi)存資源。

Fig.3 Detection of normal distribution圖3 正態(tài)分布檢測(cè)

通過(guò)2.4節(jié)可知，改進(jìn)算法在通過(guò)匹配點(diǎn)生成三維空間點(diǎn)后，同樣會(huì)將這些點(diǎn)按照距離從小到大進(jìn)行排序，但并非像原算法那樣從小到大依次嘗試生成面片，而是通過(guò)本文提出的雙約束條件策略對(duì)這些有序點(diǎn)進(jìn)行選取，選取那些能夠成功生成面片概率較大并且置信度較高的點(diǎn)，將平均值點(diǎn)及其左右周圍點(diǎn)依次插入數(shù)組中，然后從數(shù)組中選取點(diǎn)嘗試生成面片，直到成功。

2.6 原算法以及改進(jìn)算法時(shí)間復(fù)雜度分析

本文是對(duì)初始面片的生成階段進(jìn)行研究，該階段原算法偽代碼詳細(xì)步驟歸納如下。

本文在選取特征點(diǎn)集合F時(shí)利用USAC算法去除誤匹配點(diǎn)，并使用雙約束條件將集合F中置信度較高的點(diǎn)插入到集合F的前端，然后進(jìn)入算法第三步。改進(jìn)算法偽代碼如下。

其中，算法步驟2.3為根據(jù)創(chuàng)建點(diǎn)時(shí)的分?jǐn)?shù)以及該點(diǎn)的距離兩條件設(shè)置閾值，將不符合條件點(diǎn)進(jìn)行剔除，進(jìn)一步提高點(diǎn)置信度。算法步驟3之后操作與原算法相同，這里省略。

算法時(shí)間復(fù)雜度分析：假設(shè)總共有m張圖片，每張圖片被分為p×q大小的網(wǎng)格，并假設(shè)網(wǎng)格中只有一個(gè)特征點(diǎn)，而利用極線幾何約束條件找到該特征點(diǎn)在其他圖像中的匹配點(diǎn)數(shù)總和為n,即集合F中點(diǎn)的個(gè)數(shù)，這里n為原算法步驟3的規(guī)模。設(shè)步驟3中代碼的實(shí)際運(yùn)行次數(shù)是s。為了方便計(jì)算，這里忽略原算法步驟3中的刪除p對(duì)應(yīng)圖像塊中的所有特征點(diǎn)這一操作，則原算法的時(shí)間復(fù)雜度為O(m×p×q×s)。由于原算法選取點(diǎn)的盲目性，使得s的值趨近于n/2。即實(shí)際時(shí)間復(fù)雜度為O(m×p×q×n/2)，本文通過(guò)對(duì)置信度較高的點(diǎn)進(jìn)行選取，從而使得s的范圍基本在1～3之間，由此本文在該階段時(shí)間復(fù)雜度為O(m×p×q)?？梢钥闯?，當(dāng)n的規(guī)模不大時(shí)，本文算法與原算法在時(shí)間上基本無(wú)差別，但重建精度及重建面片數(shù)卻有很大提高；當(dāng)n的規(guī)模較大時(shí)，本文算法在時(shí)間以及重建結(jié)果上就可以很好地表現(xiàn)出來(lái)，這一點(diǎn)在本文實(shí)驗(yàn)中的Buddha數(shù)據(jù)集上得到了驗(yàn)證。

此外，由于本文改進(jìn)算法在初始面片選取階段選取了置信度較高的種子點(diǎn)，而擴(kuò)散階段，面片是以這些種子點(diǎn)為基準(zhǔn)進(jìn)行擴(kuò)散的，從而使得擴(kuò)散出的點(diǎn)置信度也較高。迭代該過(guò)程3次使得最終面片的精度以及重建面片的數(shù)量都得到了提高。

3 實(shí)驗(yàn)

本文利用提出的改進(jìn)算法與其PMVS原算法進(jìn)行三維重建結(jié)果的對(duì)比，并用7組數(shù)據(jù)對(duì)其進(jìn)行分析和驗(yàn)證。這里所采用的數(shù)據(jù)都是公共數(shù)據(jù)集，實(shí)驗(yàn)環(huán)境為Intel?CoreTMi7-4790K，8 GB內(nèi)存，處理器主頻為4.0 GHz，在Windows7 64操作系統(tǒng)下，利用VS2010對(duì)所有算法進(jìn)行了實(shí)現(xiàn)。

文中使用 PER（patch enhancement rate）和 ERR（error reduction rate）來(lái)分別表示面片提高率及面片錯(cuò)誤降低率，并使用NORP（number of reconstructed patches）、NOPAR（number of patches after remove）及ROP（rate of patch）來(lái)分別代替重建面片數(shù)、去雜點(diǎn)后面片數(shù)、面片錯(cuò)誤率。文中對(duì)面片提高率、錯(cuò)誤降低率以及面片錯(cuò)誤率的定義如下：設(shè)改進(jìn)算法去除雜點(diǎn)后面片數(shù)、原算法去除雜點(diǎn)后面片數(shù)、原算法面片錯(cuò)誤率、改進(jìn)算法面片錯(cuò)誤率分別為M、N、X、Y。

本文的實(shí)驗(yàn)數(shù)據(jù)集包括Kermit、ET、Dino、Temple、Buddha、清華生命科學(xué)樓（下文使用QHB來(lái)代替）、教堂。算法對(duì)各個(gè)數(shù)據(jù)集的重建效果如圖4～圖10所示，實(shí)驗(yàn)中所涉及的各參數(shù)與原算法保持一致，數(shù)據(jù)集中所有圖像用Bundler獲得攝像機(jī)參數(shù)。

如圖4（a）所示，Kermit[20]模型紋理比較清晰，輸入11張圖片就能很好地完成模型的創(chuàng)建。PMVS算法和改進(jìn)算法重建的效果都比較好，但是PMVS算法在頭部和身體等某些細(xì)節(jié)部分的體現(xiàn)并不是很理想，如圖4（b）紅色橢圓標(biāo)記區(qū)域。從整體模型的重建完整度得知，本文改進(jìn)算法漏洞很少，頭部、身體等部位的重建完整性更好，如圖4（c）紅色橢圓標(biāo)記區(qū)域。原算法重建點(diǎn)云面片數(shù)為9 944，本文算法則為12 624。

如圖5（a）所示，該Dino模型比較光滑，紋理相對(duì)較少，每幅圖片獲得的特征點(diǎn)較少，需要輸入幾十張照片才能創(chuàng)建出效果較好的模型，如圖5（b）所示。PMVS算法對(duì)該數(shù)據(jù)集的重建效果并不是很理想，很多細(xì)節(jié)部位都存在較大漏洞，算法創(chuàng)建的面片數(shù)也只有8 370，時(shí)間為11 s。相比之下，如圖5（c）所示，改進(jìn)后的模型效果則好很多，重建的面片數(shù)為11 267，時(shí)間也減少為8 s。

圖5～圖7是文獻(xiàn)[21-22]中的Dino、Temple以及ET。從數(shù)據(jù)集在PMVS算法和本文改進(jìn)算法的基礎(chǔ)上的應(yīng)用結(jié)果得知，本文算法相對(duì)于PMVS原算法來(lái)說(shuō)都有很大的提高。

Fig.4 Results of reconstructed Kermit by PMVS and improved algorithm圖4 PMVS和改進(jìn)后PMVS重建Kermit的結(jié)果

Fig.5 Results of reconstructed Dino by PMVS and improved algorithm圖5 PMVS和改進(jìn)后PMVS重建Dino的結(jié)果

圖8是Autodesk 123D Catch中的實(shí)例圖片，圖9的數(shù)據(jù)集來(lái)源于中國(guó)科學(xué)院自動(dòng)化研究所模式識(shí)別國(guó)家重點(diǎn)實(shí)驗(yàn)室（http://vision.ia.ac.cn/data），圖10的數(shù)據(jù)集來(lái)源于網(wǎng)站下載（http://www.robots.ox.ac.uk/～vgg/data/data-mview.html）。原算法和本文改進(jìn)算法都對(duì)模型有了很好的重建，但PMVS算法對(duì)某些細(xì)節(jié)有些丟失，如圖8（b）、圖9（b）、圖10（b）所示。改進(jìn)后的重建效果則彌補(bǔ)了這一不足，如圖8（c）、圖9（c）、圖10（c）所示。圖8中PMVS算法重建點(diǎn)云數(shù)（面片數(shù)）為278 209，本文改進(jìn)算法則為288 986。生成面片的提高率達(dá)到8.04%，生成面片錯(cuò)誤降低率更是達(dá)到了4.21%，重建的時(shí)間也從原算法的328 s變?yōu)楝F(xiàn)在的284 s。圖9中原算法重建點(diǎn)云面片數(shù)為70 707，本文算法則為76 558。面片的提高率為8.275%，生成面片的錯(cuò)誤降低率為2.663%。圖10中PMVS算法重建點(diǎn)云面片數(shù)為7 042，本文改進(jìn)算法則為9 081，面片的提高率為28.950%，生成面片的錯(cuò)誤降低率為4.562%。兩算法相較而言，本文算法生成面片的提高率及錯(cuò)誤的降低率都有了很大的提升。

Fig.6 Results of reconstructed Temple by PMVS and improved algorithm圖6 PMVS和改進(jìn)后PMVS重建Temple的結(jié)果

Fig.7 Results of reconstructed ET by PMVS and improved algorithm圖7 PMVS和改進(jìn)后PMVS重建ET的結(jié)果

Fig.8 Results of reconstructed Buddha by PMVS and improved algorithm圖8 PMVS和改進(jìn)后PMVS重建Buddha的結(jié)果

表1為PMVS算法與本文算法在給定實(shí)驗(yàn)數(shù)據(jù)集上得到的面片數(shù)以及運(yùn)行時(shí)間的對(duì)比。從表中可以看出，除了第四組數(shù)據(jù)，本文算法在其他數(shù)據(jù)集上得到的點(diǎn)云數(shù)據(jù)相比于PMVS算法都有很大提高，這種提高在輸入圖片較少并且圖像紋理較弱的數(shù)據(jù)集上表現(xiàn)尤為明顯。在運(yùn)行時(shí)間基本相同，甚至減少的情況下，Kermit、Dino、Church重建面片數(shù)分別從原算法的9 944、8 370、7 042變?yōu)楸疚乃惴ǖ?2 624、11 267、9 081，面片數(shù)增加幅度顯著。針對(duì)于第四組數(shù)據(jù)，本文在下面會(huì)給予解釋。這里，表中的面片數(shù)是去除雜點(diǎn)后的面片數(shù)。

Fig.9 Results of reconstructed Tsinghua by PMVS and improved algorithm圖9 PMVS和改進(jìn)后PMVS重建清華生命科學(xué)樓的結(jié)果

Fig.10 Results of reconstructed church by PMVS and improved algorithm圖10 PMVS和改進(jìn)后PMVS重建教堂的結(jié)果

Table 1 Comparison of PMVS and improved algorithm for reconstruction of facet number and running time表1 原算法與改進(jìn)算法重建面片數(shù)及時(shí)間對(duì)比分析結(jié)果

表2、表3為各個(gè)實(shí)驗(yàn)數(shù)據(jù)集合上，PMVS算法和本文算法產(chǎn)生的面片錯(cuò)誤率。表中第三行是所計(jì)算的面片錯(cuò)誤率。從表中得知PMVS原算法的重建面片錯(cuò)誤率都高于本文算法。其中，Kermit、Buddha、Church重建面片的錯(cuò)誤率分別從4.595%、12.258%、8.020%降低為0.001%、8.041%、3.460%，降低幅度顯著，特別是在輸入圖像較少，模型表面紋理少的Dino數(shù)據(jù)集上，錯(cuò)誤率從12.438%降為5.533%。

Table 2 PMVS algorithm for reconstructing error rate of point cloud表2 PMVS算法重建點(diǎn)云錯(cuò)誤率

Table 3 Improved algorithm for reconstructing error rate of point cloud表3 改進(jìn)算法重建點(diǎn)云錯(cuò)誤率

表4為本文算法與PMVS算法在實(shí)驗(yàn)數(shù)據(jù)集合上，對(duì)面片提高率、錯(cuò)誤降低率進(jìn)行的比較結(jié)果。從表中可以得知，各組數(shù)據(jù)面片的提高率以及面片的錯(cuò)誤降低率都有了很大的提高。最為顯著的莫過(guò)于紋理較少的Dino數(shù)據(jù)集，面片提高率高達(dá)34.612%，錯(cuò)誤降低率也高達(dá)6.905%，很好地解決了原算法在圖像紋理較少時(shí)，面片重建精度不高的問(wèn)題。表1中數(shù)據(jù)之所以會(huì)不同，是因?yàn)檩斎雸D片數(shù)量較少，重建正確面片數(shù)相差不多且數(shù)據(jù)量不大的情況下，正確率就顯得極為重要，這一點(diǎn)可以從圖7重建的結(jié)果對(duì)比中清晰地表達(dá)出來(lái)。

Table 4 Patch enhancement rate and error reduction rate of improved algorithm表4 改進(jìn)算法的面片提高率及面片錯(cuò)誤降低率 %

國(guó)內(nèi)對(duì)PMVS算法的研究有很多，但大多都是從特征點(diǎn)的檢測(cè)與提取階段入手，使用其他特征匹配算法來(lái)代替該階段的匹配算法，還有一些從擴(kuò)散階段面片的方向優(yōu)化入手等，其結(jié)果也是差強(qiáng)人意。史穎等人[6]與本文一樣也是對(duì)種子點(diǎn)置信度的排序進(jìn)行研究，提出了MFPMVS（patch with multiple features based multi-view stereopsis）算法，并且取得了很好的重建效果。這里，將本文改進(jìn)算法與之進(jìn)行對(duì)比，其結(jié)果如表5所示。表中的面片數(shù)與表1中的數(shù)據(jù)不同，是因?yàn)檫@里需要與MFPMVS算法保持同步，即使用的是去除雜點(diǎn)前的數(shù)據(jù)。從表中可知本文算法與MFPMVS算法重建面片數(shù)基本相同，而MFPMVS算法是在犧牲時(shí)間效率的前提下進(jìn)行的，但本文改進(jìn)算法在達(dá)到重建結(jié)果基本相同的條件下，同時(shí)也降低了時(shí)間復(fù)雜度。

Table 5 Comparison of improved algorithm and MFPMVS for reconstruction of facet number表5 本文改進(jìn)算法與MFPMVS算法重建面片數(shù)對(duì)比分析結(jié)果

4 結(jié)束語(yǔ)

本文在PMVS算法的基礎(chǔ)上，針對(duì)其細(xì)節(jié)重建效果不佳，創(chuàng)建稠密點(diǎn)云錯(cuò)誤點(diǎn)較多，對(duì)紋理不太明顯物體重建效果極差等缺點(diǎn)進(jìn)行了改進(jìn)。所測(cè)數(shù)據(jù)，生成稠密點(diǎn)云中點(diǎn)云的錯(cuò)誤降低率提高了0.040%～6.905%，使得點(diǎn)云擴(kuò)建細(xì)節(jié)問(wèn)題得到了很好的解決。點(diǎn)云的面片提高率為3.873%～34.612%，使得紋理不太明顯物體重建出點(diǎn)云片較少問(wèn)題得到了很好的解決。可以得知，本文算法具有更強(qiáng)的穩(wěn)定性和實(shí)用性。

[1]Wu Changchang.Towards linear-time incremental structure from motion[C]//Proceedings of the 2013 International Conference on 3D Vision,Seattle,Washington,USA,Jun 29-Jul 1,2013.Washington:IEEE Computer Society,2013:127-134.

[2]Zheng E,Wu Changchang.Structure from motion using structure-less resection[C]//Proceedings of the 2015 International Conference on Computer Vision,Santiago,Chile,Dec 7-13,2015.Washington:IEEE Computer Society,2015:2075-2083.

[3]Triggs B,McLauchlan P F,Hartley R I,et al.Bundle adjustment—a modern synthesis[C]//LNCS 1883:Proceedings of the 1999 International Workshop on Vision Algorithms:Theory and Practice,Corfu,Greece,Sep 21-22,1999.Berlin,Heidelberg:Springer,1999:298-372.

[4]Wu Changchang,Agarwal S,Curless B,et al.Multicore bundle adjustment[C]//Proceedings of the 24th Conference on Computer Vision and Pattern Recognition,Colorado Springs,USA,Jun 20-25,2011.Washington:IEEE Computer Society,2011:3057-3064.

[5]Vazquez-Duchêne M D,Freis O,Denis A,et al.Virtual reality for skin exploration[C]//Proceedings of the 2013 Virtual Reality International Conference,Laval,France,Mar 20-23,2013.New York:ACM,2013:5.

[6]Shi Ying,Wang Wenjian,Bai Xuefei.3D dense reconstruction method based on multiple features[J].Journal of Frontiers of Computer Science and Technology,2015,9(5):594-603.

[7]Shi Limin,Guo Fusheng,Hu Zhanyi.An improved PMVS through scene geometric information[J].Acta Automatica Sinica,2011,37(5):560-568.

[8]Furukawa Y,Curless B,Seitz S M,et al.Towards internetscale multi-view stereo[C]//Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition,San Francisco,USA,Jun 13-18,2010.Washington:IEEE Computer Society,2010:1434-1441.

[9]Furukawa Y,Ponce J.Accurate,dense,and robust multiview stereopsis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(8):1362-1376.

[10]Taveira G,Fernandes L A F.Automatic alignment and reconstruction of facial depth images[J].Pattern Recognition Letters,2014,50(C):82-90.

[11]Matyunin S,Vatolin D,Berdnikov Y,et al.Temporal filtering for depth maps generated by kinect depth camera[C]//Proceedings of the 3DTV Conference:The True Vision-Capture,Transmission and Display of 3D Video,Antalya,Turkey,May 16-18,2011.Piscataway,USA:IEEE,2011:1-4.

[12]Pons J P,Keriven R,Faugeras O.Multi-view stereo reconstruction and scene flow estimation with a global imagebased matching score[J].International Journal of Computer Vision,2007,72(2):179-193.

[13]Tran S,Davis L.3D surface reconstruction using graph cuts with surface constraints[C]//LNCS 3952:Proceedings of the 9th European Conference on Computer Vision,Graz,Austria,May 7-13,2006.Berlin,Heidelberg:Springer,2006:219-231.

[14]Zaharescu A,Boyer E,Horaud R.TransforMesh:a topologyadaptive mesh-based approach to surface evolution[C]//LNCS 4844:Proceedings of the 8th Asian Conference on Computer Vision,Tokyo,Japan,Nov 18-22,2007.Berlin,Heidelberg:Springer,2007:166-175.

[15]Furukawa Y,Ponce J.Carved visual hulls for image-based modeling[J].International Journal of Computer Vision,2009,81(1):53-67.

[16]Furukawa Y,Curless B,Seitz S M,et al.Manhattan-world stereo[C]//Proceedings of the 2009 Conference on Computer Vision and Pattern Recognition,Miami,USA,Jun 20-25,2009.Washington:IEEE Computer Society,2009:1422-1429.

[17]Furukawa Y,Curless B,Seitz S M,et al.Towards internetscale multi-view stereo[C]//Proceedings of the 23rd Conference on Computer Vision and Pattern Recognition,San Francisco,USA,Jun 13-18,2010.Washington:IEEE Computer Society,2010:1434-1441.

[18]Lewis J P.Fast normalized cross-correlation[J].Vision Interface,1995,10(1):120-123.

[19]Raguram R,Chum O,Pollefeys M,et al.USAC:a universal framework for random sample consensus[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2013,35(8):2022-2038.

[20]Furukawa Y.Patch-based multi-view stereo software[EB/OL].(2014-07-17).http://www.di.ens.fr/pmvs/.

[21]The middlebury computer vision pages[EB/OL].(2014-07-17).http://vision.middlebury.edu/mview/.

[22]Robot vision group pages[EB/OL].(2014-07-17).http://vision.ia.ac.cn/zh/data/index.html.

附中文參考文獻(xiàn)：

[6]史穎,王文劍,白雪飛.多特征三維稠密重建方法[J].計(jì)算機(jī)科學(xué)與探索,2015,9(5):594-603.

[7]史利民,郭復(fù)勝,胡占義.利用空間幾何信息的改進(jìn)PMVS算法[J].自動(dòng)化學(xué)報(bào),2011,37(5):560-568.

2017-04,Accepted 2017-06.

Improved PMVSAlgorithm with Double Constraints

YANG Wenbo,SUN Bowen+
School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China
+Corresponding author:E-mail:Sunbw01@163.com

The PMVS(patch-based multi-view stereo)algorithm is widely used in the multi-view stereo field because of its good performance.However,the surface details of the reconstructed model are lost and the exact location of the reconstruction points is not accurate.These problems are very serious in some cases,especially while the input images are few and the texture of the reconstructed model is less.In order to solve these problems,this paper studies the removal of mismatched candidate points and the ranking of seed point reliability:firstly,use USAC(Universal-RANSAC)to remove the candidate matching error;then,put forward the double constraint strategy,meanwhile select the candidate space point which has high reliability as seed.The details of the reconstruction model fit to the original object more.Meanwhile the number of reconstruction points in the model with less texture has been significantly increased and the holes of the texture model are obviously reduced.The validity of the improved algorithm is proven to be more effective and practical.

PMVS algorithm;Universal-RANSAC;double constraints;multi-view stereo reconstruction

10.3778/j.issn.1673-9418.1703097

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-06-27,http://kns.cnki.net/kcms/detail/11.5602.TP.20170627.1246.004.html

YANG Wenbo,SUN Bowen.Improved PMVS algorithm with double constraints.Journal of Frontiers of Computer Science and Technology,2017,11(11)：1804-1815.

A

TP391.9

YANG Wenbo was born in 1989.He is an M.S.candidate at Harbin University of Science and Technology.His research interests include virtual reality and computer simulation,etc.

楊文博（1989—），男，河南安陽(yáng)人，哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)樘摂M現(xiàn)實(shí)，計(jì)算機(jī)仿真等。

SUN Bowen was born in 1963.He is an associate professor at Harbin University of Science and Technology,and the member of CCF.His research interests include virtual reality and computer simulation,etc.

孫博文（1963—），男，遼寧開(kāi)元人，哈爾濱理工大學(xué)副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)樘摂M現(xiàn)實(shí)，計(jì)算機(jī)仿真。