（计算机软件与理论专业论文）滤波重要性采样算法的研究与实现.pdf

摘要 在全局光照模型下，对真实感图像的绘制是目前计算机图形学中研究的热 点。图像采样和根据采样信息进行的重建是绘制过程中的两个重要环节。为了避 免图像产生走样以获得良好的视觉效果，人们提出了大量巧妙而实用的算法，但 通常只应用于其中某一环节。 本文通过对滤波重要性采样算法进行了深入细致的研究，选择将高斯滤波器 与该算法结合，提出新的高斯滤波重要性采样算法。它是把绘制图像过程中的光 源采样、像素采样、像素重建三个阶段紧密联系，综合考虑，是一种使各阶段整 体效果达到最佳的采样和滤波方法。根据场景文件中的信息建立高斯c d f 映射 表，将符合均匀随机分布的二维初始采样进行高斯函数的重要性变换。选择位于 高斯滤波器核心像素中的采样作为最后用于计算像素光照值的采样，并使用抖动 技术避免生成图像的走样现象。理论上，根据m o n t ec a r l o 积分的重要性采样技 术计算最终像素的颜色值，因此重建过程采用覆盖单个像素的箱式滤波器。在 p b r t 绘制系统中实现该算法，作为系统中新的采样器插件。 设计以及完成对比实验，根据得到的实验结果和数据分析高斯滤波器的参数 变化对该算法r m s 值和消耗时间的影响；分析该算法在对比实验中与随机采样 结合m i t c h e l l 滤波的方法相比时，性能上表现略差的原因，指出存在的问题并提 出改进的想法。 关键词：滤波重要性采样高斯滤波器高斯c d f 映射表 a b s t r a c t p h o t o r e a l i s t i ci m a g er e n d e r i n gb a s e do ng l o b a li l l u m i n a t i o nm o d e li so n ea c t i v e r e s e a r c ha r e ao fc o m p u t e rg r a p h i c s i m a g es a m p l i n ga n dr e c o n s t r u c t i o nb ys a m p l e s i n f o r m a t i o na r et w oi m p o r t a n ta s p e c t so fr e n d e r i n g t h e r ea r em a n ye x c e l l e n ta n d p r a c t i c a b l ea l g o r i t h m sp r o p o s e dt oa v o i dt h ea l i a s i n go fi m a g ea n dg e td e s i r a b l ev i s u a l e f f e c t h o w e v e r , m e ya r eu s u a l l ya p p l i e dt oo n es t a g eo fr e n d e r i n g t h o u g hd o i n gt h ed e e pr e s e a r c ho nt h ef i l t e rs a m p l i n ga l g o r i t h m , t h i sp a p e r c h o o s e sg a u s s i a nf i l t e rt ob ec o m b i n e dw i t ht h ea l g o r i t h ma n dp r o p o s et h eg a u s s i a n i m p o r t a n c es a m p l i n ga l g o r i t h m t h en e wa l g o r i t h mm a k e st h er e l a t i o na m o n gt h r e e s t a g e so fi m a g er e n d e r i n g ，w h i c ha r ei l l u m i n a t i o ns a m p l i n g ，p i x e ls a m p l i n ga n dt h e r e c o n s t r u c t i o n , a n dc o n s i d e r st h e ma saw h o l ei no r d e rt oh a v et h eo p t i m a le f f e c t c o n s t r u c tg a u s s i a nc d fm a p p i n gt a b l ea c c o r d i n gf ot h ei n f o r m a t i o ni ns c e n ef i l e s ， a n dt r a n s l a t ei n i t i a ls a m p l e sg e n e r a t e df r o mu n i f o r m l yd i s t r i b u t e dr a n d o mv a r i a b l e st o f o l l o wg a u s s i a nf u n c t i o ni m p o r t a n c es a m p l i n g c h o o s et h es a m p l e sl o c a t e di nt h e k e r n e lp i x e lo f g a u s s i a nf i l t e ra st h o s ef i n a l l yb e i n gu s e dt oc a l c u l a t et h ei l l u m i n a t i o n , a n dm a k eu s eo fj i t t e r i n gt e c h n i q u et oa v o i di m a g ea l i a s i n g i nt h e o r y , u s et h e i m p o r t a n c es a m p l i n go fm o n t ec a r l oi n t e g r a t i o nt oc a l c u l a t et h ef m a lv a l u eo fp i x e l ， s oi nr e c o n s t r u c t i o nw eu s et h eb o xf i l t e rc o v e r i n gs i n g l ep i x e l i m p l e m e n tt h e a l g o r i t h mi nt h ep b r tr e n d e r i n gs y s t e ma san e ws a m p l e rp l u g - i n d e s i g na n dc o m p l e t et h ec o m p a r i n ge x p e r i m e n t s o n t h eb a s i so ft h e e x p e r i m e n t a lr e s u l t sa n dd a t a ，a n a l y z eh o wt h ec h a n g e so ft h eg a u s s i a nf i l t e r p a r a m e t e r sw i l ln l a k ea ni m p a c to nr m sv a l u ea n dc o n s u m i n gt i m eo ft h ea l g o r i t h m ， a n dt h er e a s o nw h yt h ea l g o r i t h mp e r f o r m sp o o r l yw h e nc o m p a r e dw i t ht h er a n d o m s a m p l i n gc o m b i n e dw i t hm i t c h e l lf i l t e ri nt h ec o m p a r i n ge x p e r i m e n t s ，a n dt h e nf i g u r e o u tt h ep r o b l e ma n dp r o v i d em a k ei m p r o v i n g s u g g e s t i o n s k e yw o r d s ：f i l t e ri m p o r t a n c es a m p l i n g ，g a u s s i a nf i l t e r , g a u s s i a nc d f m a p p i n gt a b l e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：丑f 爱 签字日期： ) 叼 年月f 弓日 学位论文版权使用授权书 本学位论文作者完全了解苤盗盘堂有关保留、使用学位论文的规定。 特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：占p 俊 签字日期：歹。叼年月，多日 导师繇诉磅、 签字日期：2 。叼年月 f ；日 第一章绪论 第一章绪论 计算机图形学是一门利用计算机研究图形的表示、生成、处理、显示的学科。 经过3 0 多年的发展，已成为计算机科学中最为活跃的分支之一，并得到广泛的应 用。目前，计算机图形学的应用已深入到真实感图形、科学计算可视化、虚拟环 境、多媒体技术、计算机动画、计算机辅助工程制图等领域。在人们的工作、生 活、娱乐扮演着越来越重要的角色n ，。 在真实感图形学的研究领域中，基本要求就是在计算机中生成三维场景的真 实感图形图像。为了模拟现实世界中的场景，通常需要知道这个场景光照效果的 物理模型，然后利用数学模型表示，通过对数学模型的计算得到计算机模拟出来 的真实感效果。光照模型从简单到复杂的排列分别是：简单光照模型、局部光照 模型和整体光照模型。简单的局部光照模型假定光源是点光源，物体是非透明体， 不考虑折射，反射光的情况。局部光照模型只能处理直接光照，整体光照模型能 够对环境中物体之间的各种反射、折射光进行精确模拟。 整体光照渲染是目前研究的热点之一。整体光照模型依据物理学原理刻画光 能在虚拟环境中的传递过程建立的，在真实感图形合成领域扮演着十分重要的角 色瞳3 。绘制方程与位势方程口3 从不同的角度准确地定义了整体光照模型。根据该 模型计算虚拟环境中某个区域、某个方向上的光通量即为整体光照计算。整体光 照主要算法分为两种：光线跟踪算法和辐射度算法。光线跟踪算法非常适合处理 镜面反射和规则透射，可以计算出准确的高光和聚焦失焦现象。由于它考虑了物 体之间的相互作用，可以产生效果逼真的结果图。辐射度算法是从光能分布的角 度，求解能量平衡方程组，较好的解决了场景的漫反射问题，真实的模拟出洇色 现象。对于纯漫反射场景，运用辐射度技术可以产生非常真实的绘制效果。而且 由于绘制时与视点无关，因此一旦能量分布计算结束后，就可以快速绘制出位于 任何视点的光照效果图。 1 1 研究背景及现状 早期出于绘制目的的采样工作开始于1 9 8 4 年，c o o k 提出分布式光线跟踪算 法 4 - 5 1 。他根据采样的解析函数分布光线方向。通过这种方式，模糊的现象例如 软阴影、有光泽的反射和运动模糊可以被光线跟踪模拟出来。为了产生无走样的 图像，随机采样技术首先被d i p p e 提出6 1 。在图像平面中，使用泊松和抖动采样 第一章绪论 而不是规则的模式。m i t c h e l l 和n e t r a v a l i 研究为绘制过程设计一种最佳的重建滤波 函数。他们引进了由两个参数定义的一系列分段立方滤波函数。除了w i n d o w e d s i n ef i l t e r 之外，这是现在已知最好的图像重建函数之一。m i t c h e l l 还研究在更高 维空间如何为分布式光线跟踪产生采样模式的问题。更近一点，k e l l e r 等人为低 差异点集合在图形学上的应用做出了出色的工作，提出低差异采样法。自适应采 样也是减少生成图像噪声的一种采样方法。人们已经提出了许多自适应采样方 法。m i t c h e l l 根据人眼对比度的概念，提出一种自适应采样模型7 j ；d i p p e 和w b l d 提出的错误评价机制是基于噪音率的r m s 信号值，同时也考虑了以方差作为采样 数的函数【6 1 ；l e e 等人用样本值的方差来确定采样频率【8 】；p u r g a t h o f e r 汞j 用统计学 方法，提出基于置信区间方法的自适应采样【9 1 ；b o l i n 和m e y e r 研究出一种使用统 计和视觉模型的感知方法【1 0 】。r i g a u 、f e i x a s 和s b e r t 弓i 入香农信息熵和低差异采 样的概念建立起像素计算质量的评测标准【1 1 1 。 目前人们还注意到采样函数和重建过滤器的相互的作用会对最终生成图像 的质量产生影响。例如，低差异采样器( l d s a m p l e r ) 对单一像素而言是一种很 好的采样分布模式，但是当它对图像平面中多个像素采样进行分布时，却没有考 虑邻近像素之间采样的分布情况。所以使用箱式滤波器与它结合就会产生很不错 的效果，而在使用跨越多个像素，权重值不为常值的滤波器时这种抽样就没有那 么有效了。本文研究的正是针对这一现象的滤波重要性采样算法。 1 2 本文结构 本文的各章节内容安排如下： 第一章，概述了在真实感图像绘制的基本理论知识。简要介绍了当前采样与 重建领域中已取得的研究理论和成果。 第二章，介绍本文研究所基于的专业理论和数学知识。对选用的实验平台 p b r t 物理绘制系统的绘制流程做整体描述。针对图像绘制过程抽样和重建阶段 中最常见的走样问题，介绍并分析了常见的反走样技术和自适应采样技术。 第三章，深入研究滤波重要性采样算法，包括它的理论基础和自身特点。提 出高斯滤波重要性采样算法。实现该算法作为实验平台中一个新的采样器。在实 现过程中使用例如抖动等技术，以提高该算法的性能。 第四章，设计实验，从不同角度评价该算法的性能。对实验结果进行整理和 总结，分析结果和数据产生的原因，并提出相关的改进方法。 第五章，对工作进行总结，通过对算法的研究和实践，深入了解算法的特点， 指出进一步工作的方向。 2 第二章光线跟踪算法与采样重建理论 第二章光线跟踪算法与采样重建理论 2 1 光线跟踪算法 光线跟踪算法是典型的整体光照模型，这个思想是由a a p p e l 1 2 】首先提出的。 他提出按光线传播的相反方向跟踪光线，即按从观察者到景物的方向。后来， g 0 1 d s t e i n 和n a g e l t l 3 1 对a p p e l 的光线跟踪思想作了一些改进，并首次用光线跟踪算 法产生了阴影效果，使计算机绘制图形的真实感向前迈进了一大步。但由于当时 计算机运算速度和图形显示设备性能等硬件条件的限制，使光线跟踪算法的发展 受到了一定程度的限制。直到1 9 7 9 年，d s k a y 用光线跟踪算法产生了反射和折 射效果，才迎来了光线跟踪算法的又一次飞跃。这个算法对镜面反射和透明性的 模拟非常成功，使物体的高光点、镜像和透明效果非常自然。它是真正意义上的 高度真实感图形显示算法，现在仍被广泛采用。 图2 1 光线跟踪算法图示 光线跟踪算法的基本思想如图2 1 所示，图中以两个透明球和一个不透明物 体的场景为例，对该算法进行分析。对于屏幕上的每个像素，跟踪一条从视点出 发通过该像素中某点的光线，求出光线与环境中物体的交点。在交点处光线分为 两支，再分别沿镜面反射方向和透明体的折射方向进行跟踪，形成一个递归的跟 踪过程。建立一棵递归的光线跟踪树以记录光路情况。光线每经过一次反射或折 第二章光线跟踪算法与采样重建理论 射，由物体材质决定的反射、折射系数都会使其强度衰减。渲染方程描述了能量 从光源发射，经过各种材质表面的多次反射、折射，最后进入人眼的这一过程。 在面片上某点x 沿方向秒出射的辐射度可以定义如下： l ( x 一印= l a x 一d + l z ( x ，y ”印( x 7 - 5 v ) c o s ( m ，d q 公式2 1 其中q ，是点x 的所有半球方向集合，t 寸们是点x 沿秒方向发射的辐射 度，：是双向散射分布函数( b s d f ) ，l ( x 卜矿) 是点x 从吵方向得到的入射辐射 度，c o s ( u ，) 是点法向量和入射方向y 的夹角余弦。x 在实际的算法进行过程中，出现以下情况光线跟踪中止： 1 光线在传播过程中没有和场景中任何物体相交。 2 光线遇到了场景的背景。 3 光线在经过许多次反射和折射以后，发生的衰减使得该光线对原 像素光亮度的贡献小于预先设定的阈值。 4 光线反射或折射次数即跟踪深度大于设定值。 光线跟踪的阴影处理也很简单，只需从光线与物体的交点处向光源发出一条 测试光线，就可以确定是否有其他物体遮挡了该光源( 对于透明的遮挡物体需进 一步处理光强的衰减) ，从而模拟出场景中软阴影和焦散的效果。 光线跟踪很自然地解决了环境中所有物体之间的消隐、阴影、镜面反射和折 射等问题，能够生成十分逼真的图形，而且算法的实现也相对简单。但是作为一 种递归算法其计算量十分巨大。减少光线与物体之间求交运算的计算和提高求交 效率是提高光线跟踪效率的关键，常用的方法有：包围盒、层次结构及区域分割 等技术。 光线跟踪是一个典型的采样过程，各个屏幕像素的亮度值都是分别计算的， 因而会产生走样现象，但算法本身的计算量使得传统的加大采样频率的反走样技 术难以在现实中使用。像素细分是一种适用于光线跟踪的反走样技术。与象素细 分不同，c o o k 、p o r t e r 和c a r p e n t e r 提出的分布式光线跟踪是一种随机采样的方法， 在交点处镜面反射方向和折射方向所夹的立体角内，按照一定的分布函数同时跟 踪若干根光线，然后进行加权平均。c o o k 等人还提出了利用分布式随机采样技 术模拟半影、景深和运动模糊等效果的方法【悼”】。 光线跟踪的另一个问题是，光线都是从视点发出的，阴影测试光线则需另外 处理，因而无法处理间接的反射或折射光源，例如镜子或透镜对光源所产生的作 4 第二章光线跟踪算法与采样重建理论 用就难以模拟。为解决这一问题，可以从光源和视点出发对光线进行双向跟踪。 2 2m o n t ec a r l o 方法 m o n t ec a r l o 方法，也称统计方法模拟，是以著名的赌城m o n t ec a r l o 命名。 二十世纪四十年代中期由于科学技术的发展和电子计算机的发明而被提出的，是 一种以概率统计理论为指导的，非常重要的一类数值计算方法。它是使用随机数 ( 或更常见的伪随机数) 进行离散模拟来解决数值计算问题的方法。 m o n t ec a r l o 方法的应用主要是自然现象的模拟以及数值分析，即利用m o n t e c a r l o 方法求积分。根据欲研究的物理系统的性质，建立能够描述该系统特性的 理论模型，导出该模型某些特征量的概率密度函数；从概率密度函数出发进行随 机采样，得到特征量的一些模拟结果；对模拟结果进行分析总结，预言物理系统 的某些特性。 m o n t ec a r l o 的基本思想是：给定一个一维的积分坛f ( x ) d x 和一个随机变 量x ：p ( x ) ，随机变量函数f ( x ) 的数学期望可以由随机变量样本的函数均值 近似求得。如公式( 2 2 ) 所示： = 古y 譬等 公式- r 3 , ( 2 2 z )一， ，- - _ _ _ 一 7 ，- 二一p ( x f ) “一、。一7 f = 1 同理扩展到高维空间，m o n t ec a r l o 方法也适用于高维积分求解，只是x ，是 高维空间的点。根据c h e b y s h e v 不等式可得m o n t ec a r l o 方法的收敛速度为 d ( ) ，并且与被积函数f 的维数无关。 m o n t ec a r l o 方法的基本过程是这样的，首先要根据所研究的问题确定一种 概率密度函数，然后根据概率密度函数对所研究的问题进行采样。其中最常用的 一种方法是反函数法，即利用一个或更多的均匀随机变量并将他们映射成为要求 分布的随机变量。根据求得的概率分布函数的反函数，对随机变量进行变换，然 后得到服从任意概率密度函数p ( x ) 的采样x ，。最后对这些采样进行计算，求均 值，得到最终结果。 要降低对积分估计的错误程度并提高精度，必须提高m o n t ec a r l o 方法中的 采样点的个数，即增加的值。由于m o n t ec a r l o 方法较慢的收敛速度，如果只 是单纯增加采样点个数，会导致大量的运算代价。考虑到效率问题，我们提出了 重要性采样的策略。计算估计值时，必须设法使得g ( x i ) p ( 五) 的方差降低，也就 第二章光线跟踪算法与采样重建理论 是要设法使得p ( 毛) 和g ( 五) 两个函数有相似的形状，那么，在g ( x i ) 函数值大的 地方获得更多的采样，即让更多的采样落在更重要的区域。 在图像场景的绘制过程中，要使用到渲染方程等复杂的高维积分方程式。它 们通常没有解析解，尽管标准的数值积分技术，像梯形积分法或者高斯积分法对 于解决低维平滑的积分很有效，但是它们的收敛率在高维积分和不连续积分这些 情况下表现较差。m o n t ec a r l o 积分法的随机性和独立于被积函数维数的收敛率， 为此提供了一种解决方法。1 9 8 6 年，k a j i y a 首次将蒙特卡罗方法应用到全局光 照领域，提出以建立从视点到光源的随机游动链为基础的蒙特卡罗光线跟踪算法 来逐像素地生成图像，将m o n t ec a r l o 方法与光线跟踪结合起来【1 4 j 。 2 3p b r t 绘制系统 本文的研究主要是针对图像生成过程中，算法的实现和改进。只有通过设计、 渲染出现实、直观的图像，并对所得图像及相关数据进行整理，才能分析出算法 改进后的成果。因此选择的是由m a t tp h a r r 和g r e gh u m p h r e y s 1 5 j 编写的基于物理 的全局光照渲染系统的p b r t 绘制系统，作为实验平台。 在系统中有一个非常重要的模块称为核心模块c o r e ，该模块中包含有控制整 个系统绘制流程的代码，但是其中不包含任何的具体几何形状或光源的实现代 码。该模块是由各种在插件中定义的接口的抽象基类构成，所有的插件类型都是 从c o r e 中继承派生的。当进行场景绘制时，绘制系统会根据场景文件描述的需 要来动态的选择加载插件，协作完成绘制任务。这种结构使得系统易于被扩展， 可以向c o r e 模块中加入新的接口，然后在外部实现相应的插件。 大部分真实感绘制系统是基于光线追踪算法的，p b r t 绘制系统也遵循这一 点。要实现光线追踪算法，系统必须模拟以下的物体和现象：模拟相机、光线一 物体求交、光源分布、可见性、表面散射、递归光线跟踪、光线传播。 p b r t 系统的图形绘制过程分为三个阶段： 1 读取用户提供的场景文件。场景文件本身是一个文本格式文件，文件中 给出场景中的物体的位置，物体的几何形状以及表面的材质属性，光源 的位置，场景中虚拟镜头位置，系统中各个算法的参数信息等的描述。 将所有的场景信息在内存中构造。 2 调用s c e n e ：r e n d e r 0 方法进入绘制主流程。通过主循环程序计算得出每 个光线采样的光照值，并且在将它们的值都写入f i l m 模块中后，该阶段 结束。这也是整个系统绘制过程中耗时最多的阶段。 3 当所有采样值对像素的贡献被计算出来之后，进入后处理阶段，向控制 6 第二章光线跟踪算法与采样重建理论 台打印统计信息和系统资源耗费情况等，最后将这幅图像写入到磁盘中 保存。 图2 2p b r t 系统绘制流程图 由图2 2 中可知在完成了一系列内存分配和初始化工作之后，p b r t 绘制系 统的主要流程如下： 1 由采样器生成一系列采样，然后将采样的信息送到c o t e 模块中。 2 c o t e 模块调用绘制函数s c e n e ：r e n d e r ( ) ，该函数将采样值传给虚拟相机 模块。虚拟相机根据采样点的位置，连接采样点和镜头的位置形成一条 射线，这条所得的射线即通常所称的光线与自然界的实际光线逆向，是 由视点发出射入场景。然后虚拟相机将光线返回给c o t e 。 3 路径积分器i n t e g r a t o r 追踪该光线在场景中的传播、反射、折射的事件， 生成一条路径并返回光照值。在这个过程中要使用根据各种不同的材质 确定的b s d f 计算出射方向，使用光线与场景中各种几何体的相交运算 方法计算交点。 最后把计算所得的采样光照值记录在虚拟胶片( f i l m ) 的p i x e l 数组中。在一些 滤波、值映射处理后，最终生成用户场景文件描述的图像，即e x r 格式图片。 2 4 走样与反走样 在合成图像的过程中，对图像的连续和离散表示方式进行转换是图像处理很 重要的内容。采样就是将连续信号转换成离散信号，重建则是采样的一个逆过程。 7 第二章光线跟踪算法与采样重建理论 在图像中由于信息遗失或者错误导致的走样现象表现为锯齿形的边缘、动画 中出现的闪烁等。当原始信号的高频细节泄漏到重建信号的低频区域的时候，产 生的低频假象就称之为走样。根据产生的不同阶段，走样现象可分为两种：在采 样阶段，由于采样率过低导致的预走样( p r e a l i a s i n g ) ；在滤波阶段，由于采用的 滤波函数性能较差产生的后走样( p o s t a l i 嬲i i l g ) 1 8 - 1 9 。 首先介绍预走样现象。在频域空间观察发现，由于采样序列的采样率过低， 使得原始函数相邻频谱间产生混叠现象，这样滤波函数抽取出的频谱函数就发生 了走样。 i l 图2 - 3 采样率过低导致走样 显然，提高采样率可以避免混叠现象的产生。采样定理指出，对于均匀采样， 采样的频率不小于信号中存在的最高频率的两倍，就可以从所得采样中完整的重 建出原始信号，这个最小的采样频率称为奈奎斯特频率。但是采样定理的前提条 件是原始信号存在最高的频率，即是频带有限信号。遗憾的是，现实生活中大量 的信号都不是带限信号。例如图像中的几何体边缘是一种阶梯函数，该函数的间 断点处包含无限的频率内容，无法通过提高采样率来避免走样现象。这也是最常 见的走样现象的原因。后走样是由于选择的滤波函数没能够恰好提取出一个频谱 函数的信息而将邻近的频谱信息也包括进来的情况。如图2 4 所示： 一一 i 一 ， 图2 - 4 滤波函数较差导致走样 8 第二章光线跟踪算法与采样重建理论 针对走样现象提出的一些技术和方法称为反走样。通常可以通过改进采样的 方式进行反走样处理，下面介绍几种常见的采样方法： 非均匀采样。这种方法最简单，易行。它通过在冲激序列中引入一个随机变 量，使得采样不再是均匀分布。虽然这样也无法得到完全正确的重建信号，但是 它将图像中规则的走样假象变成了噪声，与走样相比噪声对人眼视觉系统的影响 相对较小，使人感觉图像质量有所提高。 分层采样。它是将采样域划分成互不覆盖的几个区域，在每个区域选择单一 的采样。这样既不大可能遗漏整个图像的重要特征，也避免了随机采样可能出现 采样点聚集的情况。换句话说，对于给定数目的采样，如果多个采样来自于采样 空间的邻近点，那么就不能提供在已有基础上关于图像的更多信息。最佳的情况 是各个采样点有较远的间隔，分层显然是改善了这一点。 n r o o k s 采样，也称为拉丁超立法采样法。如果只是简单的将分层采样应用 到高维空间，那么需要的采样数目将会迅速地成指数增长，这种情况称为维度灾 难( c u r s eo f d i m e n s i o n a l i t y ) 。n r o o k s 采样法解决了这个问题，它是将较高的维数 分成几个子集，每个子集使用低维分层采样的模式采样，然后将几个子集的采样 进行随机连接。这样就既能获得分层采样的好处又避免了总共采样量增加过多的 代价。与分层采样的方法相比，它选择出来的采样的分布能对整个高维空间有更 好的覆盖；并且可以在任意维中选择任意个数的采样数目，而不只是限于n x n 个采样的情况。在每一维中，沿着它的轴均匀分成n 个区域，并在每个区域产 生一个抖动采样。在某一维中将采样进行随机移动。 图2 5 二维n r o o k s 采样生成过程 图2 5 是以二维为例，要求产生4 个采样，首先沿着x ，y 轴，各分成四个 区域。沿着栅格的对角线产生随机采样，然后随机置换它们的坐标位置，最后使 得栅格中每行每列只有一个采样。同时这种方法还可以避免在分层采样中可能出 现的一种最差的情况，即多个采样投影在某一维坐标轴中相同的位置。 低差异采样。数学上提出了一个差异性的概念，用来量化采样点分布的质量。 9 第二章光线跟踪算法与采样重建理论 h a m m e r s l e y 序列和( o ，2 ) 序列都具有低差异性。利用这两个序列可以产生高维的 高质量的像素采样。低差异采样，生成的图像视觉效果比包含抖动技术的分层采 样更好，但是由于该采样具有的规则性，所以走样错误比较明显。 泊松圆盘采样。上述方法都是针对单个像素中的采样，没有考虑多个像素之 间采样的关系。为了避免产生的采样点在邻近像素间发生聚集，每次产生新的采 样点时，如果它与现有的采样点的距离过近时，则拒绝该采样点。泊松圆盘的直 径d 的选取对产生的采样有很大影响。 其他反走样技术，例如预滤波技术。它是根据采样定理，过滤掉原始函数中 不能被采样频率精确捕捉的高频部分。预过滤使得图像模糊，主要应用在图像的 纹理处理中。 2 5 自适应采样技术 自适应采样技术，是为了避免由于提高整体图像采样率而产生的巨大计算开 销，人们考虑只增加信号频率超过奈奎斯特限制的区域的采样吩们。因此判断需要 增加额外采样的区域就是关键问题。通常是通过检查邻近采样的值，找到采样值 之间存在巨大变化的区域，并假设这个区域存在高频信号。当然这种方法也存在 局限性。因为可能出现虽然区域中出现了巨大的变动，但是恰好该区域采样值是 相同的情况。或者尽管邻近采样值差异很大，但是并没有出现走样现象，比如纹 理。不过该方法还是能有效地改善一幅走样严重的图像的质量。 光线跟踪是一种基于点采样的图像合成技术。由于有限采样点的使用，场景 中的一些信息出现损失，走样错误不可避免。但是这些错误可以通过在采样值改 变很大的区域增加额外的采样来减少。为了得到可靠的数据，与均匀光照区域相 比，物体的边缘，阴影的轮廓，高亮梯度变化区域，都需要加强处理。这就需要 使用自适应采样技术：先对一个像素进行相对低密度的采样，根据初始的采样值， 一个细化标准用来决定是否需要更多的采样，最后所有的采样都用来得到最终的 像素颜色值。 对于自适应采样，大量的研究工作集中在判断哪些区域需要增加采样。由此 提出各种基于颜色强度或者场景几何体的自适应采样细化标准，来控制采样率。 以对比度作为细化标准，m i t c h e l l 对每个r g b 通道使用一种对比度度量，如 下定义：c = 争l 卫阜。其中k 和m j n 分别表示通道光强的最小和最大值。 m a x + m i n 对于任何对比度超过给定阈值的区域进行超采样。m i t c h e l l 建议r g b 的阈值分别 为0 4 ，0 3 ，0 6 ，这是根据视觉的敏感性给出的。而g l a s s n e r 提出的方法是以像 1 0 第二章光线跟踪算法与采样重建理论 素的平均颜色作为衡量标准的 2 h 。 以采样的方差作为细化标准。基于采样方差的基本思想是持续采样直到置信 水平或者说辐射光照值l 的估计值三在给定区域d 中为真值的概率是l 一口： p r ll ( 三一d ，三+ d ) l = 1 一口。这种情况即t l - a , n - i d ，其中t 表示t 分布，s l 、 7 j v 胛 是n 个采样的标准差。使用置信区间的优点在于，可以显式的限制每个像素中的 错误界限。由于每个像素的估计值不确定性程度相同，因此整个图像的噪声水平 也是相同的。考虑到基于m o n t ec a r l o 方法绘制图像的一个很大的问题是整个图 像噪声水平差异较大，上述性质是很吸引人的。 基于熵的自适应采样。香农熵即信息熵【2 2 】，它是对信息进行量化度量的一种 手段。它可以衡量出随机变量的平均信息量或者称为不确定性。借鉴信息论中的 n | 这一经典概念和相关性质，定义像素通道熵的概念1 ：h 。= 一p ，l o gp f 。其 i = 1 中p ；表示光线i 的某一个颜色通道的值与穿过其所在像素所有光线颜色值的比 值。表示经过讨论像素所有光线的数量。像素通道熵可以理解为穿过同一像 素的光线的通道颜色相似性。因此，可以作为衡量像素颜色质量的一种标准。要 作为细化标准，对像素通道熵进行归一化，得到像素通道对比度的概念： o c c = 1 一七。表示一个像素通道颜色不相似性的程度。同理可以定义像素几 l o g hs 何熵，以光线交点与眼睛的距离和与法向量的夹角作为考虑的因素。在自适应采 样的细化阶段，首先，利用给定区域中采样集合的已知信息计算出通道熵值，如 果它们的不相似性太高，就将区域进行细化，直到每个区域都均匀，即计算的相 似性值小于阈值。这个递归过程将形成一棵递归树结构。 一种两个概率分布之间差异的衡量方法称为f - d i v e r g e n c e 。这种方法是由 c s s z a7 ，_ ，a l i 和s i l v e y 独立提出的【2 5 。2 6 】。它已被应用于不同的领域，如医学成像 的定位、分类检索等。选取不同的f 函数，得到不同的f - d i v e r g e n c e 自适应才有方 法，在字面上都称之为散度。其中最重要的一些f - d i v e r g e n c e 有：k u l l b a c k - l e i b l e r d i s t a n c e 2 7 1 ，选取厂( x ) = x l o g x ；c h i s q u a r ed i s t a n c e 【2 8 】，选取厂( x ) = ( x - 1 ) 2 ； h e l l i n g e rd i s t a n c e 2 钆3 0 1 ，选取( x ) = 去( 1 一, f f ) 。 第三章高斯滤波重要性采样算法设计与实现 第三章高斯滤波重要性采样算法设计与实现 3 1 高斯滤波重要性采样算法设计 3 1 1m o n t ec a r l o 重要性采样技术 利用m o n t ec a r l o 光线跟踪方法计算，其中的方差在图像中表现为噪声现象。 为了能够降低方差值，一直以来，在优化m o n t ec a r l o 方法方面进行了大量的研 究工作。回顾第二章中介绍m o n t ec a r l o 方法时提到该方法的收敛速度为 d ( ) ，可知要想使估计值的方差减半必须将采样率增加四倍。而运行时间与 采样的个数成正比，这样减少方差的时问代价就会相当高。 要提高m o n t ec a r l o 积分的效率，即在降低方差的同时而不使采样个数大量增 加，许多理论和技术被提出。如俄罗斯轮盘赌( r u s s i a nr o u l e t t e ) t 3 1 j 和分裂法 ( s p l i t t i n g ) 是两种提高m o n t ec a r l o 方法效率的重要技术，它们都是采用增加对最终 计算结果有重要贡献的采样的可能性的方法。 重要性采样是m o n t ec a r l o 计算中经常使用的技术之一【3 2 1 。它易于应用，并 且当选择的分布函数较好时非常有效。计算m o n t ec a r l o 积分时，对采样的分布函 数p ( x ) 有一定的选择自由。如果选择的p ( x ) 函数与被积函数f ( x ) 有相似的形状，那 么m o n t ec a r l o 积分收敛的速度会加快。它的基本考虑是将工作都集中在被积函数 值相当高的地方，这样计算精确估计值的效率更高。 假设使用m o n t ec a r l o 方法计算i f ( x ) d x 积分。此时如果选择采样分布函数 ， 1 p ( x ) o cf ( x ) ，或者p ( x ) = c f ( x ) ，其中c = t 士，此时： j f 【x ) a x 目= 专喜而f ( x i ) = 专磐少( z 进 蛐3 - 1 ) 因为c 是一个常量，每个估计量都是相同的值，那么方差就为零。当然，要 找到公式( 3 1 ) 中的分布函数p ( x ) 需要知道积分的值，而这正是我们要求的，所以 公式中的理想状态几乎不可能达到。但是这表明如果p ( x ) 的形状与f 【x ) 相似，方 差就会降低。但是如果重要性采样选择的分布函数太糟糕的话，反而会增加方差 值。 1 2 第三章高斯滤波重要性采样算法设计与实现 在图形学中，经常出现的是对两个或多个函数乘积的积分求解。可能已知被 积函数中各个乘积因子的函数形式，但使用何种策略连接这些分布函数，以降低 方差多重重要性采样正是处理这种问题的一种简单和容易实现的技术。它的 基本思想是当估算一个积分的时候，对于被积函数中包含的多个采样分布，尽管 初始条件下并不知道究竟哪个函数与整个被积函数的形状近似，但是可以根据这 些采样分布，选择一个至少与被积函数的形状尽量相匹配的函数进行采样。多重 重要性采样提供了一种方法，通过权衡每种采样方式中采样的权重来去除由于被 积函数和采样密度函数不匹配而造成的较大方差值【3 孓3 4 1 。 3 1 2 滤波重要性采样 人们对采样和滤波两个方面都有了深入的研究，但是对二者之间的相互作用 还没有能够完全的理解。存在这样的情况，在没有光源采样时，如同预期的 m i t c h e l l 滤波器的表现比箱式滤波器的表现要好，能更好的改进图像的质量。但 是也会出现由于光照计算的加入使得图像噪音增加的情况。并且箱式滤波器能够 提供比覆盖范围为4 个像素宽度的m i t c h e l l 滤波器更平滑的图像效果。同时，当 给定像素得到更多采样的贡献，即包含邻近像素中的部分采样时，带采样权值的 滤波似乎没有产生更让人满意的图像。同样的效果在任何一个非均匀的滤波函数 中都可以观察到。而这种情况下箱式滤波器即一种采用相同采样权值的方法却总 是优于具有更复杂技术的滤波器。 首先的想法是，在像素边缘处采样的大量聚集或者邻近像素的采样问相关性 是走样的来源。但是当箱式滤波器在重建过程中应用在大于一个像素的范围时， 也会产生这两个问题。事实上，这个问题是由非均匀滤波函数导致的。光源采样 被随机指定给像素中的采样。这种方式，使得在光源中重要的光线采样可能被指 定给一个像素中有着较低滤波权值的像素采样，或者指定给一个邻近像素中高权 值的采样。那么方差会出现相当大的增加。根据经典的采样方法，避免这种情况 的唯一办法是，使所有采样的权值相等。 对像素使用存在采样权值且共享采样的策略，会对光源采样产生负面的干 扰。相反，我们支持无权重且无共享的像素采样策略。不共享像素采样的代价是 较低的，因为来自邻近像素的采样对于像素最终颜色的贡献是很小的，而对结果 图像的噪音减少则是很明显的1 3 6 。 滤波重要性采样中，像素采样是由滤波函数的重要性采样产生的。通过这种 方式，可使像素的较多采样分布在滤波函数值较大的区域。如果滤波函数本身的 覆盖范围多于一个像素，那么由此产生的部分采样必将位于指定象素之外。这样 在选择所需采样时将会舍弃指定像素外的采样。 第三章高斯滤波重要性采样算法设计与实现 在重建的过程中，还要区分两种情况。没有负值区域的滤波函数，最后像素 的颜色是像素中所有采样值的简单平均。含有负值区域的滤波函数处理起来会相 对复杂，在滤波函数正值区域的采样权重值为1 ，而在负值区域的权重值为1 。 首先解释采样过程，产生基于一个任意二维滤波函数f 【u ，v ) 的重要性采样， 且该函数具有有穷扩展范围。重要性采样首先要求定义一个概率密度函数( p d f ) p ( u ，v ) ，这个函数与重建滤波函数的形状很相像。作为一个概率密度函数，该函 数必须是非负的而且对整个定义域积分的值为1 。通常情况下，滤波函数f ( u ，v ) 可能违背上述两个条件而不能直接被用作p d f 。不过，f ( u ，v ) = i f ( u ，v ) i 在用因 数户归一化后就可以作为p d f 使用了，其中： 户= 肜y ) d u d v “) = 掣 公部- 2 ) 考虑滤波函数f 【u ，v ) 解析式的重要性采样。除了要求p d f ，还要求计算累积的分 布函数c d f ，p ( u ，v ) 以及它的逆p 一( “，v ) 。通过它们对初始产生的随机采样进行 变换，最后得到符合滤波函数的重要性采样。 然后考虑图像的重建过程。一般情况下，以( x ，y ) 为中心的像素，它的最终颜 色值i ( 墨y ) 是通过在像素中心放置一个以f ( u ，v ) 为滤波函数的滤波核心，对滤波函 数和它扩展范围内所有采样的辐射能量值进行乘积，。计算它们的积分求得，但是 这种传统的方法是一种有偏的计算方法。在该算法中这个值是按照m o n t ec a r l o 积分的方法，利用n 个从二维随机采样中均匀选出的日，罡r 来计算的： 11n i ( x ，