h.264全搜索以及快速全搜索算法

Full Search

全搜索算法是最简单暴力的一种搜索算法，对搜索范围内的所有像素点都进行匹配对比，选出最合适的运动向量，以下就是一个搜索范围为4的全搜索范围（单个像素点）

/*!
 ***********************************************************************
 * \brief按照螺旋搜索顺序进行全搜索
 *    Full pixel block motion search
 *    目标是得到(mv_x,mv_y)和min_mcost，(mv_x,mv_y)指示从哪里开始做分像素搜索，search center
 *    后者用来跟分像素搜索结果做比较
 ***********************************************************************
 */
int                                               //  ==> minimum motion cost after search
FullPelBlockMotionSearch (pel_t**   orig_pic,     // <--  original pixel values for the AxB block
                          int       ref,          // <--  reference frame (0... or -1 (backward))
                          int       list,
                          int       pic_pix_x,    // <--  absolute x-coordinate of regarded AxB blockAxB宏块原点在图像中的绝对坐标
                          int       pic_pix_y,    // <--  absolute y-coordinate of regarded AxB block
                          int       blocktype,    // <--  block type (1-16x16 ... 7-4x4)
                          int       pred_mv_x,    // <--  motion vector predictor (x) in sub-pel units
                          int       pred_mv_y,    // <--  motion vector predictor (y) in sub-pel units
                          int*      mv_x,         // <--> in: search center (x) / out: motion vector (x) - in pel units
                          int*      mv_y,         // <--> in: search center (y) / out: motion vector (y) - in pel units
                          int       search_range, // <--  1-d search range in pel units
                          int       min_mcost,    // <--  minimum motion cost (cost for center or huge value)
                          double    lambda)       // <--  lagrangian parameter for determining motion cost
{
  int   pos, cand_x, cand_y, y, x4, mcost;

  pel_t *orig_line, *ref_line;
  pel_t *(*get_ref_line)(int, pel_t*, int, int, int, int);//
//参考帧偏移量 帧场自适应且宏块地址为偶数=4 帧场自适应宏块地址为奇数=2 非帧场自适应=0
  int   list_offset   = ((img->MbaffFrameFlag)&&(img->mb_data[img->current_mb_nr].mb_field))? img->current_mb_nr% ?  :  : ;
  pel_t *ref_pic            = listX[list+list_offset][ref]->imgY_11;
  int   img_width     = listX[list+list_offset][ref]->size_x;
  int   img_height    = listX[list+list_offset][ref]->size_y;

  int   best_pos      = ;                                        // position with minimum motion cost
  //计算最大需要搜索的位置个数
  int   max_pos       = (*search_range+)*(*search_range+);    // number of search positions
  int   lambda_factor = LAMBDA_FACTOR (lambda);                   // factor for determining lagragian motion cost
  int   blocksize_y   = input->blc_size[blocktype][];            // vertical block size
  int   blocksize_x   = input->blc_size[blocktype][];            // horizontal block size
  int   blocksize_x4  = blocksize_x >> ;                         // horizontal block size in 4-pel units
  int   pred_x        = (pic_pix_x << ) + pred_mv_x;       // predicted position x (in sub-pel units)1/4子像素为单位的预测MV
  int   pred_y        = (pic_pix_y << ) + pred_mv_y;       // predicted position y (in sub-pel units)
  int   center_x      = pic_pix_x + *mv_x;                        // center position x (in pel units)
  int   center_y      = pic_pix_y + *mv_y;                        // center position y (in pel units)
  int   check_for_00  = (blocktype== && !input->rdopt && img->type!=B_SLICE && ref==);

  //===== set function for getting reference picture lines =====
  //通过判断搜索范围会不会出界，设置获取参考像素值的函数
  if ((center_x > search_range) && (center_x < img->width --search_range-blocksize_x) &&
      (center_y > search_range) && (center_y < img->height--search_range-blocksize_y)   )
  {
     get_ref_line = FastLineX;//未出界
  }
  else
  {
     get_ref_line = UMVLineX;//出界
  }

  //===== loop over all search positions =====
  //max_pos是搜索位置的个数,计算见上面
  for (pos=; pos<max_pos; pos++)
  {
    //--- set candidate position (absolute position in pel units) ---
    /*(center_x,center_y)是由预测MV估计出来的搜索中心，在以它为中心的范围内，
    对按照螺旋形顺序排列的候选点进行搜索，
    每个候选点都是一个可能参考块的左上角起始点
  */
    cand_x = center_x + spiral_search_x[pos];//螺旋搜索
    cand_y = center_y + spiral_search_y[pos];

    //--- initialize motion cost (cost for motion vector) and check ---
    //计算MVD的代价，换算成四分之一像素(cand--candidate候选点)
    mcost = MV_COST (lambda_factor, , cand_x, cand_y, pred_x, pred_y);
    if (check_for_00 && cand_x==pic_pix_x && cand_y==pic_pix_y)
    {//螺旋搜索到的点为原点,不过为什么是减去16bit?
      mcost -= WEIGHTED_COST (lambda_factor, );
    }
    //如果只是MV的代价就已经大于现有的最小代价就舍弃
    if (mcost >= min_mcost)   continue;

    //--- add residual cost to motion cost ---
    //blocksize_y blocksize_x4 是分块大小16x16 16x8 8x16......
    for (y=; y<blocksize_y; y++)
    {
      //(cand_x,cand_y+y)是一行的起始坐标，y++ 遍历每一行
      ref_line  = get_ref_line (blocksize_x, ref_pic, cand_y+y, cand_x, img_height, img_width);
      orig_line = orig_pic [y];
      //计算当前帧和参考帧的像素残差
      for (x4=; x4<blocksize_x4; x4++) //以4个为一组计算
      {
        mcost += byte_abs[ *orig_line++ - *ref_line++ ];
        mcost += byte_abs[ *orig_line++ - *ref_line++ ];
        mcost += byte_abs[ *orig_line++ - *ref_line++ ];
        mcost += byte_abs[ *orig_line++ - *ref_line++ ];
      }

      if (mcost >= min_mcost)  //如果已经比最小代价大，就没必要计算下面的行了
      {
        break;
      }
    }

    //--- check if motion cost is less than minimum cost ---
    //记录下最小代价和最佳匹配位置
    if (mcost < min_mcost)
    {
      best_pos  = pos;
      min_mcost = mcost;
    }
  }

  //===== set best motion vector and return minimum motion cost =====
  if (best_pos)
  {
    *mv_x += spiral_search_x[best_pos];  //因为螺旋搜索数组中记录的是该位置的点
    *mv_y += spiral_search_y[best_pos];  //与(center_x,center_y)的差
  }
  return min_mcost;  //返回最小代价
}

