x264 亚像素插值及其内存结构

参考：
https://blog.csdn.net/leixiaohua1020/article/details/45936267

1. 亚像素插值原理

先简单介绍一下亚像素插值是如何进行的，基本来自这篇博客 https://blog.csdn.net/leixiaohua1020/article/details/45936267
h264 中像素可以分为整像素、半像素、1/4像素，其中半像素和1/4像素都是通过对整像素插值的来的，类似图像缩放算法中的插值。
具体为什么要插值出亚像素，为什么亚像素比整像素对帧间运动搜索效果更好等算法原理，这里不做讨论。
借用 https://blog.csdn.net/leixiaohua1020/article/details/45936267 的图，画的很清晰：

如上图所示，亚像素插值分为两步：

• 第一步是先插值出半像素：b, h, j, m, s
• 第二步是再插值出剩下的1/4像素：a, c, d, e, f, g, i, k, n, p, q, r

那么整像素 G 加上上述的亚像素，加起来一共 4x4=16 个像素。可以这么理解，通过插值，将一个整像素扩展为一个 4x4 矩形，矩形左上角第一个像素是整像素，其余都是插值出来的亚像素。
当然，亚像素不是单个整像素生成的，而是多个整像素生成的。

另外半像素还有一个概念对后面理解存储结构很重要，这里说明一下：

• 我们上面说的 4x4 矩形中，半像素在矩形中实际上只有 b, h, j 3 个，另外两个半像素 m, s 可以看作属于其它整像素代表的 4x4 矩形
• 像素 b 被称为 H 像素(水平半像素), 像素 h 被称为 V 像素(垂直半像素)，像素 j 被称为 V 像素(对角线半像素)

2. 运动矢量 mv 如何表示亚像素

运动矢量 mv 表示当前宏块的像素级偏移量，坐标原点是当前宏块的左上角，数值可正可负数，也可以为 0。如果宏块是 16x16 分割，那么只会有一个运动矢量。
在 h264 中，码流中的运动矢量都是 1/4 像素精度:

• 逻辑上 mv 可以看作为小数，例如 1.25，即表示移动 1 个整像素，然后移动 1 个 1/4 像素。小数部分可以取值 0, 0.25, 0.5, 0.75 即 4 种
• 码流中如何表达这种小数呢，答案是码流中的数值是小数 mv 乘以 4 得来的，例如 1.25 * 4 = 6。乘以 4 的原因是，4 种小数乘以 4 后都可以转为整数

以一个真实的 pskip 宏块为例，其运动矢量为 (-36, -39)，换算为小数形式就是 (-9.0, -9.75)，即实际上参考的宏块相对于当前宏块的偏移是 (-9.0, -9.75) 个像素

结合上面说的 4x4 矩阵，我们可以进一步推测运动矢量小数部分分别表示哪些位置：

• 运动矢量 0 即表示 G 整像素
• 运动矢量 0.25 即表示向右或向下走第一个亚像素
• 运动矢量 0.5 即表示向右或向下走第二个亚像素
• 运动矢量 0.75 即表示向右或向下走第三个亚像素
• 再往右或向下走就到了其它 4x4 矩阵的整像素了，所以这里我们就可以通过 4 个小数索引 4x4 矩阵的所有亚像素

3. 插值是必须的吗？什么时候进行

插值不是必须的，例如 x264 中有一个可设置的参数 i_subpel_refine，如果将其设置为 0，表示不会开启亚像素运动搜索，那么就不需要再进行插值了。我们一般设置 preset 为 ultrafast 后，i_subpel_refine 就会被设置为 0.
插值在什么时候进行的呢，这要分情况：

• 半像素插值是在编码完一行宏块，进行滤波的时候，进行插值的。继续参考：https://blog.csdn.net/leixiaohua1020/article/details/45936267，里面有写明
• 1/4 像素不会提前插值，而是在需要的时候才会插值出来，例如在运动搜索的时候，通过调用 get_ref() 函数，来进行临时插值。每调用一次，都需要插值一次

4. 亚像素的内存存储结构

下面进入重点，亚像素的内存存储结构是怎么样的呢，解答这个问题需要先了解 x264 内部的几个变量/数据类型：

