基于Minimum s-t Cut三維表面重建算法

詹洋，尹顏朋

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0　引言

隨著計(jì)算機(jī)視覺(jué)技術(shù)發(fā)展，3D點(diǎn)云獲取更加便捷。然而如何根據(jù)3D點(diǎn)云重建出完整而準(zhǔn)確的三維表面仍然是一個(gè)難題。本文的主要目的是采用多視圖三維重建算法所產(chǎn)生的3D點(diǎn)云作為輸入，重建出盡可能完整而準(zhǔn)確的表面模型，為VR（Virtual Reality），AR（Augmented Reality）等提供三維模型。常見的多視圖三維重建算法有 Structure-from-Motion（SfM）[1]、planesweeping[2]、growing based[3]等。本文采用 Bundle Adjustmen[4]三維重建算法獲取稀疏點(diǎn)云，PMVS[5]對(duì)稀疏點(diǎn)云進(jìn)行優(yōu)化和加密，得到稠密3D點(diǎn)云。目前常用的三維表面重建的算法有：泊松（Poisson）表面重建[6]，泊松表面重建采用隱函數(shù)的方式擬合3D點(diǎn)云，從而得到水密的三維表面模型，但缺點(diǎn)是易受噪聲的干擾而丟失細(xì)節(jié)信息；Calakli F 等提出 SSD（Smooth Signed Distance）表面重建[7]，采用變分的方法計(jì)算三維表面模型，其缺點(diǎn)也易受噪聲的干擾；Laurentini提出一種Visual-hull[8]的方法，但對(duì)實(shí)驗(yàn)條件要求苛刻，無(wú)法適應(yīng)室外的情況。其中泊松表面重建和SSD只運(yùn)用到三維點(diǎn)的坐標(biāo)信息，而忽略其他例如可見性等信息，Visual-hull雖然利用可見性信息，但其無(wú)法適應(yīng)室外條件。可見性為每個(gè)三維點(diǎn)由哪些攝像機(jī)產(chǎn)生，即可見性序列。通過(guò)可見性信息，可以去除大量噪聲和重現(xiàn)三維表面細(xì)節(jié)。本文采用Delaunay三角化對(duì)3D點(diǎn)云空間進(jìn)行分解，利用可見性信息將表面重建問(wèn)題轉(zhuǎn)化為能量最小化問(wèn)題，構(gòu)建有向圖，采用Minimum s-t Cut進(jìn)行優(yōu)化得到三維表面重建模型。圖1為本文算法和泊松表面重建算法、SSD（Smooth Signed Distance）表面重建算法，通過(guò)對(duì)比可以看出本文算法可以去除噪聲的干擾且呈現(xiàn)細(xì)節(jié)信息。

1　背景

1.1　Delaunay三角化

對(duì)任意在d維空間中的點(diǎn)集進(jìn)行三角化網(wǎng)格操作，其原理是將其凸包分割為單形。Delaunay三角化具有空球?qū)傩裕?jiǎn)單來(lái)說(shuō)，在每個(gè)單形外接球中不存在d+2個(gè)點(diǎn)，所以Delaunay三角化是唯一的。在計(jì)算機(jī)圖形學(xué)和表面處理中Delaunay三角化是一個(gè)常用的工具。

圖1　

1.2　Minimum s-t Cut

有限元有向圖G(V,E)，其中V={v1,v2,…,vn}為頂點(diǎn)，E為有向邊其非負(fù)權(quán)重為wpq。額外增加兩個(gè)特殊頂點(diǎn)，源點(diǎn)s和終點(diǎn)t。運(yùn)用s-t Cut算法可以將頂點(diǎn)V分為兩個(gè)集合 S和T，其中 s∈S,t∈T。其能量方程為：

其中wpt為頂點(diǎn)p到終點(diǎn)t構(gòu)成的有向邊的權(quán)重，wsp為源點(diǎn)s到頂點(diǎn)p構(gòu)成的有向邊的權(quán)重，wpq由頂點(diǎn)p到頂點(diǎn)q構(gòu)成的有向邊的權(quán)重。應(yīng)用Ford-Fulkerso[9]理論可將s-t Cut轉(zhuǎn)化為最大流最小割求解，使得C()S,T的能量最小。

