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

詹洋，尹顏朋

（四川大學計算機學院，成都 610065）

0　引言

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

1　背景

1.1　Delaunay三角化

對任意在d維空間中的點集進行三角化網(wǎng)格操作，其原理是將其凸包分割為單形。Delaunay三角化具有空球?qū)傩裕唵蝸碚f，在每個單形外接球中不存在d+2個點，所以Delaunay三角化是唯一的。在計算機圖形學和表面處理中Delaunay三角化是一個常用的工具。

圖1　

1.2　Minimum s-t Cut

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

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

2　重建算法

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

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

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

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

圖2　

圖3　

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

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

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

3　實驗結(jié)果

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

4　結(jié)語

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

參考文獻：

[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.