作者:姜生,PP云高级技术经理,10余年视频编解码算法设计优化,流媒体应用等领域开发经验。
一 SAO 技术介绍
SAO 的全称是 Sample adaptiveoffset,对应的中文意思是采样自适应补偿。SAO 是H.265编码规范中一项重要的压缩技术,该技术的思想源于Samsung提案JCTVC-A124。实验测试结果显示 SAO 能够带来的压缩增益远超过Deblock和ALF。
SAO 模块在编码器的结构图一中所处的位置如下(红色的部分):
图一 SAO在编码器中的位置
SAO 在解码器的结构图二中所处的位置如下(红色的部分):
图二 SAO在解码器中的位置
从流程图中可以看出,SAO和ALF是loop内的操作,接在Deblock的后面,输入包括原始的YUV图像和Deblock的输出,生成的参数需要进行entropy编码。参考图三:
图三 SAO 的算法概图
二 SAO 算法介绍
图像经过压缩和解压后,精度会损失。通过psnr计算公式可以看出,重构数据和原始数据YUV之间差值的平方和决定了psnr。SAO 通过分析原始数据和重构后的数据,对deblock之后的进行offset补偿操作,使得尽量接近原始的像素值,达到提高psnr 的目的。
均方误差:
峰值信噪比:
如何具体运算来提高PSNR值呢,一个直接的想法是把deblock的重构数据和原始的YUV 中每一个相同位置的pixel做差值,把这个差值传给decoder,这样可以完全恢复YUV。实际上,这样做会导致码率非常高,达不到压缩的效果。
为了能够提高psnr,同时只会增加极少量的码率,H.265 在码率和psnr之间做了一个tradeoff。下面看一下是怎么做的。
H.265是基于CTB来做SAO的,通过分析原始数据和deblock后的重构数据,将pixel 分成三种SAO模式:
SaoTypeIdx[cIdx][rx][ry]
SAO type
Not applied
1
Band Offset(BO)
2
Edge Offset(EO)
由上表可以看出,SAO 有三种模式:不做,BandOffset, Edge Offset, 后面两种模式分别介绍如下:
EdgeOffset Mode:(边界补偿模式)
在这种模式下,SAO 需要为CTB 选择一种梯度模式,水平/垂直/45度角/135度角。这四个类别用sao_eo_class 语法元素表示,如图四:
图四 edgeoffset 梯度四种模式
为当前的CTB选择好一种梯度模式后,开始计算该CTB中每一个像素和相邻两个像素的大小关系,这个大小关系分成5类:
EdgeIdx
Condition
Meaning
P = n0 and p = n1
Flat area
1
P < n0 and p < n1
Local min
2
P < n0 and p = n1 or P = n0 and p < n1
Edge
3
P > n0 and p = n1 or P = n0 and p > n1
Edge
4
P > n0 and p > n1
Local max
图五 EdgeIdx 四种类型
对CTB而言,EO(Edge Offset)的梯度模式在码流里面被包含了,但是对于每一个像素而言,EdgeIdx 是通过计算得来的,编码器和解码器所使用的计算方法一样,所以得到的结果一样,码流里面不需要编码EdgeIdx信息,这样节省了码率,付出的代价是增加了CPU 的运算量。
对于EdgeIdx 为0的flat area,可以不需要做任何操作。对于其余四类,SAO为每一类分配了一个Offset 整数补偿值,这个Offset会add到被重构的每一对应类像素中。同时H.265规定,EdgeIdx=1,2 这两类,offset 值必须为正数,EdgeIdx=3,4必须为负数,这样符号位不需要编码,节省码率。
Band Offset Mode:
YUV 像素值的取值范围通常是 0~255,平均分成32个band,每一个band包含的横跨的范围是8.通过一定的算法来选择连续的4个band进行补偿,当CTB的YUV 像素值处于选定的4个band中时,需要对这个sample补偿。
图六 BandOffset 补偿模式
Band Offset 的原理是:在编码器端,对32个band分别做像素值的直方图统计,求每一个band像素值的平均值。下面是一个例子:
假设对于原始的CTB,其中有一个band,位于[28,35], 有三个pixel,像素值分别是:32,35, 35,这样可以知道该band 的像素平均值是(32 + 35+35)/3 = 34; 而对应的deblock之后的band,包含三个像素,分别是30,32,34,平均值是(30 + 32 + 34) / 3 = 32, 可见,在该band上,原始的像素值平均值比重构的大 34-32=2,因此,可以分配offset=+2给这个band,在decoder 端为这个band 的每一个像素值加2.这样保证在该band上出现的重构pixel和原始的平均值相等。对32个都做这种处理,最后选择连续的4个。
对于Band OffsetMode和Edge Offset Mode而言,如果当前的CTB的SAO 参数与左边或上边CTB的SAO 参数相同,这时不需要为当前的CTB传输SAO参数,而是直接使用左边或上边CTB的SAO 参数。
三 SAO 算法的优化
1. 优化之前的常用算法:
对于CTB 内的每一个像素而言,需要计算:
1. 先要计算出原始像素值和重构像素值的差值,每个像素的差值用变量offset_value 表示;
2. 需要根据重构的像素值,分别计算每个像素BO,EO0, EO1, EO2, EO3 这五种类型内的每一种子类型值,这个类型之命名为 sao_class,这样 64*64的CTB 方阵,要遍历5次,访问次数大约为:5*64*64
3. 然后对CTB的64*64的方阵,一共4096个像素统计每一个类型的offset_value之和,以及每个类型像素个数 cnt_of_class。
2. 优化后的算法:
该算法的特点是,把每个像素的 offset_value 向左偏移 12位,一个32位的整数,高20位放offset_value 值,低12位放像素个数. 对于每一个像素而言,低12位初始化为1. 64*64 的CTB 块,同一个SAO 的子类型,最多只有 2^12 个像素,所以用低12位保存子类型个数刚刚好不会溢出,如下图:
12 ~ 31 bit (offset_value)
0 ~ 11 (cnt_of_class)
图七 复合数据格式
这样把offset_value 和 cnt_of_class 合并到一个 32 位整型数内,可以让两个数据同时累加运行,运算量减少一半。
假设 64*64的CTB 块,offset值定义为下面的数组:
Offset_value[64][64] = { … …} ; 其中的每个数据格式都是符合数据格式
Rec_pixel_value[64][64] = { … …} ; 重构像素值 0 ~ 255
BO_class[64][64] = { … …} ; 取值范围 0 ~ 31
EO0_class[64][64] = { … …} ; 取值范围 0 ~ 4
EO1_class[64][64] = { … …} ; 取值范围 0 ~ 4
EO2_class[64][64] = { … …} ; 取值范围 0 ~ 4
EO3_class[64][64] = { … …} ; 取值范围 0 ~ 4
定义一个数组:
Int BO_Class[32] = {0} ;
For(int i = 0; i < 64; i++)
For(intj = 0; j < 64; j++)
{
Int Rec_pixel_value[i][j] >> 3;
BO_Class[class]+= Offset_value[i][j];
}
上面运算完成后,可以从BO_Class中分离出每一个子类的:
For(int i = 0; i < 32; i++)
{
offset_value = BO_Class[i] >> 12;
cnt_of_ BO_Class[i] & 0xFFF;
}
Edge Offset Mode:
1. 把 EO0, EO1 和并到一个数组中:EO0, EO1 都包含了 5个子类 0 ~ 4, 需要3bit,为了把两个子类合并起来,需要建立一个二维数组,两个下标分别代表两个类型的子类索引。假设左边的下标代表 EO1 的子类索引,右边的下标代表 EO0 的子类索引:
EO_01[8][8]
2. 按照上面的方法把 EO2, EO3合并到一个数组中:
EO_23[8][8]
3. 完成下面的运算:
{
Intclass_0 = EO0_class[i][j];
Int class_1 = EO1_class[i][j];
Int offset = Offset_value[i][j];
EO_01[class_1][class_0] += offset
EO_23[class_3][class_2] += offset;
4. 分离出 EO0, EO1, EO2, EO3:
Int EO0[5] = {0};
Int EO1[5] = {0};
Int EO2[5] = {0};
Int EO3[5] = {0};
For(int i = 0; i < 5; i++)
For(int J =0; J < 5; J++)
EO0[j] += EO_01[i][j];
EO1[i]+= EO_01[i][j];
EO2[j]+= EO_23[i][j];
最后把每一类的 offset 和 count 分离出来。
四 总结
优化后,SAO 中 offset 统计部分的计算量减少到原来的 25%左右。整个 SAO 模块 90%的运算时间被统计部分消耗掉,所以这个算法的优化在C 层面比较明显。在汇编层面,有一定效果,但不太明显,因为在运算的中间加了一个 8*8的数组,这个数组不利于用多媒体指令集并行方式来实现。