基于二维奇异值分解的低复杂度的视频编码

基于二维奇异值分解的低复杂度的视频编码

作者：Zhouye Gu, Weisi Lin, Senior Member, IEEE, Bu-sung Lee, Member, IEEE, and ChiewTong Lau, Member, IEEE

摘要：本论文中，我们提出了一种基于二维奇异值分解（2-D SVD）的低复杂度的视频编码方案，该方案利用了视频信号基本的时域相关性而没有处理运动估计（ME ）。通过利用2-D SVD 的系数矩阵的能量集中特性来获得高效的编码特性。这种方案与现有的视频编码方案相比在计算复杂度和时域中取得了一个很好的折中。另外，此方案也避免了混合编码中独立帧编码诸如难以避免的随机存储问题。我们将提出的2-D SVD 方案与现有的非基于ME 的低复杂度的视频方案相比较，结果表明我们的方案的有效性。

索引：计算复杂度，能量压缩，帧独立，矩阵的低秩估计，视频压缩。

I ．介绍

混合视频编码是帧间预测与变换编码的结合。H.261/3，MPEG-1/2/4 [4]-[7]，和H.264/ACV[1]-[3]视频编码标准都采用了这种编码框架。视频信号的时域冗余性被用于帧间预测，例如基于块的运动估计。因此，通常编码效率都很高。

然而，尽管其使用了快速的运动估计，其高效的编码特性主要是由于高的计算复杂度换来的。据估计，H.264的帧间编码复杂度是侦内编码的5-10倍（在不使用运动估计）[8][9]。高复杂度就会导致很长的计算时间，硬件资源要求也很高[9]-[15]。另外，对于侦内独立压缩，混合编码系统常常会出现其在无线传输中易出错的严重问题，而且错误率很高。再有就是基于运动估计（ME ）的编码常常会由于视频编辑等应用的需要改变帧的需要而重新编码，增加了其复杂度，因而其也不适用与视频编辑的需要。

另一方面，视频帧间编码，例如：H.264/ACV[2][3]和移动JPEG2000(motion J2K)[44][45]，由于是帧是独立编码的，因此不存在以上提到的问题。帧间编码允许帧随机存储，因此对于视频编辑应用很适合。另外，独立帧编码使得每帧之间的编码是独立的，因此在传输中的错误也不会影响其他帧。然而，虽然H.264/ACV相比Motion J2K[46][47]而言编码效率有很大提升，但在相同的比特率下其相比混合编码而言编码效率仍然很低。

一些非基于运动估计的地复杂度的视频编码方案应用在移动电话视频或视频监视系统中[12]-[19]。Chin 和berger 提出了基于------的低复杂度的视频编码方案[19]，kamath 和jackson 基于------的motion JPEG编码，其相邻帧的系数的编码是不同的[17]。Law et al，提出了一种基于小波的快速编码算法[12]，在[12][17][19]中，与motion JPEG和motion JPEG2000比较而言编码效率都是提升的。然而他们都是基于连续帧间的差别编码的，因此这些编码方案失去了帧编码的独立性，从而导致易出错。在[15]中，Asif 提出了一种应用在抵比特率的多媒体应用中的非因果预测编码方案，虽然在编码过程中他没有用到ME ，但其编码过程的迭代是复杂而耗时的。

众所周知的分布式视频编码（DVC ）在编码上也具有很好的低复杂的特性。大概与2002年，一些新的编码方案，例如：Wyner-Ziv （WZ ）编码（WZVC ）[23]的提出是基于主信息原理，slepian-wolf[21]和[22]。DVC 放弃了编码端的帧间相关性而利用了解码端的帧间相关性，该方案在编码端有严格限制的情况下极为用。Wu et al，为移动手机应用提出了基于校验子的简易编码方案。Liu et al 提出了一种具有低复杂性的视频监视编码方案，该方案基于WZ 编码原则并在编码效率和计算复杂度间取得一个好的权衡[9]。对于DVC 系统而言，虽

然计算复杂度在编码端减少了，但其解码端的复杂度却大大提高。

