錢(qián)蘇斌

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

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

錢(qián)蘇斌

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

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

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

0 引言

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

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

1.1 輪廓線提取

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

圖1 斷層剖面閾值分割

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

1.1.1 輪廓點(diǎn)的確定.

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

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

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

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

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

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

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

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

圖3 經(jīng)過(guò)其中1個(gè)孔洞

3)同時(shí)經(jīng)過(guò)2個(gè)孔洞.

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

圖4 同時(shí)經(jīng)過(guò)2個(gè)孔洞

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

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

1.1.2 輪廓點(diǎn)的配對(duì).

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

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

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

1.1.3 歸入層集.

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

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

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

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

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

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

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

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

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

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

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

1.2 相鄰層輪廓點(diǎn)匹配

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

圖6 相鄰斷層剖面輪廓線

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

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

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

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

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

圖7 分段拼接

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

2 實(shí)驗(yàn)結(jié)果與結(jié)論

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

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

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

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

2.2 結(jié)論

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

:

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

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

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

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

［5］袁方，唐杰，武港山，等.一種基于三維Delaunay三角化的曲面重建算法［J］.計(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.

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