一種基于建模的圖像渲染算法的并行實現(xiàn)﹡

于昊，郭 立，劉 鵬，王成彰

（中國科學(xué)技術(shù)大學(xué) 電子科學(xué)與技術(shù)系，安徽 合肥 230027）

0 引言

隨著多媒體技術(shù)的不斷發(fā)展，傳統(tǒng)的二維視頻已不能滿足人們的生活工作的需要。相對于二維視頻，三維視頻增添了視覺效果的現(xiàn)實感，并且能夠讓用戶自由選擇視角，是一種交互性很強的媒體。三維視頻技術(shù)還可以廣泛應(yīng)用于數(shù)字電視，遠(yuǎn)程教育，遠(yuǎn)程工業(yè)控制，三維視頻會議系統(tǒng)，和虛擬現(xiàn)實系統(tǒng)等方面。

三維視頻技術(shù)[1]的關(guān)鍵在于3D渲染方法。傳統(tǒng)的3D渲染方法有，基于圖像的建模技術(shù)（IBM）和基于圖像的渲染技術(shù)（IBR）。

IBM是傳統(tǒng)的圖形學(xué)立體成像方法。通過計算場景的精細(xì)模型和拍攝少量的環(huán)繞視點圖像，借助空間坐標(biāo)系與屏幕坐標(biāo)系間的映射規(guī)則進(jìn)行采樣與投影，繼而獲得很好的渲染效果。其優(yōu)點是紋理數(shù)據(jù)量小。然而由于渲染結(jié)果的好壞受到重建模型的精確度的影響，所以對模型的精確度要求較高，對于簡單場景可實現(xiàn)實時渲染，但在處理復(fù)雜場景時則將大量時間耗費在場景建模部分上，不利于實時渲染。

IBR根據(jù)已知的圖像來合成新視圖，其優(yōu)點是無需對場景進(jìn)行建模，計算量與場景復(fù)雜度無關(guān)，而且渲染結(jié)果具有照片級的逼真效果。1996年，M.Levoy和P.Hanrahan首次提出了基于Light field[2]的渲染方法；2006年，清華大學(xué)設(shè)計了一個8×8CCD傳感器陣列作為光場采集系統(tǒng)[3]，使用Light field算法實現(xiàn)了實時交互式動態(tài)光場的傳輸系統(tǒng)。由于這種方法沒有幾何模型作為約束，為避免模糊現(xiàn)象，導(dǎo)致采樣過于密集，表面光場數(shù)據(jù)量大，不利于光場數(shù)據(jù)的存儲與傳輸。

結(jié)合以上兩種算法的優(yōu)點，在此提出了一種基于建模的圖像渲染技術(shù)IBMR[4]，采用傳統(tǒng)的Light field方法，通過增加粗糙模型信息來減少視點采樣。

近年來，多核計算機發(fā)展迅速，半導(dǎo)體廠商們正致力于在單個基片上集成更多的執(zhí)行核，而不是提高處理器的主頻，四核和八核的計算機已進(jìn)入市市場。隨著多核計算機的應(yīng)用推廣，基于多核的算法并行設(shè)計逐漸成為研究熱點[5-7]。對于3D渲染算法中涉及的大量計算，可通過多核并行設(shè)計實現(xiàn)。1997年，OpenMP標(biāo)準(zhǔn)形成[8]，它是一種用于編寫可移植的多線程應(yīng)用程序的API，其優(yōu)點是在不影響實驗結(jié)果的前提下，通過多核處理器加速串行程序。由此采用OpenMP對IBMR算法進(jìn)行了并行化分析改進(jìn)[9]。實驗表明，本算法可以獲得比較滿意的渲染效果，而且算法的關(guān)鍵部分在雙核處理器上平均加速比可以達(dá)到1.70。

1 光場模型Light field

Light field的思想就是建立一個光場函數(shù)以記錄目標(biāo)的表面光場信息，即目標(biāo)的表面顏色信息。

1.1 光場信息的獲取

