paper: Sample Adaptive Offset for HEVC
《HEVC标准介绍、HEVC帧间预测论文笔记》系列博客，目录见：http://www.cnblogs.com/DwyaneTalk/p/5711333.html
一、概述：这是目前H265中比较热门的技术，根据以前的测试，SAO性价比远远超过Deblock和ALF.
1、 SAO标准框架中位置：
编码器端：
从流程中可以看到，SAO和ALF是loop内的操作，接在Deblockingfilter（也是loop内操作）的后面，输入包括原始的YUV图像和Deblocking的输出，最后产生部分需要参数需要entropy进行编码。ALF是类似的。
解码器端：
2、SAO起源：
SAO原始的思想来自于Samsung的提案JCTVC-A124，可以参考这个文档获得详细的信息。在三星的提案中提出了比较复杂的BDC(Band- correction， 位于ALF和RPB之间)和EXC(extreme-valuecorrection，位于DeblockingFilter（DF）和ALF之间，也就是现在SAO的位置)，BDC和EXC都是对pixel进行分类，然后为每一个分类分配一个offset值。这个offset就是在entropy中要编码的参数。不同的是，BDC使用的是pixel的intensity(Luma值)来对pixel进行分类；而EXC使用的模板中心pixel和neibor pixel之间的梯度来进行的分类(edge特性).
使用经过BDC/EXC处理后的参考帧，能够取得更好的压缩率，但是因为BDC/EXC太复杂，因此没有被H265采用。但是基于BDC/EXC提出的SAO（JCTVC-BO77/C147/D122/E049）最后被采用了。在原始的提案中SAO分为LUMA SAO和CHROMA SAO(JCTVC-F056）。SAO的offset包含BO(Band offset)和EO(Edgeoffset)。SAO采用了不同于BDC/EXC的pixel分类的方法，降低了复杂度。
3、SAO理论基础
在对SAO算法分析之前，需要对三星的BDC/EXC的算法进行了解，参考JCTVC-A124文档。
第一次提出了几个概念：
CU : CodingUnit，可以是16x16,32x32,64x64,128x128（后被舍弃）。然而，CU的size可以不是固定的，而是可以变化的，在SPS中定义了LCU/SCU来限制CUsize的变化范围。（必须是正方形)
sps->log2_min_coding_block_size_minus3 (SCU)
sps->log2_diff_max_min_coding_block_size(LCU)
可以把一个picture划分成LCU的集合，在每一个LCU中再进行CU的划分（CUhierarchy Depth). Hierarchy 的层次决定了可以出现的CU的size的数目： 比如
LCU =64x64， MAX_hierarchy_depth = 4
那么CU可以出现的size只有5种，为：
64线4(LCU), 32x32 , 16x16, 8x8(SCU)
在一个LCU中可以包含INTER CU和INTRA CU，因此CU才是等同于MB。LCU只是一个概念上的值，在编码上还是以CU为单位。
PU: PredictionUnit，是prediction时使用的size，包括intra prediction/interprediciton类似于H264中的partition。
TU： transform Unit， DCTtransform时使用的unit,比如DCT4X4/8X8/16X16/32X32/64X64，可以包含一个或者多个PU。更大的DCTsize有利用处理超分辨率的图像。
在H265中提供了更大的size的选择。这也是为了支持超分辨率的图像的原因。
二、 H265 draft SAO 算法原理
通过PSNR的计算公式可以看到，重构数据和原始YUV之间的差的平方和是决定PSNR的因素。SAO通过分析deblocking后的数据和原始YUV之间的关系来对deblock后的数据进行delta操作，使得尽量接近原始YUV，达到提高PSNR的目的。
一个最基本的想法就是把deblock的重构数据和原始YUV中每一个相同位置的pixel做差值，把这个差值传给decoder，这样可以完全恢复原始YUV.但是这实际上是不现实的，如果每一个pixel都传输一个offset，这会导致码率会非常的高，达不到压缩的效果(如同DPCM)。H265在码率和PSNR之间做了一个tradeoff，以较小的码率增加来提高PSNR。下面就看H265是怎么做的。
H265是基于CTB来做SAO。通过分析deblock重构pixel和原始输入YUV之间的关系将pixel分成了三种SAO模式：
如上表中可以看到，可以不做SAO/Band offset/edge offset 三个mode。
1、EdgeOffset mode:
在这种模式下，SAO首先需要为该CTB选择使用哪一种梯度模式，水平/垂直/45度/135度，这是用sao_eo_class来表示，选择过程通过RDO。
当为某个CTB选择使用了上面某种梯度模式后，开始计算该CTB中的当前sampleP和相邻2个pixel之间的关系，用edgeIdx表示：
因为edgeIdx的计算是针对deblocking以后的重构图像进行的，encoder和decoder使用相同的方法来计算，因此不需要传输这个信息给decoder，而是可以由decoder自己来计算，这样虽然增加了计算量，但是可以降低码率。
对于edgeIdx 为0的flatarea，可以不需要做任何操作。对于1~4，SAO为每一个edgeIdx分配了一个offset，这个offset会add到重构像素中。因为SAO不是为每一个pixel分配一个offset，而是先把pixel进行梯度的计算，并且做edgeIdx的分类，对每一个edgeIdx类分配一个offset(对每一个CTB有4个offset就足够)，这样可以减少码率的消耗。另外，为了进一步降低码率，H265SAO规定对于edgeIdx=1,2这两种情况下，offset值必须是正数；对于edgeIdx=3,4时，offset必须是负数。通过这种强行的要求，符号位可以不进行编码。
2、Bandoff Mode：
SAO encoder把有效的YUV取值范围(0-255 fullRange,16-235 BT601/709)平均分为32个band(如下图，如果是0-255,就是每一个band的范围是8，一共分成32个band)，通过某些算法来选择其中连续的4个band进行补偿，当CTB中的sample的Luma/Chroma处于这4个选定的band中时，需要对这个sample进行补偿(把该band相关的offset值加到sample的值上)。
encoder端如何选择4个band：
从上面这个图中可以看到这个原理：在encoder端会统计原始图像当前CTB中的sample的Luma/chroma值，做32band的直方图统计，每一个band中包含的该YUV中的sample求均值，下面举个例子：
比如假设有一个band是31-38,假设该CTB中有3个pixel的值在这个band中，分别为：32、34、36。这样可以知道原始YUV该CTB中的sample出现在这个band中的均值为(32+34+36)/3= 34。对deblock后的重构图像同样做这样的处理，也求出该band中的均值，假设为32.
那么可见，deblocking后的重构YUV和原始YUV在该CTB上，并且该band上有均值上的差值为34-32=+2.SAO因此可以分配band offset=+2到这个band上，在decoder端，为每一个处于该band上的deblocking后的sample值加上2，这样可以保证在该band上出现的重构pixel和原始YUV上的该CTB的该band上的均值是相等的。
对32个band都做这样的处理，最后选择连续4个，offset值最大的band作为最终确定的需要补偿的band。并且起始band值和4个bandoffset值写到码流中传输给decoder。 通过这种bandoffset的方式，可以把均值差别最大的4个band补偿成均值相等，来拉近原始YUV和重构图像之间的差值。
一个问题：为什么band offset模式中只是选择4个连续的band？标准给出的答案是：
1. 在flatarea部分，大部分的pixel的取值应该会集中在很少的几个band中，因此使用连续的4个band能够覆盖大部分的pixel。(也就是说如果对flatarea的某一个CTB做直方图的话，这个pixel会很集中在很少的几个取值点，因此使用4个连续band可以很好的覆盖.
2. 因为edgeoffset模式使用了4个offset值，为了不增加码率，bandoffset也复用了这4个offset值的syntax，这样不需要另外再增加syntax来专门表示bandoffset。
附录上H265语法来表示上面的信息：
从上面的语法中可以看到：
对于edgeoffset模式，提供sao_eo_class_luma/chroma的值来选择使用什么模式的梯度。并且为1-5这4种edgeIdx提供了offset值，一共4个offset。没有符号位提供。
对于band offset模式，提供了sao_band_position来表示4个连续band的起始band是哪一个。并且为这4个band分别提供了bandoffset值，并且提供了符号位。
另外，如果当前CTB的SAO参数和左边或者上面的CTB的SAO参数相同，那么也就不需要为当前CTB再传输SAO参数了，而是直接使用左边CTB或者TOPCTB中的SAO参数即可。这样可以进一步降低码率。这就是sao_merge_left_flag/sao_merge_up_flag的作用。需要注意的是因为H265引入了TILE/SLICE结构，而tile是并行处理的，另外也不能跨SLICE，因此当前CTB只有和left/TOPCTB处于同一个tile/SLICE时才能共享SAO参数。
总结： SAO是一在deblocking后的一个后处理步骤，会影响到interprediction的参考帧值。SAO是对重构像素进行了PSNR提升的一个重要步骤，直接对luma/chroma值进行非线性操作。H265SAO做的tradeoff就是首先对CTB中的pixel进行分类，再对每一个类别分别进行处理，这样避免了对每一个pixel直接进行处理带来的高码率的代价，从而转换成了对分类后的类进行的处理，而分类的类别的数目是比较少的，对于bandoffset和edge offset都是4个类别。因此只是需要提供4个offset值就足够。
三、编码算法处理过程：
一张图片会被切割成多层的四元树区域，为了决定取样自适应偏移的系数，下列为处理的过程：
以下说明如何从取样自适应偏移编码器的四元树切割得到统计资料，Nl,i,t,c为在阶层l、区域i、类t、型态c的像素数目，al,i,t,c为相对应的偏移，el,i,t,c为相对应原始讯号和重建讯号差的合，Rl,i,t为相关偏移的预测率，借由使用收集到的统计资料，可以利用简单的式子计算出预测的失真减少量，Dl,i,t为阶层l、区域i、类t、型态c的预测失真减少量。
Dl,i,t =(Nl,i,t,ca2l,i,t,c - 2al,i,t,cel,i,t,c) (1)
得知预测失真减少量之后，我们可以计算出位元率-失真成本(Rate-Distortion-Cost)，λ为拉格朗日乘数。
Jl,i,t = Dl,i,t + λRl,i,t (2)
编码器会根据式子(4)选择有最低位元率-失真成本且在阶层l、区域i的类，T为取样自适应偏移类的集合。
Jl,i =(Jl,i,t) (3)
tl,i =(Jl,i,t) (4)
得到最低位元率-失真成本以及最佳取样自适应偏移类之后，编码器会尝试合并子区域成一个父区域，J’l,t和t’l,i分别是合并后的位元率-失真成本以及选择的取样自适应偏移类，Ωl,i是阶层l和区域i的集合。
J'l,i =(
Jl+1,k，Jl,i) (5)
t'l,i =(
Jl+1,k，Jl,i) (6)
根据合并子区域后的结果，相关父区域的分离资讯由以下公式决定：
Sl,i为1代表当前区域会被切割成若干个子区域，为0则代表当前区域不会被切割，处理所有阶层k的区域后，编码器会继续处理阶层k-1的区域直到阶层0的区域，最后使用决定的取样自适应偏参数更新每一区域的解码器图像缓冲区。
四、其他说明：
1、 其他部分说明参考Paper:Sample Adaptive Offset in the HEVC Standard
对于一个CTU，关于EO、BO和no SAO的决策，参见论文Fast Distortion Estimation部分，同样对于EO的offset值选择也参考这一部分。基本思想就是通过RDO进行尝试。
对于EO的offset值，由于SAO是在DF之后，所以在DF过程中，可以顺便产生很多SAO中会用到的值，其中EO的可能的offset值也可以在这个过程中产生，然后在附近的几个值进行RDO。
2、关于限制EO的offset的正负和将BO传输band offset的数目从16减到4个的说明和原因，参见Paper：IMPROVED SAMPLE ADAPTIVE OFFSET FOR HEVC