李瀟瑤

（四川大學計算機學院，成都 610065）

0 引言

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

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

1 隨機森林

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

1.1 隨機森林算法

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

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

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

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

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

圖1 隨機森林原理示意圖

1.2 變量重要性

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

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

（1）設置i=1，針對訓練樣本Bi構造決策樹Ti，并將袋外數(shù)據(jù)標記為

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

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

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

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

2 算法描述

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

2.1 空間劃分

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

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

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

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

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

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

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

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

2.2 劃分終止條件

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

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

2.3 算法步驟

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

3 實驗結果

3.1 實驗數(shù)據(jù)

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

圖2 算法流程圖

圖3 LLL

圖4 OIT

圖5 SSAO

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

3.2 實驗結果

本文根據(jù)不同的場景漫游路徑生成多組實驗數(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模糊半徑。從以上結果可以看出，經(jīng)過劃分后的空間均有著各自不同的影響場景繪制性能的瓶頸因素。

4 結語

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