融合多繪制算法的復(fù)雜場景性能瓶頸分析

李瀟瑤

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

現(xiàn)今，虛擬現(xiàn)實(shí)及游戲等領(lǐng)域的熱度逐漸高漲，這些領(lǐng)域都將面對來自用戶越發(fā)嚴(yán)苛的考驗(yàn)，尤其是場景的實(shí)時繪制性能及仿真程度。因此，針對這些領(lǐng)域中大規(guī)模復(fù)雜場景的性能調(diào)優(yōu)和瓶頸檢測受到了越來越多的關(guān)注。由于這些場景融合了多種不同的繪制算法，因此準(zhǔn)確判斷出場景性能瓶頸是很困難的。迄今，針對復(fù)雜場景繪制性能瓶頸的確定仍大多依據(jù)開發(fā)者對相關(guān)算法的了解及經(jīng)驗(yàn)人為推定，始終缺乏具體的定量分析。

本文以隨機(jī)森林算法為基本工具研究基于空間劃分的瓶頸分析方法?；陔S機(jī)森林算法本身的變量重要性（Variable Importance，VI）度量進(jìn)行特征重要性排序，確定每一子空間內(nèi)各繪制算法中相關(guān)影響因素的重要性，根據(jù)二八定律計(jì)算子空間內(nèi)變量重要性比例作為劃分空間優(yōu)劣程度的表達(dá)。實(shí)驗(yàn)結(jié)果表明，本文提出的瓶頸分析方法能夠有效劃分場景空間，并準(zhǔn)確分析得到場景子空間內(nèi)最重要的性能影響因子。

1 隨機(jī)森林

隨機(jī)森林（Random Forest，RF）是 Leo Breiman提出的一種集成機(jī)器學(xué)習(xí)方法，利用多棵決策樹對數(shù)據(jù)進(jìn)行判別與預(yù)測，同時可以評估各個變量的重要性。隨機(jī)森林主要應(yīng)用于回歸和分類問題，本文主要討論基于隨機(jī)森林的回歸問題。

1.1 隨機(jī)森林算法

隨機(jī)森林由多棵決策樹組合而成，每棵決策樹之間沒有任何關(guān)聯(lián)。隨機(jī)森林中每一棵決策樹都為二叉樹，其生長遵循自頂向下的分裂原則。隨機(jī)森林的構(gòu)建步驟如下：

（1）使用 Bagging（Bootstrap Aggregating）方法生成訓(xùn)練樣本。Bagging方法使用均勻采樣，每個樣本具有相同的權(quán)重。假設(shè)原始數(shù)據(jù)集的樣本個數(shù)為N，從中有放回地隨機(jī)選取N個樣本作為一個新的訓(xùn)練集，以此構(gòu)建一棵決策樹。通過Bagging方法得到的訓(xùn)練集并不是全部的樣本，每次未被抽取的樣本組成了袋外數(shù)據(jù)（Out-Of-Bag，OOB）；

（2）隨機(jī)選取特征（即指瓶頸因素，以下同）對決策樹的節(jié)點(diǎn)進(jìn)行分裂。假設(shè)共有M個特征，指定一個正整數(shù)m<

（3）每棵樹最大限度地生長，不進(jìn)行剪枝。

隨機(jī)生成訓(xùn)練樣本以及隨機(jī)選取特征進(jìn)行節(jié)點(diǎn)分裂，使得隨機(jī)森林中的決策樹都能夠彼此不同，降低了單棵決策樹之間的相關(guān)性，從而提升系統(tǒng)的多樣性以及決策效能；因此，隨機(jī)森林對于噪聲數(shù)據(jù)和存在缺失值的數(shù)據(jù)具有很好的魯棒性，具備分析復(fù)雜相互作用特征的能力。

圖1 隨機(jī)森林原理示意圖

1.2 變量重要性

變量重要性度量是隨機(jī)森林算法的一個重要特性。隨機(jī)森林常規(guī)的變量重要性度量是根據(jù)袋外數(shù)據(jù)（OOB）錯誤率計(jì)算得到，特征Xj Xj的得分統(tǒng)計(jì)量用表示。

基于袋外數(shù)據(jù)的變量重要性定義為袋外數(shù)據(jù)自變量值發(fā)生輕微擾動后的預(yù)測準(zhǔn)確率與擾動前預(yù)測準(zhǔn)確率的平均減少量。假設(shè)有K個Bootstrap樣本B1,B2，…，Bi，…，BK(1≤i≤K),特征Xj(1≤j≤M)的變量重要性度量按照如下方法計(jì)算：

