基于信息熵重新加权采样的改进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没有得到很大提高，未来工作将针对这一问题继续改进。