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

錢蘇斌

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

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

錢蘇斌

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

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

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

0 引言

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

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

1.1 輪廓線提取

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

圖1 斷層剖面閾值分割

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

1.1.1 輪廓點的確定.

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

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

圖2 行掃描線與目標區域的交點

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

1)直接經過目標區域.

圖2所示為行掃描線直接經過目標區域，在此前提下一般分為2種情況:一種情況如圖2(a)所示，產生2個突變點P0和P1，將P0和P1直接歸入layer0層，并且將它們添加進點結構體數組layer0_point中;另一種情況如圖2(b)所示，僅產生1個突變點P2，將P2歸入layer0層，并將其添加進點結構體數組layer0 _point中.

2)僅經過其中1個孔洞.

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

圖3 經過其中1個孔洞

3)同時經過2個孔洞.

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

圖4 同時經過2個孔洞

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

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

1.1.2 輪廓點的配對.

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

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

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

1.1.3 歸入層集.

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

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

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

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

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

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

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

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

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

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

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

1.2 相鄰層輪廓點匹配

將每一個斷層剖面中的輪廓線提取了出來，并且按照逆時針順序對輪廓線進行了分層處理，各層輪廓線上的輪廓點均存放在對應的結構體數組layer0 point［count］［i］、layer1 _point［count］［i］及layer2 _point［count］［i］中.由于通常處理的形體各斷層剖面上的輪廓線具有幾何形狀的相似性，這一特性不僅符合上述過程中的最外層輪廓線，同樣也符合內層的孔洞邊界.

圖6 相鄰斷層剖面輪廓線

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

各分層間的輪廓點匹配的步驟為:將第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，采用文獻［4］中介紹的曲率角及曲線長度的方法分別計算2點在半徑為R的區域內的曲率角，然后再計算它們在曲率角θ(i)和曲線長度s(i)上的誤差值.這里，分別設定曲率角和曲線長度的誤差值上限為ζ1、ζ2(一般情況下將ζ1設為0.003，ζ2設為3)，當且僅當同時滿足條件 θ(i)≤ζ1和s(i)≤ζ2時，Pi和Qi匹配成功，從Q集合中剔除Qi.重復上述過程，直至遍歷P中所有的點.對layer0層和layer2層分別使用以上方法進行點的匹配.

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

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

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

圖7 分段拼接

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

2 實驗結果與結論

2.1 實驗結果

在實驗中，以OpenGL和VC++6.0為開發工具，采用本研究提出的方法實現了一個基于輪廓線的任意形體三維重建.

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

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

2.2 結論

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

:

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

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

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

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

［5］袁方，唐杰，武港山，等.一種基于三維Delaunay三角化的曲面重建算法［J］.計算機技術與發展，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—)，女，碩士，從事計算機圖形學與虛擬現實技術研究.