视频压缩基本概念

2021年1月24日 / 80次阅读 / Last Modified 2021年3月11日
图像处理

原始视频数据非常庞大,如果不压缩,就难以传输和复制。codec就是指视频压缩和解压的专业术语。视频压缩一般都是有损的,这样可以在不影响视觉效果的前提下,达到更好的压缩效率。无损压缩的压缩效率会低很多。本文是一篇读书笔记。

视频压缩算法的原理:移除视频数据中的时间冗余,空间冗余,以及频率冗余信息,然后通过熵编码(比如哈夫曼编码等)进一步压缩。时间冗余指在时间上相邻的frame中,存在大量没有变化的数据;空间冗余指:在同一个frame中,有很多低频区域,这些区域内的数据没有变化;频率冗余指frame中可以去掉的高频数据(比如用低通滤波器(LPF)做图像背景虚化,去掉后数据能减少,也符合视觉效果需求)。

  • frame: a representation of the complete visual scene;
  • field: consisting of odd- or even-numbered lines of spatial samples. (还看到3个词:top field, bottom field, interlaced video sequence。在一个fps间隔里,采样两个fields,bitrate不变的情况下,可以提高画面的平滑效果,但现在此技术已经基本废弃,显示器都已经是progressive)
  • sample,采样点,就是pixel
  • fps: frame per second, 电视图像的fps是25或30,fps越高,图像变化越平滑,但是bitrate也越大。
  • raster scan order:从左到右,从上到下。
  • color space,如何表示颜色,最容易理解的就是RGB,视频压缩领域一般都使用YCbCr(YUV);相关概念 bits depth;颜色通道 color channel,只是每一种颜色,比如RGB就有3个channel。
  • CIF,Common Intermediate Format,也叫 video frame format,就是一组定义好的分辨率而已,现在看这些分辨率都太小,可能在手机上还有应用吧。

--------

PSNR,Peak Signal to Noise Ratio,用来客观评价视频压缩质量的一个数量指标,很常用,也有缺陷,但似乎一直没有更好的指标出来:

$$ \text{PSNR}_{db}=10\log_{10}\frac{(2^n-1)^2}{\text{MSE}} $$

$$\text{MSE}=\frac{1}{H \times W}\sum_{i=1}^{H}\sum_{j=1}^{W}\bigl(X(i,j)-Y(i,j)\bigr)^2$$

MSE: mean squared error between original frame and impaired (compressed). n is the number of bits per image sample (n一般取8). 因此,PSNR越大越好,因为MSE要越小越好。

PSNR的缺陷在于:

  • 需要用 original frame 来参与计算,但有时可能难以获取或分辨其fidelity;
  • 与 subjective video quality measure (ITU-R 500)的相关性不好,更低的PSNR值在主观上并不一定就更差,比如一张仅做了背景虚化的图片,它的PSNR可能很低,但是视觉效果并不差。

上述计算公式可用于灰度图,只有一个channel的图片计算。如果是彩色图片,有3个channel的情况,如何计算PSNR呢?

1, 分别计算 RGB 三个通道的 PSNR,然后取平均值。
2, 计算 RGB 三通道的 MSE ,然后再除以 3 。
3, 将图片转化为 YCbCr 格式,然后只计算 Y 分量也就是亮度分量的 PSNR。(另外看到一种说法是,将RGB转换成灰度图,然后求灰度图的PSNR,转灰度图的计算方法是不确定的....)

其中,第2和第3种方法比较常见。

average PSNR:将所有frame的PSNR加总取平均。


在时间上相邻的frame,存在大量的 temporal redundancy,fps越大,这种冗余就越多。在空间上,相邻pixel值通常也强相关。

motion compensated prediction,运动补偿,motion compensation 是指将 参考帧(reference frames)的部分区块,通过 motion vector, 补偿到当前的frame中的这个动作,最后得到的结果current frame的一个prediction(predictor)。因此 current frame - prediction = residual frame。参考帧对于当前帧,可以是过去的,也可以是将来的(H.264的B,是用过去和将来的frame,合在一起取平均),目的是得到更好的prediction,so less energy is contained in the residual frame。可以想象,如果仅仅是简单的用当前帧减去前一帧,得到的residual frame一定有比较高的energy,为了减少energy,用motion compensation技术。但是这个技术不是万能的,有一些motion is very hard to compensate,比如 deformable objects,rotation, warping,complex motion such as a cloud of smoke。

