（计算机软件与理论专业论文）基于tsallis理论的自适应采样算法.pdf

中文摘要 真实感图形学是计算机图形学的重骥组成部分，舆实感图形技术的广泛应用 对其算法提出了更高的要求。基于蒙特卡罗积分技术的整体光照计算是生成赢膜 蘩粪实感图像豹主要方法。程绘铡图像熬过程孛，需甏雳离数静像豢来表示连续 的闰像，从本质上讲，绘制问题实际上就是采样的问题。本文从走样和反走样入 筝，针对某些像索的蒙特卡罗整体光照计算收敛速度较快，而另外些像素则较 缓熬特点，弓l 入窦适应采谨露法。其算法憨想为：营煲在每个豫索蠹分配较少静 固定数目的采样点数，然聪根据计算出的像素质量来决定是否增加更多的采梯 点。 在回顾了熬子方差、鬣信区间、对比蔗、香农熵秘卜敖度这魃经典的自逶 纛采襻算法之嚣，本文雩l 入了t s a l l i s 瑾论，疆爨了基予t s a l l i s 熵帮萋予 t s a l l i s 散度的自适应采样算法。在基于t s a l l i s 熵的自适应采样算法中，引入 最小二乘法根据不同的场景自动地选取合适的熵指数，由该算法生成图像在细节 秘诗算复杂靛熬壤表理较好，溅褥豹均方援r m s 也鞍其媳算法奎；农慕 ：t s a l l i s 激度的自适应袋样算法中，本文通过手动地选取散度指数的一些安数值，经过蜜 骏，证明了只黢选择合适的指数，由此裁法生成的图像和得到的r m s 数据均比以 缀的经典采样算法有很大驹提高。 关键词：蒙特卡罗，整体光照，t l 适应采样，t s a l l i s 熵，t s a l l i s 散度 a b s t r a c t r e a l i s t i cg r a p h i c si sa ni m p o r t a n tp a r to fc o m p u t e rg r a p h i c s ，a n dw i t ht h e e x t e n s i v ea p p l i c a t i o no ft h er e a l i s t i ci m a g es y n t h e s i st e c h n o l o g y , m o r ec r e a t i v e a l g o r i t h mi sr e q u i r e d t h em e t h o db a s e do nm o n t ec a r l oi n t e g r a t i o ni st h em a i n t e c h n o l o g y 幻g e n e r a t et h er e a l i s t i ci m a g e sw 醯h i 砖q u a l i t y i nt h ep r o c e s so f r e n d e r i n g ，d i s c r e t ep i x e l sa r en e e d e dt op r e s e n tt h ec o n t i n u o u si m a g e ，s oi ne s s e n c e ， r e n d e r i n gp r o b l e mi ss a m p l i n gp r o b l e m w i t ht h eb e g i n n i n g o fa l i a s i n ga n d a n t i a l i a s i n g ，t h et h e s i sd e s c r i b e st h ea d a p t i v es a m p l i n ga l g o r i t h m a d a p t i v es a m p l i n g p u t sm o t es a m p l e so nt h ec o m p l e xa r e a sa n dt h el e s so nt h es i m p l ea r e a so f t h ei m a g e n o tt h es a m eo nt h ew h o l ei m a g eb e c a u s et h a tt h ec a l c u l a t i o n so fm o n t ec a r l og l o b a l i l l u m i n a t i o no fa l lt h ep i x e l sa r ed i f f e r e n t s o m ep i x e l sc o n v e r g i n gf a s t e ro n l yn e e d f e w e rs a m p l e st og e ta c c u r a t ev a l u e sw h i l eo t h e r sn e e dm o r e a f t e rr e v i e w i n gt h ec l a s s i c a la d a p t i v es a m p l i n ga l g o r i t h m sb a s e do i lt h ev a r i a n c e ， c o n t r a s t ，s h a n n o na n df - d i v e r g e n c e ，t h et h e s i sp r e s e n tt s a l l i st h e o r ya n dp u tf o r w a r d t h ea d a p t i v es a m p l i n ga l g o r i t h m sb a s e do nt s a l l i se n t r o p ya n dt s a u i sd i v e r g e n c e o n t h eb a s i so ft h ee r r o ro fr e n d e r i n gi m a g ea n dt h er e f e r e n c ei m a g e ，t h em e t h o do fl e a s t s q u a r ei si n t r o d u c e di n t ot h ea d a p t i v es a m p l i n gu s i n gt s a l t i se n t r o p yt oa u t o m a t i c a l l y c h o o s et h ea p p r o p r i a t ee n t r o p yi n d i c e sa c c o r d i n gt ot h ed i f f e r e n ts c e n e s ，a n dt h en o i s e o ft h ei m a g e sr e n d e r e db yt h ea l g o r i t h ma r el e s st h a nt h ec o u n t e r p a r t sr e n d e r e db y o t h e rc l a s s i c a la l g o r i t h m s ，e s p e c i a l l yo nt h ed e t a i l sa n dc o m p l e xa r e a sa n dt h er m s v a l u e sa r es m a l l e r ；w h i l ei nt h ea d a p t i v es a m p l i n gb a s e do nt s a l t i sd i v e r g e n c e ，b y w a yo fe x p e r i m e n t s ，s e v e r a ld i f f e r e n td i v e r g e n c ei n d i c e sa r ec h o s e nt ov e r i f yt h a tt h e i m a g e sa n dr m s v a l u e sa l et h ei m p r o v e m e n tt ot h eo t h e rc l a s s i c a la l g o r i t h m s k e yw o r d s ：m o n t ec a r l o ，g l o b a li l l u m i n a t i o n ，a d a p t i v es a m p l i n g ，t s a l l i s e n t r o p y , t s a l l i sd i v e r g e n c e 独创性声明 本人臻掰呈交鲍学位论文楚本入在导绛指爵下进雩亍的研究工作穰取得的 研究残栗，除了文辛特嗣蕊鞋搽淀耧致落之照舞，论义孛不包含英链入疆经发表 或撰写过的研究成果，也不包禽为获得盘盗盘鲎或其他教育机构的举位或证 书而使用邋的材料。与我一同工作的同志对本研究所做的任何贡献均己猩论文中 作了明确的说明并表示了谢意。 学位论义作者签名： 催啦精 签字r 期；雌年弼庐目 学位论文版权使用授权书 本学缎论文捧者完全了勰基凄盘堂有荚僳馨、使用学位论文的舰定。 特援投吞凌盘茎霹鞋饕学娩论文豹全嫠或嫠分内容编入毒关数攥黪透露检 索，并采掰影印、缩印或扫描麓复制手段保存、汇编以供查阅和借阕。湖意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密膳适用本授权说明) 学位论文作者妣拂郏蟪 黝躲斫久 签字f 3 期；神舀年工月 g 翻 签字f 1 期：、妒f 年月游i j 第一耄 1 1 计算视图形学简介 第一章绪论 计算机图形学的研究最早起源予美国麻省理工学院，从2 0 世纪5 0 年代到 6 0 年代中期，麻管理工学院( m i t ) 积极扶事现代计算视辅助设计制造技术的 嚣据蛙嫒究。计算极图形( c o m p u t e rg r a p h i c s ) 这个本语是在1 9 6 2 冬美国寐省 理工学院林肯实验室的i v a ne s u t h e r l a n d 发表的一篇题为“s k e t c h p a d ：个 人杌遴信的图形系统“的博士论文中首次使用。它证明了交互妓计算机图形学 罴令霹行豹、有耀豹礤究领域，扶嚣确立了计算视燃形学作为一个豢薮豹学科 分支的独立地位。 2 0 世纪7 0 年代是计算机闰形掌发展过程中一个整要的历史时期。由予光栅 显示器豹产生，在秘年代裁露薅芽豹走搬图形举算法迅速发震起来。区域填充、 裁剪、消隐等基本图形概念及其相应算法纷纷诞生，闼形学进入了第一个兴盛的 时期，并开始出现实用的c a d 图形系统。又因为通用的与设备无关的图形软件的 发震，翔形软传功熊豹辍准纯| 嗣题援提了爨寒。毒 算极图形技本豹应羯进入了实 用化的阶段，进入到在军事上、工业、教育、科研、事务管理等领域。计算机图 形学另外两个重要进展冀实感图形举和实体造型技术开始产生。1 9 8 0 年提出了 巍透睾凳模型秘惫线缳踩筹法，标志豢真实感图形显示算法也逐澎成熬。 随着计算机图形学和计算机本身的发展，真实感图形学在人们日常的工作， 学习和生活中已经有了非常广泛的威用。如果用计算机在嘲形设备上篷成连续色 溺靛奏实惑鬣形，必须究残下嚣4 个基零静饪务： ( 1 ) 三维造型或建模是用数学方法建立所需三维场景的几何描述，并将它们输 入到计算机中。这一部分的工作通常是由兰维立体造型系统或曲面造型系统完成 豹。场景静死露箍述壹接影确了鹜彩的复杂性释整形绘翱豹诗舞开链。 ( 2 ) 将三维几何描述转换为二维透视图话丁通道对场景的透视变换来究成。 ( 3 ) 确定场景中所有可见面，这需要使用隐藏面消除算法将视野之外或被其他 锈俸遮挡豹不可冕螽潜去。 ( 4 ) 根据基于光学物理的光照明模型计算可见翅投射到观察者眼中的光照度大 小和色彩组成，并将它转换成适合图形设备的颜色值，从而确定投影碱面上每一 像素静颜色，最终生成黼形。 第一章 1 2 蒙特卡罗彀分 蒙特卡罗方法( m o n t ec a r l o ) ，也称统计模拟方法，是二十世纪四十年代提 出的一种以概率统计理论为指导的一类非常重要的数值计算方法。m o n t ec a r l o 方法利用随机采样，使用随机数( 或更常见的伪随机数) 来解决很多计算问题。 在积分计算中，有些积分是极其簧杂的以至于稻一般方法来计算是不可戆象 的，魏时可以搿蒙特卡罗方法来 中算这些积分。 考虑有以下积分式： i lf ( x ) a x ( 卜1 ) 。玉 公式( i - 1 串，a 为积分区域，x 是茭孛任意选取熬点，若数积魍数厂可以分解 成( x ) = g ( 盖) p ( x ) ，当x 在积分域4 上有某种概率分布，p ( x ) 是其概率密度分 商函数，0 尹( x ) l ，lp ( x = l ，此时( 1 一1 ) 式可以写为： 摧 i 。lg ( 砖p ( x ) d x ( 1 - 2 ) 艇 公式( 卜2 ) 实际上计算的是当函数g ( x ) 有概率密度函数p o , ) 时的数学期 e ( g ( x ) ) 。j c 于予e ( 譬( x ) ) ，可酸采用袖取陡梳点来近 黻的计算： ，= 联g * 吉g ( t ) ( 1 3 ) t 是在a 中随机选撵的采样点，当n 峥0 0 采样量趋向于无穷时， 方法计算积分能够得到( 卜1 ) 式精确的积分值。 ，= e ( g ( x ) ) = 熙面1 善ng ( ) 运用蒙特卡罗 ( 1 - 4 ) 也许对于被积函数f ，分解是不明显的复杂的，但是同样能够按照这种思路，稍 加变换计算其积分值，人为的选择一个概率密度函数p ( x 1 ，将( 卜i ) 式改写为 止三m 胁三筹哦 m s ) 将2 关税为公式( 1 2 ) 中的被较函数，瓣( 1 5 ) 式同徉可戳根据蒙特卡箩计算： p t o ， 埘 等h 二矧 m s ， 所以无论被积溺数如何，都可以借助于蒙特卡罗方法，把复杂的积分问联转换成 为稻辩简肇的通过淹穰采样来遥钕计算的函数数学耘繁问题。 2 第一章 可以证明，当选择的概率密度函数p ( x 1 ，与被积函数的形状越接近，所计 算出来的积分值越精确，所需要的采样点越少+ 在掇限情况下，警概率密度函数 尹o ) 寿尹( x ) = 粤堕露，只需要一个采样点裁可以得到，粒壤确俊。 难是因为，的难于计算，所以我们才会采用蒙特卡罗方法计算积分，所以也 许无法为，找到很好的p ( x ，能是可以证明，随着采样量的上升，计算误差盯是 缩小豹，误差与暴样量之阉的关系为公式 和规则采样样，毽行，= n 。效栗黼觅匿2 - 3 。还可以使用其他的分层方戏，铡如 由d i p p e 和w o l d 1 3 提出的六角形的格子，但是长方形是最容易实现的。 2 2 4 半抖幼的采样( h a l f - j i t t e r e ds a m p l i n g ) 获图2 - 3 皆露竣善塞，辩动袋撵存在一令滔题，鄹赣是采襻点容荔产生聚集 的情况。这个瓣题可班通过半辩动采样方式来解决，采样点在长方形区城内均匀 采样，但只烧长方形宽度的一半。算法如下： f o ri - - o t o 致一1 f o rj 司t o 氐一l k = 毽i + j x k = r a n d f r o m ( ( i + o 2 5 ) 毽，( i + o 7 5 ) 吃) 儿= r a n d f r o m ( ( j + 0 2 5 ) 月，( j + o 7 5 ) 灯，) 效果图见图2 - 4 。半抖动采样方戏缓解了采样点的聚集，但是比简单的抖动采样 方式更规则化。 2 2 。5 波掇蹒鑫采棰( p o i s s o nd i s ks a m p l i n g ) 避免采样点聚集的一个简单的方法就是产生一熄采样点，如果一个新的采样 点和已有的漾样点太接近，就抛弃它 1 3 1 4 。这种方法就称为波松圃缴采样， 算法如下： i = 0 w h i l ei n 置= r a n d f r o m ( 0 ，1 ) y = r a n d f r o m ( 0 ，1 ) 第二章 r e j e c t = f a ls e f o rj = 0t oi 一1 i f 【( x 一t ) 2 + ( 只- y j ) 2 】 d 2 r e j e c t = t r u e b r e a k i fn o tr e j e c t i = i + l d 是允许的最小距离( 波松圆盘直径) ， 对于适当大的d 可以使得采样点不会太聚集 但是更大的d 就会造成采样点取不到。 图2 - 2 随机采样 图2 4 半抖动采样 图2 - 1 规则采样 图2 - 3 抖动采样 图2 - 5 波松圆盘采样 第二二章 2 3 超级采棰 超级采样就是农每个像素点上均匀分毒超过个的采样点。如果采样点在空 闻被均匀分布，高频信号就会显现为态样，即他 f j 被错误的显示为低频信号。超 级采样是通过提高祭奎斯特限制来调节走样，但是并不能消除走样。问题不在于 使建了多少令采撵点，瑟是那些导致走撵垂冬频率仍然存在。该方法虽然麓单易弦， 但是它有两个致命的弱点； ( 1 ) 效粜不经济，不能自适应地增加图像分辨率。 ( 2 ) 缮麴闰像分辨率并不艇镪底解决图形走榉阋题。因为这祥骰一方瑟受翳技 术和设备的限制。另一方面由于屏幕的分辨率是一定的，不可能随方法增加，因 此降低失粪疫是有羧豹。 超级采样技术的不经济住主要是由于它对一些不必要的加密采样的屏幕联 域也进行商密度采样，从而辟致了计算量的剧增。这样就需要自适成采样。 2 4 自邋应采样 在岛适应采样中，在边缘等附近会附加跟踪光线：与越级采样不同，该技术 可以可靠的进行边缘等区域的反走样。自适应采样避免对每个像素采用同样的浆 样量，瑟建有选择攥的，氇裁蹩裰蕹橡豢的光照斡诗算难度寒决定豫繁静采棰豢。 在区域内亮度、颜色变化比较强烈，比如高光区域、阴影边界等地方，蒙特卡罗 簿法收敛速度馒，邂常震要大量豹采撵才能够计冀准确：褥在区域中光照变化并 不是十矜剃烈，比如漫反射袭面，蒙将卡罗算法收敛速度较侠，以较少的采样蠢 基本上就可以得到比较精确的结果。 叁适应算法霹瑷麓擎逢搔述必： ( 1 ) 在光线追踪中先对每个像素进行低密度采样，生成一幅初始图像。 ( 2 ) 掇攥第一步擞成的图像n 柬确定那嫂屏幕区域需要超级采样，墩就是根掘初 始样时褥到的每个像索的值采决定是否逶行再次采样。 ( 3 ) 对那些需要_ i 2 行再次采样的区域增加采样点，生成殿终所需图像。 第二多楚一令最关键豹步骤，邈是难杰耩在，是黎令算法豹核心，兹入骰了大爨 的工作。 2 4 。1 基手方差麓是适应袋样 在 1 5 中，l e e 等人提出了基于像索方差的方法。该算法利用像豢的方嫠来 译餐一令像素豹震璧。像素豹方差反映了像素痰番个采撵煮豹值秘均毽豹离教毽 第二牵 度。如果方差越大，那么像素内的采样点的值波动越大，像素的质量就越差，就 翥要怼这令像素遴褥再次采捧。 算法是基于像豢内n 个随梳采样点，置，i = l ，n ，分别对疯各个采 样点的的光照度( l u m i a n c e ) ，l 是n 个采样点平均光照艘。通过蒙特卡罗方法 估计缮出： 三：三y 三f ( 2 一t ) 疗? 像素的方差定义如下： s 2 = 圭娓一) 2 ( 2 2 ) 强一个像素的方差超过预定的值时，就对这个像素增加采样点，轰捌这个像 素的值小于预定的阀值。 2 4 。2 基手置僖区阖豹自逶痰采样 在 1 6 中，p u r g a t h o f e r 掇出了基于置信区间的方法。置信区间这种方法基 于像索的光照度l 。l 定义见公式( 2 - 1 ) 。臀信区间算法怒一直采样赢剿置信水 平达剿一定豹范围，期壹到 p l e l - d ；l + d = l 一毋 ( 2 3 ) 卜a 就是置信水平，d 是所允许的误差，在糕幅图像中是样的，p 代袭特定事 件的概率。这个算法的优势由予所有的像素值都是以同样不确定性程度来估计 夔，掰疆噪声窳警凌整令图豫上楚一样豹。瑟蒸予蒙特卡梦方法绘制的麓题之一 就在予在整个图像上噪声水平嫩不一致的，因此，利用置信水平的这种方法来评 价像索的质量具肖一定的优势。但是，这种方法没有考虑人眼的视觉因索。 2 4 3 基于霹琵凌( c o n t r a s t ) i 羹适应采祥 谯 1 7 中，m i t c h e l l 提出了经典的对比鹰( c o n t r s t ) 算法。对比度定义为： c 。k 二刍( 2 4 ) 三一+ 毛。 在公式( 2 4 ) 中，工。，k 。分别一个像素所有采样点的最大的和最小的光照 度值，一个采样点的值分别包括3 个颜色通邋：红、绿、菔。基于视觉系统的相 对敏黪度，这三令蕨色通道的溺馑分剐为0 4 ，0 。3 ，0 6 。如果一个像素瓣三个通 道的任何一个计冀得到的对眈菠值高于所给的阂值，那么就对这个像素增加采样 点。 在 1 8 中，s i m m o n s 基予以上的概念( 对比度和感官知觉 ( p e r c e p t i o n ) 1 7 】【1 9 】) ，缓蠢l 了权篷，定义为： 第二章 地4 k t m z x - - r m mr 。+ 导毫一- v k b m d 叱- b m b 。 ( 2 _ 5 ) 在公式( 2 5 ) 牵，m a x ，m i n ，a v g 分嗣是羟、缘、蓝三今颜色逶遂懿矮天，最小 和平均光照值。 在第三章最小二乘法分析中用的是基予公式( 2 4 ) 的对比度定义。 2 霹。4 基于香农熵( s h a n n o n ) 的宣逶应采样 r i g a u 。f e i x a s 和s b e r t 邋过引进香农熵来评测穿过一个像素所有光线的均 一链袋傲是适应袋棒 2 0 ，2 1 ，2 2 3 。 令x 为为一个随辊变量豹集合，x 。x ：，各苓糖黼，p = p n 孙 是其 对威的概率分布，且p k = l 那么香农熵就定义为 t = l 丑= 一热l 0 9 2 致= e ( 1 0 9 土。) ( 2 6 ) 一l o g p k 表示扎所代表的信息，信息熵给出了一个随机交爨所表示的平均信息量。 在算法中，n 是穿过一个像素的所有光线数，即像素中的采样点数，见指的 是对予同一个颜稳通道，其中条光线所带来的颜色值与穿过这个像索辑有光线 群带来的颜色德的总和的眈德p k = ：l 。警见( k = l ，n ) 的值褶闷备等于二 丘 甩 k = l 时，熵值达到最大，最大为l o g ，封，当其中的一个概率慎为l 时，香农熵达到最 小，最套篷为0 ，定义0 l o g ，0 = 0 。 2 4 5 基于f 一散度( f - d i v e r g e n c e ) 自邋应采样 r i g a u ，f e i x a s 移s b e r t 逐雩| 送7 菇强耱不露靛方法基于f - d i v e r g e n c e ( f 散度 2 3 】) 的自适应算法。 在 2 3 中，共提出了三种不同的f 一散鹰算法，并进行了对比，在本论文中， 取其中效果最好的箕法基于h e l l i n g e r 距离( d i s t a n c e ) 【2 4 豹自适应雾法和本 论文所提出静算法进行比较。h e l l i n g e r 躐离定义为； 2 ( p ，口) = 妻( 厄一厄) 2 ( 2 7 ) 二，= l 最：毒l ，嚷：三，终壹条转楚三三誓丽 0 的值，t s a l l i s 熵是凹函数。当n = 2 时，t s a l l i s 熵就被称为t s a l l i s 二元熵，如图3 一l 所示。 h w r ( ) 2 击( 矿+ ( i - p ) l 1 ) ， 3 7 图3 - it s a l1i s 二元熵和s h a n n o n 二元熵 在算法中，t s a l l i s 熵写为： 研= 忐( 1 一) ( 3 8 ) 。( q 1 ) 、智 和香农熵里含义一样，l 表示颜色通道，n 是穿过一个像素的所有光线数，见指 的是对于同一个颜色通道，其中一条光线所带来的颜色值与穿过这个像素所有光 线所带来的颜色值的总和的比值，p k = ：l 。为了准确地描述像素的质量，像 丘 素的熵值需要归一化。在本论文算法中，使用的是r g b 颜色系统，对于每一个颜 色通道，t s a ll i s 熵值归一化为： 7 = 上 ( 3 - 9 ) l o g 。疗 综合所有的颜色通道月。，像素的质量就定义为： m 是每一颜色通道的权重，对于r g b 颜色空间来说，其权重分别为0 4 ，0 3 ，0 6 。 i = 去：。毋表示对于每一个颜色通道一个像素内的平均颜色值a 把以上t s a l l i s 熵定义的像素质量的测量方法用在白适应采样算法中。自适 霉酗 第三章 应采样算法如下： 程序的主要功能由函数g e t n e x t s a m p l e ( ) 来实现在渲染过程中生成所需的 取样点，直到图像中所有像素所需取样点全部生成。 ( 1 ) 首先，根据设定的每个像素取固定数目的取样点，计算他们的颜色值，加 入最终图像。根据所得到的一系列颜色值按照t s a l l i s 熵定义求取像素质量的方 法对像素的质量进行初步估定。 ( 2 ) 然后判断像素的质量是否满足预先设定阂值，如果不满足，增加一定数量 的取样点，计算他们的颜色值，加入最终图像，然后和前面计算的颜色值一起重 新作为估算这一像素的质量，如果质量仍不满足设定值，则重复上面的过程，直 到满足要求或达到设定的能够取的采样点数目的最高值。 函数说明： c o m p u t e q u a ( ) ：基于信息熵的像素质量计算方法。 输入：像素中现有取样点的颜色值。 输出：像素的质量值。 g e t r a d0 ：计算在指定像素中的取采样点并计算其颜色值，加入到最终图像。 输入：像素位置，指向取样点数据类型的指针 输出：返回该像素中某个取样点计算出的颜色值 本程序的主要函数伪代码： g e t n e x t s a m p l e ( ) ： f o r ( y 从起始像素y 坐标开始到中止像素y 坐标) f o r ( x 从起始像素y 坐标开始到中止像素x 坐标) ( 像素质量值初始化为0 ： 设置像素质量初步判断所需取样点的数量h u m ； 计算n u m 个该像素中取样点的颜色值，加入最终图像； 根据上一步的值判断像素的质量； w h il e ( 像素质量满足要求或达到最高取样点) f 计算增加的耿样点的颜色值，加入最终图像； 根掘前面两部分的值计算像素的质量： e n do fw h i l e 返回： 结束 对于t s a l l i s 熵定义的评估像素质量的算法，其中的指数q 是未知的，但 第三章 楚它又楚歪关重要豹，影翻藿t s a l l i s 熵不确定镶熬大，l 、。鞠 嚣对麓辫数进行选 择是一个难点 2 6 2 7 2 8 。可以对q 间隔地取一些实数 踅，按照上筒的程序步 骤，利用场景文件求生成图像，然后比较图像效果，最终找到一个念适的q 值。 经过实验证明如果# 选择合逶的q 值，蘩于t s a l l l s 熵的蠡适应算法在生成效莱 上是优于熊他算法的。但是不同的场景需要不同的q 值，如果每次都这样尝试筝 魂熬来取 罄合适豹q 毽，爨l j 会瀵耗大爨不必要豹隧闯。 在本论文中，尝试着引入最小二乘法理论自渤地选取指数q 值。 3 3 。2 最, b z 乘晷归方法分析 设经验方程是y = f ( x ) ，方程中含有一贱待定系数a n ，绘出真实慎 ( x i ，y i ) | i = l ，2 n ，将这些x ，y 镬代入方程然后作熬，萄以攒述误差： y i f ( x i ) ，为了考虑整体的误差，可阻敬平方和，之所以要平方是考虑到误差w f 可负宣接相加可以相互抵消，所以记误差为：萨( y i f ( x i ) ) 2 ，如果是一个多 元番鼗，骞8 r l 共1 1 令未翔薰，现在要求黪是最小僮。繇戳必然满是露各变量靛 偏导等于o ，于是子辱到n 个方程： d e d a l = 0 d e d a 2 = o d e d a n = o n 个方程确定n 个术知量为常量是理论上可以解出来的。用这种误蓑分析的方法 进行回归方程的方法就是最小二乘法。 辗豢激上弱鬣夺二乘法壤论，羁瓣泰勒公式，搀t s a l l i s 滚在譬= i 点最嚣 得到： h ( z ) z 一最i n 冀一去( 孽一1 ) 芝：置( 1 n 最) 2 ( 3 1 1 ) 在本论文中，需要个参考德，使得t s a l l i s 熵的展开值和这个参考值差的平方 靼最，j 、，具体式予定义如下： s ：芝( 掣_ q ) ： ( 3 - 1 2 ) m 为图像中所有像豢的个数，烀；( 茗) 代表每个缳袭中t s a t l i s 熵的氇，好二袭 示t s a l l i s 熵的最大值t 砩。= ( n “9 - 1 ) 。同样根据泰勒公式，把竹。4 在q = l l q 点处展珂缛到： h “4 l + l n n ( 1 一g ) + 喜( 1 n n ) 2 0 g ) 2 ( 3 一1 3 ) 则 第三章 日l ：| x = i 七( 月“9 一1 ) z i n n + ( 1 i l 疗) 2 ( 1 一g ) ( 3 一1 4 ) - 一q 上 q 代表参考图像每个像素的值，它由对比度和标准差两部分线性组合，见公式 ( 3 - 1 5 ) 。为了单位上一致，这翠使用标准差。 q ：口型竺+ b + ! ! ! 型( 3 一1 5 ) s t d v 8 c o n t r a s l m x a 取0 6 6 ，b 取o 3 4 ，s t d v a r 是标准差，c o n t r a s t 是对比度，$ t d v a r m ，表示标准 差中的最大值，c o n t r a s t m 。表示对比度中的最大值。 对公式( 3 - 1 2 ) 进行一阶求导运算，并令导数为零，得到： ( ( p k ( i n p k ) 2 + 以l n ( p k ) i n n ) ( p ki n ( p k ) + q si n n ) ) g = l i l t 一 ( 3 1 6 ) ( ( 寺仇( 1 f l 以) 2 一寺g ( 1 n n ) 2 ) ( 仇( 1 n p k ) 2 + 见l n ( p k ) i n n ) ) j 。l 利用所求的q 值，按照3 3 1 节所描述的算法，加上场景文件，整个程序就是一 个完整的可执行程序，整体算法流程见3 3 3 节。 3 3 3 整体算法流程 根据实验流程，具体的实验结果和分析见第四章。 第二章 3 4 探讨t s a l l i s 散度( t s a l l i sd i v e r g e n c e ) 在自适应采样的应用 在 2 3 中，r i g a u ，f e i x a s 和s b e r t 引入了f - d i v e r g e n c e ( f 散度) 柬评价 像素的质量。在本节中，主要探讨t s a l l i s 散度在自适应采样中的应用。 当评价一个像素的质量时，主要是看各个采样点值和所有采样点的平均值的 距离，如果采样的值都在平均值左右徘徊，大小相差不大，那么这个像素的质量 就比较高，反之则低，就需要增加适当的采样点。散度理论能够很好地描述概率 分钿之间的距离，它们曾被广泛地应用在图像处理和一些工程领域 2 9 3 0 3 1 。 定义p 和q 是两个离散变量，由t s a l l i s 所提出的t s a l l i s 敬度定义为 3 2 ： 1 一 岛( p i i q ) 2 击( 1 - 善- 虿p ) ( 3 。1 7 ) j ：iq p ，q ，分别是p 和q 的概率分布。 利用公式( 3 1 7 ) 所定义的t s a l l i s 散度，自适应采样算法描述如下： ( 1 ) 先在每个像素内采少量的同样的采样点，得到每个采样点的光照度的值 刨。：。 ( 2 ) 定义b = l 和q l = 二，像素的质量定义为： ” 1 一 q u a l i t y = 二d l ( p i l q ) ( 3 1 8 ) 代表一个像素里的平均光照度，定义见公式( 2 - 1 ) ，1 3 为像素内的采样点数。 ( 3 ) 在采样过程中，当所定义的q u a l i t y 的值大于某一预先定义好的闽值时， 那么就要在这个像素内增加采样点数，直到小于这一闽值或者达到最大的采样点 数目。 注意在公式( 3 一1 8 ) 中要乘以平均光照度的值，就象g l a s s n e r 所定义的经典 的对比度一样 3 3 ，除以n 是为了不受采样点数目的影响。 在公式( 3 1 7 ) 中，也有一个参数0 ，如果用3 3 2 节所描述的最d - 乘分 析法来求公式( 3 1 7 ) 中a ，则会由于最终所要解方程阶次太高而不能实现但 是在本文4 3 节中尝试地取一些a 值，并得到基于t s a l l i s 散度的自适应算法的绘 制图像，证明了如果能选择合适的q 值，此算法的提出是成立的。 第四鬟 第四章实验结果与分析 在备个领域中广泛应用的信怠熵技术的弓l 入为裔适应采样技术的发震开辟 了条毅豹黪径，露算法是否骞效仍霉要实验来验证，这一章中我 f 】将用联提出 的算法绘制一些图像，并和以往的缀典算法进行比较。 4 。1 实验环境 在鬟验平台p b r t 上 3 4 】，我们运行了本论文中搓出的在随梳路径追踪过程 中的自适应采样算法。掰有的算法运行在p 41 8 ，2 5 6m br a m 为了更好她测 试这个算法，我们选取了三个场景。场景l 是一个经过改修的c o r n e l l 盒予，其 表嚣具寿漫发射鞠镶面反射豹特性，还有个秘天花板相接的椭圆形的光源。虽 然这个场景的材质不是报复杂，但楚这个测试场景几乎包括了所有的光照效果， 即软弱影( s o f t s b a d o w ) ，潮色( c o l o rb l e e d i n g ) ，焦数( c a u s t i c s ) 和离光 ( h l g h lig h t ) 。测试场景2 是个复杂的场景包括3 个光源和许多带有漫反射和 辘夔反瓣特热豹嚣片。场景3 包括纹理秘6 0 0 0 0 多个荣露漫反射和镜西反射特 性的面片。三个场景的分辨率分别怒2 0 0 * 2 0 0 ，2 5 6 * 1 9 2 ，2 0 0 * 2 0 0 ，标准图像是在 隧枫光线追踩孛每令像素分剐采1 0 0 0 0 ，1 0 0 0 0 ，1 0 0 0 0 个采样点，宅织是爨来判 断用不同方法所生成图像与之的误差。在本论文中，我们使用缀常用的r m s ，即 l ， 均方根的方法。r m s e r m - - i ( o ，e r o ) 2l ，五，州和，分别为标准 a “p “p ， 图像和所计算图像的像索值。 4 ，2 基芋t s a l l i s 熵自适应采样笺法黪实验结暴 4 2 1 实验 实验一是利用场景l 来测试基于t s a l l i s 熵的自适应采样算法，根据3 3 节 掰提出鲍算法，在该场荣中，t s a l l i s 璃指数q = 1 8 5 。 凰4 一l 鼹示了平均采样点分别为3 4 ，5 8 ，1 1 6 ，2 1 6 ，4 1 3 的基于t s a l l i s 熵 和其他算法的r m s 值的比较。 图4 2 分别显示了平均采样点为5 8 的基予t s a l l i s 信怠璃，p 敬度，香农 傣息熵，置傣区阈算法鹳效粜图和r 燃值，鞠傻分别为 0 9 9 8 ，0 9 9 8 5 ，0 9 9 3 5 ，0 9 7 5 像素中允许最多采样点。初始采样点，每次增加的 第四犟 袋徉熹分粼是9 * 9 ，9 ，9 ， t s a l l i s 赡r m s = 5 0 5 香农熵r m s = 5 9 0 图4 - 1b o xr m s 魏线 匿4 - 2b o xt s a l l i s 熵绘镥 f 一敖发r m s = 5 7 0 霄信区问r m s = 6 9 3 第四章 从嫩成图像来考，基于t s a l l i s 熵的自适成采样算法在阴影和边界及玻璃球 等难戮绘露l 懿复杂嚣域筠噪声煮魄其缝雾法帮簧少，糍够较好逢表凌鹫豫豹缨 节。 4 。2 2 实验二 实验二是利用场景2 来测试基于t s a l l i s 信息熵所提出的算法，根据3 3 节 所提出的算法，在该场景中，t s a l l i s 熵指数q 。1 7 3 。 图4 3 显示了平均采样点分别为3 3 ，5 2 ，7 7 ，1 1 4 ，2 2 9 ，4 1 9 的基于t s a l l i s 熵帮箕稳算法豹r m s 德的范较。 图4 - 3r o o mr m s 曲线 燃4 - 4 分别显承了平均采徉点海7 7 的基予t s a ll i s 售怠熵，f 一教度，香农 信怠嫡，置信区间算法的效栗图，溺值分剐为0 9 9 1 5 ，0 9 9 8 9 ，0 9 9 7 2 ，0 9 8 3 5 。 像素中允许最多采样点，初始采样点，每次增加的采样点分别是1 0 1 0 ，1 0 ，1 0 。 从圈4 - 4 生成的四幅图像来餐，出基于香农熵采样算法擞成的图像噪声点最 多，茏葜在毙嚣部分，嚣基予t s a l l i s 薅熬采撵簿法生戒熬黧像虽然鑫琏翡先潺 程度不及基于置信区间和f 一散度，但是总体的r m s 比两者小，而且在细节描述 上优于另外两个，如图中柱子的阴影和中间大象棋的阴影处，见图4 5 。 第四章 t s a l l i s 熵r m s = 3 4 0 f - 散度r m s = 3 5 3 臀农熵r m s = 4 2 4 黉信区间r m $ = 4 i i 图4 4r o o mt s a l l i s 熵绘制 t s a l t i s 熵 4 2 3 实验三 f 一散发 耱农璃嚣馈送阔 灏4 - 5r o o m 霞影始 实验三怒利用场景3 束测试基于t s a l l i s 熵的爨适应采样算法，擐搦3 3 节 繇提出戆黪法，在该场景孛，t s a l l i s 矮摇数譬= 毒1 3 。 图4 - 6 嚣示了平均采棒赢分剐为6 6 ，1 2 4 ，2 0 1 ，4 0 2 的基于t s a t l i s 熵和其 他算法的r m s 值的比较。图4 7 分别显示了平均采样点为6 6 的基于t s a l l i s 信 息熵，香农信息熵，置信区间，f - 散度算法的效粜图。像素中允许最多采样点， 繁姻章 识始浆襻点，每次蠖热鲍采撵点分裂楚9 * 9 ，9 ，9 。 图4 - 6s p o n z ar m s 曲线 t s a l1i s 熵r m s = 7 。6 4 f 一散度r m s = i o 2 3 褥农燎 髯倍区间 图4 7s p o n z at s a l l i s 熵绘制 撼四章 放銎4 7 来臻，由蒸于t s a l l i s 熵豹采撵算法整体生成的噪声点蠼少，r m