錢蘇斌

(鹽城師范學(xué)院信息科學(xué)與技術(shù)學(xué)院，江蘇鹽城 224002)

基于輪廓線的任意形體三維重建

錢蘇斌

(鹽城師范學(xué)院信息科學(xué)與技術(shù)學(xué)院，江蘇鹽城 224002)

由二維灰度圖像恢復(fù)形體的三維形狀已經(jīng)成為計算機(jī)視覺領(lǐng)域的一個研究熱點.對該問題進(jìn)行了深入的研究，提出了一種基于單幅圖像，利用輪廓線進(jìn)行形體三維重構(gòu)的方法.該方法從一幅二維灰度圖像的斷層剖面中使用行掃描線法提取帶有孔洞的輪廓線，并且根據(jù)一定的準(zhǔn)則對其進(jìn)行分層處理，采用曲率法對各相鄰層輪廓線中的分層輪廓線進(jìn)行匹配，結(jié)合最小對角線優(yōu)化策略完成三角面片拼接，最終實現(xiàn)任意形體表面的三維重建.實驗證明，該方法可以根據(jù)形體的二維灰度圖像方便有效地重建出其三維形狀.

任意形體;三維重建;行掃描線;分層輪廓線;三角面片拼接

0 引言

近年來，三維重建技術(shù)逐步成為計算機(jī)視覺領(lǐng)域的一個研究熱點.客觀世界是一個三維的空間，而現(xiàn)有的圖像采集裝置所獲取的圖像(如數(shù)碼相機(jī)所拍攝的照片)是二維的，在二維圖像中往往又含有某種形式的三維結(jié)構(gòu)信息，如形體邊與邊的平行或垂直關(guān)系、形體本身的特殊幾何對稱性［1］，對這樣的形體進(jìn)行重建只需要一幅圖像就可以構(gòu)造出物體的模型.而另外一些形體本身結(jié)構(gòu)構(gòu)成中各幾何要素間并不具備明顯的結(jié)構(gòu)信息，對于這樣一些形體，其二維圖像上的輪廓線便成為理解其幾何形狀的一個重要線索.基于輪廓線的三維重建，傳統(tǒng)方法是將每層圖像的輪廓提取出來，然后以輪廓上的點為頂點進(jìn)行三角面片的連接［2-4］，該方法對于結(jié)構(gòu)簡單的形體效果比較好，對于結(jié)構(gòu)較為復(fù)雜的形體而言，相鄰兩層輪廓線的對應(yīng)關(guān)系較難確定.針對上述問題，有報道提出，首先對輪廓線進(jìn)行凹凸性層次分析，然后將相鄰輪廓線從外到內(nèi)依次逐層拼接，從而構(gòu)造一個三角化的物體表面［5］，但該算法在進(jìn)行凹凸性層次分析時涉及到的數(shù)據(jù)量較大.在此基礎(chǔ)上，本研究提出了一種基于輪廓線的改進(jìn)算法:使用行掃描線法對帶有孔洞的斷層剖面提取輪廓線，并且依照一定的規(guī)則對輪廓線進(jìn)行分層處理，然后采用曲率法對各相鄰層輪廓線中的分層輪廓線進(jìn)行匹配.該方法可以快速、高效完成形體三維重建.

1 基于輪廓線的任意形體表面重建

1.1 輪廓線提取

輪廓線是實體與某一特定平面的交線，它在相當(dāng)大的程度上反映了實體的形狀特征.在進(jìn)行輪廓線提取之前，首先對原始的斷層剖面圖像做閾值分割，將目標(biāo)對象從背景圖中分離出來，如圖1所示，黑色部分即為形體的斷層剖面經(jīng)過閾值分割處理后得到的目標(biāo)區(qū)域.

圖1 斷層剖面閾值分割

由于上述目標(biāo)區(qū)域中存在孔洞，而孔洞的邊界輪廓也是像素信息發(fā)生突變的點，所以輪廓線提取的過程中應(yīng)當(dāng)對所提取出來的突變點做分層處理.根據(jù)實際需要，以圖1為例，按照逆時針的順序?qū)⑤喞€分為3層:layer0、layer1及l(fā)ayer2，一般情況下，將最外層輪廓線定義為layer0層.設(shè)置相應(yīng)的點結(jié)構(gòu)體數(shù)組layer0 _point［count］［i］、layer1 _point［count］［i］及l(fā)ayer2 _point［count］［i］，用于存放實體每一斷層剖面上的相應(yīng)分層輪廓線的像素點信息，下標(biāo)count對應(yīng)于構(gòu)成實體的第count層剖面，i對應(yīng)于第count層剖面上相應(yīng)分層輪廓線上的第i個像素點.其中，數(shù)組變量layer0 _point［count］［i］.x、layer0 _point［count］［i］.y 分別用于存儲像素點的二維坐標(biāo)信息.