理论上,以pixel为单位进行motion compensation,可以得到一个energy为全0的residual frame,但是带来的问题是motion vector数量超大,每个pixel对应一个vector,还不如不压缩呢,没有实际意义。而且,计算量也是巨大的。因此,motion compensation 都是 block-based

Block-based motion estimation and compensation,假设一个当前帧中MxN大小的block,在参考帧中去search the best match block with the same size。search有不同的策略,best match也有不同的criterion(比如两个MxN block相减之后energy最小),tradeoff with computation cost,这个过程就是 motion estimation,输出 motion vector。

macroblock,宏块,16x16大小,这个概念在MEPG-1,MPEG-2,MPEG-4 Visual,H.261,H.263,H.264中都被使用。(H.265突破了macroblock的限制,CTU可以到64x64)

encoder内含有一个小型的decoder!在decoder端,参考帧也是decode出来的,为了保证encoder和decoder使用相同的参考帧数据进行编码和解码,encoder需要对residual进行encode- -> decode后,再使用!(一般quantization都是lossy的,除非lossless,或者不做quantization,这时encoder端可以不做decode)

  • intra mode:encoding without motion compensation,当前帧相对参考帧有非常显著的变化时,比如场景切换,适合此模式。
  • inter mode:encoding with motion compensation prediction。如果参考帧选择的是将来的,frames must be encoded out of order。

用来执行motion compensation的block多大合适呢?虽然macroblock是16x16固定大小,但H.264采用的adaptive block size的方式,即根据画面性质来选择最终执行motion compensation的block size,比如变化不大的区域,就可以用16x16,充满细节和复杂变化的区域,可以用4x4大小。执行motion compensation的block size越小,得到的residual的energy就越小,即效果越好,但是overhead(motion vector)也越多,因此要选择adaptive的方式。

SAE:Sum of Absolutie Error。

Sub-pixel motion estimation and compensation。有些场景,用interpolation算法将block的分辨率提高,然后再做estimation和compensation,效果更好!书中有个例子:用SAE值来度量residual的energy,pixel > harl-pixel > quarter pixel。

虽然sub-pixel减少了residual的energy,但也需要在使用时权衡:

  • 计算复杂度增加,encoder和decoder必须要使用相同的interpolation算法来构建相同的参考帧数据;
  • 要用更多的bit来编码motion vector,因为需要表示位置的小数部分;

补充一个好图,可以更清晰的看到half-pixel和quart-pixel的位置:

左边有一个放大区域,其中圆点是原pixel,三角形是half,+号是quart!

region-based motion compensation。不是所有的场景,都能够在block-based模式下,取得很好的match,即很小的residual energy。MPEG-4 Visual有一些这样的工具,H.264没有。(Deep Learning?)

自然图像有一个特点,每个pixel都与它周围的pixel存在相关性,这种相关性随着两个pixel之间距离的增大而减小。Residua数据的这种相关性就要弱很多。因此,通过motion compensation得到residual,其实是在做decorrelation。这里有个image model的概念(经过此model的一系列步骤后,得到的数据形式更有利于做entropy coding,这一系列的步骤的目的,就是为了entropy coding?),包含几个部分:

  • transform,decorrelates and compacts data
  • quantization, reduces the precise of the transformed data
  • reordering, arranges the data to group together significant values

临近block的motion vector也存在相关性,比如一个占了很多block的object在运动,这些block的mv必然相似,相似的mv在编码时还可以进一步压缩,只对变化进行编码,motion vector difference,MVD。(predictive coding,用前面的mv来预测后面的mv,然后补偿一个difference)

关于transform:

  • transform后的数据,应该是降低了相关性(decorrelated),并且有一定的压缩效果(大部分的energy集中在少数几个数据上);
  • transform是可逆的计算;
  • tranform的计算量和计算精度tractable;(计算的精度损失,算不算lossy compress?)