利用时域间的冗余来提高编码效率而不增加计算的复杂度是很有挑战性的工作。本论文中，我们提出了一种基于二阶奇异值分解（2-D SVD）的编码方案，2-D SVD是张量的分解的一种[24]-[27],[53]，在提出以来被广泛的应用在计算机视觉上。我们方案是很有预见性的，我们的方案结合可奇异值分解（1-D SVD）和离余玄变换（DCT ）[60]的优点。基于块的一维奇异值分解编码[37][38]，虽然变换后其系数矩阵式对角的但是对于每一个块它都需要传输两个特征向量矩阵，这两个矩阵使得编码效率大大下降，使得其难以应用在实际编码中。我们提出的2-D SVD 方案只需传输两个特征向量矩阵来构造一组帧或块，与基于非运动估计的DCT 相比，本文中2-D SVD的系数矩阵更好。与基于运动估计的混合编码相比较，我们方案的计算复杂度也是很低的，与分布式视频编码相比较我们的编码方案在编解码也是相当简易的。

也有基于主成分分析（PCA ）的视频编码系统例如[51][52][57][58]，然而基于PCA 的编码系统有很多局限性，[51][52][57]都需要计算很多矩阵的特征向量，这些我们也会在IV-C 章节做详细分析。对于如[58]系统而言，PCA 是离线计算的，特征向量在编码端和解码端都存储。虽然这种方案实时PCA 避免了，但其应用也只局限在人脸压缩和传输。

本文余下的部分的内容安排如下：第II 章，我们介绍2-D SVD的理论基础，以及其与DCT 和基于块的1-D SVD的比较，相关的2-D SVD过程将会被用在后文中的视频压缩过程中。第III 章中介绍了我们的2-D SVD与DCT 和基于块的1-D SVD的比较。在地IV 章中，我们讨论整个编码框架，以及在编码复杂度与基于ME/PCA视频编码的比较（例如：基于一组图像（GOP ） 1-D SVD），最终我们给出我们的2-D SVD编码方案。第V 章我们列出了所有的实验结果和与相关编码方案的比较结果。最后第VI 章我们总结了全文。

II ． 二维奇异值分解应用于视频压缩

A ．二维奇异值分解概述

视频的一帧或者一幅图像可以被分成非重叠的大小为m x n的块。我们这里讨论的变换即可应用在帧也可用于块（这里我们只讨论帧的变换，但结果同样可以用在块）。如果表视频的第i 帧，那么其变化形式可表示为： A i 代

M i =U l T A i U l

其中(1) M i 是转换的系数矩阵，U l 和U r 分别是左转换矩阵和有转换矩阵，其精确程度依赖于其转换的形式（例如：DCT SVD等）。这个转换也是可逆的，因此同样一帧也可以如下方式恢复：

A i =U l M i U l T (2)

U l 和U r ，以在SVD 的情况下（如：1-D SVD），一帧分解为两个特征向量矩阵，如：

及一个对角阵

M i 。分解形式如图1所示。

U l 和U r 不确定，U 和U r ，每次都要传输变换矩阵l 最终导致基于1-D SVD基于块的1-D SVD 编码主要问题是，虽然系数矩阵与其他编码方式相比包含少量的非零系数，但由于其

的编码方案难以推广[37][38]。

对于DCT[28][29]编码，固定一个矩阵，即：U l =U r ，DCT 变换形式如图2所示。由于转换矩阵的形式固定因此我们要用M i 表示A i 就相对简单了。

2-D SVD分解如图3所示，在2-D SVD情况下U l 和U r 是从一组帧{A , , , , A }基于（3）1n 式获得的，最终在MSE 准则下获得一组转换系数矩阵{M 1, , , , M n }。

与基于块的1-D SVD 相比，对于一组帧来说我们只需传输两个转换矩阵，而基于块的1-D SVD要为每帧传输两个转换矩阵。与DCT 相比较而言，2-D SVD的一组系数矩阵是有最小二乘准则下获得的，2-D SVD的转换矩阵的获得也是适应改组帧的，然而DCT 用的是预先设定的转换矩阵。更详细的比较将在第III 章阐述。

2-D SVD过程可以用一下矩阵低秩近似[27]的形式来表达：

J =min

s . t

