fast_me.c

H.264 codec source code

                                  int       blocktype,    // <--  block type (1-16x16 ... 7-4x4)
                                  short     pred_mv_x,    // <--  motion vector predictor (x) in sub-pel units
                                  short     pred_mv_y,    // <--  motion vector predictor (y) in sub-pel units
                                  short*    mv_x,         //  --> motion vector (x) - in pel units
                                  short*    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)
                                  int       lambda_factor)       // <--  lagrangian parameter for determining motion cost
{
  int   pos, cand_x, cand_y,  mcost;
  int   list_offset   = ((img->MbaffFrameFlag)&&(img->mb_data[img->current_mb_nr].mb_field))? img->current_mb_nr%2 ? 4 : 2 : 0;

  int   mvshift       = 2;                  // motion vector shift for getting sub-pel units
  int   blocksize_y   = input->blc_size[blocktype][1];            // vertical block size
  int   blocksize_x   = input->blc_size[blocktype][0];            // horizontal block size
  int   blocksize_x4  = blocksize_x >> 2;                         // horizontal block size in 4-pel units
  int   pred_x        = (pic_pix_x << mvshift) + pred_mv_x;       // predicted position x (in sub-pel units)
  int   pred_y        = (pic_pix_y << mvshift) + 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   best_x = 0, best_y = 0;
  int   search_step,iYMinNow, iXMinNow;
  int   i,m,j; 
  float betaFourth_1,betaFourth_2;
  int	temp_Big_Hexagon_x[16];//  temp for Big_Hexagon_x;
  int	temp_Big_Hexagon_y[16];//  temp for Big_Hexagon_y; 
  short mb_x = pic_pix_x - img->opix_x; 
  short mb_y = pic_pix_y - img->opix_y;
  short pic_pix_x2 = pic_pix_x >> 2;
  short block_x = (mb_x >> 2);
  short block_y = (mb_y >> 2);
  int ET_Thred = Median_Pred_Thd_MB[blocktype];//ET threshold in use
  int   *SAD_prediction = fastme_best_cost[blocktype-1];//multi ref SAD prediction
  //===== Use weighted Reference for ME ====

  int  apply_weights = ( (active_pps->weighted_pred_flag && (img->type == P_SLICE || img->type == SP_SLICE)) ||
                         (active_pps->weighted_bipred_idc && (img->type == B_SLICE)));  
  height=((img->MbaffFrameFlag)&&(img->mb_data[img->current_mb_nr].mb_field))?img->height/2:img->height;
  ref_pic = (apply_weights && input->UseWeightedReferenceME) ? listX[list+list_offset][ref]->imgY_11_w : listX[list+list_offset][ref]->imgY_11;

  

  //===== set function for getting reference picture lines =====
  if ((center_x > search_range) && (center_x < img->width -1-search_range-blocksize_x) &&
    (center_y > search_range) && (center_y < height-1-search_range-blocksize_y)   )
  {
    get_ref_line = FastLineX;
  }
  else
  {
    get_ref_line = UMVLineX;
  }
  
  //////allocate memory for search state//////////////////////////
  memset(McostState[0],0,(2*input->search_range+1)*(2*input->search_range+1));


  //check the center median predictor
  cand_x = center_x ;
  cand_y = center_y ;
  mcost = MV_COST (lambda_factor, mvshift, cand_x, cand_y, pred_x, pred_y);
  mcost = PartCalMad(ref_pic, orig_pic, get_ref_line,blocksize_y,blocksize_x,blocksize_x4,mcost,min_mcost,cand_x,cand_y);
  McostState[search_range][search_range] = 1;
  if (mcost < min_mcost)
  {
    min_mcost = mcost;
    best_x = cand_x;
    best_y = cand_y;
  }

  iXMinNow = best_x;
  iYMinNow = best_y;
  for (m = 0; m < 4; m++)
  {   
    cand_x = iXMinNow + Diamond_x[m];
    cand_y = iYMinNow + Diamond_y[m];   
    SEARCH_ONE_PIXEL
  } 

  if(center_x != pic_pix_x || center_y != pic_pix_y)
  {
    cand_x = pic_pix_x ;
    cand_y = pic_pix_y ;
    SEARCH_ONE_PIXEL

    iXMinNow = best_x;
    iYMinNow = best_y;
    for (m = 0; m < 4; m++)
    {   
      cand_x = iXMinNow + Diamond_x[m];
      cand_y = iYMinNow + Diamond_y[m];   
      SEARCH_ONE_PIXEL
    } 
  }
/***********************************init process*************************/
//for multi ref
  if(ref>0 && img->structure == FRAME  && min_mcost > ET_Thred && SAD_prediction[pic_pix_x2]<Multi_Ref_Thd_MB[blocktype])
	goto terminate_step;

//ET_Thd1: early termination for low motion case
  if( min_mcost < ET_Thred)	
  {
    goto terminate_step;
  }
  else // hybrid search for main search loop
  {
/****************************(MV and SAD prediction)********************************/
    setup_FME(ref, list, block_y, block_x, blocktype, img->all_mv );
	ET_Thred = Big_Hexagon_Thd_MB[blocktype];  // ET_Thd2: early termination Threshold for strong motion



	// Threshold defined for EARLY_TERMINATION 
	  if (pred_SAD == 0) 
	  {
		betaFourth_1=0;
		betaFourth_2=0;
	  }
	  else
	  {
		betaFourth_1 = Bsize[blocktype]/(pred_SAD*pred_SAD)-AlphaFourth_1[blocktype];
		betaFourth_2 = Bsize[blocktype]/(pred_SAD*pred_SAD)-AlphaFourth_2[blocktype];
 
	  }  
/*********************************************end of init ***********************************************/
  }  
// first_step: initial start point prediction 

    if(blocktype>1)
  {
    cand_x = pic_pix_x + (pred_MV_uplayer[0]/4);
    cand_y = pic_pix_y + (pred_MV_uplayer[1]/4);
    SEARCH_ONE_PIXEL
  } 


  //prediciton using mV of last ref moiton vector
 if(pred_MV_ref_flag == 1)	  			//Notes: for interlace case, ref==1 should be added
  {
      cand_x = pic_pix_x + (pred_MV_ref[0]/4);
      cand_y = pic_pix_y + (pred_MV_ref[1]/4);
      SEARCH_ONE_PIXEL
  }
  //small local search
  iXMinNow = best_x;
  iYMinNow = best_y;
  for (m = 0; m < 4; m++)
  {   
    cand_x = iXMinNow + Diamond_x[m];
    cand_y = iYMinNow + Diamond_y[m];   
    SEARCH_ONE_PIXEL
  } 

  //early termination alogrithm, refer to JVT-G016
    EARLY_TERMINATION
  
  if(blocktype>6)
    goto fourth_1_step;
  else
    goto sec_step;
  
sec_step: //Unsymmetrical-cross search 
  iXMinNow = best_x;
  iYMinNow = best_y;
  
  for(i = 1; i < search_range; i+=2)
  {
    search_step = i;
    cand_x = iXMinNow + search_step;
    cand_y = iYMinNow ;
    SEARCH_ONE_PIXEL    
    cand_x = iXMinNow - search_step;
    cand_y = iYMinNow ;
    SEARCH_ONE_PIXEL
  }
  for(i = 1; i < (search_range/2);i+=2)
  {
    search_step = i;
    cand_x = iXMinNow ;
    cand_y = iYMinNow + search_step;
    SEARCH_ONE_PIXEL
    cand_x = iXMinNow ;
    cand_y = iYMinNow - search_step;
    SEARCH_ONE_PIXEL
  }


  //early termination alogrithm, refer to JVT-G016
    EARLY_TERMINATION
  
  iXMinNow = best_x;
  iYMinNow = best_y;

//third_step:    // Uneven Multi-Hexagon-grid Search 
//sub step 1: 5x5 squre search
  for(pos=1;pos<25;pos++)
  {
    cand_x = iXMinNow + spiral_search_x[pos];
    cand_y = iYMinNow + spiral_search_y[pos];
    SEARCH_ONE_PIXEL
  }

  //early termination alogrithm, refer to JVT-G016
  EARLY_TERMINATION

//sub step 2:  Multi-Hexagon-grid search
  memcpy(temp_Big_Hexagon_x,Big_Hexagon_x,64);
  memcpy(temp_Big_Hexagon_y,Big_Hexagon_y,64);      
  for(i=1;i<=(search_range/4); i++)
  {

    for (m = 0; m < 16; m++)
    {
      cand_x = iXMinNow + temp_Big_Hexagon_x[m];
      cand_y = iYMinNow + temp_Big_Hexagon_y[m];
	  temp_Big_Hexagon_x[m] += Big_Hexagon_x[m];
	  temp_Big_Hexagon_y[m] += Big_Hexagon_y[m];	

      SEARCH_ONE_PIXEL
    }
// ET_Thd2: early termination Threshold for strong motion
	if(min_mcost < ET_Thred)
	{
	  goto terminate_step;
	}
  }


//fourth_step:  //Extended Hexagon-based Search
// the fourth step with a small search pattern
fourth_1_step:  //sub step 1: small Hexagon search
      for(i=0; i < search_range; i++) //change into 1/2
      {
        iXMinNow = best_x;
        iYMinNow = best_y;
        for (m = 0; m < 6; m++)
        {   
          cand_x = iXMinNow + Hexagon_x[m];
          cand_y = iYMinNow + Hexagon_y[m];   
          SEARCH_ONE_PIXEL

        } 
        if(best_x == iXMinNow && best_y == iYMinNow)
            break;
      }
fourth_2_step: //sub step 2: small Diamond search

      for(i = 0; i < search_range; i++) //change into 1/2
      {
	    iXMinNow = best_x;
	    iYMinNow = best_y;
        for (m = 0; m < 4; m++)
        {   
          cand_x = iXMinNow + Diamond_x[m];
          cand_y = iYMinNow + Diamond_y[m];   
          SEARCH_ONE_PIXEL

        } 
        if(best_x == iXMinNow && best_y == iYMinNow)
            break;
      }

terminate_step:
	  
// store SAD infomation for prediction	  
    //FAST MOTION ESTIMATION. ZHIBO CHEN 2003.3
	  for (i=0; i < (blocksize_x>>2); i++)
	  {
	    for (j=0; j < (blocksize_y>>2); j++)
		{
		  if(list == 0) 
		  {
		    fastme_ref_cost[ref][blocktype][block_y+j][block_x+i] = min_mcost;
		    if (ref==0)
			  fastme_l0_cost[blocktype][(img->pix_y>>2)+block_y+j][(img->pix_x>>2)+block_x+i] = min_mcost;
		  }
		  else
		  {
		    fastme_l1_cost[blocktype][(img->pix_y>>2)+block_y+j][(img->pix_x>>2)+block_x+i] = min_mcost;
		  }
		}
	  }
//for multi ref SAD prediction
	  if ((ref==0) || (SAD_prediction[pic_pix_x2] > min_mcost))
		SAD_prediction[pic_pix_x2] = min_mcost;

      *mv_x = best_x - pic_pix_x;
      *mv_y = best_y - pic_pix_y; 
      return min_mcost;
}


  /*!
 ************************************************************************
 * \brief
 * Functions for fast fractional pel motion estimation.
 * 1. int AddUpSADQuarter() returns SADT of a fractiona pel MV
 * 2. int FastSubPelBlockMotionSearch () proceed the fast fractional pel ME
 * \authors  
 *    Zhibo Chen
 *    Dept.of EE, Tsinghua Univ.
 * \date 
 *    2003.4
 ************************************************************************
 */