采用環(huán)繞場景目標(biāo)拍攝的方式設(shè)置相機，拍攝不同視點下的目標(biāo)圖像，然后通過三維立體重構(gòu)計算目標(biāo)的三維網(wǎng)格模型，根據(jù)相機的定標(biāo)參數(shù)，確定目標(biāo)與相機的投影關(guān)系。

1.2 光場信息分割

假設(shè)光線在空間中傳播輻照度不變，那么七維的全光函數(shù)可以簡化為四維P(r,s,θ, φ) ,其中(r, s) 表示目標(biāo)表面上一點，(θ, φ)表示視線方向。由于采用的是三維網(wǎng)格模型，所以將目標(biāo)表面光場信息分割到所在三角面的頂點上，如式（1），PΔ(r, s,θ, φ)為三角面上像素的光場信息，vj為三角面的頂點:

2 算法流程

算法流程圖如圖1所示。

圖1 算法流程

算法分為編碼和解碼2個部分。編碼部分生成表面光場信息，即表面紋理和視點紋理；解碼部分則是生成新視點視圖。

2.1 編碼部分

由于采用的3D模型是三角面網(wǎng)格模型,為了避免渲染結(jié)果出現(xiàn)顏色過渡不連續(xù)的現(xiàn)象,所以編碼部分選用的采樣單元是模型頂點的三角面環(huán)。

首先計算每個頂點的可見視點列表，三角面環(huán)的采樣在可見視點圖像中進(jìn)行。然后建立世界坐標(biāo)系與視點屏幕坐標(biāo)系間的映射關(guān)系，計算投影矩陣M。按照 OpenCV的標(biāo)準(zhǔn)，可以設(shè)置模型視點矩陣Mmodelview和視錐體投影矩陣Mproj，根據(jù)這2個矩陣可以完成世界坐標(biāo)系到視點屏幕坐標(biāo)系的投影。對于每個可見視點圖像，將 3D模型投影到可見視點屏幕坐標(biāo)系中，以三角面環(huán)為單位進(jìn)行采樣。

由于要進(jìn)行自由視點觀測，所以要生成虛擬視點以及虛擬視點下的采樣信息。采用 Delaunay三角剖分法來實現(xiàn)虛擬視點的生成。虛擬視點下的采樣信息則通過真實視點的采樣信息插值產(chǎn)生，生成頂點的光場矩陣 Pvj，如式（2），M為三角面環(huán)采樣點數(shù)，N為可見視點數(shù)，其中包括可見虛擬視點。

由于矩陣Pvj的冗余度高，不利于數(shù)據(jù)傳輸，需要提取Pvj的主導(dǎo)成分。采用矩陣分解[10]的方式，如式（3）所示，其中稱gk(r, s)為表面紋理，稱hk(θ, φ)為視點紋理:

矩陣分解完成后，可采用一些經(jīng)典的壓縮算法對結(jié)果進(jìn)行進(jìn)一步壓縮處理，如S3TC等。

2.2 解碼部分

首先對壓縮碼流進(jìn)行預(yù)處理，完成坐標(biāo)變換，投影，屏幕映射等操作。

然后以三角面為單元，以3個頂點的局部坐標(biāo)系作為參考系，先分別計算三角面內(nèi)像素的紋理坐標(biāo)，從表面紋理中讀取相應(yīng)的紋理值，(rm,sm)，再計算3個頂點局部坐標(biāo)系下視點的m m紋理坐標(biāo)，從視點紋理中讀取視點紋理，hvj(θn,φn)，通過式(4)可得到三角面內(nèi)像素的值:

3 算法的并行實現(xiàn)

并行實現(xiàn)方式有任務(wù)分解和數(shù)據(jù)分解。任務(wù)分解是將一個算法分為若干個任務(wù)模塊，根據(jù)模塊間的獨立性來判別是否可以并發(fā)執(zhí)行，由于是在串行算法上進(jìn)行并行優(yōu)化，各模塊有嚴(yán)格的執(zhí)行順序，所以不滿足任務(wù)分解的條件；數(shù)據(jù)分解則是對待處理數(shù)據(jù)集進(jìn)行分組，要求各組數(shù)據(jù)是相互獨立的，可通過派生線程完成數(shù)據(jù)的并行處理。數(shù)據(jù)分解是一種比較普遍的并行實現(xiàn)方式。

