李 霞

（中國石油山東銷售公司 調(diào)度運輸處，山東 濟南 250011）

幀間一致性的八叉樹可視外殼三維重建

李 霞

（中國石油山東銷售公司 調(diào)度運輸處，山東 濟南 250011）

針對動態(tài)物體三維重建計算量大的問題，提出利用幀間一致性的動態(tài)物體可視外殼重建算法。算法采用八叉樹的存儲結構，利用幀間一致性，判斷前一幀重建的可視外殼邊界體素的鄰域體素狀態(tài)，生成后續(xù)幀的可視外殼。相比于每次從八叉樹的根節(jié)點開始判斷的方法，幀間一致性算法減少了判斷次數(shù)，提高了算法效率。試驗結果表明，該算法有效地減少了計算量。

三維重建；可視外殼；幀間一致性；八叉樹

基于視頻圖像的三維重建是虛擬現(xiàn)實、計算機視覺等領域研究的重要內(nèi)容?？梢曂鈿な怯煽臻g物體的所有已知側影輪廓決定的空間包絡，是動態(tài)物體實時三維重建的一種有效方法［1－3］?；隗w素的重建算法穩(wěn)定，能夠重建拓撲結構復雜的物體，但由于所使用的元素是離散的體素單元，所以只能得到近似的結果。為了獲得動態(tài)物體的高精度三維模型，需要多個相機和精細的體系，導致計算量大。法國INRIA的GrImage系統(tǒng)使用8臺雙核PC機組成機群，在640×480的相機分辨率下，重建速度達到30 fps［4］?；趥鹘y(tǒng)八叉樹可視外殼算法的動態(tài)物體重建過程中，每一幀都是從八叉樹的根結點開始計算，算法計算量較大。三維重建過程中，在連續(xù)的兩幀之間重建的物體相似程度高，因此，可利用幀間的連貫性來減少算法在每一幀中的計算量，以提高算法的效率。

1 基于八叉樹的體素可視外殼

可視外殼算法總體上分為兩大類：基于體的方法與基于面的方法［5］。基于體的可視外殼方法能夠重建具有復雜拓撲結構的物體，算法穩(wěn)定?；诿娴目梢曂鈿し椒ㄊ侵苯訉梢曞F體求交，可直接得到物體的三維網(wǎng)格，但這種方法需要復雜的幾何計算，存在數(shù)值不穩(wěn)定的問題。本文采用體素方法重建三維模型。

1.1 體素狀態(tài)判斷

假設體素為V，構成體素的8個頂點表示為Pi（i＝0…7），那么對于頂點Pi在第k個相機里的狀態(tài)定義為Sk（Pi），計算式如下：

其值為0時表示頂點在物體外，值為1表示頂點在物體內(nèi)。

當計算體素在相機k中每個頂點的狀態(tài)后，接著判斷體素在相機k里的狀態(tài)Sk（V），最后可由體素在每個相機中的狀態(tài)計算體素與物體間的關系S（V），S（V）為1表示體素位于物體內(nèi)，－1表示體素落在物體外，0表示體素在物體表面上。計算方法如下：

1.2 八叉樹算法

基于體素的算法主要采用空間完全剖分和八叉樹兩種算法實現(xiàn)。前面一種方法首先將物體所在空間完全劃分成等大小的體素，重建時需要判斷每個體素的狀態(tài)，最后用邊界體素表示物體。

八叉樹算法是：首先將整個建?？臻g作為一個體素V，判斷體素狀態(tài)，若體素在物體邊界上（即S（V）＝0），需將體素八等分，再對每個體素重復上述過程，直到體素分解到一定精度為止。如圖1所示，（a）為體素分解的圖形示意，（b）為相應的八叉樹結構，樹中節(jié)點存在三種情況：黑色節(jié)點（值為1）表示對應體素完全落在物體上，白色節(jié)點（值為－1）表示對應體素完全落在物體外，灰色節(jié)點（值為0）表示體素部分在物體內(nèi)，部分在物體外。

圖1 簡單的兩層八叉樹