2　重建算法

通過(guò)Bundle Adjustmen加PMVS得到稠密3D點(diǎn)云以及每個(gè)點(diǎn)的可見性序列。第一步是對(duì)3D點(diǎn)云P進(jìn)行Delaunay三角化自適應(yīng)的四面體分解。由于3D點(diǎn)云中可能存在噪聲點(diǎn)，為了減弱噪聲的影響，在Delaunay三角化過(guò)程中，對(duì)當(dāng)前插入的三維點(diǎn)(p,C)∈P,其中p為三維坐標(biāo)，C為可見性序列集合。先檢查是否已經(jīng)插入，如果已經(jīng)插入只需找到插入點(diǎn)更新其可見序列信息，如果沒(méi)有，則查找其最近鄰并根據(jù)當(dāng)前點(diǎn)的可見性序列將當(dāng)前點(diǎn)和其最近鄰?fù)队暗蕉S空間中，檢查其像素差，如果其像素差小于k則當(dāng)前點(diǎn)不插入只更新最近鄰點(diǎn)可見序列信息，否則插入當(dāng)前點(diǎn)。

得到Delaunay三角化T結(jié)果后，下一步需要利用可見性信息將表面重建問(wèn)題轉(zhuǎn)化為能量最小化問(wèn)題，其能量方程的形式為：

其中S*為目標(biāo)表面。Edata是數(shù)據(jù)項(xiàng),Esmooth為平滑項(xiàng)。Edata記錄Delaunay三角化中每個(gè)三角形的權(quán)重，也是有向圖中有向邊的權(quán)重。其公式為：

其中 f為Delaunay三角化T中三角形，()p,c為3D點(diǎn)云P包含可見性序列中攝像機(jī)點(diǎn)坐標(biāo)（c∈C）-三維點(diǎn)（p）坐標(biāo)點(diǎn)對(duì)，C為可見性序列集合，α(p)為當(dāng)前點(diǎn)p與三角形 f交點(diǎn)的個(gè)數(shù)，d為交點(diǎn)距p的距離，σ為調(diào)節(jié)參數(shù)。其計(jì)算的原理是，對(duì)于每個(gè)三維點(diǎn)(p,C)∈P,，每個(gè)攝像機(jī)點(diǎn)坐標(biāo)（c∈C）-三維點(diǎn)（p）坐標(biāo)點(diǎn)對(duì)，計(jì)算線段seg（c,p）與Delaunay三角化 T所有相交的面，并計(jì)算交點(diǎn)距p的距離d,包含c的Delaunay四面體標(biāo)記為outside并于源點(diǎn)s相連構(gòu)成有向邊，包含p的Delaunay四面體標(biāo)記為inside并與終點(diǎn)t相連構(gòu)成有向邊，為了減弱噪聲影響，采用距p點(diǎn)很小距離σ作為線段的終點(diǎn)。具體形式見圖2（a）。上述計(jì)算原理可以歸結(jié)為線面交的問(wèn)題，如果用完全遍歷的方式其時(shí)間復(fù)雜度為Ο(npncnf)，其中np為三維點(diǎn)的總數(shù)，np為攝像機(jī)的個(gè)數(shù)，nf為Delaunay三角化中三角形的個(gè)數(shù)，時(shí)間復(fù)雜度大。而線面交的問(wèn)題可以轉(zhuǎn)化為碰撞檢測(cè)問(wèn)題，可以采用AABB tree來(lái)減少時(shí)間復(fù)雜度，其時(shí)間復(fù)雜度可以減少為Ο(npnclognf)，可以很好地提高效率。

圖2　

圖3　

如果只有Edata項(xiàng)重建表面S*易受到尖銳三角形的干擾，產(chǎn)生不平滑的表面。所以Esmooth來(lái)去除S*中尖銳的三角形，使得目標(biāo)表面平滑。其目標(biāo)是盡可能地得到正三角形。實(shí)現(xiàn)方法為，在Delaunay三角化 T中所有的三角形對(duì)應(yīng)兩個(gè)四面體，分別計(jì)算四面體外接球與三角形所在的平面形成的夾角的余弦值，當(dāng)余弦值越大，說(shuō)明三角形的質(zhì)量越好，其公式為：