（1）設(shè)置i=1，針對訓(xùn)練樣本Bi構(gòu)造決策樹Ti，并將袋外數(shù)據(jù)標(biāo)記為

（3）對于特征Xj，對中的特征Xj的值進(jìn)行擾動，擾動后的數(shù)據(jù)集記為，使用Ti對數(shù)據(jù)進(jìn)行預(yù)測，計(jì)算擾動后的預(yù)測錯誤率，記為

（4）對于i=1,2,…,K，重復(fù)步驟（1）至（3）；

（5）特征Xj的變量重要性度量通過如下公式進(jìn)行計(jì)算：

由于是通過OOB數(shù)據(jù)計(jì)算的，因此可以看作變量具有的影響能力，沒有影響力的變量在數(shù)值置換前后的OOB錯誤率不會發(fā)生改變，即數(shù)學(xué)期望

2 算法描述

本文針對融合了多種繪制算法的復(fù)雜場景，提出了一種基于空間劃分的瓶頸分析方法，利用隨機(jī)森林的變量重要性度量作為空間劃分的主要評判工具，根據(jù)二八定律決定空間劃分的主要終止條件，通過二叉樹的空間劃分來建立復(fù)雜場景的劃分路徑，逐次進(jìn)行迭代，最終得到瓶頸分析模型。

2.1 空間劃分

隨機(jī)森林的變量重要性度量僅僅在全局范圍內(nèi)對影響場景繪制性能的瓶頸因素進(jìn)行了定量的衡量，但是考慮到繪制算法與場景的空間相關(guān)性，可能出現(xiàn)以下幾種不同的情況：

（1）某一子空間內(nèi)不涉及任何繪制算法，即該空間內(nèi)僅僅繪制場景本身；

（2）某一子空間內(nèi)涉及若干繪制算法，即該空間內(nèi)存在物體及場景部分的交互；

（3）某一子空間內(nèi)涉及所有繪制算法，即該空間內(nèi)融合了物體及場景所有可能的交互作用，其繪制代價明顯高于其他空間。

因此，本文提出了在劃分子空間的基礎(chǔ)上進(jìn)一步分析性能瓶頸的思路，并在后續(xù)實(shí)驗(yàn)部分會展示針對融合了多種繪制算法的復(fù)雜場景進(jìn)行空間劃分的實(shí)際效果。

對于空間劃分的實(shí)現(xiàn)，本文約束了特征的空間劃分有效性，即只有與空間位置相關(guān)的特征允許用于劃分空間，反之則視為無效的劃分特征。當(dāng)根據(jù)特征Xj(1≤j≤M)用于劃分場景空間時，計(jì)算當(dāng)前空間內(nèi)的變量重要性并按降序排序，根據(jù)二八定律統(tǒng)計(jì)前20%特征的變量重要性數(shù)值總和占所有特征總和的比例，記為，并以同理計(jì)算劃分后兩個子空間內(nèi)的變量重要性比例，分別記為和場景空間劃分需要滿足以下兩個劃分條件：

左右子空間的變量重要性比例的均值應(yīng)大于上層空間的變量重要性比例；

即左右子空間中任一變量重要性比例小于上層空間的變量重要性比例時，兩者的差值僅允許在一定的閾值范圍內(nèi)。

2.2 劃分終止條件

在瓶頸分析過程中，判斷當(dāng)前場景空間是否達(dá)到劃分終止條件，如果當(dāng)前空間不滿足終止條件，則繼續(xù)向下劃分，反之，則終止該空間的迭代劃分，將其置為葉子節(jié)點(diǎn)并分析當(dāng)前空間的瓶頸因素。劃分終止條件的計(jì)算公式如下：

其中，M為特征個數(shù)，80/20的取值參考于巴萊多定律，即二八定律。二八定律認(rèn)為在任何特定群體中，重要的因數(shù)通常只占少數(shù)，而不重要的因數(shù)則占多數(shù)，因此只要能控制具有重要性的少數(shù)因數(shù)即能控制全局。本文利用二八分析法進(jìn)行引申，認(rèn)為每個子空間內(nèi)少數(shù)的特征真正決定了該場景空間內(nèi)的繪制性能，那么當(dāng)該子空間內(nèi)少數(shù)特征的變量重要性比例總和達(dá)到整體特征的多數(shù)水平時，則進(jìn)一步關(guān)注這些少數(shù)特征并從中分析子空間內(nèi)的性能瓶頸。另外，劃分后子空間的數(shù)據(jù)樣本個數(shù)需要滿足大于某一最小閾值的條件，其目的是當(dāng)計(jì)算子空間內(nèi)的變量重要性時保證存在OOB數(shù)據(jù)。