• x264_frame_t，帧数据类型，里面存储了所有像素相关的数据，所有整像素，亚像素都存储在这里
• pixel *buffer[4]，此 pixel 指针型变量是 x264_frame_t 内部的一个变量，注意到维度为 4，实际上我们只关注索引 0 即可，即对应 yuv420p 中的 luma 分量
• pixel *filtered[3][4], 此 pixel 指针型变量也是 x264_frame_t 内部的一个变量，注意到维度为 [3][4]，实际上第一个维度我们只关注索引 0 即可，即对应 yuv420p 中的 luma 分量；第二个维度 4 分别为 整像素，H 半像素，V 半像素，C 半像素

在 frame.c::frame_new() 函数中，会新建一个 x264_frame_t 帧数据对象，此函数的调用时机是在 x264 所有编码逻辑之前。此函数调用会给 pixel *buffer[4] 申请内存空间：

static x264_frame_t *frame_new( x264_t *h, int b_fdec )
{
...
    // 可以认为 luma_plane_count = 1, 即 YUV420P 中的 luma
    for( int p = 0; p < luma_plane_count; p++ )
    {
        // luma_plane_size 的大小可以简单看作是输入图像的 width * height
        int64_t luma_plane_size = align_plane_size( frame->i_stride[p] * (frame->i_lines[p] + 2*i_padv), disalign );
        // 如果开启了 i_subpel_refine，那么 luma_plane_size 需要扩展 4 倍
        if( h->param.analyse.i_subpel_refine && b_fdec )
            luma_plane_size *= 4;

        // 给 frame->buffer[0] 分配内存空间
        PREALLOC( frame->buffer[p], luma_plane_size * SIZEOF_PIXEL );
    }
}
...

如上可以看到，如果没有开启 i_subpel_refine，那么基本上 frame->buffer[0] 的大小就是 widht * height 大小。
注意到代码中判断如果开启了 i_subpel_refine，luma_plane_size 需要扩展 4 倍大小，这是干嘛用的呢，我们接着看 pixel *filtered[3][4] 的赋值，同样也在 frame.c::frame_new() 函数中，在给 frame->buffer[0] 申请空间之后：

static x264_frame_t *frame_new( x264_t *h, int b_fdec )
{
...
    // 可以认为 luma_plane_count = 1, 即 YUV420P 中的 luma
    for( int p = 0; p < luma_plane_count; p++ )
    {
        // luma_plane_size 的大小可以简单看作是输入图像的 width * height
        int64_t luma_plane_size = align_plane_size( frame->i_stride[p] * (frame->i_lines[p] + 2*i_padv), disalign );
        if( h->param.analyse.i_subpel_refine && b_fdec )     // 如果开启了 i_subpel_refine 走这里
        {
            // 注意到这里有个 4，即对应 filtered[3][4] 的第二个维度，代表 整像素，H 半像素，V 半像素，C 半像素
            for( int i = 0; i < 4; i++ )
            {
                // 这里是关键，每轮循环，`+ i*luma_plane_size` 表示每种像素占的空间是 luma_plane_size 大小
                // 后面 `frame->i_stride[p] * i_padv + PADH_ALIGN` 一串可以忽略
                frame->filtered[p][i] = frame->buffer[p] + i*luma_plane_size + frame->i_stride[p] * i_padv + PADH_ALIGN;
            }
        }
        else                                                 // 如果没有开启 i_subpel_refine 走这里
        {
            frame->filtered[p][0] = frame->plane[p] = frame->buffer[p] + frame->i_stride[p] * i_padv + PADH_ALIGN;
        }
    }
}
...

如上可以看到，frame->filtered[0][4] 的内存空间实际上就取自 frame->buffer[0]。
当开启 i_subpel_refine 后，frame->filtered[0][4] 将 frame->buffer[0] 平分为 4 段，每段长度差不多是 width * height 大小。整像素在第一段，H 半像素在第二段，V 半像素在第三段，C 半像素在第四段，且他们都是 plane 存储，而不是交织存储
对应到前面说的 4x4 矩阵:

• 整像素 G 及其代表的整像素按顺序存储到 frame->filtered[0][0] 中
• 半像素 b 及其代表的 H 半像素按顺序存储到 frame->filtered[0][1] 中
• 半像素 h 及其代表的 V 半像素按顺序存储到 frame->filtered[0][2] 中
• 半像素 j 及其代表的 C 半像素按顺序存储到 frame->filtered[0][3] 中

5. me.c::get_ref() 调用如何取出亚像素

