影像与视频压缩

1影像与视频压缩211.1前言11.2消息理论11.3不失真压缩11.4矢量量化法11.5静态影像压缩11.6动态影像压缩11.3.1霍夫曼编码11.3.2算术码内容311.2消息理论定理11.2.1给任意n个事件，其熵。证明：n个事件且机率分别为、、…和。

4图11.2.1

的示意图5Kraft不等式。长度为，假设完成了后，为避免发生为的前置码(PrefixCode)，则必须满足条件，这里为不合法的码数。同理，考虑时，则需满足。不等式两边同除以，可得。依此类推，可得下列Kraft不等式Kraft不等式将帮助证明熵可视为平均码长的下限。编码:

6定理11.2.2

令且已被编成长度为的码， 则熵，这里L代表平均码长。

已知证明：

又

7巨集符号(MacroSymbol)集的平均码长

n个符号形成一个巨集符号(MacroSymbol)。字母集

假设两两符号为彼此独立表一个巨集符号所需的位元长度。推得若n趋近于无穷大，则。

811.3不失真压缩

11.3.1霍夫曼编码霍夫曼树

符号集对应频率Key:将频率最小的二个符号编码，可建构出图11.3.1.1的霍夫曼树。码可编成

=码长度为图11.3.1.1霍夫曼树9范例1:给一4×4灰阶影像，请建出霍夫曼树并写出灰阶值50的霍夫曼码长。60102809595401556010215510215550801559510解答:S=<40,50,60,80,95,102,155>，而W=<1,1,2,2,3,3,4>，霍夫曼树如下:灰阶值50的霍夫曼码长为4解答完毕11图11.3.1.2

单边成长霍夫曼树单边成长(Single-sideGrowing)霍夫曼树首先令且。。单边成长霍夫曼树往左成长，所以。可建出图11.3.1.2的单边成长霍夫曼树且

令代表第i层的叶子树。令代表第i层的内部节点数。给

，，需跳过中的两个树叶，译码只需的时间，d指的是单边成长霍夫曼树的深度。12速度最快的霍夫曼译码器

图11.3.1.3霍夫曼树在霍夫曼树上进行广先搜寻，在内部节点旁存上的值，r代表位于同一层但在该内部节点左边的内部节点数；l代表在同一层上，内部节点右边的节点数。第0层到第2层形成了一个完全子树，可利用变量记录这特性。储存令输入，，，，，

霍夫曼译码可在的时间内完成。

1311.3.2算术码字母集且字母的机率为、、和。我们要编码的讯息为

我们可用标签的中间值0.2844表示原始之讯息。收方收到的值是0.2844该如何译码呢？因为0.2，可知第一个字母为；从0.28可知第二个字母亦为。最终可推得原讯息为。1411.4矢量量化法令码表中的码为而待搜寻的区块矢量为X，找到使得这里，。15再令，，金字塔式矢量搜寻法

给二非负整数x和y

对任意矢量，令

16回到VQ的方法上，令

若每四个元素缩成一个平均值

其中q表示金字塔的高度。不等式中，为X缩小1/4后的上一层之矢量，而为的上一层之矢量，这里X和Ci皆为最底层的矢量。每一个Ci皆事先建好自己的金字塔。X也建出属于自己的金字塔。计算两金字塔的顶端的相关值，即。若计算得到的值比目前暂时的最小值都来的大时，则就不必再往金字塔的下层考虑了。1711.5静态影像压缩JPEG一直是彩色影像和高灰阶影像的压缩标准。JPEG首先将输入的影像切割成8

8的子影像集。将输入全彩影像中每一像素的R、G和B值转换为Y、Cb和Cr值。(1)将DCT作用在8

8的子影像上：每一像素皆先减去128，以下列的计算完成DCT图11.5.1经DCT

作用后的结果

(a)8

8子影像(b)8

8系数矩阵18(2)将第(1)步骤所得的频率域值除以8

8量化表(QuantizationTable)图11.5.2量化表与量化后的结果(a)8

8量化表(b)8

8量化后DCT系数矩阵(3)将第(2)步骤所得的结果四舍五入以取整数

图11.5.2(b)的DCT系数矩阵经IDCT(InverseDCT)作用后，可得解压后的影像，如图11.5.3所示。

图11.5.38

8解压后影像