1.1.1 輪廓點的確定.

目標(biāo)區(qū)域的像素信息往往與圖像其他區(qū)域像素信息存在較為明顯的區(qū)別，它們通常具備以下特點:該點的顏色值及坐標(biāo)位置是固定的;該點的四鄰域中至少存在一個不屬于目標(biāo)區(qū)域的像素點.

根據(jù)上述特點，使用逐行掃描的方法找到每一行發(fā)生像素信息突變的點，這些點即為行掃描線與目標(biāo)區(qū)域邊界的交點.如圖2(a)、(b)所示的P0、P1及P2即為像素信息發(fā)生突變的點，也即輪廓點.

圖2 行掃描線與目標(biāo)區(qū)域的交點

一般情況下，行掃描線對上述目標(biāo)區(qū)域進(jìn)行掃描時，會出現(xiàn)以下幾種情形:第一種是不經(jīng)過孔洞，直接穿過目標(biāo)區(qū)域;第二種是僅僅經(jīng)過其中1個孔洞(與該孔洞有1個或者2個交點);第三種是同時經(jīng)過2個孔洞(與這2個孔洞有3個或者4個交點).

1)直接經(jīng)過目標(biāo)區(qū)域.

圖2所示為行掃描線直接經(jīng)過目標(biāo)區(qū)域，在此前提下一般分為2種情況:一種情況如圖2(a)所示，產(chǎn)生2個突變點P0和P1，將P0和P1直接歸入layer0層，并且將它們添加進(jìn)點結(jié)構(gòu)體數(shù)組layer0_point中;另一種情況如圖2(b)所示，僅產(chǎn)生1個突變點P2，將P2歸入layer0層，并將其添加進(jìn)點結(jié)構(gòu)體數(shù)組layer0 _point中.

2)僅經(jīng)過其中1個孔洞.

圖3所示為行掃描線在經(jīng)過目標(biāo)區(qū)域的時候僅經(jīng)過其中1個孔洞，在此前提下一般分為2種情況:一種情況如圖3(a)所示，僅與該孔洞有1個交點，此時產(chǎn)生3個突變點P0、P1及P2;另一種情況如圖3(b)所示，與該孔洞有2個交點，此時產(chǎn)生4個突變點P0、P1、P2及P3.

圖3 經(jīng)過其中1個孔洞

3)同時經(jīng)過2個孔洞.

圖4所示為行掃描線在經(jīng)過目標(biāo)區(qū)域的時候同時經(jīng)過2個孔洞，在此前提下一般分為2種情況:一種情況如圖4(a)所示，與2個孔洞有3個交點，此時產(chǎn)生5個突變點P0、P1、P2、P3及P4;另一種情況如圖4(b)所示，與2個孔洞有4個交點，此時產(chǎn)生6個突變點P0、P1、P2、P3、P4及P5.

圖4 同時經(jīng)過2個孔洞

在獲取每一個突變點的同時，對該突變點做一次特性分析(除最外層的一對突變點).假設(shè)某點P(x，y)已經(jīng)被確定為突變點，進(jìn)一步判斷P'(x+1，y)在二值圖上是否為目標(biāo)區(qū)域像素點:如果不是，則P(x，y)是掃描線經(jīng)過該孔洞時的入點，接下來的掃描中，在該孔洞上必將有1個出點與之配對，即當(dāng)前掃描線與孔洞有2個交點;如果是，再次判斷P'(x-1，y)在二值圖上是否為目標(biāo)區(qū)域像素點，如果條件成立，則P(x，y)既是掃描線經(jīng)過該孔洞時的入點，也是掃描線經(jīng)過該孔洞時的出點，即當(dāng)前掃描線與孔洞僅有1個交點.設(shè)置數(shù)組flag point［k］用于記錄每個突變點的特性值，如為前者所述，則特性值設(shè)置為“1”，反之則設(shè)置為“0”，下標(biāo)1≤k≤n-1.

此外，具有多個孔洞的斷層剖面其輪廓點確定及特性分析可根據(jù)實際情況同理推得.

1.1.2 輪廓點的配對.

一般情況下，行掃描線與一條封閉曲線的交點個數(shù)至多為2 個.假設(shè)輪廓點集為，P={P0，P1，P2，P3，P4…Pi-1，Pi…Pn-2，Pn-1}，對點集中的輪廓點進(jìn)行兩兩配對.首先，確定＜P0，Pn-1＞為最外層輪廓線(layer0層)上的輪廓點對，再根據(jù)實際情況確定其余孔洞層上的輪廓點對.

1)當(dāng)輪廓點個數(shù)為“1”，即行掃描線僅與斷層剖面邊界有一個交點P0，則輪廓點對為＜P0，P0＞.