me.c::get_ref() 函数实际上用于通过给定的运动矢量 mv，从 frame->filtered[3][4] 中取出参考帧的参考像素。这个函数比较复杂，下面进行拆解分析。

首先是运动矢量 mv 的表示和一些运算，通过前文我们知道，运动矢量是整数表示的，通过乘以 4 将小数表示为整数，x264 内部也是整数表示，但是有时候需要取出整像素和小数部分：

• get_ref() 函数中，有个 &3 的计算，3 的二进制即 0b11，所以这里实际上就是取运动矢量的小数部分
• get_ref() 函数中，有个 qpel_idx = ((mvy&3)<<2) + (mvx&3) 的计算，这里 &3 即取小数部分，我们知道了，加法前面还有一个 <<2 的操作，即将 y 轴运动矢量的小数部分先扩大，然后加上 x 轴运动矢量的小数部分，这样可以组成一个唯一的数
• get_ref() 函数中，有个 if( qpel_idx & 5 ) 的判断，5 的二进制即 0b0101，结合前面说的 y 轴运动矢量小数部分 <<2 的操作，我们能够知道，这里实际上是判断 x 轴和 y 轴运动矢量的小数部分，是否有 0.25 和 0.75 这两个值存在

其次，在 get_ref() 函数内部有一个重要的变量 qpel_idx，这个变量是什么意思呢，下面进行说明:

• 结合上面，qpel_idx 通过取运动矢量的小数部分，组合成一个唯一的数，这个数的取值大小实际上我们可以计算出来，即 0 到 15 共 16 种
• 同时结合前面第 2 节说明的运动矢量小数部分对 4x4 矩阵索引的概念，qpel_idx 的含义就能明白了：其代表了 4x4 矩阵的索引
• 即 4x4 矩阵左上角第一个整像素代表 qpel_idx = 0 位置；4x4 矩阵右下角最后一个亚像素代表 qpel_idx = 15 的位置，其它类推

其次，在 get_ref() 函数内部有两个重要常量数组 x264_hpel_ref0 和 x264_hpel_ref1，这两个数组是干嘛的呢：

• x264_hpel_ref0 和 x264_hpel_ref1 数组是结合 qpel_idx 使用的，qpel_idx 是其数组索引
• x264_hpel_ref0 和 x264_hpel_ref1 数组内部的取值只有 4 种，即 0, 1, 2， 3，这 4 种数值即对应了 整像素，H 半像素，V 半像素，C 半像素
• 结合上面对 qpel_idx 的说明，我们能够推测出这两个数组的作用：即要得到 4x4 矩阵中某个像素，我们需要 整像素，H 半像素，V 半像素，C 半像素 这几种中的哪几种
• 例如我们要得到 e 像素，首先根据 x264_hpel_ref0 得到 b 像素，然后通过 x264_hpel_ref1 得到 h 像素
• 例如我们要得到 a 像素，首先根据 x264_hpel_ref0 得到 b 像素，然后通过 x264_hpel_ref1 得到 G 像素

经过上面的前置分析，我们可以来正式分析 me.c::get_ref() 函数了(以取 16x16 分割大小的像素为例)：

