一種魯棒的可視外殼生成算法
2010-01-01 00:00:00程銘婁銀霞劉先鋒文高進
計算機應用研究 2010年2期
摘 要:針對各種傳統可視外殼生成算法中數據冗余、精確度低、健壯性不足等問題， 提出了一種新的可視外殼生成算法，即采用加權線段求交、線段集合中心線性過濾、多邊形邊界檢測等方法重建物體模型。與傳統方法相比，本算法能夠更穩定地計算線段交集，表面邊界提取更加準確，重建結果精確逼近真實物體。實驗表明， 通過該算法計算的物體可視外殼能夠更好地逼近真實模型，精度高。
關鍵詞:可視外殼; 側影輪廓; 線段相交; 三維重建
中圖分類號:TP391.41
文獻標志碼:A
文章編號:1001-3695(2010)02-0751-03
doi:10.3969/j.issn.1001-3695.2010.02.097
Robust visual hull computation method
CHENG Ming1， LOU Yin-xia1， LIU Xian-feng1， WEN Gao-jin2
(1.College of Mathematics Computer Science， Hunan Normal University，Changsha 410006， China; 2.Shenzhen Institute of Advanced Technology， Chinese Academy of Sciences， Shenzhen Guangdong 518055， China)
Abstract:The traditional volumetric visual hull generating methods were not applicable to huge-volume objects due to redundant calculations. The methods based on segments intersections were sensitive to input perturbations and were hence lack of robustness. This paper represented a new algorithm for reconstructing an object’s visual hull from its silhouette. Compared with traditional methods， the approach employs the maximum overlap line segments intersection to calculate line segment intersection stably. In addition， the extraction of the border surface is more accurate. The experiments show that the approach is more accurate and the result of reconstruction approximates the real objects better.
Key words: visual hull; silhouette contour; segments intersection; 3D reconstruction
0 引言
快速獲取物體三維造型技術在計算機視覺、虛擬現實、人工智能、機械制作、數字娛樂、文物保護等領域有著廣泛的應用。目前，三維模型獲取技術主要有利用建模軟件構造三維模型、通過儀器設備獲取三維模型、利用影像序列來重建場景三維模型這三種方法[1]。第一種方法利用建模軟件如3DMax、AutoCAD構造三維模型，可以精確地構造虛擬物體和渲染奇特的效果，但相應軟件使用復雜，建模周期長;第二種方法利用三維掃描設備獲得三維信息，建模精度高，周期短，但設備較昂貴;第三種方法根據影像序列建模，用戶只需使用普通數碼相機圍繞目標對象進行拍攝，通過相片影像信息重建模型，其數據采集設備簡單、效率高。因此，基于影像序列的三維重建以其簡單的操作、低廉的設備、較高的效率已成為計算機視覺的重要研究對象。
本文研究基于方法三的可視外殼[2]生成算法?？梢曂鈿さ乃枷胧怯晌矬w在一組二維照片上的側影輪廓信息來重建物體原始模型的技術。其中二維照片的拍攝角度越多，重建結果越逼近真實物體，如圖1所示。
一般基于可視外殼的算法可以定義為
vhR=∩r∈Rvhr
其中:vhr為拍攝相機視點和圖片側影輪廓線所形成的錐體，錐體的母線穿過圖片r上的側影輪廓線，vhr就是物體重建后的可視外殼，它是由多個錐體求交所產生的結果;R是照片的集合。由于相機視點和側影輪廓所產生的錐體把物體包括在內，只能得到與真實物體逼近的物體模型。目前基于可視外殼技術的算法主要分為兩大類[3]，即體素裁剪和表面重建。
1)體素裁剪方法 Martin等人[4]最早提出了從不同角度的相機拍攝到的照片生成可視外殼的體素方法。后來，Chien等人[5]提出了在平行拍攝條件下利用八叉樹結構來表示可視外殼的方法，通過八叉樹的數據結構存儲空間裁剪的體素信息，這種空間表達式能高效地處理空間的分割與存儲信息，提高了運算效率。Szeliski等人[6]在Chien等人的基礎上提出了在任意角度拍攝的八叉樹改進算法?？傮w上說，基于體素裁剪的方法有以下幾個缺點:a)重建出來的可視外殼精確度較低;b)時間復雜度、空間復雜度較高，即使在引入八叉樹的存儲結構后，問題仍然沒有得到很好的解決;c)表面是由相互獨立的體素元素間接生成的，相互之間缺乏緊密聯系且多數的情況下會產生冗余信息。隨著多處理器并行技術的發展，體素剪裁方法可以得到很好的改進[7]。
2)表面重建方法 該方法能夠解決體素方法的第三個缺點。Matusik等人[8]提出了多邊形求交的方法，此算法用相機的拍攝視點與圖片上的側影輪廓線所形成的錐體直接求交生成可視外殼。后來，Franco等人[3]使用了極線幾何與邊界檢測的方法直接重構物體表面，提高了算法效率。這種方法所包括的主要步驟是:多面體求交運算、多邊形求交運算、檢測邊的運算[3]。根據每個錐體的側面去切割物體表面，直接記錄物體的面信息。這種方法雖然解決了表面之間的連貫性，但隨著拍攝照片數量的增多，物體的重建表面會非常復雜。大部分表面重建方法的穩定性都會受到邊界點的影響，經常會導致重建表面不完整，尤其是當重建的物體有著復雜的拓撲結構時。除此之外，在通過表面重建方法建模時，還需要考慮不同的約束條件，如平滑約束性[9]、遮擋邊緣和紋理邊緣[10]、部分遮擋[11]、可靠性[12]。
基于以上基礎，本文通過加權線段求交，線段集合中心線性過濾與線段集合多邊形檢測的方法計算物體的可視外殼，克服傳統線段求交與表面邊界檢測不準確的缺點，同時保證算法結果的精確度，增強了算法的魯棒性。
1 魯棒的可視外殼生成算法
1.1 算法概述
可視外殼是由多個相機視點和圖片側影輪廓線構成的錐體求交得到的結果，如果將圖像側影輪廓線離散為緊密相連的點，就可以將物體看成是從相機視點到側影輪廓離散點的所有射線的交集結果。物體表面所有線段的集合不僅構成了物體的可視外殼，而且這些線段集合之間有相互關聯的空間關系，這樣就可以通過線段集合檢測多邊形，再通過多邊形集合重構物體表面，這也是本算法的理論基礎。本文所提出的算法主要包含如下幾個步驟:
a)圖像處理。首先得到從各個視角拍攝的用于重建的物體照片，并對這些照片作預處理操作(提取物體輪廓信息)。
b)線段集合加權求交。錐體母線穿過其他錐體時，會產生交線段或切點，記錄母線穿過其他錐體的所有交線段結果，對這些線段結果進行交運算得到的交集即是母線在可視外殼的部分。通過記錄所有錐體母線所產生的交集結果，即得到可視外殼模型的線段集合。
c)線段集合中心線性過濾。線段求交的結果只能得到可視外殼的近似結果。其中會有受到噪聲的影響，通過中心線性過濾的方法平滑線段集合，使線段集規則排列整齊。
d)表面重建。從已經平滑后的線段集合中構造多邊形，再通過多邊形集合計算相鄰多邊形之間的公共邊界，重構物體的表面模型。
本文的框架如圖2所示，下面詳細討論算法的三個部分。
1.2 圖像處理
一般而言，相機所拍攝的圖像平面是由一系列二維像素點表示， 每一個像素點包含了物體表面某一點在當前視線方向上的亮度信息，圖像中亮度明顯而急劇變化的點就是物體的邊緣和邊緣點。在本算法中，需要正確獲取物體在每幅照片上的側影輪廓線，一般會采用單一色調作為背景拍攝物體圖像，便于物體和背景分離。使用最優的階梯型邊緣檢測算法(Canny邊緣檢測算子)提取圖像輪廓。
1.3 加權線段求交算法
對于一條從相機視點向側影輪廓邊緣射出的射線會穿過其他所有錐體，并且與每個錐體都會有相交的情況。其相交結果可能是一條交線段或也可能切于一點，那么這條射線會被其他錐體分割為多條相互之間重疊或存在部分重疊的線段集合。將這些線段集合進行求交運算得到的結果就是物體可視外殼信息。但這些線段集合并不一定能得到準確的交集結果，因為它們不能準確地決定射線在每一個錐體內的部分，所以線段集合在進行交集運算后會產生空集的現象。在此，本文提出了加權線段求交的方法計算線段集合的近似最大交集。
加權線段求交算法是通過記錄線段集合中加權次數最多的公共部分為線段集合的交集結果，最大程度地得到這些線段的近似交集結果，彌補傳統求交算法中信息缺失問題。
算法描述如下:
假如{Si｝Ni=1是一組在R中的線段集，并且Si=∪k∈{1，2，…，mi}[aik，bik]。其中aik≤bik≤aik+1;{Si｝Ni=1中的所有線段在進行加權線段求交運算后結果不是一個空集:SMOLSI=∩j∈ESj，加權因子為|E|， E{1，2，…，N}。
輸入: 一組在R中的線段集合{Si｝Ni=1，Si=∪k∈{1，2，…，mi}[aik，bik]。
輸出: 加權線段求交結果SMOLSI=∩j∈ESj。
a)找到{aik}i=N，k=mii=1，k=1中的最小值a0，{bik}i=N，k=mii=1，k=1中的最大值b0;
b)建立一個加權線段集合SOLSS=[a0，b0]，一個加權計數器l0=0，一個元素計數器M = 1;
c)從i=1到N{S=;從j=1到mi{從k=0到M {如果s=[aij，bij]∩[ak，bk]，且s≠{插入s到S中，同時加權計數器變為lk+1;插入[ak，bk]/s到S中，同時加權計數器為lk;從SOLSS中刪除[ak，bk] ; }}}SOLSS=SOLSS∪S;M=|SOLSS|; }
d)從M=|SOLSS|中得到加權計數L。
SMOLSI={[ai，bi]:[ai，bi]∈SOLSS。其中加權計數器為L;}。
其中，如果∩Ni=1Si≠， 那么SMOLSI就是線段的加權線段交集結果，如圖3(a) 所示，SMOLSI=∩4i=1Si線段的顏色越來越暖，它的加權系數就越高，線段的最大加權系數為4;如果∩Ni=1Si=，那么SMOLSI=∩Ni=1Si，SMOLSI=T1∪T2，此時線段的最大加權系數為3，如圖3(b)所示;圖3(c)展示的是一個復雜的例子，其中最大加權系數為9。
1.4 線段中心線性過濾方法
圖像上的側影輪廓離散為緊密相連的像素點信息，從相機視點到側影輪廓像素點的射線集合同樣是緊密排列。通過加權線段求交的方法可以有效地計算出一條射線和其他錐體相交后所得的交集結果，對側影輪廓的所有射線計算得到的交集結果集合應該是規則的緊密排列，而通過加權線段求交的方法計算一條射線中的線段集合的近似交集結果會受到噪聲的影響產生偏差，所以，本文使用線段中心線性過濾的方法來調整求交后的射線集合排列情況，使結果排列整齊，有顯著趨勢。
算法描述如下:
假如{Si}Ni=1是一組在R中的線段集合，并且Si=[ai，bi]，其中ai≤bi，這組線段集合的中心線性過濾器{S′i}Ni=1:
li=bi-ai;
l′i=∑Nj=-Nhjli+1，其中∑Nj=-Nhj=1，N∈{3，5，7};
a′i=(bi+ai)/2-l′i/2;
b′i=(bi+ai)/2+l′i/2;
如果直接使用a′i=∑Nj=-Nhjai+j，并且b′i=∑Nj=-Nhjbi+j進行過濾，那么將出現平滑后的線段集合整體漂移的情況。通過加權線段求交算法所得到的可視外殼模型的線段集合是對物體可視外殼的最大近似結果，對于存在的異常線段信息，可以通過中心線性過濾的方法把不規則的線段集合規整化，使線段集合整體趨勢走向明顯，便于從中檢測多邊形重構物體表面。圖4給出了原始線段集合與過濾后線段集合的對比。
1.5 表面重建
如果一個光錐平面對于n張輸入照片可見，則該光錐平面會相交于n個相片錐體，顯然只有它們的交集才會落在最終的多面體可視外殼的內部。該光錐平面與其他所有相片錐體相交得到的多邊形即為物體的可視外殼信息，該相交過程是增量計算過程，圖像的輪廓信息越復雜計算復雜度越高。本文采用了基于多邊形距離的多邊形檢測方法重建物體的表面。
算法思想:首先通過每條線段的法向量信息對線段集合進行分類，即法向量相近線段分為一類。在進行分類時，需要設定一個合理的判斷法線相近的閾值來標記線段集合。根據已分類的線段集合，可以判斷線段集合中哪些線段共面，然后通過平面的截距d來區分不同的平面，截距d為每個平面到原點的距離。最后，通過已標記的距離矩陣D，按順時針或逆時針方向搜索與已知平面相鄰的平面，進行面面相交計算平面之間的邊界，記錄邊界信息，從任意一條邊界出發順時針計算相鄰邊界之間的交點作為多邊形的頂點，依次計算直到回到開始邊界。當對所有平面作上述處理后，就得到了物體可視外殼的多邊形表面信息。
算法描述如下:
輸入: 一組在R中的線段集合{Si}Ni=1，(Si=[ai，bi])并且與之對應的法線向量集合為{ni}Ni=1。
輸出: 多邊形{Pi}Ni=1。
a)根據法向量集合{ni}Ni=1劃分線段集合{Si}Ni=1到不同的類型{Ci}Mi=1中;
b)根據以分類的線段集合(法線信息分類)，計算每組線段集合所產生的平面類，Fj:p#8226;nj-dj=0;
c)根據距離dj分割每個平面類得到多個平面信息;
d)計算每兩個平面之間的距離得到距離矩陣D，Dij=dis tan ce(Fi，Fj)，0≤i≤K，0≤j≤K;
e)通過距離矩陣D在每一個面中查找相鄰的平面，并計算面與其相鄰面之間的交線;
f)查找相交的點，為每個面得到精確的邊界。
圖5給出表面重建算法示意圖，相交計算中的每一個平面的臨時邊界，需要計算與之相鄰的所有平面之間的交來確定邊界的長短。
2 算法仿真結果與分析
本文已經用C++語言和OpenGL在AMD Athlon2.21 GHz，1 GB的微機上實現了上述可視外殼生成算法，并對若干實例進行測試。本文的測試模型都是利用POSER造型軟件生成的。在本算法中，需要準確地獲取物體在每幅圖片上的側影輪廓線，將物體和背景分離開并分別記錄，搭建拍攝場景拍攝照片，采用邊界檢測算法分離圖片的輪廓和背景。通過C++和OpenGL實現算法時，實驗數據不包括照片的拍攝和側影輪廓線的提取時間。
第一個實驗是以12幅分辨率為620×620照片序列為例對算法進行了實現和實驗，測試對象是人體模型。圖6給出了算法的重建過程，重建結果展示了物體的正面圖、側面圖以及背面圖，很好地再現了三維模型和相機的位置及姿態信息得到了較好的重建結果。
第二個實驗是在相同分辨率、不同輸入照片個數條件下對可視外殼重建結果的影響，實驗對象為人體跑步模型。從表1可以看出，物體在拍攝角度越多(拍攝相機數越多)時重建結果越逼近于真實物體。當相機數目達到某一上界，重構結果趨于穩定(最大逼近原始模型)如圖7所示。
3 結束語
與傳統算法相比，本文算法具有較強的抗干擾力，魯棒性強，保留了體素方法和表面重建方法的優勢，在進行物體可視外殼的重建過程中能夠更好地逼近物體的真實模型，精度高。對于物體被遮擋而使重建結果丟失某些信息的情況，在這里可以有兩種解決方法:a)建立一個完整可視外殼的原始模型來修復其他幀的重建結果;b)利用更多的時間序列來修補物體在重建中缺失信息幀。在未來的工作中，將進一步完善此算法，使其能夠更加精確地處理任意遮擋情況的模型重建。
參考文獻:
[1]蔡欽濤.基于影像的三維重建技術研究[D].杭州:浙江大學， 2004.