int AddUpSADQuarter(int pic_pix_x,int pic_pix_y,int blocksize_x,int blocksize_y,
                    int cand_mv_x,int cand_mv_y, StorablePicture *ref_picture, pel_t**   orig_pic, 
                    int Mvmcost, int min_mcost,int useABT, int blocktype)
{

  int j, i, k;  
  int diff[16], *d; 
  int mcost = Mvmcost;
  int c_diff[MB_PIXELS];
  int y_offset, ypels =(128 - 64 * (blocktype == 3));
  int ry0, ry4, ry8, ry12;
  int y0, y1, y2, y3;
  int x0, x1, x2, x3;
  int abort_search, rx0; 
  int img_width  = ((ref_picture->size_x + 2*IMG_PAD_SIZE - 1)<<2);
  int img_height = ((ref_picture->size_y + 2*IMG_PAD_SIZE - 1)<<2);

  //===== Use weighted Reference for ME ====
  pel_t **ref_pic;      
  pel_t *ref_line;
  pel_t *orig_line;
  int  apply_weights = ( (active_pps->weighted_pred_flag && (img->type == P_SLICE || img->type == SP_SLICE)) ||
                         (active_pps->weighted_bipred_idc && (img->type == B_SLICE)));  
  
  if (apply_weights && input->UseWeightedReferenceME)
  {
    ref_pic = ref_picture->imgY_ups_w;
  }
  else
    ref_pic = ref_picture->imgY_ups;
  ///////////////////////////////////////////

  
  for (y0=0, abort_search=0; y0<blocksize_y && !abort_search; y0+=4)
  {
    y_offset = (y0>7)*ypels;
    ry0  = (y0<<2) + cand_mv_y;
    ry4  = ry0 + 4;
    ry8  = ry4 + 4;
    ry12 = ry8 + 4;
    y1 = y0 + 1;
    y2 = y1 + 1;
    y3 = y2 + 1;


    for (x0=0; x0<blocksize_x; x0+=4)
    {
        rx0 = (x0<<2) + cand_mv_x;
        x1  = x0 + 1;