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

李 霞

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

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

李 霞

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

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

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

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

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

可視外殼算法總體上分為兩大類：基于體的方法與基于面的方法［5］。基于體的可視外殼方法能夠重建具有復(fù)雜拓?fù)浣Y(jié)構(gòu)的物體，算法穩(wěn)定。基于面的可視外殼方法是直接對(duì)可視錐體求交，可直接得到物體的三維網(wǎng)格，但這種方法需要復(fù)雜的幾何計(jì)算，存在數(shù)值不穩(wěn)定的問題。本文采用體素方法重建三維模型。

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

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

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

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

1.2 八叉樹算法

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

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

圖1 簡(jiǎn)單的兩層八叉樹

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

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

2 幀間一致性體素處理

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

2.1 數(shù)據(jù)結(jié)構(gòu)

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

圖2 體素?cái)?shù)據(jù)結(jié)構(gòu)

2.2 隊(duì)列處理

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

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

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

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

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

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

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

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

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

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

2.3 分裂與合并

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

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

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

3 試驗(yàn)結(jié)果與分析

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

圖4 仿真平臺(tái)效果圖

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

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

4 結(jié) 論

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

［1］ 蘇煥煥.安全多面體可視外殼及應(yīng)用研究［D］.東營(yíng)：中國石油大學(xué)計(jì)算機(jī)與通信工程學(xué)院，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］ 李濤.基于圖像的建模技術(shù)研究［D］.長(zhǎng)沙：國防科學(xué)技術(shù)大學(xué)機(jī)電工程與自動(dòng)化學(xué)院，2007.

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

TP391.9 < class="emphasis_bold">［文獻(xiàn)標(biāo)識(shí)碼］A［文章編號(hào)］

1673－5935（2012）01－0024－03

2011－12－29

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

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

［責(zé)任編輯］ 彭麗娟