// dst 是取出的 16x16 个像素目标地址
// i_dst_stride 是 dst 目标地址的 stride，这个 stride 与 i_width 有关
// src[4] 即源像素地址，维度 4 即分别存储了 整像素，H 半像素，V 半像素，C 半像素，注意每种像素在整个图像中都是连续存储的
// i_src_stride 即源像素的 stride，这个 stride 可以简单认为就是源图像的 width
// mvx, mvy 即相对于当前宏块的运动矢量
// i_width, i_height 在 16x16 分割中即为 16
// weight 是加权参数
static pixel *get_ref( pixel *dst,   intptr_t *i_dst_stride,
                       pixel *src[4], intptr_t i_src_stride,
                       int mvx, int mvy,
                       int i_width, int i_height, const x264_weight_t *weight )
{
    // 上面已经分析了
    int qpel_idx = ((mvy&3)<<2) + (mvx&3);
    // 结合上面的分析，容易知道这里是组合运动矢量整像素，乘以 i_src_stride 是因为一个 mvy 跨越一整行
    int offset = (mvy>>2)*i_src_stride + (mvx>>2);
    // x264_hpel_ref0[qpel_idx] 即当前运动矢量是依赖哪种像素类型
    // src[x264_hpel_ref0[qpel_idx]] 即去到像素类型所在的维度
    // + offset 即从位置 0 去到目标位置
    // (((mvy&3) == 3) * i_src_stride 的意思是，如果当前是取 n, p, q, r 这几种 1/4 像素，那么还需要走到下一行，因为 1/4 像素插值需要用到下一行的半像素
    pixel *src1 = src[x264_hpel_ref0[qpel_idx]] + offset + ((mvy&3) == 3) * i_src_stride;

    // 上面已经分析了，即是否是取 1/4 像素
    if( qpel_idx & 5 ) /* qpel interpolation needed */
    {
        // 取 1/4 像素插值需要的两一个半像素
        pixel *src2 = src[x264_hpel_ref1[qpel_idx]] + offset + ((mvx&3) == 3);
        // 所有的 1/4 像素都能通过两个已经提前计算并存储好的半像素插值得到
        pixel_avg( dst, *i_dst_stride, src1, i_src_stride,
                   src2, i_src_stride, i_width, i_height );
        if( weight->weightfn )
            mc_weight( dst, *i_dst_stride, dst, *i_dst_stride, weight, i_width, i_height );
        return dst;
    }
    else if( weight->weightfn )
    {
        mc_weight( dst, *i_dst_stride, src1, i_src_stride, weight, i_width, i_height );
        return dst;
    }
    else
    {
        // 如果是取整像素或者半像素，那么这里直接返回 src1 即可，不需要再做其它逻辑
        // 注意这里 i_dst_stride 赋值为了 i_src_stride，因为实际上没有对输入的 dst 做任何修改，而是直接返回的 src，所以外面要正确取值，需要正确的 stride
        *i_dst_stride = i_src_stride;
        return src1;
    }
}

需要注意的是，我们获取的 16x16 的亚像素大小(16x16 分割)，结合上述的内存连续的特征，其中每个像素要么都是整像素，要么都是 H 半像素，要么都是 1/4 像素等，不存在混合。

7. 亚像素如何使用

我们获取亚像素一般用来在模式选择中计算 cost，注意一下当前待编码宏块没有亚像素的概念。
例如我们现在有一个给定的运动矢量，如何计算其 cost 呢，我们可以这么写代码(一个 16x16 分割的宏块)：

x264_mb_analysis_t a;
// 初始化 a
mb_analyse_load_costs(h, a);
// 新建运动搜索对象
x264_me_t m;
m.i_pixel = PIXEL_16x16;
// 载入当前待编码帧的宏块整像素
LOAD_FENC(&m, h->mb.pic.p_fenc, 0, 0);
// 参考帧序号
int i_ref = 0；
// 参考帧开销
m.i_ref_cost = REF_COST(0, i_ref);
// 加载参考帧像素指针
LOAD_HPELS(&m, h->mb.pic.p_fref[0][i_ref], 0, i_ref, 0, 0);
LOAD_WPELS(&m, h->mb.pic.p_fref_w[i_ref], 0, i_ref, 0, 0);
// 预测运动矢量
x264_mb_predict_mv_16x16(h, 0, i_ref, m.mvp);

// 给定的运动矢量
int mx = 0;
int my = 0;
// 16x16 中，bw, bh = 16
int bw = x264_pixel_size[m.i_pixel].w;
int bh = x264_pixel_size[m.i_pixel].h;
// get_ref() 输入参数中的 i_src_stride
int stride = m.i_stride[0];
// get_ref() 输入参数中的 dst
ALIGNED_ARRAY_32(pixel, pix, [16 * 16]);
// get_ref() 输入参数中的 i_dst_stride
intptr_t stride2 = 16;
// 调用 get_ref()
pixel* src = h->mc.get_ref(pix, &stride2, m.p_fref, stride, mx, my, bw, bh, &m.weight[0]);
// 待编码宏块像素
pixel* p_fenc = m.p_fenc[0];
// 计算残差 cost
m.cost = h->pixf.fpelcmp[m.i_pixel](p_fenc, FENC_STRIDE, src, stride2);
// 累加参考帧 cost
m.cost += m.i_ref_cost;
const uint16_t* p_cost_mvx = m.p_cost_mv - m.mvp[0];
const uint16_t* p_cost_mvy = m.p_cost_mv - m.mvp[1];
// 累加运动矢量 cost
m.cost += p_cost_mvx[mx] + p_cost_mvy[my];