贪心思想在视频码流截取中的应用

这篇文章属于《恰同学少年》系列，写于2012年。

贪心法（Greedy Approach）是一种通用的算法设计技术，在许多优化问题求解中得到了广泛应用。贪心并非一种特定的算法，而是一种算法设计思想。本文通过我们在视频码流截取研究中的实例说明贪心思想的运用。

一、关于贪心思想

贪心思想指的是：在问题求解时，总是做出在当前看来最好的选择，即不从整体上加以考虑，只求得到局部最优解。之所以如此，是因为考虑全体时复杂性太高，而对一些问题来说，采用每一步都求局部最优的贪心算法最终也能得到全局最优解。当然，不是所有的问题都可以得到真正的最优解。贪心算法能够得到最优解是需要证明的，一般可通过归纳法（对算法步数的归纳、对问题规模的归纳），或交换论证的方法证明。

二、实际问题描述

码流截取是可伸缩视频编码研究领域中的一个重要问题。可伸缩视频编码简单来说就是编码后的码流是分层的，可以从中去掉部分数据得到一个低码率的仍然可解码的码流，以此来适应不同的带宽和终端。实际应用中，当需要截掉特定大小的数据时，我们希望余下的码流解码得到的视频质量尽可能好，即截取数据带来的失真（用峰值信噪比PSNR的降低来表示）能达到最小。这是一个组合优化问题（若暂不考虑下文提到的每个数据包对应失真的变化），可以进一步描述如下：

假设原码流中有N个可丢弃的数据包，其中数据包i的大小为\( {\mathrm{\Delta R}}_i \)（此记法表示丢弃它带来的码率变化），丢弃它带来的失真为\( {\mathrm{\Delta PSNR}}_i \)。现在需要丢掉总大小为R的数据，那么应该丢弃哪些数据包从而使截取带来的总失真最小。

需要说明的是，实际中很难准确得到每个数据包的\( {\mathrm{\Delta PSNR}}_i \)，而且同一数据包在不同阶段丢弃所带来的失真也是不相同的，甚至一个截取方案引入的总失真也不严格等于所丢弃的每个数据包带来的失真的简单相加。这都是由编解码的复杂性（各个数据包紧密联系，并非独立）导致的，但原则上并不影响对贪心思想的使用。

三、求解算法

我们进行研究的创新之处主要在于对丢弃每个数据包后带来的失真的动态估计，在此不再详述；而得到每个数据包对应的失真（\( {\mathrm{\Delta PSNR}}_i \)）之后确定丢包顺序则主要依据贪心思想。算法具体过程如下：

• 将余下的可丢弃的数据包按照\( \phi_i=\frac{\Delta {PSNR}_i}{\Delta R_i} \)从小到大排序；

• 选择\( \phi_i \)最小的丢弃（丢弃之后会重新计算余下各数据包对应的失真，即更新\( {\mathrm{\Delta PSNR}}_i \)值，因为每进行一次丢弃后余下数据包再解码时对应的失真会变化）；

• 重复以上过程直到达到要丢的数据量要求。

算法中的“贪心”主要是“选择\( \phi_i \)最小的丢弃”这一步。这里的\( \phi_i \)代表着一个数据包的“率失真影响”，\( \phi_i \)较小意味着该数据包单位数据量对视频质量的影响小。每次丢弃当前\( \phi_i \)最小的数据包，不一定使得这个截取方案带来的总失真最小，即该算法得到的结果是否是最优的并不确定。考虑到数据包间的互相影响和对失真估计的不准确性，无法严格证明贪心算法在这里能得到最优解。但由于“选择\( \phi_i \)最小”这一贪心策略在直观上是“合理的”，因此仍能采用，并得到很好的解。

实际结果也说明该算法是有效的。事实上，对码流截取问题若要得到严格的最优解，只能是枚举所有可能的丢包方案，进行解码并计算带来的实际失真，然后选择失真最小的方案——这样做的复杂性是无法接受的。上述基于贪心思想的算法时间复杂度很低（当可丢弃数据包数目为N时，不超过\( N\ast N\log{N} \)，即N次排序的复杂度；算法中更新\( {\mathrm{\Delta PSNR}}_i \)并没有带来更高的复杂度），而且实验中得到的截取方案也是相当好的。

四、总结和讨论

以上结合对可伸缩视频编码领域中码流截取问题的研究展示了贪心思想的应用。采用贪心策略的截取算法得到的不一定是最优方案（没有进行证明），但其足够低的复杂性和足够好的结果使其不失为有效的算法。

一般来说，贪心算法具有复杂度低、设计简单的优势，但往往需要正确性证明。对于某些优化问题，可能贪心法仅对部分实例能得到最优解；此时为了利用贪心法的高效率，可以对输入进行分析，判断在哪些条件下是正确的，只要判定这些条件的时间复杂度也不太高即可。另外一些情况下，虽然无法证明贪心算法能得到最优解，但如果其得到的解是近似最优的（或足够好的），而能得到最优解的算法复杂度又太高，仍可以选择贪心算法。本文介绍的码流截取问题就是这样一个例子。

总之，贪心思想虽然不一定总能得到最优解，但非常简单高效，在实际算法设计中可权衡选择采用。

注：本篇博客使用了MathJax渲染数学公式需要一定时间。如果公式显示不正常，可尝试刷新页面。