3D表面重構中的共平面約束及其解的空間分析

于永彥,王志堅

1.內江師范學院計算機科學學院,四川內江641100

2.河海大學計算機及信息工程學院,江蘇南京210098

3D表面重構中的共平面約束及其解的空間分析

于永彥1,王志堅2

1.內江師范學院計算機科學學院,四川內江641100

2.河海大學計算機及信息工程學院,江蘇南京210098

基于單圖像的3D重構因其先天性約束不足和潛在的巨大價值成為計算機視覺領域的研究熱點，被廣泛應用于航空航天、機械制造、醫療、考古、地質、犯罪現場復原、建筑設計、城市規劃等領域。針對圖像中幾何元素的共平面性可提供景深信息的特點，提出一種基于交叉曲線共平面性約束的3D重構方案，即對于不平行于投影方向的某一個平面，根據其所含曲線與另一平面中某曲線的交叉構型構造一個線性系統，當一組這樣的交叉曲線位于擬求解表面時，可獲得精確解。對于含噪系統，要求測得的交點遠離平坦面，增加新的約束條件，定義表面的平坦度度量模型，使用SVD法獲得極小化線性系統的代數誤差的逼近解。由于利用正投影和透視投影的等價性，可將透視投影轉化為正投影，從而將這兩種投影下的3D重構規劃一個框架中。實驗表明，這種方法大大提高了3D重構的健壯性，對噪聲的敏感性小，可適用于完全未標定結構光等真實場景。

共平面性;線性系統;表面平坦度;解空間;3D重構

基于圖像的3D重構是計算機視覺的核心問題，已出現許多理論、技術和方法[1-7]，在軍事、遙感、導航、醫療等領域有著廣泛的應用。其中，基于單幅圖像的3D重構由于其成像過程丟失了景深等信息造成約束條件的嚴重不足，而成為極具挑戰性的研究熱點和難點，雖然借助一些先驗知識[8-11]，可以實現特殊場合、特定領域或特定對象的重構，但不具普適性。生理學和感知心理學研究表明，人類視覺總是自覺使用共平面假設來感知2D圖像中的3D對象[12]。共平面性是一種特殊的幾何特性，包括點的共線性和線的平行性，被廣泛應用于攝影、建筑、制造等領域。Roberts[13]首次將共平面性用于已知多面體重構，Guzman等[14-16]則將其用于解決未知對象的識別，而Malik[17]等將其擴展到曲面研究中。最有影響的是Rothwell等[18]提出的多面體籠子理論，即將一個3D對象用一個虛擬多面體環繞。由于多面體頂點的投影為視常量，一旦識別出虛擬多面體的頂點集就可計算出對應的視常量，再通過查詢一個預設數據庫即可識別出3D對象。Burns等[19]指出，一個頂點集能確定視常量的條件是存在共平面性[20]。例如，正投影下4個共平面點即可確定視常量，而透視投影則需要5個共平面點。因此，正確描述共平面性，構造合理的共平面約束模式，是有效實現單圖像3D重構的一種新思路。

1 構造共平面約束模式

設表面含有N條曲線Γ1,...,ΓN，分別位于平面π1,...,πN上。曲線Γi,Γj的交點為p( Xij,Yij,Zij)，在正投影下，對應的投影線Γ'i,Γ'j在像平面形成交點m( xij,yij)。如圖1所示。

圖1 平面、曲線及交點的正投影Fig.1 Orthographic projection of planes,curves and their intersections

若平面πi, πj不平行于投影方向，則其參數化表示如下：

由于是正投影，空間交點P的(Xij,Yij)坐標即等效于(xij,yij)，點P處兩平面πi, πj上的Z坐標之差為zi(xij,yij)-zj(xij,yij)=(ai-aj)xij+(bi-bj)yij+(di-dj)，這意味著圖像中的一個2D交點對應著一個3D表面上的曲線交點，該式子可用于估算空間點的未知深度。

假設系統不含噪聲，則存在下述關系：

考察所有可見交點，將對應的式（2）集成在一起構成一個線性方程組：

其中，v=(a1,...,aN,b1,...,bN,d1,...,dN)，A是稀疏矩陣，由xij,-xij,yij,-yij,1,-1等元素構成。

顯然，若能測得足夠多的交點(xij,yij)，則可由式（3）確定V，通過V反投影圖像曲線到他們的平面可得到表面曲線(Γi,Γj)，進而確定對應平面(πi,πj)，實現表面重構。