//螺旋搜索（全搜索）位置初始化
 for (k=, l=; l<=max(,search_range); l++)
  {
    for (i=-l+; i< l; i++)
    {
      spiral_search_x[k] =  i;  spiral_search_y[k++] = -l;
      spiral_search_x[k] =  i;  spiral_search_y[k++] =  l;
      /*
       *
       *                         9  3 5 7 10
       *          1 0 2          11 1 0 2 12
       *                         13 4 6 8 14
       *
       */
    }
    for (i=-l;   i<=l; i++)
    {
      spiral_search_x[k] = -l;  spiral_search_y[k++] =  i;
      spiral_search_x[k] =  l;  spiral_search_y[k++] =  i;
      /*                             15 17 19  21 23
       *         3 5 7                9  3  5  7  10
       *         1 0 2               11  1  0  2  12
       *         4 6 8               13  4  6  8  14
       *                             16 18 20 22  24
       */
    }
  }

Fast Full Search

由于运动搜索时有多种块的类型（16x16,8x16,8x8,4x4等）因此，在全搜索时，会由于位置重叠而产生同一处的像素残差多次计算的情况，为了避免这种情况，可以一次性把搜索范围内的所有像素残差计算出来，不同块类型只需要把残差进行组合即可得到该类型的SAD

/*!
 ***********************************************************************
 * \brief快速正像素搜索
 *    Fast Full pixel block motion search
 *    目标是得到(mv_x,mv_y)和min_mcost，(mv_x,mv_y)指示从哪里开始做分像素搜索，search center
 *    后者用来跟分像素搜索结果做比较
 ***********************************************************************
 */