完全剖分法數(shù)據(jù)結構簡單，但需要逐個判斷體素，計算消耗較大。八叉樹法數(shù)據(jù)結構復雜，只有當體素位于物體邊界上才進行分解，因此總的計算消耗明顯低于完全剖分法。

對于連續(xù)運動物體，現(xiàn)有方法都是每幀采用八叉樹算法重建物體，當重建模型精度要求高時，需要更多相機，這樣就難以達到實時重建。通過試驗可得，如果連續(xù)幀間的物體空間位置變化較小時，那么八叉樹中節(jié)點狀態(tài)發(fā)生變化的個數(shù)也較少。為此，連續(xù)重建多幀中的物體時，只需要根據(jù)前幀中邊界體素的狀態(tài)進行判斷，從而減少從根節(jié)點開始判斷的時間。

2 幀間一致性體素處理

對于一般的低速運動物體而言，連續(xù)幀具有一定相關性。這是由于在實時系統(tǒng)中連續(xù)幀間隔時間很短，在此短時間內(nèi)物體移動的范圍是有限，這使得前一幀重建的物體與當前幀重建的物體具有較高的重疊率。因此可以從前一幀三維重建的可視外殼邊界體素出發(fā)，根據(jù)物體運動情況，判定下一幀物體的邊界體素。

2.1 數(shù)據(jù)結構

當一幀重建后，用邊界體素（葉子節(jié)點且S（V）＝0）表示物體模型，后繼幀中的邊界體素由前幀體素計算。需要計算的前幀中體素包括邊界體素及八叉樹中的非邊界葉子結點體素，分別用兩個隊列（bQue和lQue）存放這兩類體素。當重建第一幀的模型時，采用基本八叉樹算法從根節(jié)點開始建立八叉樹，同時將邊界體素及葉子節(jié)點分別存放到兩個隊列中。八叉樹和隊列中的節(jié)點采用同樣的數(shù)據(jù)結構，如圖2所示，Data數(shù)據(jù)域存放體素幾何數(shù)據(jù)，pParent和pSons［］分別存放父親和孩子節(jié)點指針，Satus＝S（V）。

圖2 體素數(shù)據(jù)結構

2.2 隊列處理

后繼幀中物體的邊界體素將由前幀中的b Que和l Que中的體素計算而來，對各自隊列中的體素進行不同的處理。

若體素V為l Que隊列中的體素，經(jīng)當前幀測試后有以下3種情況進行處理：

（1）體素狀態(tài)S（V）不發(fā)生變化，V 繼續(xù)在l Que隊列中，如圖3中的節(jié)點0、5、6；

（2）體素狀態(tài)S（V）值為－1和1互換，V 繼續(xù)在lQue隊列中，如圖3中的節(jié)點3、4；

（3）體素狀態(tài)S（V）值由－1或1變?yōu)?，V 從lQue隊列中刪除，如圖3中的節(jié)點1；

注意：若不在l Que隊列體素V狀態(tài)S（V）值由0變?yōu)椋?或1時，V 需添加到lQue隊列中，如圖3中的節(jié)點2。

若體素V（S（V）＝0）為b Que隊列中的體素，經(jīng)當前幀測試后有以下兩種情況進行處理：

（1）體素狀態(tài)S（V）不發(fā)生變化，V 繼續(xù)在b Que隊列中；

（2）體素狀態(tài)S（V）值從0變?yōu)椋?或1，V 從b Que隊列中刪除，如圖3中的節(jié)點23、26、70。

圖3 連續(xù)幀間的八叉樹的局部最低3層變化

2.3 分裂與合并

l Que中體素狀態(tài)值改為0時，需要分解體素，即需要進行分裂處理。b Que中體素狀態(tài)值改為非0時，需要合并兄弟體素，即需要進行合并處理。

分裂處理：在刪除lQue中的體素時，此體素需要分裂從而產(chǎn)生更細精度的體素，這些體素將需要分別插入到兩個隊列中。如圖4中的節(jié)點1的S（V）值由－1變?yōu)?時，體素將分裂為八個子體素，若體素達到最高精度時，那么節(jié)點10和13將插入到b Que中，其他子節(jié)點插入到l Que中。