其中A i ∈R r ⨯c U l , U r M i ∑||A -U M U i l i i =1n T r ||2F (3) T U T U =I , U U r =I l 2l l 1l r 表示视频的第i 帧，我们的目的是求出两个U l ∈R r ⨯l 1U r ∈R c ⨯l 2, I l 1∈R l 1⨯l 1

和I l 2∈R l 2⨯l 2，M l ∈R l 1⨯l 2其中l 1≤r , l 2≤c ，这样对于每个i=1,2...n，使得∑||A -U M U i l i

i =1n r ||2F 最小，其中||∙||F 表示矩阵的F 范数。

根据矩阵迹的特性我们有：

J =min

=min

=min U l , U r M i n ∑||A -U M U i l i i =1i l n T r ||2F T r U l , U r M i ∑trace ((A -U M U i i =1n T ) ⋅(A i -U l M i U T ) ) r

U l , U r M i ∑trace (M M i i =1T i T T -2U l M i U T A +A A i i ) r i (4)

上式对M i 求导，并令倒数为零，我们有：J /∂M i =M i -U r A i U l =0，因此我们有： T T

M i =U l T A i U r

将（5）带入（4）式可得：

n n n (5) ∑||A -U M U i l i

i =1T r ||=∑||A i ||-∑||U T A i U r ||2F l 2F 2F

i =1i =1(6)

因此（4）式就可以等价为下述形式：

2max ∑||U T A U ||i r F l U l , U r i =1n

s . t U l T ⋅U l =I l 1, U r T ⋅U r =I l 2

*(7) *上式（7）的最优解U l *和U r 也是（3）式的最优解，M i =U l *T A i U r ，更详细的分析

请看[27]。

B ．二维奇异值分解应用于视频压缩

上边（7）式并没有精确解[26]，因此文献 [26]中给出了其最优解的近似解。基于以上分析和[26]的结论，我们对每组图像块（group of block GOB）的2-D SVD处理过程如下。

1） 给定一组由n 帧视频序列组成的图像组，我们将A i 表示第i 帧，A mean 表示n

帧的均值，我们将这n 帧去均值有：A i ' =A i -A m ean .

2） 对于任意一组去均值后的图像块 B ，我们用b 1,... b n 表示B 中的每一块，并且

其行与行之间和列与列间的协方差矩阵定义如下：

F =∑b i b i T

i =1

n n

G =∑b i T b i

i =1

因此U l 和U r 分别由F 的k 个主特征向量和G 的s 个主特征向量构成，即：

F =∑λp u p u T

p

p =1

n T G =∑ςq v q v q

q =1n U l ≡(u 1,... u k ) U r ≡(v 1,... v s )

其中k ≤r , s ≤c 分别是U l 和U r 中的特征向量的个数。

3） M i =U l T b i U r b i ' =U l M i U r T 我们最终获得每块的最有值b i 为：

b ~

l b mean 相应A mean 的快的均值。 =b i ' +b m e a ，其中n

通过[27]的结论我们可知当s ≈k 时将获得最小值，因此在接下来的分析当中我们设定s=k。

2-D SVD编码的详细步骤将在IV 章中介绍，经过2-D SVD后帧间的共同特性将集中在U l 和U r 中，对于一个GOB 我们只需要传输一次U l 和U r 。每个块的不同都集中在少数几个系数M i 中。

III ．2-D SVD编码的有效性

基于块的1-D SVD编码，每帧图都被分成若干个快儿，然后每块都用1-D SVD编码[37]，

[38]。假如我们要压缩的视频是由n 帧组成的GOP ，每帧的分辨率为W x H 块的大小为m ⨯n ，对于1-D SVD 编码需要计算mW H (2m 2+m ) /m 2个系数，然而我们的2-D SVD 方案只需（2+n）WH 个系数。表一表明了2-D SVD需要的系数只是1-D SVD的50%。

通过与DCT 比较，在基于最小二乘的2-D SVD情况下，图4表是2-D SVD与DCT 在对carphone 视频150帧进行相同量化后的编码获得系数矩阵的结果，（2-D SVD 的GOP 的尺寸是24）。

图4表明，2-D SVD系数（图中黑点所示）远小于DCT 的系数。