通過對算法的分析，編碼部分的關(guān)鍵在于頂點光場矩陣的生成，因為頂點光場矩陣的分解壓縮可采用一些經(jīng)典的高效壓縮算法，所以矩陣壓縮部分可不作并行考慮；解碼部分則是計算三角面像素的坐標(biāo)以及檢索表面紋理和視點紋理，這部分的耗時要遠(yuǎn)小于編碼部分，所以解碼部分也不需并行實現(xiàn)。

由圖1可知，頂點光場矩陣的生成可分為頂點可見性計算及采樣和虛擬視點生成及采樣，實驗中采用雙核處理器實現(xiàn)。

3.1 頂點可見性計算及采樣的并行實現(xiàn)

根據(jù)攝像機標(biāo)定，先計算攝像機中心在世界坐標(biāo)系中的坐標(biāo) O=(XC，YC，ZC）。假設(shè)三角面的3個頂點的世界坐標(biāo)為X1,X2,X3，三角面中心坐標(biāo)為→)/3，歸一化的三角面法向量 N。計算與N的夾角θ的余弦值以判定三角面的可見性:若cosθ大于0，則認(rèn)為可見，反之，則認(rèn)為不可見。頂點的可見性判別:頂點的三角面環(huán)中只要有一個三角面被認(rèn)為是不可見的，則該頂點被認(rèn)為不可見。由此，得出每個頂點的可見視點列表。

頂點采樣。對于一個真實視點圖像，根據(jù)攝像機標(biāo)定，將 3D模型投影到視點的屏幕坐標(biāo)系中，將屏幕坐標(biāo)系中的投影三角面與二維平面上的等腰直角三角形對應(yīng)，如圖2所示。采用基于重心坐標(biāo)權(quán)重的顏色采樣計算每個采樣點 x的顏色值。

圖2 三角面與等腰直角三角形的對應(yīng)關(guān)系

由于各頂點的計算任務(wù)都是獨立的，所以采用數(shù)據(jù)分解的并行化方式。如果將每個頂點的可見性計算及采樣看作一個任務(wù)，各任務(wù)相互獨立，所以可采用數(shù)據(jù)分解的方式實現(xiàn)。解決方案如圖3所示，假設(shè)有3000個待處理的頂點，平均分為2組由2個核執(zhí)行完成。

圖3 頂點計算任務(wù)分配

頂點可見性計算及采樣的并行偽代碼如下。

3.2 虛擬視點生成及采樣的并行實現(xiàn)

虛擬視點生成。首先建立頂點的局部坐標(biāo)系:以頂點的法向量N作為局部坐標(biāo)系的Z軸，然后再空間中任選一垂直于N的向量S作為X軸，以S×N作為Y軸，將所求得的向量單位化，即得到頂點的局部坐標(biāo)系。

將可見的參考視點投影到頂點局部坐標(biāo)系中,采用Delaunay三角剖分法，如圖4所示。將單位圓內(nèi)的虛擬視點加入到頂點的可見視點列表。

采用基于重心坐標(biāo)的權(quán)重插值法計算虛擬視點與真實視點的權(quán)重，由真實視點的采樣值插值產(chǎn)生虛擬視點的采樣值。

圖4 虛擬視點的生成

虛擬視點生成及采樣的并行位代碼如下。

4 實驗結(jié)果與分析

表1為實驗數(shù)據(jù)，采用的實驗平臺是 Intel Core2 T5450@1.66GHz，1.67 GHz。程序用 C++編譯,用OpenMP2.0實現(xiàn)并行部分。

表1 實驗數(shù)據(jù)包