在無噪情況下，一組真實平面對應的V必然是式（3）的一個解，即v∈Null(A)。另外，Null(A)包含一個平凡解子空間，記為V=Span{v1,v2,v3}，其中的v1, v2,v3稱為平凡基：

上式中的1N,0N,02N分別表示元素為1、0的N-向量和2 N-向量。

可見，理想無噪情況下，式（3）存在一個四維解空間，其中的v1, v2,v3為平凡解，源自于淺浮雕歧義性[21]，第4維v來自于真實解。顯然，v, v1, v2,v3的某線性組合也是式（3）的一個解。

那么，是否存在含有更多線性無關的精確非平凡解的系統呢？研究表明，解空間的維數主要依賴于觀察到的交點構型，例如，若曲線存在脫臼現象，或表面由三角網格構成，都可能影響自由度數量，導致解空間變異。

2 含噪系統的解

在含噪情況下，式（3）是典型的超定問題，沒有精確非平凡解[22]。處理這類問題一般有兩種方法。一是假設曲線Γi,Γj是嚴格平坦的，而它們交叉點的投影點測量值需要矯正。目前的很多方法都屬于這類范疇。二是假設投影點測量值是完全正確的，而空間曲線非嚴格平坦。這方法的明顯優勢是，可采用數值化線性代數方法[23,24]。本節的目標即尋找一種方案，以極小化線性系統的代數誤差。

2.1 平凡解子空間

在含噪情況下，式（4）中的v1,v2,v3有時并不能構成平凡解的整個子空間，也就是說可能還有其他的平凡解。例如，當某曲線與其他曲線的所有交點排列在一條直線上時，特別是交點小于3個時，存在一種平凡解，即曲線位于同一個平面，而直線位于另一個不同的平面。由于所有交點位于同一個幾何平面，因此，交點處的曲線之間沒有間隙。

為了描述平凡解的完備空間，需要度量表面的平坦度。一種有效的方法是采用線性回歸法，根據采集到的k個交點擬合一個平面，并度量其殘差。如果所有點共面，則殘差為0。盡管不知道交點的深度信息，但可將點的深度描述為V的一個線性函數。令Z為一個矩陣，用于將點(xi,yi)反投影到對應平面，即Zv=(z1,...,zk)T。定義矩陣C如下：

P+為P的偽逆。

iii于求解下述最小二乘問題：

若令(a, b, d)T=P+Zv，則上述殘差可寫為下式：

定義平凡子空間為C的零空間，即Null(C)={v∈V| Cv=0}。平凡子空間的所有向量相對應于空間的共平面點集，也包括了直曲線情況。由于非共線的三點確定一個平面，所以選擇這個共平面存在3個自由度，但是Null(C)的維數可能比較大。

2.2 尋找平凡解

這個平凡子空間的自由度可由某些附加信息來加以確定，如某些已知點的深度。如果沒有這些附加信息，在正投影下，可以找一個正交于該平凡子空間的平面，以獲得高質量的解。這種選擇很自然，因為平面解對于任何曲線集合是公用的。而非平凡分量僅存在于觀察到的曲線，即僅限于問題數據。

式（4）中v1, v2,v3的相對幅度為：

由于正交投影丟失了絕對深度，因此有：

則式（8）的上限為：

因此，如果沒有附加信息，在正投影的情形下，可以選擇一個正交于該平凡子空間的解V，即該V與平凡子空間的每個向量都正交，記為，得到一個高質量的解。

2.3 精確非平凡解

含噪系統的平凡解是精確的，但非平凡解一般是不精確的。這意味著點處的平面之間存在深度間隙。解決的方法是尋找一個V使得最小。問題是，如果數據點位于一個近似平坦面時，對任何V總是呈較小的值。因此，總是希望數據點遠離一個公共平面，條件是。

已知Null(C)中的平凡解可擬合一個平面，根據式（5）、式（6），Cv=0意味著，其中a, b, d為平面參數，即，這意味著Av=0，因此。

為了求解式（11），令U D VT為C的奇異值分解。通過分別移除相當于小于指定ε的．奇異值的V中的列和D中的行，得到V,D。V中被移除的列覆蓋了平凡子空間，該平凡子空間至少是三維。V的列恰好構成平凡子空間的正交補的一個基。

若再令v=VD-1w，由于U是正交的，則上式可改寫如下：

上述求解過程描述如下：

1．根據測得的交叉點，構造A，Z，P；

3．將C奇異值分解，即C=UDVT；

4．根據D, V構造D，V；

