基于信息熵重新加權采樣的改進MMLT算法

賀懷清，任瑋潔，劉浩翰

(中國民航大學 計算機科學與技術學院，天津 300300)

0 引 言

由于傳統光線追蹤[1]算法的求交計算基本占據整個過程運算量，渲染時間較長，同時點采樣容易造成圖像走樣。使用Monte Carlo光線追蹤[2,3]可以離散采樣來估計場景中真實光照的近似結果，但對復雜光照場景的渲染仍有不足。因此Veach等[4]提出的MLT(Metropolis light transport)算法由于在復雜場景中展現了強大的處理能力，引起了學者關注。以此為基礎，研究者們提出了多種改進方案，最為經典的就是PSSMLT(primary sample space Metropolis light transport)[5]算法和MMLT(multiplexed Metropolis light transport)[6]算法。PSSMLT算法針對MLT采樣局部性問題，將突變應用到基礎樣本空間，隨機擾動獲得路徑。Hachisuka等提出的MMLT算法將多重重要性采樣(multiple importance sampling，MIS)引入到基礎樣本空間，成為MLT發展的最新里程碑算法。

曾笮等[7]引入雙向Lightcuts算法思想提高路徑空間連貫性以及路徑重用率。賈潔等[8]通過對初始樣本進行方差過濾來減少啟動偏差。Zirr等[9]通過對螢火蟲樣本重新加權來減少樣本估計的方差。湛少勝等[10]從樣本采樣數量出發優化采樣分布。Pantaleoni[11]通過圖表映射和坐標轉換的方式提升了算法路徑探索能力。而Bitterli等[12]提出的RJMLT算法(reversible jump metropolis light transport)通過確定性的方法突變解決漣漪效應。

這些算法均是以提高路徑探索效率為目的來改進MMLT算法。而文獻[13]從路徑樣本影響像素合成的角度出發，在傳統光線追蹤算法上通過使用信息熵表現像素內的樣本均勻程度來評價樣本噪聲水平，改進了渲染圖像過程中產生的噪聲問題。

本文借鑒采用信息熵評價像素內樣本均勻性的思想，不同的是，本文將信息熵引入到MMLT算法的重要性函數中進行重新加權，同時動態修改突變概率，在保留高貢獻樣本的同時不忽略低貢獻但結構信息豐富的樣本，優化采樣分布，使渲染的圖像輪廓更清晰，渲染效果更逼真。

1 相關工作

1.1 MLT算法

MLT光線追蹤算法是將Metropolis-Hastings采樣引入到全局光照渲染的采樣當中，基于MCMC(Markov chain monte carlo)[14]方法在局部區域內進行光線探索，通過對獲得的有效路徑進行突變和復用，以有限采樣點和光線來達到較好的渲染效果。

MLT算法首先通過對路徑空間進行部分采樣生成一系列采樣點xi構成采樣路徑Xi，并定義路徑空間的貢獻函數f。然后以某一已知分布函數p正式采樣這些路徑來構建馬爾可夫鏈，從而，生成一個路徑序列X0,X1,…,Xn并記錄路徑在圖像表面的分布。其中每一條路徑Xi都是對前一條路徑Xi-1進行轉移而得到的(Xi可稱為提議樣本)，且每一條路徑的生成只與前一條路徑相關，與采樣過程的歷史狀態無關。無論選擇哪一個初始分布，生成的序列最終都會逐漸收斂于一個與函數f成比例的穩態分布。提議樣本的接受與拒絕由接受概率決定。其中，接受概率a(xi,y) 表示形式為

(1)

式中：T為轉移函數，也可稱為突變策略。T(xi,y) 為描述當前樣本xi突變為提議樣本y的概率密度函數。為了使采樣過程盡快達到穩態分布，要在不影響收斂速度的狀況下盡可能增大接受概率，因此可以將接受概率較大者的值設為1，則提議樣本被接受的概率為a。若被接受則xi+1=y，否則xi+1=xi。同時，需要滿足細節平衡條件來保證采樣過程是收斂的，細節平衡可表示為

f(xi)T(xi,y)a(xi,y)=f(y)T(y,xi)a(y,xi)

(2)

1.2 MMLT算法

MMLT算法在MLT算法的基礎上，引入了多重重要性采樣，通過MIS自動地自適應地構建路徑，使得采樣分布可以更接近于真實的光照分布。MMLT算法依舊通過在基礎樣本空間上突變獲得新路徑，但額外使用兩個隨機變量，選取指定的頂點對來限制子路徑的連接。接受函數也是基于重要性采樣，這樣使得馬爾可夫鏈在獲得重要采樣的同時，可以更快地達到穩態分布。