表2為頂點光場矩陣生成的加速比，從實驗數(shù)據(jù)可知，兩個模塊的并行計算均達(dá)到了比較滿意的加速效果。雙核平臺上的加速比的理論值為2.0，然而由于線程的創(chuàng)建和銷毀，以及線程間的同步開銷，讀寫鎖操作等原因，不能達(dá)到理論值。另一個制約加速比的因素是計算負(fù)載均衡的問題。由于OpenMP的線程創(chuàng)建與調(diào)度都是操作系統(tǒng)隨機分配完成的，所以會產(chǎn)生負(fù)載不均的情況。在頂點的可見性計算及采樣模塊的并行中，每個頂點的三角面環(huán)的采樣點數(shù)目不同，兩個核所承載的計算量無法均衡，從而降低了加速比；在虛擬視點生成的模塊中，由于各頂點的可見視點數(shù)量不均，導(dǎo)致在Delaunay三角剖分時的計算復(fù)雜度有較大的差異，所以這一模塊受負(fù)載不均的影響較大，加速比較比前一模塊要低。

表2 頂點光場矩陣生成的加速比 ms

算法渲染的結(jié)果如圖5所示,圖5(a)與圖5 (c)為原始視圖，圖5(b)與圖5 (d)為渲染結(jié)果。從實驗結(jié)果可知，算法的渲染結(jié)果還是另人滿意的。

圖5 渲染結(jié)果對比

5 結(jié)語

提出了一種基于建模的圖像渲染技術(shù)的并行實現(xiàn)方法。在已知目標(biāo)的三維網(wǎng)格模型和環(huán)繞視點圖像的前提下，對頂點的三角面環(huán)進(jìn)行采樣，獲得目標(biāo)的表面光場信息，并通過三角剖分法生成虛擬視點，從而達(dá)到在自由視點下觀測和漫游目標(biāo)的目的。為加快程序的運行速度，對算法的關(guān)鍵部分進(jìn)行了并行化分析和改進(jìn)，實驗表明，并行部分的平均加速比達(dá)到了 1.70。下一步工作是對矩陣壓縮部分進(jìn)行并行化分析及加速[11]，以及探討本算法在行為檢測方面上的應(yīng)用。

[1]沈燕飛,代鋒,張勇東.交互式三維視頻技術(shù)[J].信息技術(shù)快報,2005,3(08):13-31.

[2]LEVOY M, HANRAHAN P.Light Field Rendering[C]//Proc. SIGGRAPH’96. New Orleans:ACM SIGGRAPH,1996:31-42.

[3]LIN Y,DAI Q,XU W. A Real Time Interactive Dynamic Light Field Transmission System[C]//Multimedia and Expo, 2006 IEEE International Conference.Toronto:IEEE Conference Publications,2006:2173-2176.

[4]CHEN Wei-Chao, CHU M H. Light Field Mapping:Efficient Representation and Hardware Rendering of Surface Light Fields[C]// SIGGRAPH’2002.San Antonio:ACM SIGGRAPH,2002: 447-456.

[5]李金奎,郭立,池凌鴻,等. 一種分層置信傳播立體匹配并行算法[J].通信技術(shù),2012,45(07):57-61.

[6]LI Hongyu.Summarization of Program Development in Multi-core Environment[J].Computer and Information Science,2009,1(03):135-139.

[7]PAOLIERI M, QUINONES E, CAZORLA F J, et al.A Software-Pipelined Approach to Multicore Execution of Timing Predictable Multi-Threaded Hard Real-Time Tasks[C]//14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing.Newport Beach, CA:IEEE Confernce Publications,2011:233-240.

[8]多核系列教材編寫組編著.多核程序設(shè)計[M].北京:清華大學(xué)出版社,2007.

[9]REN G,CHEN G.A Parallel Processing of View-Dependent Visual Hull Texture Mapping[C]//2011 International Conference on Virtual Reality and Visualization.[s.l.]:VRV,2011:225-230.

[10]張賢達(dá).矩陣分析與應(yīng)用[M].清華:清華大學(xué)出版社,2006.

[11]王薊翔,張揚.基于矩陣分解的壓縮感知算法研究[J].通信技術(shù),2011,44(06):138-140.