2.3 算法步驟

本文針對融合了多種繪制算法的復(fù)雜場景，實(shí)現(xiàn)的基于空間劃分的瓶頸分析方法流程如圖2所示。

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文以宮殿模型為基礎(chǔ)場景，融合了基于光源鏈表(Light Linked List，LLL)的實(shí)時光照算法，實(shí)現(xiàn)了場景內(nèi)部多光源的實(shí)時動態(tài)變化。同時，本文結(jié)合了順序無關(guān)的半透明(Order-Independent Transparency，OIT)渲染技術(shù)以及屏幕空間環(huán)境光遮蔽(Screen-Space Ambi?entOcclusion，SSAO)渲染技術(shù)，實(shí)現(xiàn)了較好的透明物體繪制效果及全局光照效果。本文所有實(shí)驗(yàn)數(shù)據(jù)均來自于以下場景，如圖所示：

圖2 算法流程圖

圖3 LLL

圖4 OIT

圖5 SSAO

本文設(shè)計(jì)了宮殿場景內(nèi)不同的漫游路徑，記錄了漫游過程中每一幀的相機(jī)信息、透明物體片元個數(shù)、光源半徑、光源個數(shù)、SSAO采樣半徑、SSAO模糊半徑及光源位置信息。將場景漫游后記錄下的所有信息進(jìn)行數(shù)據(jù)處理，最終得到以下特征如表1所示。

3.2 實(shí)驗(yàn)結(jié)果

本文根據(jù)不同的場景漫游路徑生成多組實(shí)驗(yàn)數(shù)據(jù)，通過基于空間劃分的瓶頸分析模型得到以下幾組不同的效果圖：

表1

圖6

圖7

圖8

圖9

圖6-圖9分別展示了漫游數(shù)據(jù)被劃分成2～6個場景子空間的效果。圖6中兩個子空間的性能瓶頸因素從左至右分別為光源個數(shù)和透明物體片元個數(shù)；圖7中三個子空間的性能瓶頸因素從左至右分別為SSAO采樣半徑、光源個數(shù)和透明物體片元個數(shù)；圖8中四個子空間的性能瓶頸因素從左至右分別為SSAO采樣半徑、光源個數(shù)、透明物體片元個數(shù)和SSAO模糊半徑；圖9中六個子空間的性能瓶頸因素從左至右且從上至下分別為SSAO采樣半徑、光源個數(shù)、光源半徑、光源個數(shù)、透明物體片元個數(shù)和SSAO模糊半徑。從以上結(jié)果可以看出，經(jīng)過劃分后的空間均有著各自不同的影響場景繪制性能的瓶頸因素。

4 結(jié)語

針對融合多繪制算法的復(fù)雜場景性能瓶頸分析問題，本文提出了基于隨機(jī)森林變量重要性度量的空間劃分方法，將復(fù)雜場景細(xì)分成不同的子空間，通過結(jié)合子空間內(nèi)相關(guān)的繪制算法定位影響繪制效率的瓶頸因素，從而對復(fù)雜場景的繪制性能提出指導(dǎo)性的改進(jìn)方案。但是本文利用隨機(jī)森林算法作為基本工具，其算法的隨機(jī)性會導(dǎo)致瓶頸分析模型存在不穩(wěn)定的問題。未來的工作會進(jìn)一步優(yōu)化瓶頸分析過程，讓整體模型趨于穩(wěn)定。

參考文獻(xiàn)：

[1]Breiman L.Random Forests[J].Machine Learning,2001,45(1):5-32.

[2]Breiman L.Out-of-Bag Estimation[OE/OL].1996.ftp.stat.berkey.edu/pub/users/breiman/OOBestimation.ps.

[3]Verikas A,Gelzinis A,Bacauskiene M.Mining Datawith Random Forests:A Survey and Results of New Tests[J].Pattern Recognition,2011,44:330-349.

[4]Abdul Bezrati.Real-Time Lighting Via Light Linked List[M].GPUPro 6,2016:183-193.

[5]Luna F.D.Introduction to 3DGame Programming with Directx11[M].Mercury Learning&Information，2012.