盡管MMLT算法減少了對每一條路徑連接時做可見性測試的概率，但降低了路徑的重用率。同時MMLT算法使用光照強度作為重要性函數，強調光照強度高的路徑采樣的重要性。但在采樣數量一定的情況下，集中對光照強度高的區域進行大量的采樣，會導致光照強度低但信息豐富的位置未獲得足夠的采樣，使得最后的渲染結果在這些位置出現明顯的噪聲或使這個位置根本沒有被很好地渲染出來。

2 改進的MMLT算法

2.1 改進思想

對于像素合成而言，像素值為像素內所有采樣樣本光照強度值的均值。因此樣本值的均勻性是表征像素質量的關鍵。像素值越均勻，噪聲水平越低。MMLT算法使用蒙特卡羅積分估計像素樣本值，而蒙特卡羅積分是一個在積分區域內獨立獲取并隨機采樣來對積分值進行估計的過程[15]，其隨機性導致無法獲知像素樣本值均勻性或一致性的確切情況，從而使得像素質量測量具有不確定性。當從單一像素擴大到局部區域時，區域像素值的均勻性則可表示該區域是否具有不確定性，即當前區域所映射場景的結構信息豐富程度，從而可知該區域的重要性。

而熵可以很好地表示一個體系的混亂程度，是衡量不確定性、無序性、分散性和變異性的指標。信息熵則表示一個信源的不確定度，即所包含的信息量的多少，且它和信源所包含的信息量成正相關。若信源符號X為n種不同值的離散隨機變量，X={x1,…,xn}，其對應的概率為P={p1,…,pn}，則信息熵的公式表示為

H=-∑Xpilog2pi

(3)

根據式(3)可以得知如果信源所包含樣本均不相同時差異性最大，此時信息熵最大且包含的信息量最大。將信息熵引入到圖像中時，當一個圖像有且僅有一個無任何變化的物體時，如一片純色的畫布，不需要任何條件就可以確定圖像的情況，此時該圖像不包含任何結構信息量。而當圖像包含各種不同物體時，需要的信息量大，這個時候圖像包含的結構信息也十分豐富。

因此我們采用局部區域的信息熵來獲得區域權重，從而表現某個區域的重要性。當這個區域信息熵大的時候表示這個區域內像素位置映射到場景中的信息相對復雜，通常情況下這些區域為圖像交界、陰影、高光周圍等結構信息變化劇烈的地方，也就是本文中需要在場景中找到的光照強度低但結構信息豐富的位置。

2.2 改進之處

考慮到MMLT算法采用光照強度作為重要性函數在高貢獻度像素的周圍頻繁采樣，使采樣分布不均勻，所以本文將信息熵引入重要性函數進行重新加權，優化高貢獻度區域周圍的采樣分布。由于灰度能夠很好地呈現圖像的整體結構，能將圖像更好地分割且可離散地表示，因此使用灰度作為圖像的信源。根據式(3)可知，要獲得一個信源的信息熵時，需要遍歷該信源內所有的變量，因此為便于計算，本文算法使用256級灰度。

首先使用m表示區域范圍內的灰度級數，則g[m] 表示區域范圍內灰度級m出現的次數，即灰度級頻率。

然后根據式(3)可得圖像的信息熵

(4)

(5)

其中，H代表對應像素所映射的場景結構信息復雜情況。

MMLT中僅使用光照強度作為像素采樣合成的依據，但實際中影響像素合成的因素還包含材質、紋理等結構信息，而H正反應了該信息的豐富度。因此，我們將信息熵引入重要性函數中，用信息熵來平衡光照強度，使得光照強度低但所映射場景中結構信息豐富的位置采樣權重增大。最終使整體采樣分布更加均勻，同時減少漣漪效應。因此，將H添加到重要性函數中得到新的重要性函數為

W=HL

(6)

其中，L為樣本的光照強度，H值越大，像素對應的結構信息越豐富，則采樣權重越大。