transform分两类:

  • block-based,SVD和DCT等,将图像或residual划分成block,分别对block进行transform,计算过程内存占用少,并能很好的与block-based motion compensation配合,但在block边缘,容易有artifacts。
  • image-based,DWT(比如Discrete Wavelet Transform,小波变换),对一整张图像整体(或者一大块区域,tile)进行处理,对静态图片(still picture)压缩效果比block-based transform好,但是计算过程内存占用很高,与block-based motion compensation也不太好配合。

DCT(Discrete Cosine Transform)

输入X是 NxN 的一个block,Y是输出,叫做 matrix of coefficients。DCT的计算公式如下:

$$Y=AXA^T$$

$$X=A^TYA$$

我不是很能理解DCT,从这个计算公式来看,应该需要 \(A^T=A^{-1}\),即A是orthogonal matrix,但是实际上不是。

$$A_{ij}=C_i \cos(\frac{(2j+1)i\pi}{2N})$$

$$C_i=\sqrt\frac{1}{N}\text{ }(\text{when }i=0)\text{, }C_i=\sqrt\frac{2}{N}\text{ }(\text{when }i>0)$$

当\(N=4\)时,A如下:

我有一种这样的感觉:A的每一个行向量(除了第1行),就像一条cosine波浪(以中心值0上下对称),不同的列,这条波浪的周期不同;当计算 \(AX\) 的时候,这条不同周期的波浪,会将X中每个列向量的数据打碎重组,相关性强的数据,也就变的不相关了。计算 \(AX\) 是对X的列进行处理,计算 \((AX)A^T\) 是对X的行进行处理。

>>> a
array([[ 0.5  ,  0.5  ,  0.5  ,  0.5  ],
       [ 0.653,  0.271,  0.271, -0.653],
       [ 0.5  , -0.5  , -0.5  ,  0.5  ],
       [ 0.271, -0.653, -0.653,  0.271]])
>>> np.dot(a,a.T)
array([[ 1.      ,  0.271   ,  0.      , -0.382   ],
       [ 0.271   ,  0.9997  , -0.271   , -0.353926],
       [ 0.      , -0.271   ,  1.      ,  0.924   ],
       [-0.382   , -0.353926,  0.924   ,  0.9997  ]])
>>> a[:,0] @ a[:,0]
0.99985
>>> a[:,0] @ a[:,1]
0.0
>>> a[:,0] @ a[:,2]
0.0
>>> a[:,0] @ a[:,3]
0.14703199999999994
>>>
>>> a[:,1] @ a[:,0]
0.0
>>> a[:,1] @ a[:,1]
0.99985
>>> a[:,1] @ a[:,2]
0.99985
>>> a[:,1] @ a[:,3]
-0.353926
>>> x
array([[ 5, 11,  8, 10],
       [ 9,  8,  4, 12],
       [ 1, 10, 11,  4],
       [19,  6, 15,  7]])
>>> y = a @ x @ a.T
>>> y
array([[ 35.      ,  10.218   ,  -1.5     , -14.756   ],
       [  3.75    ,  -6.241104,  -3.887   ,  -5.024088],
       [  5.5     ,   5.193   ,   2.      ,  -0.253   ],
       [ -8.288   ,   0.895056,   2.421   ,   5.40302 ]])
>>> x2 = a.T @ y @ a
>>> x2
array([[ 9.41311739, 18.17851103, 18.17851103,  4.35547663],
       [ 5.2613049 , 20.77364833, 20.77364833,  4.95218875],
       [ 5.2613049 , 20.77364833, 20.77364833,  4.95218875],
       [16.60325959, 11.11580633, 11.11580633,  0.90056717]])

这显然不是orthogonal matrix,但是\(AA^T\)的对角线上的值,也很接近1。以上计算也不可逆,哪里错了?

书中有一种对DCT计算后得到的coefficient的解释:These coefficients can be considered as 'weights' of a set of standard basis patterns which are composed of horizontal and vertical cosine functions. Any image block may be reconstructed by combining all NxN basis patterns, with each basis multiplied by the appropriate weighting factor (coefficient). 下图是4x4 DCT的basis patterns:

