（十）帧间编码3：运动估计之菱形搜索

上一篇文章简单介绍了5种运动搜索算法，现在介绍5种搜索算法中最简单的一种：菱形搜索。源码如下：

    switch( h->mb.i_me_method )
    {
        case X264_ME_DIA:
        {
            /* diamond search, radius 1 */
            bcost <<= 4;   //左移4位，因为bcost低四位将要存放代表上下左右位置的标志
            int i = i_me_range;
            do
            {
                COST_MV_X4_DIR( 0,-1, 0,1, -1,0, 1,0, costs );  //计算bmx,bmy像素点上下左右四个临近点的cost
                COPY1_IF_LT( bcost, (costs[0]<<4)+1 );  //若(costs[0]<<4)+1 小于bcost则将它赋给bcost
                COPY1_IF_LT( bcost, (costs[1]<<4)+3 );
                COPY1_IF_LT( bcost, (costs[2]<<4)+4 );
                COPY1_IF_LT( bcost, (costs[3]<<4)+12 );
                if( !(bcost&15) )   //若bmx,bmy像素点的上下左右的cost都不小于bcost，则退出搜索
                    break;
                
                bmx -= (bcost<<28)>>30;  //下一个搜索中心点是本次cost最小的像素点
                bmy -= (bcost<<30)>>30;  
                bcost &= ~15;
            } while( --i && CHECK_MVRANGE(bmx, bmy) );  //超过搜索范围也要退出
            bcost >>= 4;   //将bcost还原
            break;
        }
//省略...
  }

源码中bcost是记录待编码宏块与参考宏块之间的的差值，通常为sad（绝对误差和）或satd（hadamard变换后再绝对值求和）。菱形搜索是一个while循环，遍历以bmx, bmy为中心的上下左右四个方向的像素点对应的宏块，求出最小差值的一点，再以该点为中心继续遍历。最重要的操作是COST_MV_X4_DIR宏，代码如下：

#define COST_MV_X4_DIR( m0x, m0y, m1x, m1y, m2x, m2y, m3x, m3y, costs )\
{\
    pixel *pix_base = p_fref_w + bmx + bmy*stride;\
    h->pixf.fpelcmp_x4[i_pixel]( p_fenc,\
        pix_base + (m0x) + (m0y)*stride,\
        pix_base + (m1x) + (m1y)*stride,\
        pix_base + (m2x) + (m2y)*stride,\
        pix_base + (m3x) + (m3y)*stride,\
        stride, costs );\
    (costs)[0] += BITS_MVD( bmx+(m0x), bmy+(m0y) );\
    (costs)[1] += BITS_MVD( bmx+(m1x), bmy+(m1y) );\
    (costs)[2] += BITS_MVD( bmx+(m2x), bmy+(m2y) );\
    (costs)[3] += BITS_MVD( bmx+(m3x), bmy+(m3y) );\
}

在源码中，p_fenc代表的是待编码帧，p_fref_w代表的是参考帧，注意，运动估计，菱形搜索这些都是帧间编码才有的，而非帧内编码，千万不要搞混淆了，如下图：

菱形搜索00.png

h->pixf.fpelcmp_x4[i_pixel]是一个函数指针，它的c语言版本的实现如下：

static void x264_pixel_sad_x4_8x8( pixel *fenc, pixel *pix0, pixel *pix1,pixel *pix2, pixel *pix3,\
                                      intptr_t i_stride, int scores[4] )\
{\
    scores[0] = x264_pixel_sad_8x8( fenc, FENC_STRIDE, pix0, i_stride );\
    scores[1] = x264_pixel_sad_8x8( fenc, FENC_STRIDE, pix1, i_stride );\
    scores[2] = x264_pixel_sad_8x8( fenc, FENC_STRIDE, pix2, i_stride );\
    scores[3] = x264_pixel_sad_8x8( fenc, FENC_STRIDE, pix3, i_stride );\
}

x264_pixel_sad_8x8是计算两个8x8宏块的绝对误差和的函数，它的c语言版本是一个宏，大致实现如下：

static int x264_pixel_sad_8x8( pixel *pix1, intptr_t i_stride_pix1,  \
                 pixel *pix2, intptr_t i_stride_pix2 ) \
{                                                   \
    int i_sum = 0;                                  \
    for( int y = 0; y < 8; y++ )                   \
    {                                               \
        for( int x = 0; x < 8; x++ )               \
        {                                           \
            i_sum += abs( pix1[x] - pix2[x] );      \
        }                                           \
        pix1 += i_stride_pix1;                      \
        pix2 += i_stride_pix2;                      \
    }                                               \
    return i_sum;                                   \
}