A Fast HEVC Inter CU Selection Method Based on Pyramid Motion Divergence
《HEVC标准介绍、HEVC帧间预测论文笔记》系列博客，目录见：http://www.cnblogs.com/DwyaneTalk/p/5711333.html
IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 16, NO. 2, FEBRUARY 2014
以PMD作为特征，利用kNN决策判断是否进行CU块划分。
核心公式：
分析：(1)中计算R-D的SSD是原始图像与重建图像差值平方和
但是为了节约时间，一般采用原始图像与预测图像的差值平方和来判断，如下：
(2)
X为一个CU块，x为X中一个点，m是预测得到的每个像素点的运动矢量(有专门的算法)，t和t-1表示帧号(假设t帧参考t-1帧)。在不考虑光照因素，设每个像素点实际运动矢量为m，那么
(3)
(4)
公式(4)是将率失真优化理论上归到同一帧处理，由于图像符合一阶马科夫过程，所以对于一幅图像：(一阶马科夫系数p为两点的欧氏距离)
(5)
(6)
简化模型后，(6)式中一阶马科夫系数满足
(7)
然后可以进行如下推理：
(8)
(9)
进行一阶泰勒展开：得到(10)
(10)
(11)
最终就是为了得到R-D值和距离平方正相关。下图进一步通过实验，验证了CU块内所有点MV的方差和该CU块的Cost的正相关性
(12)
然后如上图和公式12就是计算一个CU的特征，左边为当前CU，右边是分成4个子CU，m是像素级的运动矢量
然后上图验证了A 、B两个CU的PA和PB之间相似度和A、B的CU是否划分相同的概率，表名通过判断PA和PB像素来决定CU是否划分的可行性。其中PA和PB相似度ndist如下：
(13)
kNN决策就是从已编码的CU块中，找到k个和当前块PMD最想的，然后用下面策略进行决策：
(14)
进行kNN判断相似度时，除了(13)外，还可以用下面(15)
(15)
Lu是k个最近邻CU中决策为unsplit的个数，Ls是k个最近邻CU中决策为split的个数。Unsure表示按照正常的CU划分策略进行决策。
算法流程：
实际算法流程如下：
首先对图像进行下采样(为了减少Optical Flow Estimation的时间，选择x/4,y/4是为了保证每个TU块中有一个像素参与)；
然后通过Optical Flow Estimation算法，得到每个下采样之后的像素点的MV；
对每个CU块，计算PMD特征
根据kNN准则，预测是否spliting。
说明：
Previous Coded CU是一个FIFO队列，存储已经编码的CU块的PMD特征和最终的CU是否划分的判决，kNN决策时，根据FIFO队列和当前块PMD特征最近的k个，如果全是spliting，则当前块split；如果全是not-spliting，则当前块not-spliting。
实验结果：
环境：HM9.0，kNN的k=5，FIFO队列大小300。表格显示了时间、码率和质量的变化。最后一列是下采样优化的Flow Estimation花费时间所占总体时间的比例。下图不同点表示不同的k值对码率、时间的影响。