理论知识：
两帧之间的物体运动是平移运动，位移量不是很很大，所以会以块作为单位分配运动矢量，在运动估计中采用了大量的参考帧预测来提高精度，当前的待编码块可以在缓存内的所有重建帧中寻找最优的匹配块进行运动补偿，以便很好的去除时间域的冗余度。为每一个块寻求一个运动矢量MV，并进行运动补偿预测编码。在每个分割区域中都有其对应的运动矢量，并对运动矢量以及块的选择方式进行编码和传输。运动估计ME所表达的运动矢量MV，其研究的内容就是如何加速，有效的获得足够精确的mv，并且把前一帧所得的运动信息通过运动补偿MC来进行变换，量化编码，最后输出。缩写含义：me得到的是mV预测得到的是mvp差值是mvdMV:运动向量,参考帧中相对于当前帧的偏移MVp:参考运动向量MVD：两个向量间的差别
提高运动估计算法的效率的主要技术有：初始搜索点的选择，匹配准则，和运动搜索策略。1.运动估计初始点的搜索：1）直接选择参考帧对应块的中心位置，这种方法简单，但容易陷入局部最优点，如果初始的步长太大，而原点（指待搜索块的中心点在参考帧中的相同位置的对应点）不是最优点时候，可能使快速搜索跳出原点周围的区域，而去搜索较远的点，导致搜索方向的不确定性，陷入局部最优。2）选择预测的起点，以预测点作为搜索的起点，x264采用的将运动估计矢量和参考帧的左边，上边和右上边的MB的中值MV作为起点进行ME。2. 匹配准则，x264中所采用的匹配准则是SAD，SATD. SAD 即绝对误差和，仅反映残差时域差异，影响PSNR值，不能有效反映码流的大小。SATD即将残差经哈德曼变换的4×4块的预测残差绝对值总和，可以将其看作简单的时频变换，其值在一定程度上可以反映生成码流的大小。因此，不用率失真最优化时，可将其作为模式选择的依据。 一般帧内要对所有的模式进行检测，帧内预测选用SATD.在做运动估计时，一般而言，离最优匹配点越远，匹配误差值SAD越大，这就是有名的单一平面假设，现有的运动估计快速算法大都利用该特性。但是，转换后 SATD值并不满足该条件，如果在整象素中运用SATD搜索，容易陷入局部最优点。而在亚象素中，待搜索点不多，各点处的SAD差异相对不大，可以用 SATD选择码流较少的匹配位置。3.运动搜索策略x264所采用的运动搜索策略（对应的最后面的程序中有描述）：#define X264_ME_DIA 0#define X264_ME_HEX 1#define X264_ME_UMH 2#define X264_ME_ESA 3#define X264_ME_TESA 4
下面就在x264中的运动估计所涉及的函数进行跟踪：ME的分析在函数x264_slice_write( x264_t *h )中的x264_macroblock_analyse( h );中：进入这个函数：由于对于I帧类型采用的帧内编码，这部分没有采用ME，所以对于I帧的分析略。进入帧间类型（P/B）的分析中：以P帧的16*16MB为例进行跟踪：进入函数：x264_mb_analyse_inter_p16x16( x264_t *h, x264_mb_analysis_t *a ){ //对参考帧中的所有16*16块进行分析for( i_ref = 0; i_ref < h->mb.pic.i_fref[0]; i_ref++ ){......./* search with ref */LOAD_HPELS( &m, h->mb.pic.p_fref[0][i_ref], 0, i_ref, 0, 0 );x264_mb_predict_mv_16x16( h, 0, i_ref, m.mvp );//下面的有详细的注释1x264_mb_predict_mv_ref16x16( h, 0, i_ref, mvc, &i_mvc );//注释2x264_me_search_ref( h, &m, mvc, i_mvc, p_halfpel_thresh );//注释3.......}
}
//注释1：进行16*16的块的mv预测，得到运动估计的起始方向，并将获得的MV赋值给MVP，在下一步中使用x264_mb_predict_mv_16x16( h, 0, i_ref, m.mvp );void x264_mb_predict_mv_16x16( x264_t *h, int i_list, int i_ref, int16_t mvp[2] ){int i_refa = h->mb.cache.ref[i_list][X264_SCAN8_0 - 1];//亮度左边块int16_t *mv_a = h->mb.cache.mv[i_list][X264_SCAN8_0 - 1];int i_refb = h->mb.cache.ref[i_list][X264_SCAN8_0 - 8];//亮度上边块int16_t *mv_b = h->mb.cache.mv[i_list][X264_SCAN8_0 - 8];int i_refc = h->mb.cache.ref[i_list][X264_SCAN8_0 - 8 + 4];//亮度的右上边块int16_t *mv_c = h->mb.cache.mv[i_list][X264_SCAN8_0 - 8 + 4];//当i_refc不存在时，就将i_refc赋值为左上边的块if( i_refc == -2 ){i_refc = h->mb.cache.ref[i_list][X264_SCAN8_0 - 8 - 1];mv_c = h->mb.cache.mv[i_list][X264_SCAN8_0 - 8 - 1];}//看i_efa/b/c是否是在参考帧所对应中的那一块，若是i_count++，i_count是用来进行Mvp预测选择何种方式的一种标志if( i_refa == i_ref ) i_count++;if( i_refb == i_ref ) i_count++;if( i_refc == i_ref ) i_count++;
if( i_count > 1 ){median:x264_median_mv( mvp, mv_a, mv_b, mv_c );}else if( i_count == 1 ){if( i_refa == i_ref )*(uint32_t*)mvp = *(uint32_t*)mv_a;else if( i_refb == i_ref )*(uint32_t*)mvp = *(uint32_t*)mv_b;else*(uint32_t*)mvp = *(uint32_t*)mv_c;}else if( i_refb == -2 && i_refc == -2 && i_refa != -2 )*(uint32_t*)mvp = *(uint32_t*)mv_a;elsegoto median;}}
//注释2：细化16*16块mv预测/* This just improves encoder performance, it's not part of the spec */x264_mb_predict_mv_ref16x16( h, 0, i_ref, mvc, &i_mvc );
void x264_mb_predict_mv_ref16x16( x264_t *h, int i_list, int i_ref, int16_t mvc[9][2], int *i_mvc ){//设运动补偿#define SET_MVP(mvp) { /*(uint32_t*)mvc[i] = *(uint32_t*)mvp; /i++; /}......//空间预测：获取左边，上边和左上的mb的mvc[i]，得到不同的类型的MVC，获得i个mvcif( h->mb.i_neighbour & MB_LEFT ){int i_mb_l = h->mb.i_mb_xy - 1;/* skip MBs didn't go through the whole search process, so mvr is undefined */if( !IS_SKIP( h->mb.type[i_mb_l] ) )SET_MVP( mvr[i_mb_l] );}if( h->mb.i_neighbour & MB_TOP ){int i_mb_t = h->mb.i_mb_top_xy;if( !IS_SKIP( h->mb.type[i_mb_t] ) )SET_MVP( mvr[i_mb_t] );
if( h->mb.i_neighbour & MB_TOPLEFT && !IS_SKIP( h->mb.type[i_mb_t - 1] ) )SET_MVP( mvr[i_mb_t-1] );if( h->mb.i_mb_x < h->mb.i_mb_stride - 1 && !IS_SKIP( h->mb.type[i_mb_t + 1] ) )SET_MVP( mvr[i_mb_t+1] );}//时间预测//dx,dy表示在时间差上的参考帧上对应点的坐标差#define SET_TMVP(dx, dy) { /int i_b4 = h->mb.i_b4_xy + dx*4 + dy*4*h->mb.i_b4_stride; /int i_b8 = h->mb.i_b8_xy + dx*2 + dy*2*h->mb.i_b8_stride; /int ref_col = l0->ref[0][i_b8]; /if( ref_col >= 0 ) /{ /int scale = (h->fdec->i_poc - h->fdec->ref_poc[0][i_ref]) * l0->inv_ref_poc[ref_col];/mvc[i][0] = (l0->mv[0][i_b4][0]*scale + 128) >> 8;/mvc[i][1] = (l0->mv[0][i_b4][1]*scale + 128) >> 8;/i++; /} /}}
//注释3x264_me_search_ref( h, &m, mvc, i_mvc, p_halfpel_thresh );void x264_me_search_ref( x264_t *h, x264_me_t *m, int16_t (*mvc)[2], int i_mvc, int *p_halfpel_thresh ){//初始化.......
bmx = x264_clip3( m->mvp[0], mv_x_min*4, mv_x_max*4 );bmy = x264_clip3( m->mvp[1], mv_y_min*4, mv_y_max*4 );//这些变量*4，或者左移2位，是因为要得到分数像素（1/4像素）pmx = ( bmx + 2 ) >> 2;pmy = ( bmy + 2 ) >> 2;bcost = COST_MAX;
/* try extra predictors if provided */if( h->mb.i_subpel_refine >= 3 ){uint32_t bmv = pack16to32_mask(bmx,bmy);COST_MV_HPEL( bmx, bmy ); //对COST_MV_HPEL目的：获得最佳cost的坐标for( i = 0; i < i_mvc; i++ ){if( *(uint32_t*)mvc[i] && (bmv - *(uint32_t*)mvc[i]) ){int mx = x264_clip3( mvc[i][0], mv_x_min*4, mv_x_max*4 );int my = x264_clip3( mvc[i][1], mv_y_min*4, mv_y_max*4 );COST_MV_HPEL( mx, my );}}bmx = ( bpred_mx + 2 ) >> 2;bmy = ( bpred_my + 2 ) >> 2;COST_MV( bmx, bmy );}else{/* check the MVP */COST_MV( pmx, pmy );bcost -= BITS_MVD( pmx, pmy );for( i = 0; i < i_mvc; i++ ){int mx = (mvc[i][0] + 2) >> 2;int my = (mvc[i][1] + 2) >> 2;if( (mx | my) && ((mx-bmx) | (my-bmy)) ){mx = x264_clip3( mx, mv_x_min, mv_x_max );my = x264_clip3( my, mv_y_min, mv_y_max );COST_MV( mx, my );}}}COST_MV( 0, 0 );
//下面是对me方式的选择switch语句：#define X264_ME_DIA 0#define X264_ME_HEX 1#define X264_ME_UMH 2#define X264_ME_ESA 3#define X264_ME_TESA 4//switch( h->mb.i_me_method )中的参数 h->mb.i_me_method = h->param.analyse.i_me_method;//根据用户的命令输入决定运动矢量的精度程度，根据空间相关性，用求出的左，上，左上的编码的宏块的//MV得到当前mb的mv的预测值mvp，以预测向量mvp的为初始原点，进行整数像素的搜索
case X264_ME_DIA://钻石形搜索：在do_while循环中，总是以一个菱形的形式进行搜索，只是原点发生变化，这个变化时有//bcost带来的，而坐标//原点是有bmx,bmy的变化来获得：//bmx,bmy的定义：bmx = x264_clip3( m->mvp[0], mv_x_min*4, mv_x_max*4 );bmy = x264_clip3( m->mvp[1], mv_y_min*4, mv_y_max*4 );
bcost <<= 4;//这里的左移是为了和(costs[0]<<4)+N对应do{//以bmx,bmy为基点在周围进行其四点的mv cost计算COST_MV_X4_DIR( 0,-1, 0,1, -1,0, 1,0, costs );COPY1_IF_LT( bcost, (costs[0]<<4)+1 );//cost左移了，还要再加N了,加N时为了区别是哪个点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) )//后4位进行检测，如果后4位是0，就是证明所进行比较的4点都是比原点要大，所以不需要继续搜索了break;bmx -= (bcost<<28)>>30;//为什么要这么麻烦的同时左移和右移了，何不直接除以4bmy -= (bcost<<30)>>30;bcost &= ~15;if( !CHECK_MVRANGE(bmx, bmy) )break;} while( ++i < i_me_range );........case X264_ME_HEX:六边形搜索+正方形细化，先进行六边形搜索，计算六个方向的矢量的cost，以最小者为起点，再进行正方形细化，搜索当前的最佳的mv的头的8个连结点的向量的cost，比较大小得到mv，过程和钻石形类似
case X264_ME_UMH:非对称十字多六边形网格搜索，具体的搜索步骤引用（http://bbs.chinavideo.org/viewthread.php?tid=7204&highlight=
