（计算机应用技术专业论文）使用组合度量函数的自适应采样算法研究.pdf

中文摘要 在真实感图像绘制的研究中有两个主要的发展方向。其一是提高绘制的真实 感，真实地再现各种复杂的光照场景。另一个就是在图像质量与计算量之间取得 平衡，用尽可能少的计算量得到尽可能高的图像质量。我们的研究就聚焦于第二 种情况。自适应技术就是为了应对这种要求而提出来的技术。自适应技术通过将 采样数目不平均地分配到各个像素上来达到目的。即从初次采样后得到的图像中 挑出质量不好的区域，再追加计算量。自适应技术己经成为满足这种要求的主要 技术手段。而在这种方法中，评价质量好坏的标准是最关键的部分。 除了自适应技术，p r o g r e s s i v er e n d e r i n g 也是一种需要平衡图像质量与计 算量的技术。在这篇论文中，我们对自适应、质量评测标准给出了详细地介绍。 同时还对一种经典p r o g r e s s i v er e n d e r i n g 算法进行了详细介绍。从这三方面的 知识中，我们提出了自己的组合测量标准，并把它应用到自适应方法中。同时我 们改变了自适应采样中最常用的控制方法，代之以四分原始图像平面的技术。我 们通过大量的实验较为全面地探讨了这种新方法的表现。实验的结果图像与超采 样所得的结果求r m s 值。通过这个值与对应的平均采样点数就能看出算法的优 劣。通过这样的方法我们将实验结果与对应的经典对比度控制的自适应技术进行 可比较。我们对最后的结果中的优点和不足之处给出了详细地讨论，并对将来的 发展提出了建议。 关键词：自适应采样组合质量评价测度光线跟踪四分树整体光照 a b s t r a c t t h e r ea r et w og o a l sf o rr 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 o n ei st op r o d u c e p i c t u r e st h a te x a c t l yl i k eap h o t op r o d u c e db yac a m m a r e ；i tc a l ls i m u l a t ea l lk i n d so f i l l u m i n a t i n gc o n d i t i o n sa n dg u a r a n t e ea r e a l i s t i cr e s d t t h eo t h e ri st og a i nab a l a n c e b e t w e e nt h ei m a g eq u a l i t ya n dc o m p u t a t i o np r i c e w ew a n tg o o di m a g e sa sl e s s c o m p u t a t i o na sp o s s i b l e w ed e d i c a t et ot h es e c o n dg o a l o n ep r e f e r a b l ec h o s e ni st h e a d a p t i v es a m p l i n gt e c h n o l o g y t h ea d a p t i v es a m p l i n gt e c h n o l o g yc a l ld i s t r i b u t e c o m p u t a t i o na c c o r d i n gt ot h eq u a l i t yo fd i f f e r e n ta r e a si ni m a g ep l a n e a f t e ral o w s a m p l er a t e ，w eg e ta l o wq u a l i t yi m a g e t h em e t h o dc a nf r e dw h e r et h eq u a l i t yi sn o t e n o u g h ，a n da d ds a m p l e st ot h ea r e a t h ek e yt ot h ea d a p t i v es a m p l i n gt e c h n o l o g yi sa g o o dm e a s u r e m e mo f p i x e lq u a l i t y b e s i d e st h ea d a p t i v es a m p l i n gt e c h n o l o g y , p r o g r e s s i v er e n d e r i n ga l s on e e d sa b a l a n c eb e t w e e nt h ei m a g eq u a l i t ya n dc o m p u t a t i o np r i c e w ei n t r o d u c et h e k o n w d e g ea b o u ta d a p t i v es a m p l i n g ，q u a l i wm e a s u r e m e n t ，a n dac l a s s i cp r o g r e s s i v e r e n d e r i n gt e c h n o l o g y w eg e ti n s p i r a t i o nf r o mt h ek o n w d e g ea n dp r o r r i p to u ro w n q u a l i t ym e a s u r e m e n t ，a n dp r a c t i c ei ti na d a p t i v es a m p l i n gt e c h n o l o g yf r a m e w ea l s o c h a n g et h ec o n t r o lf l o wa n dr e p l a c ei tw i t haq u a d t r e ef r o mt h eo r i g i n a li m a g ep l a n e w es t u d ya l ls p c c t so ft h ep e r f o r m a n c eo ft h en e wa l g o r i t h mb ye x p e r i m e n t s w e c o m p a r et h er m so ft h er e s u l ti m a g ea n dt h es t a n d a r di m a g ep r o d u c e db yh e a v i l y s a m p l i n g t h er m sa n dt h ec o r r e s p o n d i n ga v e r a g es a m p l i n gn u m b e rd e n o t et h e p e r f o r m a n c eo ft h ea l g o r i t h m w ec o m p a r et h ea l g o r i t h mw i mt h ec l a s s i cc o n t r a c t e d b a s e da d a p t i v es a m p l i n gi nt h ew a y w es t u d yt h ea d v a n t a g e sa n dt h es h o r t a g e s a t l a s tw ep r o p o s ea d v i e e sf o rt h ed e v e l o p m e n to f t h ea l g o r i t h m k e y w o r d s ：a d a p t i v es a m p l i n g ，c o m b i n a t i o nm e a s u r e m e n t ，r a yt r a c e ，q u a d t r e e ， g l o b a li l l u m i n a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：焱踞、签字日期：如儡年三月冲日 学位论文版权使用授权书 本学位论文作者完全了解叁盗盘堂有关保留、使用学位论文的规定。 特授权鑫凄盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 嘛归、 签字蜀期：如6 年z 月计日 导师签名裤砍 签字日期：沙多年乒月竹只 第一章绪论 第一章绪论 真实感图形学是计算机图形学中的一个重要组成部分，它的基本任务就是将 储存在计算机中的三维场景变成具有真实感的图象。随着计算机图形学和计算机 本身的发展，真实感图形学在我们日常的工作、学习和生活中已经有了非常广泛 的应用。而随着计算机计算能力和久们审美品位的不断提高，人们对逼真图像的 要求也越来越高。但是，绘制一幅逼真的图像并不容易，越逼真的图像就需要越 复杂的光学模型来描述。另一方面，人们又对生成图像的时间有了很高的要求， 希望能找到在时间和质量上得到很好平衡的算法。人们对图形学越来越高的要求 促使这图形学的技术和理论迅猛发展。 1 1 研究的内容 我们把在已知物体物理形态和光源性质的条件下，能够计算出场景的光照明 效果的数学模型称为光照模型。在真实感图形学中，为了模拟现实世界中的场景， 我们一般需要知道这个场景的光照效果的物理模型，然后我们用一个数学模型来 表示它，通过计算这种数学模型可以得到计算机模拟出来的真实感效果。在现实 世界中，光照效果一般包括光的反射、光的透射、表面纹理和阴影等。这种模型 可以用描述物体表面光强度的物理公式推导出来。早期的光照明模型都是基于经 验的模型，只能反映光源直接照射的情况，而一些比较精确的模型，通过模拟物 体之间光的相互作用，可以得到令人满意的结果【1 】。 基于场景几何和光照模型生成一幅真实感图形的过程称之为绘制 ( r e n d e r i n g ) 。常用的真实感图形绘制算法包括扫描线算法、光线跟踪算法、光 能辐射度算法等。由于光栅图形屏幕通常包含数十万甚至上百万个象素，因此， 如何开发利用景物的空间连贯性，提高绘制算法的效率也是真实感图形技术研究 的重点。 真实感图形生成系研究的几个主要部分包括；颜色视觉、简单光照模型、局 部光照模型、光透射模型、纹理映射、整体光照模型、实时真实感图形学技术。 在这几个主要的部分中，我们致力于对整体光照绘制算法的研究，尤其关心算法 如何在计算量和图像质量之间取得平衡。这也是我们实验设计的目的和出发点。 第一章绪论 1 2 研究的背景与现状 1 9 6 7 年，w y l i e 等人第一次在显示物体时加进光照效果，这是光照模型的最 初提出。早期发展的简单光照模型包括p h o n e 光照模型、g o u r a t m d 光照模型。 光透射技术、阴影生成技术等。可以计算经过点光源照明的物体表面的光强，实 际上就是一种局部光照明模型。这些都是较初级的经验模型。 稍后整体光照明模型被w h i t t e d 提出。这是可以处理在物体之间光照的相互 作用的模型。它在渲染过程中考虑了整个环境的总体光照效果和各种景物间光照 的相互影响。整体光照计算不关心物体的三维模型的建立，主要目的是，在已建 立的现实场景模型包括物体与光源下，通过计算模拟出现实世界中实际的光照效 果，生成更为逼真的场景图像。 整体光照算法有三大主要的计算方法：光线跟踪算法( r a yt r a c i n g ) 【2 】，辐 射度算法( r a d i o s i t y ) 【3 ，4 】和光子映射法( p h o t o nm a p p i n g ) 【5 】。这其中光线追踪 法有它突出的优点，他思想简单，流程清晰，易于实现和理解。因此，我们选用 它作为我们使用的绘制方法。当然它也有它的缺点，计算量大是其中最突出的一 个。为了克服这一缺点，我们需要仔细平衡计算量和图像质量之间的关系。白适 应就是为了应对这一问题提出的策略之一。 1 3 本文的组织 自适应采样技术作为在保证图像质量的前提下提高图像生成速度的技术，它 的研究具有重要意义。其中的关键问题是质量评测的问题，因此我们提出了一个 新的质量评测尺度。同时我们还使用了一种不常使用的控制策略。我们使用r m s 来对试验结果分析，并取得了一些有意义的结论。 论文的第二部分简单回顾了一下需要使用的理论基础和所使用的绘制系统。 在此基础上。论文第三部分着重讨论已有的平衡图像质量和计算量的技术。在这 些技术中，都需要对图像质量进行评估，所以第四部分详细探讨了这一测度函数。 新的测度函数以及它的使用算法也在这章提出。第五部分通过实验对我们所提出 的算法进行了验证，并分析了算法的正确性、有效性和表现的稳定程度，同时对 算法的缺点进行了讨论。最后我们在第六章对整个工作进行了一个总结，对未来 的工作提出了建设性的意见。 第二章理论基础与绘制系统 第二章理论基础与绘制系统 我们研究的理论基础是蒙特卡罗光线跟踪算法，所使用的绘制系统是p b r t 。 下面我将用两节的内容简单的介绍一下。 2 1 蒙特卡罗光线跟踪算法 2 1 1 光线跟踪算法 由光源发出的光到达物体表面后，产生反射和折射，简单光照模型和光透射 模型模拟了这两种现象。在光照模型中，反射被分为理想漫反射和镜面反射光， 在简单光透射模型把透射光分为理想漫透射光和规则透射光。由光源发出的光称 为直接光，物体对直接光的反射或折射称为直接反射和直接折射，相对的，把物 体表面问对光的反射和折射称为间接光，间接反射，间接折射。这些是光线在物 体之间的传播方式，是光线跟踪算法的基础【6 】。 光线跟踪法的基本思想为：对于屏幕上的每个象素，跟踪一条从视点出发经 过该象素的光线，求出与环境中物体的交点。在交点处光线分为两支，分别沿镜 面反射方向和透明体的折射方向进行跟踪，形成一个递归的跟踪过程。光线每经 过一次反射或折射，由物体材质决定的反射、折射系数都会使其强度衰减，当该 光线对原象素光亮度的贡献小于给定的闽值时，跟踪过程即停止。 光线跟踪算法成功地模拟了景物表面间的镜面反射、规则透射及阴影等整体 光照效果，但是由基本的光线跟踪算法，每一条射线都要和所有的物体求交，然 后再对所得的全部交点进行排序，才能确定可见点。因而，对于复杂环境的场景， 这种简单的处理地效率就很低了，这里就需要对光线跟踪算法进行加速。我们的 算法，也是加速算法的一种。 2 1 2 蒙特卡罗积分 蒙特卡罗方法( m o n t ec a r l o 方法) ，也称统计模拟方法，是二十世纪四十年 代提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。蒙特卡罗 方法利用随机抽样，使用随机数( 或伪随机数) 来解决计算问题。 【7 】较详细地描叙了蒙特卡罗德方法。它的基本思想为：为问题建立一个概 第二章理论基础与绘制系统 率模型或随机过程，使它的参数等于问题的解；然后通过对模型或过程的观察或 者抽样试验来计算所求参数的统计特征。最后给出所求解的近似值。 蒙特卡罗方法有着自己独特的风格，有三个明显的特点： 1 1 方法或者计算程序简单； 2 ) 收敛的概率性且收敛的速度与问题的维度无关； 3 、适应性强： 2 1 3 蒙特卡罗光线跟踪 了解了光线跟踪和蒙特卡罗积分的主要思想，就能很好地理解蒙特卡罗光线 跟踪。其实就是用蒙特卡罗方法来解成像平面上的光照强度的分布问题。因为显 示屏是一个光栅结构。该问题实质上就是求屏幕上各像素亮度值的问题。每个像 素的亮度值可视为该像素区域内的亮度均值。按照蒙特卡罗的方法，首先就必须 从成像平面上采样，求它的统计特征。每个采样所得的位置与视点相连可得一光 线，然后使用光线跟踪的技术求之即可。 这里我们探讨一下采样对计算的影响。计算机在光栅设备上生成的图形是由 像素的点阵组成，这幅图形的点阵的多少决定了图像的分辨率。图像数字化就是 将连续图像离散化。其工作包括两个方面：采样和量化。 所谓采样就是把一幅连续图像在空间上分割成m n 个网格，每个网格，即 象素用一亮度值来表示。由于结果是一个样点阵列，故又叫做点阵采样。为了得 到一幅连续的图像，在采样点阵的规模具有一定的要求，每个采样点的亮度值与 原图像的尽量接近也是得到令人满意的图像的必要条件。在光线跟踪算法中，为 了得到每个象素的亮度值，通常采取的采样方式为，在每个象素内取一定数量的 样点，采样点的数量越多，一般所得象素的颜色与原图像越接近。这样做的理论 依据就是采样定理。 2 2 绘制系统p b r t 【8 】详细描绘了p b l 玎系统的设计和实现。p b r t 系统使用的是一种插件 ( p l u g i n ) 结构。在系统中有一个核心模块- - c o r e ，包含了控制整个系统绘制流 程的代码，但是没有任何的关于具体几何形状或光源描述的实现代码。c o l e 模块 为各种插件类型提供了抽象基类或接口，所有的插件都是从c o r e 中继承派生的。 当进行场景绘制时，绘制系统会根据场景文件描述来动态加载需要的插件。这种 结构使得系统易于被扩展，甚至我们可以自己向c o r e 模块中加入新的接口，然 后在外部实现相应的插件。 第二章理论基础与绘制系统 p b r t 系统的图形绘制可以分为三个阶段，首先是读取用户提供的场景文件。 场景文件本身是一个文本格式文件，该文件给出场景中的物体的位置，物体的几 何形状以及表面的材质属性，光源的位置以及发光强度信息，还有场景中的虚拟 镜头信息等的描述。当读入场景信息完成后，所有的场景信息在内存中构造完毕， 各个插件的构造工作也应该已经完成了，在内存中应该己经存在s a m p l e r 、 c a m e r a 、i n t e g r a t o r ( w h i n e d ，p a t h ，p h o t o m a p p i n g 等) 以及f i l m ( i m a g e ) 等对象。 然后系统运行到主绘制流程一这就是第二个阶段，该阶段由s c e n e ：r e n d e r 0 方法进入绘制主流程，计算每个象素的光照值，当所有的象素都被计算过，并且 将它们的值都写入f i l m 模块中后，该阶段结束。在图2 1 给出了整个系统的绘制 过程，并给出其中涉及到的插件详细说明。绘制流程主要由以下几步组成： 1 ) 由s a m p l e r 生成采样点，并将采样点信息送到c o r e 模块中； 2 ) c o t c 模块通过调用函数s e e n e ：r e n d e r o 将s a m p l e 值传给c a m e r a 模块； 3 ) c a m e r a 主要是负责根据采样点的位置和镜头位置的连线生成一条r a y ， 该光线与自然界的实际光线方向相反。然后c a m e r a 将r a y 返回给c o r e 。 4 ) 这时侯，系统已经拥有了r a y 。场景信息和光路积分器( i n t e g r a t o r ) 等对 象，后面的工作就是进行求交测试运算，光线采样和积分运算即光线跟 踪的过程。 5 ) 最后的工作是把已经计算好的象素的值写入到f i l m 的p i x e l 数组中。f i l m 存放我们已经计算好的图像。 图2 - 1p b r t 系统的绘制过程 最后一个阶段，当所有的像素值被计算出来之后，并且在系统将这副图像写 入到磁盘之前，系统还有一些后期处理工作，比如说，打印统计信息和系统资源 耗费情况等等。 第三章平衡图像质量和计算量的技术 第三章平衡图像质量和计算量的技术 从上一章的讨论我们可以知道，只要有足够多的采样量，我们总是能够得到 足够好的最终图像。然而在图像的不同区域，亮度的分布却并不均匀，有的地方 复杂，有的地方简单。在分布情况复杂的区域，需要更多的采样点才能得到令人 满意的效果：而在分布情况简单的区域，较少的采样点数量即能得到令人满意的 效果。将整个图像一视同仁的做法是不经济的。我们需要仔细平衡图像的质量和 计算量之间的关系。 3 1 自适应采样技术 一种经常用到的平衡图像的质量和计算量的技术是自适应采样技术。自适应 采样避免对每个像素采用同样的抽样量，而是有选择性的，也就是根据像素的光 照值的计算难度来决定像素的采样量。 3 1 1 自适应采样简介 自适应采样的思想非常简单。可以简单地描述为： 1 ) 在光线追踪中先对每个像素进行低密度采样，生成一幅初始图像。 2 ) 根据现在采样所得到的每个像素的亮度值的计算情况来决定是否追加采样。 3 ) 对那些需要进行再次采样的区域增加采样点。 4 ) 进行第二步的工作，若无需再增加采样点，则生成最终所需图像，否则继续。 第二步所做的工作就是判断一个区域图像的质量，是一个关键的步骤，也是 难点所在，是整个算法的核心。 3 1 2 自适应采样技术的发展 自适应采样的发展主要体现在对第二步的改善上。现在已经提出了各式各样 的评测一个图像区域的质量的方法，我们统称它们为质量评测函数。下一章我们 将用较多的篇幅来详细探讨。 第三章平衡幽像质量和计算量的技术 3 2p r o g r e s s i v er e n d e r i n g 技术 另一种需要仔细平衡图像的质量和计算量的技术是所谓的p r o g r e s s i v e r e n d e r i n g 技术。该算法旨在一开始就能以较少的计算量得出较多的图像信息。 下面我们介绍一种经典的p r o g r e s s i v er e n d e r i n g 技术。 3 2 1 算法简介 该p r o g r e s s i v e r e n d e r i n g 算法哇1 1 9 1 提出，建立在k a j i y a 【lo 】的b a s e l i n e 光线跟 踪算法上的。而在k a j i y a 1 0 】的b a s e l i n e 光线跟踪算法建立以前，c o o k 【1 1 】a n d w h i t t e d 【1 2 】已经为这种算法的建立提供了基础。所谓的b a s e l i n e 光线跟踪系统， 可以简单的理解为通过对图像成像平面的分辨率进行人为扩大再进行超采样、滤 波等反走样操作后形成最终结果的一项渲染技术。这项技术是建立在能对成像平 面上的单个像素光照值能进行准确估计的基础上的。通过改变这种算法的采样方 式即决定什么时候采什么位置的点，以及使用他自己提出的方法来合成近似 结果图像，可以得到符合要求的p r o g r e s s i v er e n d e r i n g 算法。 3 2 2 块的简单间断性 描叙边缘间断性的一个简单方法是为它建立一个数学模型。由于每个块都很 小，所以他们的边可以被看作直线。他们的性质可以通过定位他们的断点来加以 描述。这是事实上所采用的方法，当然，对于不同的图像，又根据其数据的性质 作相应调整。d c m 通过将图像块划分为更小的单位来描述图像块的间断性。该 单元应该最多只能被一条不连续的边通过，而且这条通过该单元的边的曲率不应 过大。本质上来说，这是一种分治策略。因为d c m 方法有效与否的关键在于它 在有简单间断性的图像块上的表现，所以我们期望通过较少的采样便能很好的抓 住图像边缘的间断性性质。传统上用来减少抓住图像边缘间断性而减少采样点数 目的技术是自适应采样( a d a p t i v es a m p l i n g ) 1 3 ，1 4 ，1 5 1 。自适应采样在平滑( 连续) 的情况下，能够显著的减少生成合格图像所需要的采样点数。然而，在这里却并 不适应。为了生成合格的图像，自适应采样技术会在不连续的地方密集采样。所 以，在最小差异方向( 1 e a s td i s c r e p a n c yd i r e c t i o n s ) 和带方向的有限单元( o r i e n t e d f i n i t ee l e m e n t s ) 概念基础上，引入了新的方法。 3 2 2 1 最小差异方向 某个k k 子块皿的最小差异方向是使对沿该方块边缘描叙差异的式子进行 线积分时，能取到最小值的单位向量。定义如下： 第三章平衡图像质量和计算量的技术 如) = ；i u ( 川( 咖) 一m ) ) 2 出 ( 3 1 ) 其中，c 为反的边界，s 是c 的长度( 事实上，只要一半即可) 。对于一个固 定的方向n 和c 上的一个定点，适当的选择t ( x ) 以使得参考线y ( f ) = x + t n 与边 缘c 相交于点x ，y = x + t ( x ) n 。只要沿着边缘的光照函数能在边缘估算的过程 中得到准确计算，那么在指定方向n 上的方向差异( d i r e c t i o n a ld i s c r e p a n c y ) d ( n ) 就能很方便的定义和计算。 图3 - 1 最小差异方向的图解 为了计算方便，剐 i l ：n = c o s o ，s i n 8 】并且将o 口 乃之间的角度离散化为 h 等分且只= f 州 ，i = o ：( 矗一1 ) 。那么，对于每一个单位方向向量_ = 【c o s 只，s i n s , 】 上的方向差异d ( 托) 可按下式计算： 口l 叫咖忐丢( m + f ( 朗h ( 肋2 ( 3 2 ) 其中，p 是边缘c 上所有点的集合，t ( p ) 是经过选择的参数，以使得 第三章平衡图像质量和计算量的技术 y ( t ) = p + t n ，与边缘c 交于点p 和p7 ；p + t ( p ) n l 。要注意的是，虽然p 是c 上的 一点，但p 7 可能不是，因此f ( p ) 有可能需要从两个相邻像素插值得到。从所得 到的序列 瓯d ，可以找到最小的一个t = 哦，以一。 ，将它作为最小差异方 向即州( b ) = 亿。图3 - 1 中描叙的就是最小差异方向。 3 2 2 2 带方向的有限单元 只要我们得到了最小差异方向，那么光照函数就能用沿着最小差异方向的有 限单元来模拟。我们认为在每个单元内部，光照函数是连续的，因而任何的一点 的光照值便可以简单的通过双线性插值来获得。即内部的任何位置的光照可由以 获得的边缘的光照值插值而得。 为了在捕捉到方块的特性同时又不至于过采样，对d c m 的求精之前需要对 方块的不连续程度进行计算。根据计算的结果，每个子块被分成三种：光滑的 ( s m o o t h ) ，简单边界( s i m p l ee d g e ) 和复杂边界( c o m p l e xe d g e ) 。我们认为光 滑的子块在内部都是连续的，因而只需要对该子块的四个角进行光照值超采样即 可，而方块内其他的像素点对应的光照值都由插值获得。而相反的，所有的边界 不连续的子块，包括简单边界和复杂边界的子块，简单的双线性插值是无法获得 做够好的结果的。对于这种性质的子块，需要对更多的像素点进行超采样才能得 到令人满意的结果。我们认为简单边界条件的子块内部存在两块光强差异明显的 区域，且两者的边界为一条直线。而复杂边界条件的子块内部存在两块以上光强 差异明显的区域，或者两者的边界不是简单的一条直线。对于简单边界条件的子 块，我们对处于四边上的所有像素点都进行超采样，而最小差异方向则沿用上层 方块的计算结果。而对于复杂边界条件的子块，不仅四边上的所有像素点都进行 超采样，而且最小差异方向也要重新计算。 a ，s m o o t l tb s i m p l ee d g ec jc o m p l e xe d 口e 图3 - 2 三种边界 3 2 3 算法流程 算法的绘制流程如图所示，主要由两个阶段组成。第一个阶段被称为规则划 分( r e g u l a rs u b d i v i s i o ns t a g e ) 。在这个阶段中用四分树的方法将成像平面划分成更 第三章平衡图像质量和计算量的技术 小的子块，或称基本块( e l e m e n t a r yb l o c k s ) 。算法从整个的图像平面开始，以成 像平面为根，递归的划分下去，直到子块成为基本块。在规则划分阶段，要估算 出每个块的四个角的光照值，然后，在任意时刻，如果需要得到近似图像，简单 的利用四个角的光照值来插值即可得到整个图像。 第二个阶段通过一个迭代的过程来建立d c m 并对其求精。在每一次迭代的 过程中，选取所有块中的一部分作为边缘块( e d g eb l o c k s ) 并分析他们边缘的间断 性：其他没有选中的块则继续进入下一步的规则划分。对于作边缘间断性分析的 边缘块来说，在该块的边界作密集的采样( 而不仅仅是在四个角上密集采样) 。这 些边界采样计算的结果以及物体空间的一些附加信息能够帮助我们得到该块的 边界间断性性质，最后，描写这一性质的数据被记入d c m 。通过d c m 中的信 息，可以为相应的图像块建立带方向的有限单元( o r i e n t e df i n i t ee l e m e n t ) ，该单元 将用来通过双线性插值获得到近似图像。当然，根据不同的要求，相应边缘块中 的像素能被继续采样并获得最终的结果。 在对d c m 进行求精之前，需要确定子块的性质。这需要通过一系列的测试 来确定。确定一个方块是否为一个边界不连续的块需要通过两个测试。第一个是 对比度测试，使用经典的对比度定义f m a x m i n ) ( m a x + m i n ) 来进行计算。如果 计算所得的对比度大于某一预先设定的闽值，则认为测试失败，方块为非光滑的。 第二个测试为所谓的可见线测试，即要求该方格内部不存在物体的几何边界。这 也就意味着该方格对应的图像内部只有一个几何物体所成的像。只有通过这两项 测试的方格才被认为具有边界光滑的性质。 所有不光滑的方格还需要继续通过一系列的测试来确定边界的复杂程度。通 过所有测试的方格被认为具有简单边界，任何一项失败的方格被认为具有复杂边 界。第一项测试( 作者称之为z e r oo r d e r t e s t ) 用来找出方格内光强差异明显的区 域的个数。所使用的方法是对轮廓线进行扫描，若发现的亮度突变的像素个数在 两个以内，那么可能两点的连线即为两个光强明显差异区域的边界，测试通过。 第二项测试( 作者称之为t h ef i r s to r d e rt e s t ) 试图找出两个不连续点的光强变化 梯度，如果二者致或相差不大，可认为两点的连线即为两个光强明显差异区域 的边界，测试通过。为了计算光强变化的梯度，需要对紧挨四边的像素进行超采 样以获得这些像素的具体光照值。图3 3 可以更好的说明这两个测试。第三项测 试则与光滑边界的测试类似，要求陔方块内只能有一个物体所成的像。 第三章平衡图像质量和计算鼍的技术 图3 - 3z e r oo r d e rt e s t 与f i r s to r d e rt e s t 3 2 4p r o g r e s s i v er e n d e r i n g 的发展与改进 【9 1 中的算法能够较好的满足p r o g r e s s i v er e n d e r i n g 的设计要求。f 1 6 】又对该算 法进行了完善，改进了它在处理小物体和纹理时的表现和效率。然而，该算法有 其天然的缺陷和局限性。在有大量噪点的情况下，算法的表现便难以令人满意， 同时过多的测试令得系统在渲染以外所作的工作太多从而浪费了资源。【1 7 】也提 出了自己的p r o g r e s s i v er e n d e r i n g 算法，相较【9 】的算法，该算法引入了人眼的感 觉为基础的同一性评测函数，计算和测试要少，但是对计算资源的浪费依然比较 严重。 第四章质量评溯函数 第四章质量评测函数 由p r o g r e s s i v er e n d e r i n g 和自适应采样的算法可以看出，度量图像平面上一 个区域的成像质量的指标是非常重要的，它决定着是否对图像继续求精。这一章 中，我们首先介绍几种被广泛使用的度量函数。然后我们试图改进其中的一种测 度函数。并把该函数用于我们自己的自适应采样算法中。 4 1 常用的度量函数 由于质量评测函数的重要性，现在已经提出了很多的质量评测函被。我们首 先回顾一些最广为使用，正确性基本得到验证的质量评测函数。在本文中，如无 特别声明，术语质量评测函数和术语度量函数没有区别。几种常用的度量函数有： 对比度，信息熵函数，直方图等。 4 1 1 对比度 c a e l l i 和t e 哪在【l8 】中提出了c o n t r a s t 的概念。这一概念在以后被广泛的应 用到图像处理、模式识别、计算机图形学以及人眼模型等诸多领域，被实验验证 为一简单、有效的质量评测函数，直到现在仍在被大量使用。c o n t r s t 的概念用 公式表示为： c ：笋争( 4 - d 。+ ，m m 式中1 一和o r o l l 分别为某一区域内各像素点亮度值的最大及最小值。m i t c h e l l 在 1 3 】中，将c o n t r a s t 引入到自适应采样技术中，提出了以后最广为应用的自适 应采样技术。只需将k 和。分别视为某一象素内各采样点亮度值的最大及最 小值，即可将其作为某个像素质量是否达标的测度。因为每个采样点包括r e d 、 g r e e n 、b l u e 三个分量值，m i t c h e l l 为每个分量计算对比值，如大于一设定的门限 值，将进行过取样，r e d 、g r e e n 、b l u e 门限值分别设为o 4 、o 3 、0 6 ，此值的设 定是根据视觉系统的相应敏感度经验。当最大值与最小值相同即采样点的颜色值 都相同，整个象素的质量最好，此时c = 0 ，当最大值与最小值相差很大时c 趋 向l ，此时象素的质量最差。 基于上述理论，许多人提出了更加复杂的综合判定式，如s i m m o n sm a r y a n n 第四章质量评测函数 【1 9 】就使用： - o 4 喜r - i r m i n + 惫老+ o 6k b = = - 吨b u 。b 。 ( 4 2 ) 作为最终的质量评测函数，式中m i n 、m a x 、a v g 值分别代表各颜色分量的 最小、最大、平均值。 4 1 2 直方图 直方图统计被广泛的用于图像增强处理领域。直方图是统计技术的一种。将 所收集的测定值或数据之全距分为几个相等的区间，对落在每个区间的样本数进 行统计，即可获得该样本的分布状况。而在图像处理领域，则需要对图像某一区 域内的光照值、亮度或者灰度等图像特征进项统计。当用于图像增强时还需要对 获得的数据再进行变换或更进一步的处理，【2 0 ，2 l 】中提出了将该技术用在图像增 强处理领域的算法。我所使用的算法也是建立在对图像区域的光照强度的直方图 统计上的，具体的算法将在后面详细介绍。 4 1 3 信息熵函数 在 2 2 ，2 3 伸有对信息熵理论的详细讨论。熵理论最早应用于热力学，由香农 引入用于描述信息理论，经过不断的发展成为一个重要的理论体系，并广泛应用 于科学试验、研究，已由实际应用证明了其有效性。 4 1 3 1 香农熵理论概述 “熵”的概念起源于热力学，是度量分子不规则热运动的单位。物理上的熵可 以说明热力学系统的演化方向、热平衡的达成与否或是代表系统上的混乱程度 等。而在信息理论里，信息熵则代表信息系统的可信度或者是忽略度。不管物理 或是信息上都可将熵视为以一个测量的工具。香农的伟大贡献在于，利用概率分 布的理论给出“熵”的严格定义。1 9 4 8 年6 月和l o 月，由贝尔实验室出版的贝 尔系统技术杂志连载了香农博士的文章通讯的数学原理，该文奠定了香农 信息基本理论的基础。他在文中用非常简洁的数学公式定义了信息时代的基本概 念熵。在此基础上，他又定义了信道容量的概念，指出了用降低传输速率来 换取高保真通讯的可能性。这些贡献对今天的通信工业具有革命性的影响，【2 4 卜 就是这一理论的具体应用。 熵在信息技术中的广泛应用还体现在：在熵的基础上定义的信道容量是通讯 中一个至关重要的概念。基于这个概念，可以推导出为达到无失真通讯的传输速 第四章质量评测函数 率的极限，现己称为香农极限。由于熵表达了事物所含的信息量，我们不可能用 少于熵的比特数来确切表达这一事物。所以这一概念己成为所有无损压缩的标准 和极限。同时，它也是导出无损压缩算法做达到或接近“熵”的编码的源泉。这些 技术现在得到了广泛的应用，像现在人们在p c 机上常用的w i n z i p ，因特网上传 递多媒体数据，除了b m p 文件以外的其他图像存储格式，当今广为人知的m p 3 音乐压缩格式，都用到了基于熵概念的无损压缩算法。所以不论在电讯业还 是计算机业中，只要涉及信息的压缩与传递，就要用到香农的理论。如上所述， 香农熵已经被用于科学研究及应用的很多领域，并已经表现出优良的性能。 4 1 3 2 香农熵理论介绍 香农熵反映了在一个随机试验( 或随机变量) 的不确定性。一个随机试验可 以表示为： r12 、 x = ij ( 4 - 3 ) 、p tp t p n i 其中1 , 2 ，n 为可能发生的结果，p i 为i 发生的概率。x 的不确定性大小取 决于n 的大小与p i 分布的均匀程度。这个不确定性是( p l ，p 2 ，, p n ) 的一个函数， 记为h ，它具有如下性质： ( 1 ) 对称连续性，即h ( p l ，p 2 ，p n ) 是( p l ，p 2 ，p n ) 的对称连续函数； ( 2 ) h ( 0 。1 ) = o ； ( 3 ) 如q = p n + p n + l 则 h ( p 1 , p 2 ，p n ，p n + 1 ) = h ( p l ，p 2 ，p n 一1 ，q ) + q h ( p n q ，p n + l q ) 。 通过数学的推导，得香农熵： 日( z ) = h ( p j ，p 2 ，以) = 一b l o g ：只 ( 4 - 4 ) j = i l o g 的底我们取2 ，h ( x ) 的单位是比特( b h t ) 。其中叫o g 只代表与各个结果 相关的信息。熵给了我们一组任意变量平均信息的概念。在我们应用中各个变量 为某一特定象素中各采样点的颜色值，p ，为某一分量在所有分量和中所占比率。 4 1 3 3 信息熵作为图像质量的测度 j a u m er i g a u ，m i q u e lf e i x a s ，和m a t e us b e g 在 2 5 1 中将信息熵作为一个像素 的质量评测函数用于自适应采样算法中。其总的思想是通过对象素内各个采样点 进行总的统计，用信息熵理论对其进行分析，得到对此象素的某些统计特征值， 从而可以得到象素质量的统计值，作为象素质量的判定标准。 第四章质量评测函数 首先，我们考虑待测图像面积内的每个采样点的光强占到总面积光强的百分 比的熵。在这里我们对每个像素进行考虑，因此每个像素内的信息熵为： 睇= 一l o g r ,( 4 5 ) 其中的n 为像素内采样点数，而则代表了i 个采样点的光强在整个像素中 所占的比例。这样得出的信息熵是某个颜色分量的信息熵，而且不在0 到1 之间， 而为了获褥0 到l 之间的一个评测指标，需要首先对其进行归一化： 研= 矗 其中以为待测像素中的采样点总数。最后将所有的颜色分量统计到一起， 可以得到最终的用于评测质量的指标： d 。：星盛 以 其中的n 为颜色分量的个数。 4 1 3 4 更多的信息熵评测函数 ( 4 7 ) 信息熵自提出以来，得到了不断的发展。传统的香农信息熵是基于 b o l t z m a n n - g i b b s - s h 黜o n ( b g s ) 统计力学，描述的系统是广度的( 可加的) ，而 实际的系统或多或少地具有时间和空间上的相关性( 象素内的各个采样点之间具 有相关性，即空间上的相关性) ，即非广度性。因此，我们引入香农熵的三种广 义化熵为r e n y i 熵和t s a l l i s - - h a v r d a - - c h a r v a t ( 称t s a l l i s ) 熵，以及标准化后的 t s a l l i s 熵。t s a l l i s 2 6 提出了非广度集内的非广度熵测度。而 2 7 ，2 8 伸有r e n y i 熵的定义和讨论。与传统的香农熵相比，广义化的r e n y i 熵和t s a l l i s 熵引入了对 系统内部相关性的体现，对数据变化的体现更加敏感，结果也更为精确，具有很 好的应用前景。而除了信息熵函数，模糊函数的理论也被引入到图像质量评测中 来。现在，质量评测函数所使用的手段和理论已经越来越多，也是各有优劣。下 面再介绍一种组合各种评测指标的评测函数，实验已证明其较好的效果，同时对 资源的消耗也较为理想。这一组合的思想也被用在我的实验和算法当中。 4 1 4 组合度量函数 【2 9 q h 提出了一种将多种度量组合在一起而得到一个新的度量函数的方法。 该方法用来衡量某一图像区域内的光照信息的同一性( h o m o g e n e i t y ) 。同一性描 述的是某一图像区域内光照值的分布状况，也即这些光照值分布的均匀状况。所 第四章质量评测函数 定义的同一性指标的取值范围是【o ，1 】，其数值大小反映了同一性的大小，数值越 大，则其同一性越大。 假设有一