5．計算AVD-1的奇異值分解，令W為右奇異向量；

6.返回v=VD-1w。

在該算法的實質是，在v的基中選擇一個解。矩陣D-1為V的列賦予權值，因此，接近于平凡解的向量獲得較高的價值。與W關聯的奇異值是式（11）的極小值。對于一個含較低噪聲的系統，期望其值逼近于零，除非那個真實表面就是一個平凡解。

3 透視投影模式下的解空間

透視投影具有類似的線性系統結構。設焦距為f，圖像坐標x,y與世界坐標X,Y之間的關系為x=fX/Z, y=fY/Z 。若平面πi不穿越相機中心，則：

再根據一對曲線的相交關系，產生類似于式（2）的線性方程：

對所有可見的交叉點，組合多個式（14）方程，構成類似于式（3）的線性方程：

下述定理說明了在正投影和透視投影模式下上述解空間的等價性。

定理設D是一個投影圖像，p為像平面前方的任一個3D點。那么，D為一個多面體關于以p為中心的透視投影，當且僅當D為該多面體的正投影。

證明：在不改變D可視性的情況下，通過變換(x,y,z)坐標系統，并調整縮放比例，使得p與原點一致，且使得像平面位于z=1的表面上。由此可見，場景的可視性既不依賴視點位置，也不依賴于是投影模式。

類似地，正投影系統具有一個精確非平凡解，當且僅當具有同樣交叉點的透視投影系統也有一個精確非平凡解。這表明，給定一個無噪線性系統，可以檢驗曲線在透視中是否是真正平坦的，即存在精確解，而無需知道相機的焦距，僅由正投影結論即可驗證。因為，如果是正投影，總能檢查是否存在一個解。這個結論完全可以推廣到含噪系統。

根據定理，在透視投影下，用f去除矩陣A,Z,P中的元素xij,yij,xi,yi，得到Af,Zf,Pf，再計算類似于式（5）中的Cf。同樣需要求解下述優化模式：

這樣，根據式（11）和式（16）得到的極小奇異值是相同的。需要注意的是，如果v垂直于平凡子空間，則結果就是vf，但根據v⊥Null(C)并不能確保存在vf⊥Null(Cf)。不過，由于Null(Cf)?Null(Af)，即使vf丟失了部分平凡分量也不影響整體成本價值。

4 實驗與分析

圖2包括無噪與含噪兩種情況，(a)圖為合成徑向正弦曲線，含80個截面，約4000個交點，無噪聲干擾。在(a)圖上添加隨機擾動構成(b)圖，擾動點達5000個（綠色點）。為簡化驗證過程，剔除了交叉點近似于直線的曲線。

圖2 合成正弦曲線的重構Fig.2 3D reconstruction of synthetic radial sines

5 結論

自覺利用共平面性特征感知3D場景是人類視覺的本能反應，一定程度上可彌補投影過程中丟失的景深信息。現有的共平面性約束方法難以直接用于單圖像3D重構，本文提出一種新的表面平坦度的度量模型，基于曲線交叉構型構造相應的線性系統，當系統無噪時，可獲得精確解。當系統含噪時，若要獲得精確非平凡解，則要求采集的數據點遠離公共平面，因而必須附加約束條件，假定一個正交于平凡子空間的平面而獲得精確解。利用正投影和透視投影的等價性，可將透視投影轉化為正投影，從而構建統一的求解框架。實驗證明，上述方法是適合于完全未標定的結構光環境，可產生高質量的重構效果，且所需附加信息比已標定結構光環境還要少，比已有的重構方案更據普適性。

[1]Dyer CR.Volumetric scene reconstruction from multiple views[M]//Foundations of Image Understanding.USA: Springer,2001:469-489

[2]Slabaugh G,Schafer R,Malzbender T,et al.Survey of Methods for Volumetric Scene Reconstruction from Photographs[M].New York:Springer Vienna,2001:81-100

[3]Lazebnik S,Furukawa Y,Ponce J.Projective Visual Hulls[J].Int'l J.Computer Vision,2007,74(2):137-165

[4]Aganj E,Pons JP,Ségonne F,et al.Spatio-Temporal Shape from Silhouette using Four Dimensional Delaunay Meshing[C].Proc IEEE Int'l Conf Computer Vision,2007

[5]金龍存.3D點云復雜曲面重構關鍵算法研究[D].上海:上海大學,2011

[6]Ramanan D.Learning to Parse Images of Articulated Bodies[M].Chicago:Neural Information Processing Systems,2006