我们同样比较了2-D SVD和DCT 在相同量化标准下的系数中零的个数，比较结果如表II 。我们用与JPEG 编码中的一样的量化矩阵（8），他是DCT 的最优系数。我们将DCT 和2-D SVD 的系数用（8）式量化量化QS Q table 然后进行对比，其中QS 是量化步长分别可以为0.1,0.5，和1。我们同样利用了MSE 计算了量化后的两个系数矩阵的重构误差，其两个转换矩阵如下：

由表II ，我们可以看出，不同的量化步长，2-D SVD在很小的重构误差下具有更少的非零系数。例如：对于QCIF 序列，在QS=0.1,2-D SVD系数中平均包涵了至少有15个以上的

零系数，然而MSE 只有DCT 的一半。虽然更多的零系数并不能保证更好的编码效率（这就是我们进行子序列分析的原因），由于零系数的分布也同影响编码效率，更多的零系数和小的MSE 同样会使得其编码具体有很高效率的潜力。

我们同样列出了2-D SVD 编码增益相比其他主流的编码方案的提高[30][31]。编码增益G TC 是编码效能的测量方法[32]-[35]。编码增益是转换系数的几何均值和其转换系数方差之比，单位为分贝，如下所示，其中σi 2第i 个系数阵的方差：

G TC ⎛1N σi 2∑ N i =1=10log 10 1/N ⎛N 2⎫ ∏σi ⎪⎪ ⎭⎝⎝i =1⎫⎪⎪⎪⎪⎪⎭(9)

通常，编码增益是一种度量，用来区别信噪比（SNR ）级别在未编码的系统和编码的系统来达到相同的比特率（BER ）[32]-[35]。表III 我们给出了DCT 和2-D SVD 在块大小为8x8，GOP 尺寸为24的情况下编码增益的比较结果。

从表中可以看出，由于2-D SVD 由于其能量集中特性，相比而言DCT 的编码增益比其低平均6.15分贝。

IV ．2-D SVD 编码框架

A ． 编码

图5描述了2-D SVD编码的详细过程，第II-B 章节中我们所分析的所有过程都可以描述如下。

首先，对一组图像（GOP ）去均值，并用JPEG 标准以高质量因子（文中选90）压缩。然后，将去均值后的的图像序列分成大小为8x8的图像块组(GOB)B j ，然后计算每一组图像块B j 的2-D SVD获得转换矩阵

j j 其中每个U l , U r 都是有8个特征向量构成的特征U l j , U r j 以及一组大小为8x8的系数矩阵M 1j ,... M n j 。

向量矩阵U l j =u 1j ,..., u 8j , U r j =v 1j ,... v 8j [][]，并且每个特征向量的重要性是不同的。设m (x , y ) 表示j

i M i j 在（x ，y ）位置处的值，那么我们可以将一个重构的块b i j 表示为：

b i =∑∑u x j m i j (x , y ) v y jT j

x =1y =1n n (10)

j 特征向量的下表越小证明其越重要，如u 1, u 2, v 1, v 2就比较重要，由于他是与系数矩阵M 1j j j j j j ,... M n j 左上角系数相应特征向量。左上角的系数包含了更多的能量，因此，u 1和u 8选择的不同会导致不同的失真

度，对最终的压缩质量也会有很大的影响。如果m i j j 导致的(1, 1) 是m i j (8, 8) 的上千倍，那么用u 1j 和u 8

失真度也同样如此。矢量量化（VQ ）主要用来编码特征向量[37][38]。这里，我们采用[38]中的VQ 策略。由于其不同的重要程度，我们对于8个特征向量[u 1, u 2,... u 8]我们分别用256,256，128,128,64,64和32的码长为其编码。这个码本同样用于[v 1, v 2,... v 8]。我们用LBG 算法[36]通过对来自6组的训练样本计算8x8 2-D SVD 来训练特征向量。训练系列分别有QCIF,Carphone,Grandma,Silent,and,Suzie, 每个都包含了192帧图像。他们都被用来编码和解码实验。通过这个方法，我们实现了特征向量的传输。表IV 列出了传输特征了向量所需的bit 数。

j j j j j j

从表IV 中我们可以看出，额外的bit 需要的很少，并且在GOP 为24时，我们最多仅仅需要0.07bpp 传输特征向量。