2)當(dāng)輪廓點個數(shù)不為“1”，則依次判斷每一個輪廓點的特性值，如果特性值flag _point［k］為“1”，則輪廓點Pi與其之后緊鄰的一個輪廓點Pi+1進(jìn)行配對，構(gòu)成輪廓點對＜Pi，Pi+1＞，那么下次的特性分析從Pi+2開始;如果特性值flag _point［k］為“0”，則輪廓點Pi與其本身配對，構(gòu)成輪廓點對＜Pi，Pi＞，那么下次的特性分析從Pi+1開始.

1.1.3 歸入層集.

以圖2～圖4為例，對獲取的輪廓點對進(jìn)行歸層操作.

1)當(dāng)輪廓點個數(shù)為“1”時，輪廓點對為＜P0，P0＞，P0直接歸入layer0層，并將其添加到數(shù)組layer0_point中.

2)當(dāng)輪廓點個數(shù)為“2”時，輪廓點對為＜P0，P1＞，P0、P1直接歸入 layer0層，并將其添加到數(shù)組layer0 point中.

3)當(dāng)輪廓點個數(shù)為其余值時，＜P0，Pn-1＞直接歸入layer0層，設(shè)置距離變量dis1和dis2，初值為∞.

設(shè)置點結(jié)構(gòu)體變量layer1 binary point、layer2_binary point，分別用于存放輪廓點對的中間點坐標(biāo)，將分坐標(biāo)的初值均設(shè)為0.假設(shè)上一對歸入layer1層的輪廓點對為 ＜P2i-5，P2i-4＞，歸入 layer2層的輪廓點對為＜P2i-3，P2i-2＞，則上述輪廓點對的中間點坐標(biāo)分別為，

①如果待歸入層的輪廓點對＜P2i+1，P2i+2＞，用 同樣方法求得其中間點坐標(biāo)temp.x、temp.y，則，

當(dāng)dis1＜dis2時，將 ＜P2i+1，P2i+2＞歸入 layer1層，并將P2i+1和P2i+2添加到數(shù)組layer1 point中，反之，歸入layer2層，并將P2i+1和P2i+2添加到數(shù)組layer2 _point中.

②如果現(xiàn)有待歸入層的輪廓點對＜P2i+1，P2i+1＞，判斷dis1或dis2是否是∞，如果dis1為∞或者兩者都為∞，則將P2i+1歸為layer1層，如果僅有dis2為∞，則將P2i+1歸為layer2層.

圖5所示即為形體的某斷層剖面使用上述算法獲得的輪廓線.

圖5 帶有孔洞的斷層剖面輪廓線

對形體的每一個斷層剖面采用上述方法及步驟，即可獲取整個形體的有效輪廓線.該算法能夠有效提高輪廓線定位精度，降低漏檢率，使輪廓線更為細(xì)致平滑.

1.2 相鄰層輪廓點匹配

將每一個斷層剖面中的輪廓線提取了出來，并且按照逆時針順序?qū)喞€進(jìn)行了分層處理，各層輪廓線上的輪廓點均存放在對應(yīng)的結(jié)構(gòu)體數(shù)組layer0 point［count］［i］、layer1 _point［count］［i］及l(fā)ayer2 _point［count］［i］中.由于通常處理的形體各斷層剖面上的輪廓線具有幾何形狀的相似性，這一特性不僅符合上述過程中的最外層輪廓線，同樣也符合內(nèi)層的孔洞邊界.

圖6 相鄰斷層剖面輪廓線

圖6所示為形體第count層及count+1層斷層剖面使用本算法提取出來的分層輪廓線.其中，layer1_point［count］［i］與layer1 _point［count+1］［i］中所存放的分層輪廓線應(yīng)當(dāng)具備一定的幾何形狀相似性.

各分層間的輪廓點匹配的步驟為:將第count+1層斷層剖面的layer1層輪廓線作為基層輪廓線，將layer1 _point［count+1］中的點賦予點集P={P1，P2，P3，…，Pm}，將第 count層斷層剖面的 layer1 層輪廓線作為待匹配層輪廓線，將layer1 _point［count］中的點賦予點集Q={Q1，Q2，Q3，…，Qn}，其中m≤n.依次從P中取出Pi，從Q中找到一點Qi，采用文獻(xiàn)［4］中介紹的曲率角及曲線長度的方法分別計算2點在半徑為R的區(qū)域內(nèi)的曲率角，然后再計算它們在曲率角θ(i)和曲線長度s(i)上的誤差值.這里，分別設(shè)定曲率角和曲線長度的誤差值上限為ζ1、ζ2(一般情況下將ζ1設(shè)為0.003，ζ2設(shè)為3)，當(dāng)且僅當(dāng)同時滿足條件 θ(i)≤ζ1和s(i)≤ζ2時，Pi和Qi匹配成功，從Q集合中剔除Qi.重復(fù)上述過程，直至遍歷P中所有的點.對layer0層和layer2層分別使用以上方法進(jìn)行點的匹配.

