3D 图形中的小波

# 3D 图形中的小波 来源: https://comonad.com/reader/1995/wavelets-in-3d-graphics/ 小波已经成为数学领域和计算机图形学领域的一个热门话题。它是对数据集进行多分辨率分析和数据压缩的有用工具。有多种流行的小波基和尺度函数。本文将重点讨论 Haar 小波基，以及它在我正在开发的一个 3D 多边形游戏引擎中用于低对比度纹理压缩的应用。在这一应用中，我同时利用了 Haar 基的这两个特性。 ## 术语 就本文而言，一个纹理由一张 32 位图像组成，宽为 2^n texels，高为 2^n texels。texel 是行业术语，指纹理在投影到屏幕之前的像素。每张图像还存储有 mipmaps。每个 mipmap 比前一个小一个二的幂，并由前一张图像经过抗锯齿生成。因此，一个 128x128 纹理的 mipmap 集合为 64x64、32x32、16x16、8x8、4x4、2x2 和 1x1。通常，最低的 3 到 4 个 mipmap 层级维护起来得不偿失，因此经常被省略——因为对于游戏来说，可以通过限制场景来避免多边形离相机那么远。而且即使它们可见，你大概更需要担心的是需要投影和显示的大量小多边形的问题，而不是远处的一点锯齿问题。存储 mipmaps 会使纹理存储需求增加三分之一。 ## 问题所在 典型的纹理尺寸是 256x256。每个 texel 占 4 字节，单张图像每张纹理就要消耗 256Kb 内存。一个实际的场景中大约同时可见十来张纹理，还有多达一百张分布在地图上不可见的位置。要让所有纹理随时保持加载，仅纹理和 mipmap 数据就需要大约 200Mb 内存，这还不包括任何游戏逻辑、光照贴图或几何体。不用说，在当时期望一个典型终端用户的电脑有这么多内存是不现实的。 ## 可能的解决方案 一种方案是将图像降级为 8 位调色板表示。这会将内存需求降至约 50Mb，如果能利用纹理在地图上分布的空间连贯性，就可以合理地与磁盘进行交换。然而，如果你无法利用任何空间连贯性或缓存，就会因为突然需要去查找纹理以继续渲染而出现卡顿。这种卡顿有非常消极的心理影响——作为玩家，你会突然意识到自己在玩游戏，沉浸感荡然无存。帧率的稳定性总体上比最佳情况下的性能更重要，因此需要一种性能均衡因子。卡顿的问题还被一个事实所加剧：为了交换纹理，引擎必须去磁盘查找，这比直接从内存访问纹理慢几个数量级。此外，调色板表示的纹理要求你使用更小的色空间子集来存储图像，转换时往往会丢失大量质量，而且即使重建，如果你使用的是六位色分量的标准调色板，重建后的 texel 最好也只有 18 位。当你想在调色板表示中存储 alpha（半透明）通道时，还会出现其他复杂问题。 另一种选择是在内存中存储纹理的压缩表示，并从中导出 mipmaps。这种方法的问题在于，即使你只需要一张 256x256 纹理的 32x32 mipmap，你也必须解压整张纹理并提取所有 mipmap 层级。通常，对于一张给定的纹理，你会先需要较低的 mipmap 再需要较大的 mipmap。这很直观，因为当你在场景中移动时，表面会先在远处出现，然后逐渐靠近。随着它们靠近，它们会逐渐需要更多的细节（更高的 mipmap 层级）。用这种方法你必须一次性承受全部开销，这会引入卡顿。JPEG 风格的压缩可以取得不错的效果，通常可以获得比我下面所采用方法更高的压缩率。不幸的是，它这种全有或全无的特性使它不适合我的需求。此外，更好的压缩是以对图像每个 8x8 块执行逆 DCT 为代价的。使用 Feig 的方法（目前在 Intel 处理器上已发表的最高效方法），这个过程每个通道需要 54 次乘法、462 次加法和 6 次移位。相比之下，使用 Haar 解压同样的 8x8 块，每个通道只需 256 次加法。 ## Haar 基概述 本节旨在提供对 Haar 基工作原理的直观理解。以下内容并非严格的数学证明或该主题的严谨考察。 `` 给定 2^n 个样本，例如： { 11, 1, 1, 7 } 将样本两两配对并求平均得到： { (11+1)/2, (1+7)/2 } = { 6, 4 } 重复直到只剩 1 个值： { (6+4)/2 } = { 5 } `` 样本 11、1、1、7 两两平均得到 6 和 4，然后得到尺度值 5。 图 1\. 两两平均值与尺度值\. 该树顶端的这个值（图 1）就是你的尺度值。 然后，你沿你配对的层级向下递归。在每一级，用当前节点的值减去其右子节点的值。不要递归到树的叶节点。 图 2\. 按层级排列的小波系数\. 层级 0 处有 1 个系数，层级 1 处有 5 和 -3。某一给定层级中有 2n 个值。这些值就是你的小波系数。有了这些值，你就可以重建原始样本集，因为这个操作是可逆的。 在层级 m 处有 2m 个系数。将尺度值加入这个集合后，就提供了与原始数据集相同数量的样本值，然而当转换为 Haar 形式后，这些数字现在指示的是相对于较小层级的变化。 重建很简单。从尺度值和层级 0 的系数开始。将系数加到尺度值上生成左子节点，从尺度值中减去系数生成右子节点。取这些节点，然后沿树向下重复： 图 3\. 重建：左侧相加，右侧相减\. 一个以 5 为起点的表达式树，先是 5 加 1 和 5 减 1，然后是 6 加 5、6 减 5、4 加 -3、4 减 -3。 求值后的树：先是 5，然后是 6 和 4，最后是恢复的样本 11、1、1、7。 接下来，你按系数在树中的层级对系数进行加权。这是为了归一化系数。有几种流行的加权机制，每一种都适用于不同的用途。我更喜欢按 1/sqrt(2^j) 乘以每个值来进行归一化，其中 j 是系数在树中的层级。 你的数据现在变成： `` 尺度值 { 6 } 小波系数 { 1, 5, -3} 加权后的小波系数 { 1, 5/sqrt(2), -3/sqrt(2) } ``` 到目前为止，这个过程还没有产生任何压缩。整个变换只是将四个值转换成了另外四个值，以及从它们派生出来的一些加权值。 ## 应用 Haar 下一步是弄清楚如何将其应用于图像压缩。图像是二维的样本网格，而不是上面提到的一维集合。 有两种常见方法： 标准分解方式会对图像的每一行执行 Haar 变换，然后逐列进行变换。不幸的是，这对于重建 mipmaps 并不太有用，因为要提取一个 2x2 mipmap，我需要重建整张图像，然后再通过抗锯齿逐步降采样到 2x2。如果我这样做，重建较低 mipmap 就没有任何优势了。 非标准分解方式对每一行向下变换一级，然后对每一列向下变换一级，重复直到只剩下尺度函数。因此直观上，你可以从 1x1 mipmap（即你的尺度系数）和层级 0 的系数集（一个行系数和两个列系数）中提取 2x2 mipmap，然后从 2x2 中利用该 mipmap 和层级 1 的系数（2 个行系数、4 个列系数）提取 4x4 mipmap，以此类推。这使你能够在游戏中逐渐接近表面时增量地重建图像。由于你避免了对大量数据的突然需求，就可以避免卡顿。如果在某一帧动画中你因为没有足够的处理时间来解压而不得不等待一个更高的 mipmap，你可以先使用较低的 mipmap 层级作为替代品，直到解压完成。在我的实践中，我发现与其因为纹理没准备好而偶尔掉到 5 fps，不如保持恒定的 25 帧每秒的刷新率效果更好。 我选择了对纹理使用非标准分解。这虽然很好，但同样，到目前为止我们所做的只是用一组数字换成了另一组数字。除了我们不必为 mipmap 层级存储额外内存这一点（因为它们可以在重建图像时从系数集导出）之外，并没有发生真正的压缩。 下一步是压缩系数集。小波的一个优势是，系数集的微小变化只会在恢复的样本集中产生类似的微小变化，并且这种误差会被很好地分散到图像周围，从而避免因此产生可见的不连续性。 一旦你根据系数在树中的层级正确地对它们加权，你就可以通过反复丢弃最小的加权系数（将其替换为 0）来消除对整体图像贡献不大的项，直到达到你设定的要移除的系数数量或最大权重。（这种启发式方法过去被证明非常有用，因为有些图像天生对压缩的宽容度更高。这迫使我不得不将压缩阶段变为一个交互式过程，但随之而来的是它也提供了更大的艺术控制权。 将系数替换为 0 提供了一种很好的系统化方式来保证有界的最大误差。不幸的是，结果证明它并没有提供一个非常可压缩的数据集。对剩余系数进行量化是必要的。在 0 替换步骤之后，我将系数集输入一个神经网络，该网络使用系数的加权形式对剩余系数执行量化。注意，我并不是对每个系数一视同仁，而是根据小波系数的权重来进行加权选择。然而，在存储到磁盘时，我使用的是未加权的形式。在我的实践中，我发现值的冗余比精确的权重更重要，在我的案例中，存储未加权的量化值提供了更好的压缩率。通过神经网络将量化为系数的"调色板"可能看起来有些小题大做，但我已经编写好了将 32 位原始表示转换为调色板纹理的例程。然后，我将较小的量化系数集和出现计数器输入一个 Huffman 树生成器，再将数据通过 Huffman 压缩器。由于所有这些都是预处理，处理时间或多或少无关紧要，只是它使修改游戏引擎变得更加繁琐和不够流畅。跳过量化阶段并将系数直接送入 QM 算术编码器，我能够获得稍好的压缩率，但解压速度大幅下降，在我看来，为了 3% 的压缩率提升而花 6 倍的时间解压并还要应付 IBM 持有的专利，是不值得的。 不利的一面是，压缩后的纹理大幅增加了我的表面缓存算法的复杂性，这使得对游戏引擎本身的广泛修改明显更加困难。我在压缩管道上花的时间也远超我所愿意的。回想起来，我可能应该在最终压缩阶段使用 zlib 或其他经过广泛测试且具有友好用户界面的库。 唯一真正的问题出现在高对比度的纹理中。幸运的是，在多边形引擎中通常都会刻意避免使用这类纹理，因为与小波类似的压缩伪影在对纹理进行 mipmap 处理时同样可见。这些伪影可以通过各向异性纹理采样等技术来避免，但在撰写本文时，这些技术还不足以胜任实时图形，因此实际上并不相关。压缩还会导致纹理的块状感明显增加，其程度与你设定的误差阈值成正比。可以通过添加双线性滤波步骤来缓解这种块状感，但这会加剧高对比度纹理的问题。当纹理传给高端 3D 加速卡时，该卡可以自动执行双线性滤波，此时双线性滤波也并非真正必要。经验法则是，纹理在压缩比达到 8:1 之前不会出现伪影，当接近 35:1 的压缩比时开始变得不可用。介于两者之间的层级的可用性在很大程度上取决于纹理大部分区域的对比度水平。压缩器能很好地处理混合了高对比度和低对比度区域的纹理。高对比度区域保留了足够的清晰度，因为剧烈的颜色变化被赋予了相对较高的权重，而低对比度区域则只是进一步被柔化了。这种效果使墙上的标志、技术设备等在变化频率较低的背景上更加突出。 小波领域的研究正在进行中。Haar 基实际上并不是一个非常好的小波基。它因为实际上是一系列脉冲的层次结构而不连续，因此比较粗糙，它的主要优势是从图像中提取速度快、从系数中恢复图像速度快，而且它相当直观，不像许多更高级的小波那样难以理解。 在我开发游戏引擎的过程中，我还探索了其他几种让小波发挥作用的方法。存在多种用于压缩极高多边形数量表面的基函数。不幸的是，在实践中，遍历层次结构并管理合理水平的表面数据缓存所需的时间，超过了仅仅为给定距离预计算最佳细分并将其应用于我所遇到的情况的存储需求。最终某种类似的东西是必需的，但目前内存比处理能力更充裕。在这个方面，小波最终还是有点令人失望。 ## 参考文献 E. Stollnitz, T. Derose, D. Salesin. "Wavelets for Computer Graphics", ISBN 1-55860-375-1 Morgan Kaufmann Publishers Inc. San Francisco, CA 1996 W. Pennebaker, J. Mitchell. "JPEG: Still Image Data Compression Standard", ISBN 0-442-01272-1 Van Nostrand Reinhold Inc. New York, NY 1993 D. Morgan. "Numerical Methods for DSP in C", ISBN 0-471-12232-2 Jon Wiley & Sons Inc. Canada 1997 B. Hubbard. "The World According to Wavelets", ISBN 1-56881-047-4 AK Peters Ltd. Welleskey, MA 1996 Foley, van Dam, Feiner, Hughes, "Computer Graphics: Principles and Practice, 2nd Ed. in C" ISBN 0-201-84840-6 Addison-Wesley Publishing Co. Reading, MA