[关闭]
@snuffles 2015-10-20T15:56:13.000000Z 字数 8385 阅读 2067

整像素运动估计代码分析

大作业

作业三
1. 找出ITM软件中整像素运动估计模块代码，并对搜索过程做简要分析
2. 分析openCV全局运动代码，描述其过程

reference
UMHexagonS算法代码有自己的注释

  1. 整像素运动估计的函数的定义在fastme.c中
  2. 其中fastme.c包括整像素估计和分像素估计算法（Fast integer pel motion estimation and fractional pel motion estimation）。主要包括
    1. get_mem_FME() and free_mem_FME() are functions for allocation and release
      of memories about motion estimation
    2. FME_BlockMotionSearch() is the function for fast integer pel motion
      estimation and fractional pel motion estimation
    3. DefineThreshold() defined thresholds for early termination

  3. 其中整像素估计的算法是UMHexagonS算法。分为4个步骤
    1. 步骤一：起始搜索点的预测，五种预测模式求预测运动矢量
    （1）中值预测:利用空间相关性，取已求出的、当前帧的左、上、右上邻块的运动矢量的中间值；
    （2）原点预测：取原点处；
    （3）上层预测：采用从模式1（16*16）到模式7（4*4）的分级搜索顺序，将已求出的当前位置的上一级模式运动向量的作为当前模式的运动向量的预测值
    （4）对应块预测：将前一帧相应位置的运动向量作为当前块的运动向量的预测值;
    （5）相邻参考帧预测：利用时间相关性，将前面参考帧的运动向量按时间进行缩放。
    2. 步骤二：不甚满意区块搜索（对应代码里面first_step）
    （1）以最佳起始搜索点为中心，用非对称十字型搜索模板进行搜索，获得当前最佳点，判断此处是否属于满意或者很满意区，跳到相应的步骤三或步骤四，或继续搜索；
    （2）以当前最佳点为中心，在[-2,2]的方形区域（5*5）中进行全搜索，获得当前最佳点，判断是否属于满意或很满意区，跳到相应的步骤三或步骤四，或继续搜索；
    （3）用大六边形模板（16点）进行搜索，直至搜索到能符合相应阈值而进入步骤三或步骤四的点为止，否则也结束步骤二的搜索而进入步骤三。
    3. 步骤三：满意区的块搜索（对应代码里面sec_step）
    以当前最佳点为中心进行六边形搜索，直至最佳点为六边形中心。
    4. 步骤四：很满意区的搜索（对应代码里面third_step）
    以当前最佳点为中心进行菱形搜索，直至最佳点为菱形中心。

  4. 代码如下

  1. /*
  2. *************************************************************************
  3. * Function: FastIntegerPelBlockMotionSearch: fast pixel block motion search 
  4. this algrithm is called UMHexagonS which includes 
  5. four steps with different kinds of search patterns
  6. * Input:
  7. pel_t**   orig_pic,     // <--  original picture
  8. int       ref,          // <--  reference frame (0... or -1 (backward))
  9. int       pic_pix_x,    // <--  absolute x-coordinate of regarded AxB block
  10. int       pic_pix_y,    // <--  absolute y-coordinate of regarded AxB block
  11. int       blocktype,    // <--  block type (1-16x16 ... 7-4x4)
  12. int       pred_mv_x,    // <--  motion vector predictor (x) in sub-pel units
  13. int       pred_mv_y,    // <--  motion vector predictor (y) in sub-pel units
  14. int*      mv_x,         //  --> motion vector (x) - in pel units
  15. int*      mv_y,         //  --> motion vector (y) - in pel units
  16. int       search_range, // <--  1-d search range in pel units                         
  17. int       min_mcost,    // <--  minimum motion cost (cost for center or huge value)
  18. double    lambda        // <--  lagrangian parameter for determining motion cost
  19. * Output:
  20. * Return: 
  21. * Attention: in this function, three macro definitions is gives,
  22. SEARCH_ONE_PIXEL: search one pixel in search range
  23. SEARCH_ONE_PIXEL1(value_iAbort): search one pixel in search range,
  24. but give a parameter to show if mincost refeshed
  25. *************************************************************************
  1. int                                     //  ==> minimum motion cost after search
  2. FastIntegerPelBlockMotionSearch  (pel_t**   orig_pic,     // <--  not used
  3.                                   int       ref,          // <--  reference frame (0... or -1 (backward))
  4.                                   int       pic_pix_x,    // <--  absolute x-coordinate of regarded AxB block
  5.                                   int       pic_pix_y,    // <--  absolute y-coordinate of regarded AxB block
  6.                                   int       blocktype,    // <--  block type (1-16x16 ... 7-4x4)
  7.                                   int       pred_mv_x,    // <--  motion vector predictor (x) in sub-pel units
  8.                                   int       pred_mv_y,    // <--  motion vector predictor (y) in sub-pel units
  9.                                   int*      mv_x,         //  --> motion vector (x) - in pel units
  10.                                   int*      mv_y,         //  --> motion vector (y) - in pel units
  11.                                   int       search_range, // <--  1-d search range in pel units                         
  12.                                   int       min_mcost,    // <--  minimum motion cost (cost for center or huge value)
  13.                                   double    lambda)       // <--  lagrangian parameter for determining motion cost
  14. {
  15.   static int Diamond_x[4] = {-1, 0, 1, 0};
  16.   static int Diamond_y[4] = {0, 1, 0, -1};
  17.   static int Hexagon_x[6] = {2, 1, -1, -2, -1, 1};
  18.   static int Hexagon_y[6] = {0, -2, -2, 0,  2, 2};
  19.   static int Big_Hexagon_x[16] = {0,-2, -4,-4,-4, -4, -4, -2,  0,  2,  4,  4, 4, 4, 4, 2};
  20.   static int Big_Hexagon_y[16] = {4, 3, 2,  1, 0, -1, -2, -3, -4, -3, -2, -1, 0, 1, 2, 3};
  22.   int   pos, cand_x, cand_y,  mcost;
  23.   pel_t *(*get_ref_line)(int, pel_t*, int, int);
  24.   pel_t*  ref_pic       = img->type==B_IMG? Refbuf11 [ref+1] : Refbuf11[ref];
  25.   int   best_pos      = 0;                                        // position with minimum motion cost
  26.   int   max_pos       = (2*search_range+1)*(2*search_range+1);    // number of search positions
  27.   int   lambda_factor = LAMBDA_FACTOR (lambda);                   // factor for determining lagragian motion cost
  28.   int   mvshift       = 2;                  // motion vector shift for getting sub-pel units
  29.   int   blocksize_y   = input->blc_size[blocktype][1];            // vertical block size
  30.   int   blocksize_x   = input->blc_size[blocktype][0];            // horizontal block size
  31.   int   blocksize_x4  = blocksize_x >> 2;                         // horizontal block size in 4-pel units
  32.   int   pred_x        = (pic_pix_x << mvshift) + pred_mv_x;       // predicted position x (in sub-pel units)
  33.   int   pred_y        = (pic_pix_y << mvshift) + pred_mv_y;       // predicted position y (in sub-pel units)
  34.   int   center_x      = pic_pix_x + *mv_x;                        // center position x (in pel units)
  35.   int   center_y      = pic_pix_y + *mv_y;                        // center position y (in pel units)
  36.   int    best_x, best_y;
  37.   int   check_for_00  = (blocktype==1 && !input->rdopt && img->type!=B_IMG && ref==0);
  38.   int   search_step,iYMinNow, iXMinNow;
  39.   int   i,m, iSADLayer; 
  40.   int   iAbort;
  41.   float betaSec,betaThird;
  43.   int   height        = img->height;
  45.   //===== set function for getting reference picture lines =====
  46.   if ((center_x > search_range) && (center_x < img->width -1-search_range-blocksize_x) &&
  47.     (center_y > search_range) && (center_y < height-1-search_range-blocksize_y)   )
  48.   {
  49.     get_ref_line = FastLineX;
  50.   }
  51.   else
  52.   {
  53.     get_ref_line = UMVLineX;
  54.   }
  56.   memset(McostState[0],0,(2*search_range+1)*(2*search_range+1)*4);
  58.   ///////////////////////////////////////////////////////////////   
  59. #ifdef MRF_HYU
  60. #ifdef MRF_RAND_P
  61.   if(img->type == B_IMG && ref > 0)   
  62. #else
  63.   if((input->low_delay && img->type != INTER_IMG && ref>0)||(input->low_delay == 0 && ref > 0))   
  64. #endif
  65. #else
  66.   if(ref>0) 
  67. #endif 
  68.   {
  69.     if(pred_SAD_ref!=0)
  70.     {
  71.       betaSec = Bsize[blocktype]/(pred_SAD_ref*pred_SAD_ref)-AlphaSec[blocktype];
  72.       betaThird = Bsize[blocktype]/(pred_SAD_ref*pred_SAD_ref)-AlphaThird[blocktype];
  73.     }
  74.     else
  75.     {
  76.       betaSec = 0;
  77.       betaThird = 0;
  78.     }
  79.   }
  80.   else 
  81.   {
  82.     if(blocktype==1)
  83.     {
  84.       if(pred_SAD_space !=0)
  85.       {
  86.         betaSec = Bsize[blocktype]/(pred_SAD_space*pred_SAD_space)-AlphaSec[blocktype];
  87.         betaThird = Bsize[blocktype]/(pred_SAD_space*pred_SAD_space)-AlphaThird[blocktype];
  88.       }
  89.       else
  90.       {
  91.         betaSec = 0;
  92.         betaThird = 0;
  93.       }
  94.     }
  95.     else
  96.     {
  97.       if(pred_SAD_uplayer !=0)
  98.       {
  99.         betaSec = Bsize[blocktype]/(pred_SAD_uplayer*pred_SAD_uplayer)-AlphaSec[blocktype];
  100.         betaThird = Bsize[blocktype]/(pred_SAD_uplayer*pred_SAD_uplayer)-AlphaThird[blocktype];
  101.       }
  102.       else
  103.       {
  104.         betaSec = 0;
  105.         betaThird = 0;
  106.       }
  107.     }
  108.   }
  109.   /*****************************/
  111.   ////////////search around the predictor and (0,0)
  112.   //check the center median predictor
  113.   cand_x = center_x ;
  114.   cand_y = center_y ;
  115.   mcost = MV_COST (lambda_factor, mvshift, cand_x, cand_y, pred_x, pred_y);
  116.   mcost = PartCalMad(ref_pic, orig_pic, get_ref_line,blocksize_y,blocksize_x,blocksize_x4,mcost,min_mcost,cand_x,cand_y);
  117.   McostState[search_range][search_range] = mcost;
  118.   if (mcost < min_mcost)
  119.   {
  120.     min_mcost = mcost;
  121.     best_x = cand_x;
  122.     best_y = cand_y;
  123.   }
  125.   iXMinNow = best_x;
  126.   iYMinNow = best_y;
  127.   for (m = 0; m < 4; m++)
  128.   {     
  129.     cand_x = iXMinNow + Diamond_x[m];
  130.     cand_y = iYMinNow + Diamond_y[m];   
  131.     SEARCH_ONE_PIXEL
  132.   } 
  134.   if(center_x != pic_pix_x || center_y != pic_pix_y)
  135.   {
  136.     cand_x = pic_pix_x ;
  137.     cand_y = pic_pix_y ;
  138.     SEARCH_ONE_PIXEL
  140.       iXMinNow = best_x;
  141.     iYMinNow = best_y;
  142.     for (m = 0; m < 4; m++)
  143.     {       
  144.       cand_x = iXMinNow + Diamond_x[m];
  145.       cand_y = iYMinNow + Diamond_y[m];   
  146.       SEARCH_ONE_PIXEL
  147.     } 
  148.   }
  150.   if(blocktype>1)
  151.   {
  152.     cand_x = pic_pix_x + (pred_MV_uplayer[0]/4);
  153.     cand_y = pic_pix_y + (pred_MV_uplayer[1]/4);
  154.     SEARCH_ONE_PIXEL
  155.       if ((min_mcost-pred_SAD_uplayer)<pred_SAD_uplayer*betaThird)
  156.         goto third_step;
  157.       else if((min_mcost-pred_SAD_uplayer)<pred_SAD_uplayer*betaSec)
  158.         goto sec_step;
  159.   } 
  161.   //coordinate position prediction
  162.   if ((img->number > 1 + ref && ref!=-1) || (ref == -1 && Bframe_ctr > 1))
  163.   {
  164.     cand_x = pic_pix_x + pred_MV_time[0]/4;
  165.     cand_y = pic_pix_y + pred_MV_time[1]/4;
  166.     SEARCH_ONE_PIXEL
  167.   }
  169.   //prediciton using mV of last ref moiton vector
  170.   if ((ref > 0) || (img->type == B_IMG && ref == 0))
  171.   {
  172.     cand_x = pic_pix_x + pred_MV_ref[0]/4;
  173.     cand_y = pic_pix_y + pred_MV_ref[1]/4;
  174.     SEARCH_ONE_PIXEL
  175.   }
  176.   //strengthen local search
  177.   iXMinNow = best_x;
  178.   iYMinNow = best_y;
  179.   for (m = 0; m < 4; m++)
  180.   {     
  181.     cand_x = iXMinNow + Diamond_x[m];
  182.     cand_y = iYMinNow + Diamond_y[m];   
  183.     SEARCH_ONE_PIXEL
  184.   } 
  186.   EARLY_TERMINATION
  188.     if(blocktype>6)
  189.       goto sec_step;
  190.     else
  191.       goto first_step;
  193. first_step: //Unsymmetrical-cross search 
  194.   iXMinNow = best_x;
  195.   iYMinNow = best_y;
  197.   for(i=1;i<=search_range/2;i++)
  198.   {
  199.     search_step = 2*i - 1;
  200.     cand_x = iXMinNow + search_step;
  201.     cand_y = iYMinNow ;
  202.     SEARCH_ONE_PIXEL        
  203.       cand_x = iXMinNow - search_step;
  204.     cand_y = iYMinNow ;
  205.     SEARCH_ONE_PIXEL
  206.   }
  208.   for(i=1;i<=search_range/4;i++)
  209.   {
  210.     search_step = 2*i - 1;
  211.     cand_x = iXMinNow ;
  212.     cand_y = iYMinNow + search_step;
  213.     SEARCH_ONE_PIXEL
  214.       cand_x = iXMinNow ;
  215.     cand_y = iYMinNow - search_step;
  216.     SEARCH_ONE_PIXEL
  217.   }
  218.   EARLY_TERMINATION
  220.     iXMinNow = best_x;
  221.   iYMinNow = best_y;
  222.   // Uneven Multi-Hexagon-grid Search   
  223.   for(pos=1;pos<25;pos++)
  224.   {
  225.     cand_x = iXMinNow + spiral_search_x[pos];
  226.     cand_y = iYMinNow + spiral_search_y[pos];
  227.     SEARCH_ONE_PIXEL
  228.   }
  229.   EARLY_TERMINATION
  231.     for(i=1;i<=search_range/4; i++)
  232.     {
  233.       iAbort = 0;   
  234.       for (m = 0; m < 16; m++)
  235.       {
  236.         cand_x = iXMinNow + Big_Hexagon_x[m]*i;
  237.         cand_y = iYMinNow + Big_Hexagon_y[m]*i; 
  238.         SEARCH_ONE_PIXEL1(1)
  239.       }
  240.       if (iAbort)
  241.       { 
  243.         EARLY_TERMINATION
  244.       }
  245.     }
  246. sec_step:  //Extended Hexagon-based Search
  247.     iXMinNow = best_x;
  248.     iYMinNow = best_y;
  249.     for(i=0;i<search_range;i++) 
  250.     {
  251.       iAbort = 1;   
  252.       for (m = 0; m < 6; m++)
  253.       {     
  254.         cand_x = iXMinNow + Hexagon_x[m];
  255.         cand_y = iYMinNow + Hexagon_y[m];   
  256.         SEARCH_ONE_PIXEL1(0)
  257.       } 
  258.       if(iAbort)
  259.         break;
  260.       iXMinNow = best_x;
  261.       iYMinNow = best_y;
  262.     }
  263. third_step: // the third step with a small search pattern
  264.     iXMinNow = best_x;
  265.     iYMinNow = best_y;
  266.     for(i=0;i<search_range;i++) 
  267.     {
  268.       iSADLayer = 65536;
  269.       iAbort = 1;   
  270.       for (m = 0; m < 4; m++)
  271.       {     
  272.         cand_x = iXMinNow + Diamond_x[m];
  273.         cand_y = iYMinNow + Diamond_y[m];   
  274.         SEARCH_ONE_PIXEL1(0)
  275.       } 
  276.       if(iAbort)
  277.         break;
  278.       iXMinNow = best_x;
  279.       iYMinNow = best_y;
  280.     }
  282.     *mv_x = best_x - pic_pix_x;
  283.     *mv_y = best_y - pic_pix_y; 
  284.     return min_mcost;
  285. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注