[7]Bowden R,Mitchell TA,Sarhadi M.Reconstructing 3D Pose and Motion from a Single Camera View[C]//Proceedings of the British Machine Vision Conference.Uxbridge:[s.n.]1998

[8]Hoiem D,Efros A,Hebert M.Automatic photo pop-up[J].SIGGRAPH,2005:577-584

[9]Prasad M,Zisserman A,Fitzgibbon A.Single view reconstruction of curved surfaces[C]//Proc IEEE Conf on Computer Vision and Pattern Recognition.UK:[s.n.],2006

[10]段繼忠.基于壓縮感知的圖像重構技術研究[D].天津:天津大學,2013

[11]Terzopoulos D,Witkin A,Kass M.Symmetry-seeking models and 3d object reconstruction[J].Internal Journal of Computer Vision,1988,1(3):211-221

[12]Pizlo Z,Li Y,Francis G.A new look at binocular stereopsis[J].Vision Research,2005,45(17):2244-2255

[13]Roberts LG.Machine Perception of Three-Dimensional Solids[D].USA:MIT,1963

[14]Guzman G.Arenas Computer Recognition of Three-Dimensional Objects in a Visual Scene[D].USA:MIT,1968

[15]Huffman DA.Impossible objects as non-sense sentences[J].Machine Intelligence,1971(6):295-323

[16]Clowes MB.On seeing things[J].Artificial Intelligence,1971,2(1):79-116

[17]Malik,D.Interpreting line drawings of curved objects[J].Internal Journal of Computer Vision,1987,1(1):73-103

[18]Rothwell C,Stern J.Understanding the shape properties of trihedral polyhedra[M]//Computer Vision-ECCV'96.UK:4th European Conference on Computer Vision Cambridge,1996,1064:175-185

[19]Burns JB,Weiss RS,Riseman EM.The non-existence of general-case vie-winvariants[M].USA:MIT Press, 1992:120-131

[20]Reiss TH.Recognizing Planar Objects Using Invariant Image Features[M].German:Springer-Verlag,1993

[21]Weyrich T,Deng J,Barnes C,et al.Digital bas-relief from 3D scenes[J].ACM Transactions on Graphics(Proc SIGGRAPH),2007,26(3):1-7

[22]Sugihara K.Machine Interpretation of Line Drawings[M].USA:MIT Press,1986

[23]Grimstead IJ,Martin RR.Creating solid models from single 2D sketches[C]//Proc3rd ACM Symposium on Solid Modeling and Applications,1995:323-337

[24]Sturm PF,Maybank SJ.A method for interactive 3D reconstruction of piecewise planar objects from single images[C]//Proc BMVC'99,1999:265-274

Analysis on the Co-plane Constraint and Space of Solution in 3D Surface Reconstruction

YU Yong-yan1,WANG Zhi-jian2
1.College of Computer Science/Neijiang Normal University,Neijiang 641100,China
2.School of Computer and Information Engineering/Hohai University,Nanjing 210098,China

3D Reconstruction based on a single image is the research hotspot of computer vision because of its natural under-constrained and huge potential worthiness,which have been applied to aviation,mechanism,archaeology,geology, recovering the crime scene,architecture and city planning,etc.By the fact that co-plane of geometric item in an image may be provide the information about depth of field,this article suggested a complete new idea for 3D reconstruction based on co-plane constraint about intersection curves.For the planes which do not contain the projection direction,one formulated a linear system by the configuration of across curves between planes.When such a set on curves lied in a solution surface,one can get a accurate solution space.For any noisy systems,a key is that data points would escape from flat and nearly-flat planes,hence to add a new constraint conditions,define a measure of surface flatness and use SVD to obtain a approximate solution that minimizes the algebraic error of the linear system.On the other hand,since the equivalent between orthographic projection and perspective projection,one can resolve perspective projection via orthographic projection,and thereby could layout a unitive 3D reconstruction formula.Experimentation demonstrated that aforementioned methods advanced the robustness of 3D reconstruction,and have less sensitive to noise,would be suitable for real scene of completeness uncalibrated structured light.

Co-plane;linear systems;surface flatness;space of solutions;3D reconstruction

TP391.9

A

1000-2324(2015)05-0747-06

2013-07-11

2013-08-01

國家自然科學基金項目:基于鑒別特征分析的遙感圖像檢索方法研究(61170200)

于永彥(1969-),男,江蘇淮安人,博士,副教授,主要從事計算機視覺、物聯網、多媒體通信研究.E-mail:shanshan_yyy@163.com