其中 f為Delaunay三角化T中三角形，?、φ為f對(duì)應(yīng)平面與四面體外接球形成的夾角。

分別計(jì)算出Edata，Esmooth后，就可以得到每個(gè)有向邊的權(quán)重，將Delaunay三角化中每個(gè)四面體當(dāng)作有向圖的頂點(diǎn)，每個(gè)三角形當(dāng)作有向圖的有向邊，按照?qǐng)D2（b）的方式構(gòu)建有向圖，通過(guò)運(yùn)用Minimum s-t Cut算法進(jìn)行優(yōu)化，對(duì)Delaunay三角化中每個(gè)四面體進(jìn)行標(biāo)簽分配（inside or outside），其中不同標(biāo)簽兩個(gè)相鄰四面體之間的三角形，即割邊就是我們所求的目標(biāo)表面S*。

3　實(shí)驗(yàn)結(jié)果

采用開源數(shù)據(jù)集對(duì)重建算法進(jìn)行驗(yàn)證，OWL有30張分辨率為5184×3456圖像，hall有61張3008×2000圖像。通過(guò)圖1說(shuō)明可以得到本文算法可以去除大量噪聲點(diǎn)的影響且重建出表面細(xì)節(jié)，而poisson表面重建和SSD表面重建算法易受噪聲點(diǎn)的影響。圖3實(shí)驗(yàn)說(shuō)明本問(wèn)算法可以較好地呈現(xiàn)出表面的細(xì)節(jié)，例外地面，門戶等。實(shí)驗(yàn)結(jié)果表明利用可見性信息結(jié)合用Minimum s-t Cut的方式對(duì)三維點(diǎn)云進(jìn)行表面重建可以有效地減少噪聲對(duì)目標(biāo)表面的干擾而可以重建出精細(xì)的細(xì)節(jié)，能夠較準(zhǔn)確而完整地重建出三維表面模型。

4　結(jié)語(yǔ)

本文采用Delaunay三角化方式對(duì)3D點(diǎn)云空間進(jìn)行自適應(yīng)分解，利用可見性信息將表面重建問(wèn)題轉(zhuǎn)化為能量最小化問(wèn)題，構(gòu)建有向圖，以Minimum s-t Cut方式求解能量最小化問(wèn)題，得到最終表面重建模型。實(shí)驗(yàn)表明基于Minimum s-t Cut三維表面重建算法可以重建出較完整且準(zhǔn)確的三維表面模型，具有一定的研究?jī)r(jià)值。但本文算法還需在效率上進(jìn)行完善，需要繼續(xù)改進(jìn)。

參考文獻(xiàn)：

[1]R.Hartley and A.Zisserman,Multiple View Geometry in Computer Vision[M].Cambridge University Press,2003.

[2]R.Collins.A space-Sweep Approach to True Multi-Image Matching[J].Technical Report UM-CS-1995-101,1995.

[3]Y.Furukawa and J.Ponce.Accurate,Dense,and Robust Multiview Stereopsis[J].In CVPR,2007.

[4]Agarwal S,Snavely N,Seitz S M,et al.Bundle Adjustment in the Large[C].European Conference on Computer Vision.Springer,Berlin,Heidelberg,2010.

[5]Furukawa Y,Ponce J.Accurate,Dense,and Robust Multiview Stereopsis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32（8）:1362-1376.

[6]Kazhdan M,Hoppe H.Screened Poisson Surface Reconstruction[J].ACM Transactions on Graphics（TOG）,2013,32（3）:29.

[7]Calakli F,Taubin G.SSD-C:Smooth Signed Distance Colored Surface Reconstruction[M].Expanding the Frontiers of Visual Analytics and Visualization.Springer London,2012:323-338.

[8]A.Laurentini.The Visual Hull Concept for Silhouette-Based Image Understanding.PAMI,16（2）:150-162,February 1994.

[9]Ford Jr L R,Fulkerson D R.Flows in Networks[M].Princeton University Press,2015.