同時使用信息熵來動態修改突變概率，使得在有限的采樣量下貢獻度低但結構信息豐富的位置可以有更好的采樣效率。為了可以在結構信息相對豐富的位置周圍進行更多的采樣，通過信息熵控制突變概率從而調整突變范圍，即信息熵越大突變概率越小，則可突變的范圍也隨之減小。同時若突變概率過小，會導致陷入局部循環采樣，降低整體的收斂速度；但突變概率過高導致樣本方差大且接受概率較低。由于當突變概率低于自身一半或超過兩倍時差異性明顯，并會出現局部循環或逃逸現象，因此為防止極端現象的出現，將突變概率設置為

(7)

在接受概率的計算公式中，為了使馬爾可夫鏈更快的收斂，將式(2)中接受概率較大者的值設為1。為了滿足接受概率選擇所需的時間可逆性，加入概率密度函數后仍需滿足細節平衡條件。在采樣狀態改變過程中，通過設置提議樣本與當前樣本之間轉移概率相同來使小范圍突變滿足對稱性，則接受概率表示為

(8)

其中，Wxi和Wy分別表示當前樣本xi和提議樣本y的重要性函數。

2.3 算法描述

本文算法步驟如下：

輸入：場景文件。

輸出：進行完全采樣后的渲染結果圖像。

步驟1 對要渲染圖像的每一個像素點進行一次采樣，獲得每一個像素點的顏色值并存放在容器中。

