于永彥,王志堅(jiān)

1.內(nèi)江師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院,四川內(nèi)江641100

2.河海大學(xué)計(jì)算機(jī)及信息工程學(xué)院,江蘇南京210098

3D表面重構(gòu)中的共平面約束及其解的空間分析

于永彥1,王志堅(jiān)2

1.內(nèi)江師范學(xué)院計(jì)算機(jī)科學(xué)學(xué)院,四川內(nèi)江641100

2.河海大學(xué)計(jì)算機(jī)及信息工程學(xué)院,江蘇南京210098

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

共平面性;線性系統(tǒng);表面平坦度;解空間;3D重構(gòu)

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

1 構(gòu)造共平面約束模式

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

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

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

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

假設(shè)系統(tǒng)不含噪聲，則存在下述關(guān)系：

考察所有可見交點(diǎn)，將對(duì)應(yīng)的式（2）集成在一起構(gòu)成一個(gè)線性方程組：

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

顯然，若能測(cè)得足夠多的交點(diǎn)(xij,yij)，則可由式（3）確定V，通過V反投影圖像曲線到他們的平面可得到表面曲線(Γi,Γj)，進(jìn)而確定對(duì)應(yīng)平面(πi,πj)，實(shí)現(xiàn)表面重構(gòu)。

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

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

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

那么，是否存在含有更多線性無關(guān)的精確非平凡解的系統(tǒng)呢？研究表明，解空間的維數(shù)主要依賴于觀察到的交點(diǎn)構(gòu)型，例如，若曲線存在脫臼現(xiàn)象，或表面由三角網(wǎng)格構(gòu)成，都可能影響自由度數(shù)量，導(dǎo)致解空間變異。

2 含噪系統(tǒng)的解

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

2.1 平凡解子空間

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

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

P+為P的偽逆。

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

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

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

2.2 尋找平凡解

這個(gè)平凡子空間的自由度可由某些附加信息來加以確定，如某些已知點(diǎn)的深度。如果沒有這些附加信息，在正投影下，可以找一個(gè)正交于該平凡子空間的平面，以獲得高質(zhì)量的解。這種選擇很自然，因?yàn)槠矫娼鈱?duì)于任何曲線集合是公用的。而非平凡分量?jī)H存在于觀察到的曲線，即僅限于問題數(shù)據(jù)。

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

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

則式（8）的上限為：

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

2.3 精確非平凡解

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

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

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

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

上述求解過程描述如下：

1．根據(jù)測(cè)得的交叉點(diǎn)，構(gòu)造A，Z，P；

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

4．根據(jù)D, V構(gòu)造D，V；

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

6.返回v=VD-1w。

在該算法的實(shí)質(zhì)是，在v的基中選擇一個(gè)解。矩陣D-1為V的列賦予權(quán)值，因此，接近于平凡解的向量獲得較高的價(jià)值。與W關(guān)聯(lián)的奇異值是式（11）的極小值。對(duì)于一個(gè)含較低噪聲的系統(tǒng)，期望其值逼近于零，除非那個(gè)真實(shí)表面就是一個(gè)平凡解。

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

透視投影具有類似的線性系統(tǒng)結(jié)構(gòu)。設(shè)焦距為f，圖像坐標(biāo)x,y與世界坐標(biāo)X,Y之間的關(guān)系為x=fX/Z, y=fY/Z 。若平面πi不穿越相機(jī)中心，則：

再根據(jù)一對(duì)曲線的相交關(guān)系，產(chǎn)生類似于式（2）的線性方程：

對(duì)所有可見的交叉點(diǎn)，組合多個(gè)式（14）方程，構(gòu)成類似于式（3）的線性方程：

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

定理設(shè)D是一個(gè)投影圖像，p為像平面前方的任一個(gè)3D點(diǎn)。那么，D為一個(gè)多面體關(guān)于以p為中心的透視投影，當(dāng)且僅當(dāng)D為該多面體的正投影。

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

類似地，正投影系統(tǒng)具有一個(gè)精確非平凡解，當(dāng)且僅當(dāng)具有同樣交叉點(diǎn)的透視投影系統(tǒng)也有一個(gè)精確非平凡解。這表明，給定一個(gè)無噪線性系統(tǒng)，可以檢驗(yàn)曲線在透視中是否是真正平坦的，即存在精確解，而無需知道相機(jī)的焦距，僅由正投影結(jié)論即可驗(yàn)證。因?yàn)?，如果是正投影，總能檢查是否存在一個(gè)解。這個(gè)結(jié)論完全可以推廣到含噪系統(tǒng)。

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

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

4 實(shí)驗(yàn)與分析

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

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

5 結(jié)論

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

[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點(diǎn)云復(fù)雜曲面重構(gòu)關(guān)鍵算法研究[D].上海:上海大學(xué),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]段繼忠.基于壓縮感知的圖像重構(gòu)技術(shù)研究[D].天津:天津大學(xué),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

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

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