int                                                   //  ==> minimum motion cost after search
FastFullPelBlockMotionSearch (pel_t**   orig_pic,     // <--  not used
                              int       ref,          // <--  reference frame (0... or -1 (backward))
                              int       list,
                              int       pic_pix_x,    // <--  absolute x-coordinate of regarded AxB block
                              int       pic_pix_y,    // <--  absolute y-coordinate of regarded AxB block
                              int       blocktype,    // <--  block type (1-16x16 ... 7-4x4)
                              int       pred_mv_x,    // <--  motion vector predictor (x) in sub-pel units
                              int       pred_mv_y,    // <--  motion vector predictor (y) in sub-pel units
                              int*      mv_x,         //  --> motion vector (x) - in pel units
                              int*      mv_y,         //  --> motion vector (y) - in pel units
                              int       search_range, // <--  1-d search range in pel units
                              int       min_mcost,    // <--  minimum motion cost (cost for center or huge value)
                              double    lambda)       // <--  lagrangian parameter for determining motion cost
{
  int   pos, offset_x, offset_y, cand_x, cand_y, mcost;

  int   max_pos       = (*search_range+)*(*search_range+);              // number of search positions
  int   lambda_factor = LAMBDA_FACTOR (lambda);                             // factor for determining lagragian motion cost
  int   best_pos      = ;                                                  // position with minimum motion cost
  int   block_index;                                                        // block index for indexing SAD array
  int*  block_sad;                                                          // pointer to SAD array

  block_index   = (pic_pix_y-img->opix_y)+((pic_pix_x-img->opix_x)>>); // block index for indexing SAD array
  block_sad     = BlockSAD[list][ref][blocktype][block_index];         // pointer to SAD array

  //===== set up fast full integer search if needed / set search center =====
  if (!search_setup_done[list][ref])//对一个参考帧只做一次
  {
    //计算搜索范围所有位置所有分块模式的SAD(整像素)
    SetupFastFullPelSearch (ref, list);
  }

  offset_x = search_center_x[list][ref] - img->opix_x; //搜索中心相对原宏块的偏移
  offset_y = search_center_y[list][ref] - img->opix_y;

  //===== cost for (0,0)-vector: it is done before, because MVCost can be negative =====
  //原点(这里的原点都是是当前块所在的位置)
  if (!input->rdopt)
  {
    //把刚才计算的SAD 跟mv代价相加得到总代价
    mcost = block_sad[pos_00[list][ref]] + MV_COST (lambda_factor, , , , pred_mv_x, pred_mv_y);
    if (mcost < min_mcost)
    {
      min_mcost = mcost;
      best_pos  = pos_00[list][ref];//每帧搜索中心的位置
    }
  }

  //===== loop over all search positions =====
  for (pos=; pos<max_pos; pos++, block_sad++)
  {
    //--- check residual cost ---
    if (*block_sad < min_mcost)
    {
      //--- get motion vector cost ---
      //计算出搜索位置，按照螺旋形顺序spiral_search_xy
      cand_x = offset_x + spiral_search_x[pos];
      cand_y = offset_y + spiral_search_y[pos];
      mcost  = *block_sad;//在SetupFastFullPelSearch已经做好
      mcost += MV_COST (lambda_factor, , cand_x, cand_y, pred_mv_x, pred_mv_y);    //计算 MV 代价

      //--- check motion cost ---
      if (mcost < min_mcost)
      {
        min_mcost = mcost;
        best_pos  = pos;
      }
    }
  }

  //===== set best motion vector and return minimum motion cost =====
  *mv_x = offset_x + spiral_search_x[best_pos];//根据代价最小，计算出最佳MV
  *mv_y = offset_y + spiral_search_y[best_pos];
  return min_mcost;
}

Edge Process

通常来说，计算SAD是以一行一行为单位进行，不过在进行搜索时，难免会有运动向量指向图像外的区域，图像以外的这些区域的像素取值为图像边界的值，即

$Pic[x,y]=\left\{\begin{matrix}
Pic[0,y] & x<0\\
Pic[width-1,y] & x\geq width\\
Pic[x,0] & 0\leq x < width,y<0\\
Pic[x,height-1] & 0\leq x < width,y \geq height\\
Pic[x,y] & other
\end{matrix}\right.$

/*如果参考块超出参考帧边界，用边界值进行填充*/
pel_t *UMVLineX (int size, pel_t* Pic, int y, int x, int height, int width)
{
  int i, maxx;
  pel_t *Picy;

  Picy = Pic + max(,min(height-,y)) * width;  //先把y范围限制在(0,height-1)内

  if (x < )                            // Left edge
  {
    maxx = min(,x+size);   //搜索范围可以大于16的，所以x+16是可以小于0的
    for (i = x; i < maxx; i++)  //把出界的部分都赋值为边界上的值，一画图就理解了
    {
      line[i-x] = Picy [];             // Replicate left edge pixel
    }
    maxx = x+size;                         //把没出界的像素也拷贝到line数组中
    for (i = ; i < maxx; i++)          // Copy non-edge pixels
      line[i-x] = Picy [i];
  }
  else if (x > width-size)         // Right edge  同理
  {
    maxx = width;
    for (i = x; i < maxx; i++)
    {
      line[i-x] = Picy [i];             // Copy non-edge pixels
    }
    maxx = x+size;
    for (i = max(width,x); i < maxx; i++)
    {
      line[i-x] = Picy [width-];  // Replicate right edge pixel
    }
  }
  else                                  // No edge  ，则返回y行x列的地址
  {
    return Picy + x;
  }

  return line;    //否则，返回line数组的地址
}