DCT的作用要通过重构图像的时候来观察,如果我们只使用coefficient中 most significant 的那一小部分值(从大到小排序,大的就是significant),可以重构出于original图像近似的效果,使用的coefficient越多,还原出来的效果越好(coefficient越大,越重要,这跟SVD压缩图片的原理类似)。

Coefficient Distribution

The significant coefficients of a block of image or residual samples are typically the 'low frequency' positions around the DC(0,0) coefficient. The nonzero DCT coefficients are clustered around the top-left (DC) coefficient and the distribution is roughly symmetrical in the horizontal and vertical directions. 下图是个例子:

概念:DC系数,直流分量,即top left位置的那一个值;AC系数,交流分量,除了top left外的其它值。(还是不太懂)

量化(quantization)的作用,就将 transformed data 进行取值范围(具体不同值的数量)的缩小,这个过程有损,不可逆。不同值数据的数量变小了,就可以更好的进行entropy coding。量化的基本原理如下:

$$FQ=\text{round}\left(\frac{X}{QP}\right)$$

$$Y=FQ \cdot QP$$

QP是量化的 step size,这个值如果很大,可以看出量化后不同值的数量就会很小,entropy coding就会有很好的的压缩效果,但是decode之后的画面质量也更差。

量化是DCT之后的步骤,其作用是将 insignificant coefficients 映射为 0,保留那些 significant coefficients,这种保留也有精度损失,中间经过了一个round操作。这个操作得到的结果,通常是一个 sparse coefficient matrix mainly contained zeros,大量的0,少量的coefficient!

Vector Quantization:这是另一种量化方法。基本思路是采用一个codebook,里面存放codeword,每一个codeword对应一个预先定义好的图像,并且编解码双方预先已经存放了这个codebook。这就像谍战片里通信双方使用的相同的密码本。首先将图像分块,然后去在codebook寻找与每一块图像最接近的codeword,这些codeword组成一个vector。解码时反过来,用vector中的codeword去在codebook中找出一块块小图像,重新拼接成完整的图像。

这个方法还可用于 motion compensated data and/or transformed data。此方法的关键在于搜索codebook的效率。

不同编码块的QP参数可能会不一样(比如改标压缩比以匹配通道的bitrate),通常这些不同的QP参数差异都很小,因此在对这些变化编码时,对新的数值进行编码不是个好方便,对变化进行编码(比如-1,+2...),可以有更好的压缩率。比如使用Golomb压缩编码

Scan Order (Reorder)

量化后的数据,一般有大量的0,scan的作用在于,更有效的去表示量化后的数据,将2D数据转成1D,给entropy coding提供input。一个典型的reordering path就是zigzag。

Run Level Encoding

2D run level encoding:

  • run: how many zeros preceding a nonzero coefficient,
  • level: the magnitude of the nozero coefficient.
  • input: 16,0,0,-3,5,6,0,0,0,0,-7.......
  • output: (0,16), (2,-3), (0,5), (0,6), (4,-7).......

高频DCT系数(啥意思?)常常在量化后就成了0,reorder之后的结果,也常常是最后一长串的0,再没有nonzero。3D run level encoding是在2D的基础上,增价格last indicator,用来表示后面全0的情况:

  • input: 16,0,0,-3,5,6,0,0,0,0,-7,0,0,0,0.......(all zero)
  • output: (0,16,0), (2,-3,0), (0,5,0), (0,6,0), (4,-7,1).......

Entropy Coding

Variable Length Coding,VLC,变长编码,典型如Huffman coding。它有几个弊端:

  • 编解码双方必须使用相同的codeword set,这会增加overhead,特别是在对比较短的 video sequence 编码时;
  • 当对比较长的 video sequence 使用VLC编码时,由于要计算 symbol probobility,必须要计算所有的数据后才能开始编码,这会带来不可接受的延时;
  • 对传输错误很敏感;(RVLC可在错误发生时,提高解码性能)
  • 压缩效率的问题,(1)表示信息的最低单位是1个bit,bit不可再分,但理论上的最优压缩效率,要使用 fraction number of bits;(2)symbol的概率分布也影响压缩效率。