19(4)依据Zig-Zag的扫描次序，将第(3)步骤所得的结果依低频为先的原则，图11.5.2(b)的矢量型式为(39,-3,2,1,-1,1,0,0,0,0,0,-1,0,0,0,…,0,0,0)。

图11.5.4Zig-Zag扫描次序(5)针对AC进行Run-Length编码

(6)进行DPCM(DifferentialPulseCodeModulation)和霍夫曼编码(HuffmanEncoding)可编码为(0,-3)(0,2)(0,1)(0,-1)(0,1)(5,-1)EOB

在Run-Length编码的格式(x,y)中，x通常采用固定长度编码，而y则依照事先建好的图11.5.5表进行变动长度编码。上述的矢量型式进一步编成(0,2)(00)(0,2)(10)(0,1)(1)(0,1)(0)(0,1)(1)(5,1)(0)001-1,12-3,-2,2,33-7,…,-4,4,…,74-15,…,-8,8,…,15::::位元数y的范围图11.5.5y的编码对照表2011.6动态影像压缩视频压缩(VideoCompression)中，例如MPEG或H.264/AVC，我们先将视频影像分成三类，分别为I

、

P和B影像。I影像用IntraMode压缩即可。P影像可利用前面的I影像，透过区块匹配

(BlockMatching)和补偿(Compensation)来压缩。夹在I和P之间的B影像之区块就由I和P所匹配到

的区块内插而成。IPBBB区块匹配21在MPEG或H.264/AVC中，区块匹配是核心的工作。区块匹配是在前一张参考影像中找到某一区块，使得找到的区块和目前区块最匹配。通常是采用在前张影像中先订出一个搜寻视窗，在这搜寻视窗内包含许多与目前区块相同大小的正方形区块。因此进行区块匹配前得先决定搜寻的范围和区域。Feng等人[22]。

假设目前区块为Bc，西边邻近区块、西北边邻近区块和北边邻近区块会用来产生Bc

的初始移动矢量。接着，利用初始移动矢量所得的区块B’r，计算两者的绝对差平均值(MeanAbsoluteDifference,MAD):

若得到的值很大，则Bc

属于高移动区块，搜寻视窗为原始搜寻范围。若是中等的值，则属于中移动区块，搜寻范围为原始搜寻范围的一半。否则属于低移动区块，搜寻范围则为1/4的原始搜寻范围。应用到全搜寻(FullSearch)算法后，有60%以上的时间改良率。估计精确度和全搜寻算法则是差不多。2223由式子可知，对每个目前区块算出参考影像中最匹配的区块，然后纪录。[24]实际分析图11.6.1所示的五种视频档中的机率，给出类型配对和搜寻范围间更合理的建议。而为了节省乘法和除法的计算，以累计绝对差(AccumulatedAbsoluteDifference,AAD)当作区块间的相似量度。定义如下：24销售员花园月历车苏西足球图11.6.2五种视频档的不同D分布图百分比根据实验，发现D=4时，几乎涵盖大多数的最大绝对值位移。图11.6.2为五种视频档的不同绝对位移分布图。25令代表在视频档l中的第i张影像中随机变量D的机率值。D的平均机率可表示为针对五种视频档，图11.6.3分别列出它们的D之平均机率。当，把五种视频的D之平均机率叠加起来，得由上式可知当D小于等于4时，平均的叠加机率高达91.17%。令，这个值在决定最低搜寻范围时会用到。

26假设在视频档l中的第i张影像已被分割成5×5个区块，见图11.6.4(a)，图中的(x,y)代表该区域的移动矢量(MotionVector)值。图11.6.4(b)这四个邻近区块的移动矢量之平均值可用来预测Bc

的初始移动后的Bc。

(a)参考影像(b)目前影像图11.6.4一个例子由图11.6.4(a)可算得，，，，，，。利用式子可得到。(0,0)D=0(0,0)D=0(0,0)D=0(0,0)D=0(1,1)D=1(0,0)D=0(0,0)D=0(0,0)D=0(1,1)D=1(1,0)D=1(0,0)D=0(1,0)D=1(3,2)D=3(2,0)D=2(2,0)D=2(1,0)D=1(3,1)D=3(5,3)D=5(6,2)D=6(2,1)D=2(1,0)D=1(2,1)D=2(3,2)D=3(2,2)D=2(2,1)D=2(3,2)(5,3)(4,1)(4,2)27完全搜寻(FullSearch)我们假定在搜寻范围中的某一搜寻正方形，如图1