英语原文共 12 页
具有完全基线JPEG解码器兼容性的行程编码，霍夫曼编码和量化表的联合优化
摘要—为了在保持JPEG语法正确性的同时最大限度地提高率失真性能，我们研究了霍夫曼表的联合优化、量化步长和DCT索引的联合优化。在给定霍夫曼表和量化步长的情况下，首先提出了一种基于图的DCT量化系数算法。在此基础上，提出了一种迭代算法，对游程编码、霍夫曼编码和量化表选择进行联合优化。所提出的迭代算法不仅使压缩比特流与现有的JPEG和MPEG译码器完全兼容，而且计算效率高。此外，在对标准测试图像进行测试时，它获得了最佳的JPEG压缩结果，在某种程度上，它自己的JPEG压缩性能甚至超过了一些最先进的基于小波的图像编码器（如夏皮罗的嵌入式零树小波算法）在比较的公共比特率下的PSNR结果。基于图片的算法和迭代算法都可以应用于网络图像加速、数码相机图像压缩、MPEG帧优化、转码等应用领域。
索引—动态规划、迭代方法、联合优化、速率失真理论、源代码。
引言
JPEG是一种流行的基于离散余弦变换（DCT）的静止图像压缩标准。它促进了JPEG格式的广泛应用，如在万维网和数码相机中。JPEG编码系统的普及推动了对JPEG优化方案的研究，这些方案仍然忠实于JPEG语法。由于这种方案在不改变标准的JPEG解码器的情况下只对JPEG编码器进行优化，因此不仅可以进一步减小JPEG压缩图像的大小，而且具有易于部署的优点。这一独特的功能使它们在接收终端简易支持新解码器的应用中具有吸引力，例如在无线通信中。
JPEG编码器由三个基本步骤组成，编码器首先将输入图像分割为8 X 8个块，然后按光栅扫描顺序（基线JPEG）逐个处理这8 X 8个图像块。每个块首先由8 X 8 DCT从像素域转换为DCT域。然后使用一个8 X 8量化表对得到的DCT系数进行均匀量化，该表的条目是每个频点的量化步长。然后用游程编码和霍夫曼编码对量化后的DCT指数进行熵编码。JPEG语法将量化步长和霍夫曼码字的选择留给编码器，前提是必须用步长来量化图像的所有块。该框架提供了在编码器上应用速率失真（R-D）优化的重要机会，其中量化表和哈夫曼表是编码器可以优化的两个自由参数。
编码器可以优化的第三个但不太明显的自由参数是图像数据本身。根据图像数据在整个JPEG编码过程中所处的阶段，图像数据采用不同的形式。在硬判决量化之前，采用DCT系数的形式；在硬判决量化之后，采用DCT指数的形式，即量化步长归一化的量化DCT系数；在曲折排序和游程编码之后，采用游程尺寸对，然后采用非零振幅的形式。由于默认量化表是独立于图像的，并且缩放也不是图像自适应的，因此默认量化表的缩放是次优的。即使使用图像自适应量化表，JPEG标准也要求将同一个表应用于图像组件的每个图像块，这表明优化DCT索引仍有潜在的增益。注意，硬决策量化加上DCT索引优化等于软决策量化。由于DCT索引可以等效地表示为运行大小对，然后通过运行长度编码表示振幅，因此我们将DCT索引优化简单地称为运行长度编码优化，与步长和霍夫曼编码优化并行。本文不仅提出了一种非常简洁的基于图的游程码优化算法，而且提出了一种迭代优化算法，该算法可以联合优化游程码、霍夫曼编码和量化步长。
本文的其余部分组织如下。第二节回顾了以往文献中的jpeg优化工作。在第三节中提出了联合优化问题，并在第四节中给出了我们的解决方案。第五节中给出了详细的实验结果和复杂性分析。最后，在第六节中得出了结论。
前期工作
如第一节所述，量化表、哈夫曼表和DCT索引是JPEG编码器优化器可以处理的三个自由参数。除了根据更新的运行大小对统计数据设计定制的哈夫曼表之外，没有空间进一步优化哈夫曼表。因此，我们将在下面分别回顾量化表优化、DCT指标优化和部分联合优化的相关研究工作。
量化表优化
jpeg的量化步长在很大程度上决定了jpeg压缩图像的失真率。如第一节所述，使用默认量化表是次优的，因为它们与图像无关。因此，任何量化表优化方案的目的都是为每个图像分量获得一个高效的图像自适应量化表。量化表优化问题可以很容易地表述如下（在不失去一般性的情况下，我们在下面的讨论中只考虑一个图像分量）。给定一个目标比特率的输入图像，我们希望找到一组量化步长，以最小化整体失真。
受比特率限制
由于jpeg使用零运行长度编码，将来自不同频率段的零DCT索引组合成一个符号，因此比特率不仅仅是对每个DCT索引进行编码所贡献的比特总数。因此，用经典的位分配技术很难得到（1）和（2）的最优解。[3]在假设DCT系数的概率分布为拉普拉斯分布的基础上，提出了一种梯度下降法求解量化表设计问题的局部最优解。随后提出了一种贪婪的最速下降优化方案，该方案不假设DCT系数的概率分布[4]。从对应于低比特率和高失真的大步长初始量化表开始，[4]中的算法一次在量化表的一个条目中减小步长，直到达到目标比特率。在每次迭代中，他们的算法更新量化表，以在量化表的每个条目的所有可能减小的步长上最大化失真减少与比特率增加的比率。在数学上，他们的算法寻求并解决以下最大化问题：
上述算法计算量很大。[6]提出了一种比较有效的算法，在不重复整个压缩解压循环的情况下，基于DCT系数分布统计数据构造量化表。他们采用动态规划方法，在速率和畸变的范围内优化量化表，并获得与[4]中报告的性能相似的性能。
最佳阈值
即使使用图像自适应量化表，jpeg也必须对每个图像块应用相同的表。因此，jpeg量化缺乏局部自适应性，这表明利用特定块的特征与平均块统计数据之间的差异仍可能获得潜在的增益。此增益是[7]的速率失真最佳快速阈值算法的动因，该算法降低了R-D意义上不太重要的DCT指数。在数学上，对于固定的量化器，快速阈值算法使原始图像和阈值图像之间的失真最小化，给定量化图像受位预算约束，即：
一个等价的无约束问题是
联合阈值和量化器选择
由于自适应量化器选择方案利用全图像统计，而阈值算法利用块级统计，这两个操作几乎是“正交的”。这表明将它们与Huffman表（留给jpeg编码器的另一个自由参数）绑定在一起是有益的。为此，Crouse和Ramchandran[8]，[9]提出了三个参数的联合优化方案，即：
其中Q是量化表，H是合并的哈夫曼表，是一组二进制阈值标记，用于指示是否阈值DCT索引。用拉格朗日乘子将（8）的约束极小化问题转化为一个无约束问题。
然后，在其他参数不变的情况下，提出了一种迭代选择Q、T、H的算法，使（9）最小化。
问题形成
现在提出全关节优化问题，其中最小化是在基线jpeg中的所有三个自由参数上进行的。本文只考虑交流系数的最佳量化和编码。利用格架结构可以实现直流系数的最佳量化和编码。
在jpeg编码中，给定一个输入图像I0和一个初始量化表Q，我们的问题被认为是对所有可能的运行大小对（R，S）序列的约束优化，然后是非零振幅，所有可能的哈夫曼表H和所有可能的量化表Q。
或等价地
我们可以把速率约束问题或畸变约束问题转化为下面的无约束问题
将我们的联合优化问题与[8]和[9]中的联合阈值和量化器选择问题进行比较，具有一定的参考价值。一方面，二者共同优化这三个参数。另一方面，我们的联合优化在两个不同的方面与[8]和[9]中考虑的有所不同。首先，我们考虑DCT指数的完全优化，而不是部分优化，即只删除[8]和[9]中考虑的无关紧要的DCT指数。正如我们将在下一节中看到的，结果是，完全优化有一个非常整洁、计算有效的解决方案。
这与[7]–[9]中提出的部分优化相对耗时的解决方案形成对比。第二，在我们将在下一节中描述的迭代求解算法（12）中，我们不应用任何耗时的量化器选择方案来搜索每次迭代中的R-D最佳步长。相反，我们从任何初始量化表开始，它可以是默认量化表，也可以是由任何其他方法（如[5]中所示的方法）生成的量化表，我们使用派生的闭环公式在每次迭代中有效地更新步骤大小，以局部优化步骤大小。这是可能的，因为(R,S,A)现在完全脱离了硬决策量化过程，实际上是一个需要优化的自由参数。
设计算法
速率失真优化问题（12）是失真、速率、哈夫曼表、量化表和序列（R、S、A）的联合优化。为了使优化问题易于处理，我们提出了一种迭代算法，在其他两个参数不变的情况下，迭代地选择序列（R，S，A）、哈夫曼表和量化表，使（12）的拉格朗日代价最小化。由于运行规模概率分布P完全决定了一个哈夫曼表，所以在优化过程中我们用P来代替哈夫曼表H。针对优化问题（12）提出的迭代算法总结如下。
由于拉格朗日代价函数在每一步上都是不递增的，因此保证了收敛性,即找到使给定的拉格朗日代价最小的序列，并用图像的新DCT指数更新量化步长。
- 基于图的游程编码优化
如第二节所述，即使有图像自适应量化表，jpeg量化也缺乏loca自适应性，这表明潜在的增益仍然来自于DCT索引的优化。此增益在步骤2中被利用）。[7]中的最优阈值仅考虑DCT指数的部分优化，即在R-D意义上降低不太重要的系数。在本小节中，我们提出了一种有效的基于图的最优路径搜索算法，以（r，s，a）序列的形式对DCT索引进行完全优化。它不仅可以降低不太重要的DCT指标，而且可以将它们从一个大小组改变为另一个（即使在R- D感测中需要改变零DCT索引到非零值也是可能的）。也就是说，我们基于图的最优路径搜索算法在所有可能的（R，S，A）序列中找到最优（R，S，A）序列，以最小化拉格朗日代价。在给定q和p的情况下，拉格朗日代价j是逐块加和的，步骤2）中的最小化可以逐块求解。也就是说，最佳序列（R，S，A）可以独立地确定每8 X 8个图像块。因此，在下面的内容中，我们将讨论限制为仅一个8 X 8图像块。
让我们定义一个有65个节点（或状态）的有向图。如图所示，编号为i＝0，1hellip;63的前64个状态对应于8times;8图像块的64个DCT指数。最后一个状态是一个称为结束状态的特殊状态，将用于处理EOB（块的结束）。每个状态i（ilt;=63）可能有来自前16个状态j（jlt;i）的传入连接，这些状态j（jlt;i）对应于一对（r，s）中的run，r（jpeg语法中，值为0到15）。最终状态可能有来自所有其他状态的传入连接，每个来自状态i (ilt;=62)的连接表示EOB代码，即，系数后面的代码(0,0)。状态63到状态结束时没有EOB代码。对于给定的状态i (ilt;=63)及其前身i-r-1(0lt;=rlt;=15)，它们之间有10个并行转换，它们对应于成对的size组,S,(R,S)。为简便起见，我们只在所示的图中绘制一个过渡;整个图需要展开。对于其中的每个状态，都有一个从状态到对应于对(15,0)的状态的过渡，即， ZRL(零运行长度)代码。我们为从一个状态到另一个状态的每个过渡分配一个代价，这个代价定义为从一个状态到另一个状态的拉格朗日增量代价当DCT系数被软量化时按人数分组(即，对应的DCT指数需要位元来表示其幅值)，在DCT系数之前出现的所有DCT系数都软量化为零。
图1
不难看出，通过上述定义，8 X 8块的每个运行大小对的序列对应于从状态0到具有拉格朗日代价的结束状态的路径。例如，块的运行大小对（0,5），（4,3），（15,0），（9,1），（0,0）的序列对应于图中所示的路径。另一方面，并非有向图中从状态0到结束状态的所有路径都表示8 X 8块的运行大小对的合法序列。我们将这些路径称为非法路径。例如，路径包括从状态0到状态1的转换（0,5），接着是从状态1到状态17的转换（15,0）以及从状态17到结束状态的转换（0,0）是一个非法路径，并不代表8 X 8块的运行大小对的合法序列。然而，不难看出，对于任何非法路径，总有一条合法的路径，其拉格朗日成本严格低于非法路径。因此，在包括合法路径和非法路径的所有可能路径中，从状态0到结束状态的最佳总路径拉格朗日成本的最佳路径始终是合法路径。因此，我们可以对整个有向图应用快速动态规划算法来找到给定的8 X 8块的最优序列(R,S,A)。
下面是对算法的更详细的逐步描述。作为初始化，算法预先计算对于每个运行大小的对(r，s)，基于给定运行大小分布P。对于每个状态i，它还递归地预先计算了由于在状态i之前删除前1到15个系数而导致的失真和状态i的EOB成本。状态0的最小代价(直流系数)初始化为0，因为它不影响运行长度编码优化。算法从状态1(第一个AC系数)开始。状态1有10条路径都是从状态0开始的。这10条路径对应第一个AC索引可能包含的10个大小组。与每条路径相关的成本使用(13)计算，其中(13)中的第一项预先计算，并确定如下。为了简单起见，这里我们只考虑正指数;负指数的处理方法与对称相似。如果,Ai为尺寸组s中最小的振幅。计算出10个增量成本后，通过将状态0到状态1的最小增量成本与状态0的最小增量成本相加，得到状态1到状态0的最小增量成本。记录这个最小成本，以及运行大小对（r，s）和Ai，这将导致状态1的最小成本。算法进入状态2。由于状态0和状态1的最小代价是已知的，所以找到状态2的最小代价的任务简化为找到从状态0到状态2和从状态1到状态2的最小增量代价。将这两个最小增量成本分别加到状态0和状态1的最小成本上;两个和中较小的那个是状态2的最小代价。记录这个最小成本（r，s）以及运行大小对Ai，这将导致状态2的最小成本。注意，如果到状态2的最优路径是直接从状态0到状态2，则存储的运行大小对（r，s）中状态2的值为1，这意味着第一个AC被量化或强制为零。如果状态2的最优路径是从状态1到状态2，那么存储的是0，这意味着第一个AC索引是非0的。这个过程继续到第三个系数，以此类推，直到最后一个系数在状态63时的最小代价
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