基于左上角的系数包含能量最大的事实，对于一组系数矩阵M 1... M 8，我们用（8）所j j

示的JPEG 矩阵量化。

通过量化之后，我们用6bit 来指明对于每个GOB 我们要传输的特征向量的个数。假如现在m i j (x , y ) 代表的是（x,y) 位置处经过量化后不为零的系数，然后，假如

x max (i ) =max(x ), y max (i ) =max(y ) 表示的是量化后的矩阵M i j 的最大不为零的系数位置。对于每个尺寸为n 的GOB 其最大位置为：

X MAX =max(x max (i ), i =1, 2,..., n ) Y MAX =max(y max (i ), i =1, 2,..., n ) 。这样对于每份GOB 我们用3bit 的X max , Y max 。我们得到X max , Y max 后对于每个GOB 我们就只需传输

[u 1j , u 2j ,..., u x j max ]和[v 1j , v 2j ,..., v x j max ]，大多数情况下X max , Y max 的个数少于4个。

压缩完均值帧和特征向量后，我们将它最为一个整个的GOP 的信息（GI ）传输出去。在大多数情况下，在GOP 为24时GI 仅仅只占整个bit 流的5%。

最后，通过采用z 型扫描进行码长编码，在JPEG 编码中码长可变，系数矩阵进一步被压缩。

从表IV 中和第IV-A 章分析可以看出在相同的情况下，GOP 越长，GI 所占的比例越小。然而，基于内存和延迟的考虑我们不能安排很长的GOP ，因为在GOP 尺寸增大时，2-D SVD的系数的维数会变得很高，这对编码效率的负面影响很大，图6我们比较了carphone 序列的150帧的GOP 分别为8,24,48的2-D SVD系数，图中可以看出当GOP 为8时，只有很少输的系数集中在左上角的位置，而当GOP 为48时，系数矩阵的左上角包含了很多的系数，同样我们也比较了块的情况。

基于以上的分析，我们需要选择合适的GOP 尺寸，这样我们在GI 和GOP 中取得一个折中，图7，我们列出了Coastguard 的GOP 分别为8,16,24和48编码的结果。GOP 从8到24增长时编码效率呈增长趋势。然而，当GOP 增长到48时，编码效率降低了，对于其他的序列而言最优的尺寸也在21到31之间。

理想情况下，我们应该设计一个自适应的GOP 尺寸的以提高编码效率。然而基于编码的简易性我们固定GOP 的尺寸为24。

我们的方法包含了初始延迟（GOP-1=23帧）。因此，我们的方案不适用于低延迟的应用中。然而，现有的视频编码中都存在这样的延迟；GI 对于GOP 的重构非常关键。如果GI 被损坏整个GOP 将会无用，然而，这也是许多IPPP 结构算法的问题；如果I 帧丢失，GOP

同样也会丢失。对于相同的24，GOP 的IPPP bit流，I 帧需要更多的bit 位。因此，如果我们也包含一些其他编码方案的像错误检测等手段，我们的方案也会有很好的容错能力。

B. 解码

解码部分，如图8所示，基本是将编码过程反过来。首先是解码GI ，得到均值帧和特征向量。然后，我们用svd 的逆重构减去均值的帧信息' =N U j M j U jT , 最后加上均值帧，A i j i i i -

我们获得重构的帧。

通过这种方法，只要GI 很小，并成功接收，我们就可以对每一帧独立的解码，就和帧内视频编码一样，独立性是编码技术中很好的一个特性，这就避免了传输过程错误的独立性，许多的复杂算法的提出都解决了这个问题[48]-[45]。

C. 计算复杂度

与混合编码相比，2-D SVD编码方法不需要ME ，而其在2-D SVD时需要VQ 。我们比较了这些区别。

我们首先估计了ME 和提出的2-D SVD方案的不同，遵照第III 章的符号表示，我们有n 帧块为m*m的GOP 。在2-D SVD情况下每个GOB 计算VQ 需要2*

（256+256+128+128+64+64+32）m=2112m次操作，需要计算2n(m^3)个协方差矩阵和26m^3个特征向量矩阵对[27][29]。对于尺寸为n 的GOB 我们每次只需要计算2个特征向量矩阵。总之，