合并處理：在刪除bQue中的體素時，當兄弟節(jié)點的S（V）值都不為0且相等時，需要將該體素的兄弟體素全從2個隊列中刪除，并修改父親節(jié)點的狀態(tài)，并需要進一步判斷兄弟節(jié)點的狀態(tài)。如圖4中的節(jié)點70的S（V）值由0變?yōu)椋?時，此時其兄弟體素狀態(tài)全為－1，需要合并兄弟節(jié)點，即修改父親節(jié)點7的狀態(tài)值為－1，并將節(jié)點7添加到l Que中，同時從b Que中刪除節(jié)點70，從l Que中刪除它的兄弟節(jié)點。

3 試驗結果與分析

可用C＋＋語言在可視外殼仿真計算平臺上實現(xiàn)具有幀間一致性的可視外殼生成算法［6］，仿真試驗的硬件環(huán)境為：主頻為2.80GHZ的Pentium（R）Dual－Core E6300雙核 CPU、NVIDIA GTX260顯卡、2.00GB內(nèi)存；軟件環(huán)境為：Windows XP、VC6.0以及三維圖形標準庫Open GL。利用仿真試驗平臺提供的接口開發(fā)的幀間一致性可視外殼仿真程序運行效果如圖4所示，圖中左上窗口為模擬可視外殼建模的虛擬環(huán)境，左下窗口顯示初始狀態(tài)下獲取的相機圖像及其側影輪廓圖，右下窗口為模擬相機獲取到的圖像，右上窗口顯示重建的模型（體素采用線框模式繪制）。

圖4 仿真平臺效果圖

仿真試驗使用兔子三維模型，獲取不同視點的五幅相機圖像，分別用基本八叉樹和幀間一致性方法重建物體幾何模型。采用的體素剖分精度分別為64×64×64、128×128×128、256×256×256，相機圖像分辨率分別為512×512，表1分別給出了不同情況下兩種算法的運行時間和加速比。

表1 八叉樹傳統(tǒng)算法與幀間一致性算法時間性能

4 結 論

在已有的基于八叉樹動態(tài)物體可視外殼算法基礎上，提出了一種基于幀間一致性的動態(tài)物體可視外殼算法。利用八叉樹及雙隊列結構，通過計算前幀中體素的狀態(tài)來快速計算當前幀中的邊界體素，從而減少體素計算數(shù)，試驗結果表明，在物體運動速度較小的情況下，算法計算效率得到有效提高，從而在較小計算資源的條件下可實時重建物體三維模型。

［1］ 蘇煥煥.安全多面體可視外殼及應用研究［D］.東營：中國石油大學計算機與通信工程學院，2010.

［2］ BO P，GANG Q.Online gesture spotting from visual hull data［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（6）：1175－1188.

［3］ LAURENTINI A.The visual hull concept for silhouette based image understanding［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1994，16（2）：150－162.

［4］ FRANCO J，BOYER E C，BOYER E，et al.A distributed approach for real time 3D modeling：Proc of the 2004 Conference on Computer Vision and Pattern Recognition［C］.Washington：IEEE Computer Society，2004：31－38.

［5］ 李濤.基于圖像的建模技術研究［D］.長沙：國防科學技術大學機電工程與自動化學院，2007.

［6］ 陳國軍，牛玉美，申寶明.多視圖像的三維重建并行計算仿真平臺［J］.系統(tǒng)仿真學報，2012，24（1）：85－88.

TP391.9 < class="emphasis_bold">［文獻標識碼］A［文章編號］

1673－5935（2012）01－0024－03

2011－12－29

中央高?；究蒲袠I(yè)務費專項資金資助項目（09CX04034A）；國家“973”項目（2009CB320805）

李 霞（1983－），女，遼寧燈塔人，中國石油山東銷售公司調(diào)度運輸處助理工程師，主要從事圖形圖像處理研究。

［責任編輯］ 彭麗娟