步驟2 對不同路徑長度(0

步驟3 根據步驟1獲取該次采樣周圍的像素顏色值，利用式(5)、式(6)分別計算該次采樣的信息熵和重要性函數。

步驟4 如果采樣數量未達到預設定樣本數量，重復步驟2～步驟3，否則進入步驟5。

步驟5 獲取馬爾可夫鏈起始樣本，利用式(5)得到當前采樣信息熵。

步驟6 根據樣本的信息熵值利用式(7)動態設置樣本突變概率，對樣本進行突變獲取提議樣本，利用式(5)計算樣本信息熵。

步驟7 利用式(8)計算接受概率a判斷提議樣本接受與否，同時更新步驟1構建的像素顏色信息。

步驟8 如果提議樣本滿足接受條件，則將馬爾可夫鏈的當前樣本轉移為提議樣本，并在此基礎上繼續突變；否則保持當前樣本不變。

步驟9 如果所構建的馬爾可夫鏈未達到所需的馬爾可夫鏈節點數，重復步驟6～步驟8，否則進入步驟10。

步驟10 重復步驟5～步驟9，直到達到場景中設置的最大采樣數量，結束路徑突變。

2.4 改進算法遍歷性和采樣分布優化說明

MMLT算法中使用光照強度作為重要性函數，使得采樣大部分集中在貢獻度高的位置。而對于光照強度差異小但結構信息豐富的位置，僅以光照強度為權重使該位置無法得到很好的采樣，當采樣量不足時甚至會出現某些貢獻度低的位置根本沒有采樣的情況。本文將信息熵引入重要性函數，讓采樣分布從貢獻度高的地方向貢獻度低但結構信息豐富的位置轉移，進一步滿足遍歷性的要求。所以本文算法的采樣分布更接近圖像真實情況，渲染的圖像在高光周圍、明暗交界等貢獻度低但結構信息豐富的位置表現會更好。

3 實驗結果

3.1 實驗環境及度量標準

通過將本文算法應用到MMLT中來驗證其改進的渲染效果。實驗中主要選取了Teapot、Bmw、Veach和Killeroo這4個具有代表性的場景，將本文算法和MMLT算法在PBRT3.0版本渲染平臺中進行4組主對比實驗。為了進一步驗證本文算法與最新的MMLT改進算法的對比，額外選取Bathroom場景，以便本文算法與MMLT算法、文獻[8]算法以及RJMLT算法進行一組輔助實驗對比，由于RJMLT算法采用Tungsten渲染平臺，該組實驗統一在該平臺下進行。由于CMLT算法主要對基礎樣本空間進行處理；文獻[10]算法主要根據采樣的分布來修改結果，而本文算法是針對重要性函數的修改，側重于像素本身而非采樣分布，且未對樣本空間進行修改。因此這兩種算法均與本文算法側重點不同，不具有可比性。文獻[13]雖為本文算法的思想啟發，但二者不在同一框架，信息熵所起作用也不同，且年份較久，因此也未進行對比。

選取5組場景的原因：Teapot場景中存在介質轉變，在光線照射下透明玻璃與透明液體相互作用會出現明暗混合現象。BMW場景與Killeroo場景中都僅存在間接光照，其中BMW場景環境光亮度偏低且存在大量高光，容易出現光斑剝離；而Killeroo場景中背景作為主要內容且環境昏暗，能夠展現出算法的噪聲改善效果。Veach場景既有直接光照，又有間接光照，同時存在焦散現象，能夠很好地展現算法的性能。Bathroom場景作為一個復雜場景，存在多個不同介質間的相互作用，可以進一步驗證算法的改進效果。實驗中每組對比圖像均在同一場景的相同采樣數下進行。實驗所用環境配置如下：

渲染器為PBRT-V3和Tungsten；開發工具為Qt Creator 5.8和Cmake 3.9；操作系統為Ubuntu 16.04；硬件環境為IntelRCoreTMi7-7700 CPU@ 3.60 GHz，8 GB內存。

在實驗中，除了將渲染圖像與參考圖像進行主觀表現上的對比外，還采用峰值信噪比(peak signal to noise ratio，PSNR)[16]和結構相似度(structural similarity，SSIM)[17]兩個客觀評價指標來對生成圖像進行質量評價。PSNR和SSIM均是全參考的圖像質量評價指標，其中PSNR是基于像素維度誤差進行的圖像質量評價，PSNR越大，像素的顏色值與參考圖越接近。而SSIM分別從亮度、對比度、結構3個層次對圖像相似度進行衡量，其值越大表示圖像質量越好。除此以外，實驗中還加入了采樣密度分布圖，通過將每個像素被采樣的數量轉換為對應的顏色觀察其漸變情況來直觀對比算法采樣分布的改進。

3.2 實驗結果分析

3.2.1 不同場景渲染結果對比

實驗1：驗證本文算法在光線情況復雜且包含不同透明介質場景中的性能。應用本文算法和MMLT算法分別對Teapot場景在相同采樣數下進行渲染，渲染結果如圖1所示。

圖1 Teapot場景渲染結果

通過圖1的對比實驗可以發現，本文算法在光線情況復雜和光線傳播介質發生變化的位置效果更加清晰，比改進前的MMLT算法更接近參考圖。由局部放大圖中可以看出壺身噪點明顯減少，反光投影處降低了模糊感，壺底紋路也更加分明。

實驗2：驗證本文算法在包含大量高光但環境較暗的間接光照場景中的性能。應用本文算法和MMLT算法分別對BMW場景在相同采樣數下進行渲染，渲染結果如圖2所示。

圖2 BMW場景渲染結果

通過圖2的對比實驗可以發現，MMLT算法在有高亮出現的偏暗區域很容易出現光斑剝離現象。本文算法通過使用信息熵平衡光照亮度，計算圖像分離邊界解決了這一問題。由局部放大圖可以看出，遠近車燈的整體輪廓更加分明，同時光照強度低的內部環境也明顯顯現出來。

實驗3：驗證本文算法在存在直接光源且光線在流形透明介質中發生復雜傳播的場景中的性能。應用本文算法和MMLT算法分別對Veach場景在相同采樣數下進行渲染，渲染結果如圖3所示。

圖3 Veach場景渲染結果

在圖3的對比實驗中，改進前的MMLT算法在墻角、燈座等需要表現出明顯交界的地方分割能力表現較差，在墻角、玻璃四周還出現了較大的噪聲干擾，本文算法在這些地方表現的場景分割能力優于改進前的MMLT算法。另外，分析局部放大圖可以發現本文算法在減少噪聲的同時使玻璃輪廓更加清晰，玻璃球體也更加通透，整體效果更加真實。

實驗4：驗證本文算法的噪聲改善效果。對于一般場景，實驗1～實驗3可以看出本文算法在貢獻度低但結構信息豐富的位置的渲染優化效果。但當場景完全處于間接光照下并由大量結構信息單調的內容組成時，由于MMLT算法使用亮度作為權重，會在信息單調的位置進行反復采樣，且總是會接受，導致結構信息豐富的位置無法得到很好的采樣，使得渲染圖像出現大量噪聲。而本文算法將信息熵引入重要性函數，減少了對結構信息單調位置的采樣，并降低了該位置的接受率，使渲染圖像的噪聲得到很大改善。應用本文算法和MMLT算法分別對Killeroo場景在相同采樣數下進行渲染，渲染結果如圖4所示。

圖4 Killeroo場景渲染結果

在圖4的對比實驗中，改進前的MMLT算法物體輪廓模糊不清，渲染圖像包含大量的噪聲。而本文算法使得渲染圖像的噪聲得到很大改善。另外，分析局部放大圖發現本文算法在減少噪聲的同時使得物體交界處輪廓更加清晰。

實驗5：進一步驗證本文算法的渲染效果。應用本文算法、MMLT算法、文獻[8]算法、RJMLT算法分別對Bathroom場景在相同采樣數下進行渲染，渲染結果如圖5所示。

圖5 Bathroom場景渲染結果

通過圖5的對比實驗可以發現，改進后的算法整體渲染效果優于其它3種算法，降低了噪聲。細節上，對于那些結構信息未發生劇烈變化的位置，如木質地板和墻面，本文算法渲染效果與其它3種算法基本相同。但在一些光線情況發生變化且結構復雜處，本文算法得到了更加逼真的渲染結果。從局部放大圖中可以看出，對于洗手池高光周圍，本文算法采樣效果更加真實，沒有出現尖銳區域，降低了噪聲；洗手池底部更接近原圖，與木臺相接的陰影部分噪聲明顯減少，沒有過多黑白斑點，底座、鏡子支架也更加清晰。

MMLT算法與本文算法在不同場景中的采樣分布圖如圖6所示。通過比較采樣密度變化可以發現，相較于MMLT算法針對高亮度區域的密集采樣或在光照亮度差異小的場景中無差別采樣，本文算法通過使用信息熵重新加權，減少高亮度區域高密度采樣的同時，將采樣分布于結構信息豐富的區域，使整體采樣更加均勻，優化渲染效果。

圖6 采樣密度分布

通過表1可以發現本文算法相比改進前的MMLT算法在各項指標上都有明顯提升。結合以上5組實驗結果圖1～圖5，可以得出本文的算法在結構信息豐富、光線情況復雜、光線傳播介質發生變化的場景中表現優于MMLT算法，并且不同場景中的噪聲相較于MMLT算法均有不同程度的提升。特別是在場景中包含大量結構信息單調的內容或需要清晰的圖像分割時本文算法表現更為明顯。

表1 PSNR和SSIM對比

但由于MMLT算法僅以光照強度作為權重，忽略其結構信息，一方面會在光照強度高的位置集中采樣，另一方面在光照強度相近的情況下，無法較好地分辨出交界、陰影等結構變化明顯的位置，從而無法達到較好的采樣效率。而本文算法引入信息熵，在平衡光照強度高位置采樣的同時，加強了對貢獻度低但結構信息豐富的位置的采樣，達到了自適應采樣的目的。因此對于貢獻度高的位置來說，其與參考圖像的像素差異較MMLT算法略微增大，但通過增強其它重要位置的采樣使整體結構與原圖更為接近。因此本文算法雖然優化了不同場景的輪廓信息，提高渲染效果，減少了生成圖像的噪聲，但PSNR沒有得到很大的提高。

3.2.2 馬爾可夫鏈收斂速度對比

任取一場景將本文算法與MMLT算法的馬爾可夫鏈收斂速度進行對比。由于MMLT算法與本文算法的采樣均基于權重，權重的變化趨勢則為馬爾可夫鏈趨于穩態的過程。采用Veach-mis場景，其參考圖像如圖7所示。

圖7 實驗用到的Veach-mis場景

圖8為Veach-mis場景在相同配置參數下隨采量的增多MMLT算法和本文算法的馬爾可夫鏈權重趨勢對比，其中橫坐標表示第幾次采樣，及算法運行時間，縱坐標表示采樣權重。

圖8 采樣分布權重趨勢對比

從圖8的權重趨勢對比可以看出，隨著采樣量的逐漸增多，兩種算法的采樣分布權重都從散亂逐漸趨向于一個穩定的區域。也就代表了隨著算法運行時間的增加，馬爾可夫鏈逐步達到穩態。而本文算法較MMLT算法更快趨于穩定，優勢明顯。由此可知本文算法有效減少了采樣到達穩態分布的時間，加快了馬爾可夫鏈的收斂速度。

4 結束語

本文借鑒信息熵能表示信源不確定度的思想，從提升光照強度低但結構信息豐富的位置的采樣權重的角度改進MMLT，解決了局部采樣數量過度依賴光照強度而忽略結構信息的問題，從而優化了輪廓信息，提升了MMLT在不同場景中渲染的真實感，達到渲染過程中自適應采樣的目的。雖然本文算法在整體上使渲染結果更逼真，但由于平衡了光照強度高的位置周圍的采樣分布使PSNR沒有得到很大提高，未來工作將針對這一問題繼續改進。