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

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

0 引言

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

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

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

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

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

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

1 光場(chǎng)模型Light field

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

1.1 光場(chǎng)信息的獲取

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

1.2 光場(chǎng)信息分割

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

2 算法流程

算法流程圖如圖1所示。

圖1 算法流程

算法分為編碼和解碼2個(gè)部分。編碼部分生成表面光場(chǎng)信息，即表面紋理和視點(diǎn)紋理；解碼部分則是生成新視點(diǎn)視圖。

2.1 編碼部分

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

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

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

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

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

2.2 解碼部分

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

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

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

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

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

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

3.1 頂點(diǎn)可見性計(jì)算及采樣的并行實(shí)現(xiàn)

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

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

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

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

圖3 頂點(diǎn)計(jì)算任務(wù)分配

頂點(diǎn)可見性計(jì)算及采樣的并行偽代碼如下。

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

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

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

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

圖4 虛擬視點(diǎn)的生成

虛擬視點(diǎn)生成及采樣的并行位代碼如下。

4 實(shí)驗(yàn)結(jié)果與分析

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

表1 實(shí)驗(yàn)數(shù)據(jù)包

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

表2 頂點(diǎn)光場(chǎng)矩陣生成的加速比 ms

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

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

5 結(jié)語

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

[1]沈燕飛,代鋒,張勇東.交互式三維視頻技術(shù)[J].信息技術(shù)快報(bào),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è)計(jì)[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]王薊翔,張揚(yáng).基于矩陣分解的壓縮感知算法研究[J].通信技術(shù),2011,44(06):138-140.