1.3 輪廓線分段連接及三角面片拼接

依次連接相鄰層已經(jīng)匹配好的各層輪廓點，將相鄰層輪廓線分成幾個獨立的部分.

如圖7 所示，Pi、Pi+1、Qi及Qi+1分別為2 個相鄰的layer1層上的點，其中Pi與Qi相匹配，Pi+1與Qi+1相匹配，由這4點構(gòu)成一個四邊形的小面片.

圖7 分段拼接

本研究在進(jìn)行三角面片拼接時，以最小對角線為優(yōu)化目標(biāo)［5］.至于對角線是連接Pi、Qi+1，還是Pi+1、Qi可由2跨距的長度來決定，一般采取的原則是取短舍長，這樣2個三角面片可同時產(chǎn)生;然后i值增加1，重復(fù)上述步驟，使上下兩層輪廓線的點同步前進(jìn)，直至所有點均連接完畢，并返回到起始點，此時一個封閉的表面已經(jīng)形成.同理，對于各相鄰層上的layer0、layer2層均采用上述方法，便可完成全部三角面片的繪制，進(jìn)而完成整個形體的三維重建.

2 實驗結(jié)果與結(jié)論

2.1 實驗結(jié)果

在實驗中，以O(shè)penGL和VC++6.0為開發(fā)工具，采用本研究提出的方法實現(xiàn)了一個基于輪廓線的任意形體三維重建.

圖8所示為經(jīng)過本研究方法重建生成的含有孔洞的三維形體.從實際效果可以看出，重建形體的表面結(jié)構(gòu)合理，基本符合形體本身的輪廓線層次分布.

圖8 本研究方法三維重建效果

2.2 結(jié)論

本研究提出了一種基于輪廓線的任意形體三維重建方法.該方法使用行掃描線法對帶有孔洞的斷層剖面提取輪廓線，并且依照一定的規(guī)則對輪廓線進(jìn)行分層處理，然后采用曲率法對各相鄰層輪廓線中的分層輪廓線進(jìn)行匹配，最后以最小對角線為優(yōu)化目標(biāo)進(jìn)行三角面片的拼接，進(jìn)而得到三維模型.這種方法不僅有效避免了一般形體重建方法所要求的需要較多的幾何參數(shù)去精確表示曲面形態(tài)的缺陷，而且在一定程度上提高了形體重建的精度.

:

［1］錢蘇斌.基于二維灰度圖像的規(guī)則形體三維重建［J］.成都大學(xué)學(xué)報(自然科學(xué)版)，2012，31(3):243-246.

［2］孔令鑫.基于輪廓線的三維重建技術(shù)研究［J］.機(jī)械與電子，2011，25(10):3-6.

［3］陳敏，鮑旭東.由任意形狀輪廓線重建表面的方法研究［J］.計算機(jī)工程與應(yīng)用，2006，41(12):74-76.

［4］王醒策，周明全，劉新宇，等.基于周期性曲率函數(shù)的輪廓線匹配技術(shù)研究［J］.系統(tǒng)仿真學(xué)報，2007，19(17):4045-4048.

［5］袁方，唐杰，武港山，等.一種基于三維Delaunay三角化的曲面重建算法［J］.計算機(jī)技術(shù)與發(fā)展，2011，21(10):14-18.

3D Reconstruction of Arbitrary Shape Object Based on Contour Line

QIAN Subin
(School of Information Science and technology，Yancheng Teachers College，Yancheng 224002，China)

3D reconstruction from the 2D grey image has been a research hotspot in the field of computer vision.This paper makes an intensive study on the hotspot，and proposes a method based on single image and completing 3D reconstruction of arbitrary shape object according to the contour line.The method adopts scanning lines to extract the contour lines with orifices from one 2D grey image’s cross sections，processes them hierarchically according to certain criteria，uses the curvature to match the hierarchical contour lines in adjacent layers，and completes the triangular plane-concatenation according to the shortest diagonal optimization strategy，finally realizes the 3D reconstruction of arbitraty shape object surface.The experimental results indicate that this method could conveniently reconstruct the 3D shape of arbitraty shape object according to its 2D grey image.

arbitraty shape object;3D reconstruction;scanning line;hierarchical contour line;triangular plane-concatenation

TP391.41

A

1004-5422(2013)03-0262-05

2013-08-15.

錢蘇斌(1984—)，女，碩士，從事計算機(jī)圖形學(xué)與虛擬現(xiàn)實技術(shù)研究.