因此有了 pre-calculated VLC ,通过在很 general 的 video material 上计算得到一组codeword set,给编解码双方直接使用。但编解码双方必须要事前存好这份codeword set。也可以通过使用exp-golobm编码codeword set。

CAVLC,Context-Adaptive VLC

Arithmetic Coding,压缩效率更接近理论最优值,代替VLC。这个算法对我来说很新颖,在得到symbol的概率分布后,对0-1这个区间不断的sub-range,在最小的range中任意取一个float number,最后用接近理论的最优bit数,对此float number进行编码。

抄个例子,我们准备对(0,-1,0,2)进行编码,首先得到这一组数字的概率分布:

编码的过程,就是不断做sub range和比较的过程:

在最后的range中,任意选择0.394这个float number,用9个bit来表示,来作为对(0,-1,0,2)在给定概率分布下的编码。

解码的过程,也是一个不断寻找range,并匹配symbol的过程。

  1. 0.394在0.3 -- 0.7之间,因此第1个symbol是0
  2. 重新分割 0.3 -- 0.7,发现0.394在0.34 -- 0.42之间,第2个symbol是-1
  3. 继续分割 0.34 -- 0.42,发现0.394在0.364 -- 0.396之间,第3个symbol是0
  4. 分割0.364 -- 0.396,发现0.394在0.3928 -- 0.396之间,第4个symbol是2

CABAC,Context-Based Arithmetic Coding

Hybrid DPCM/DCT Video Codec

Motion estimation and compensation,是前端,有时被称为DPCM。然后Transform和Entropy。这个model常常被称为Hybrid DPCM/DCT Video Codec Model。几乎所有的codec标准都是这个model,只是细节和实现上有很多不一样。

-- EOF --

本文链接:https://www.pynote.net/archives/3183

留言区

《视频压缩基本概念》有5条留言

您的电子邮箱地址不会被公开。 必填项已用*标注

  • 麦新杰

    
    There are two places in video codecs where these filters are typically used:
    
    Motion estimation/compensation
    
    Video codecs compress much better than still image codecs because they also remove the redundancy between frames. They do this using motion estimation and motion compensation. The encoder splits up the image into rectangular blocks of image data (typically 16x16) and then tries to find the block in a previously coded frame that is as similar as possible to the block that's currently being coded. The encoder then only transmits the difference, and a pointer to where it found this good match. This is the main reason why video codecs get about 1:100 compression, where image codecs get 1:10 compression. Now, you can imagine that sometimes camera or object in the scene didn't move by a full pixel, but actually by half or a quarter pixel. There's then a better match found if the image is scaled/interpolated, and these filters are used to do that. The exact way they do this filtering often differs per codec.
    
    Deblocking
    
    Another reason for using such a filter is to remove artifacts from the transform that's being used. Just like in still-image coding, there's a transform that transforms the image data into a different space that "compacts the energy". For instance, after this transform, those image sections that have a uniform color, like a blue sky, will result into data that has just a single number for the color, and then all zeros for the rest of the data. Comparing this to the original data, which stores blue for all of the pixels, a lot of redundancy has been removed. After the transform (Google for DCT, KLT, integer transform), the zeros are typically thrown away, and the other not so relevant data that's left is coded with fewer bits than in the original. During image decoding, since data has been thrown away, this often results in edges between the 8x8 or 16x16 of neighboring blocks. There's a separate smoothing filter that then smoothens these edges again.
    
     [回复]

  • 麦新杰

    【DCT在做什么】In an image, most of the energy will be concentrated in the lower frequencies, so if we transform an image into its frequency components and throw away the higher frequency coefficients, we can reduce the amount of data needed to describe the image without sacrificing too much image quality. [回复]

    • 麦新杰

      图片数据的性质是,大量低频+少量高频,高频组成了边缘,低频填充了内容。 [回复]

    • 麦新杰

      量化实际上就是对部分高频信号清零。Qstep用来控制选择的高频信号的范围。 [回复]

  • 麦新杰

    学习资料补充:https://github.com/leandromoreira/digital_video_introduction [回复]


前一篇:
后一篇:

More


©Copyright 麦新杰 Since 2019 Python笔记

go to top