search.c

运动估计

      op.c+=1;
#endif
      if(b2[i]->mae<(*err)){
         m=x+b2[i]->mv.x;
         n=y+b2[i]->mv.y;
         terr=mean_abs_err(cur,prev,x,y,m,n,BLOCK_WIDTH,BLOCK_HEIGHT);
#ifdef OPC
         op.c+=1;
#endif
         if(terr<(*err)){
            *err=terr;
            mv=b2[i]->mv;
         }
      }
   }
#ifdef OPC
   op.c-=2;   /* The first MAD needs no comparison */
#endif
   return mv;
}

MV three_step_search(u_char *prev,u_char *cur, int x, int y, int *err)
{
   int cx,cy;
   int step_size=cint(MAX_DISP)>>1;
   MV mv,tmv;
   *err=mean_abs_err(cur,prev,x,y,x,y,BLOCK_WIDTH,BLOCK_HEIGHT);
   spt++;
   mv.x=mv.y=0;
   cx=x;
   cy=y;
   while(step_size>=1){
      tmv=cir_search(prev,cur,cx,cy,x,y,err,0,8,step_size);
      spt+=8;
      mv.x+=tmv.x;
      mv.y+=tmv.y;
      cx+=tmv.x;
      cy+=tmv.y;
      step_size=step_size>>1;
   }
   return mv;
}

MV new_three_step_search(u_char *prev,u_char *cur, int x, int y, int *err)
{
   int cx,cy,err1,err2;
   int step_size=cint(MAX_DISP)>>1;
   MV mv,tmv,tmv1;
   mv.x=mv.y=0;
   cx=x;
   cy=y;
   *err=mean_abs_err(cur,prev,x,y,x,y,BLOCK_WIDTH,BLOCK_HEIGHT);
   spt++;
   err1=err2=(*err);
   tmv1=cir_search(prev,cur,cx,cy,x,y,&err1,0,8,1);
   tmv=cir_search(prev,cur,cx,cy,x,y,&err2,0,8,step_size);
   spt+=16;
   if(tmv.x==0 && tmv.y==0 && tmv1.x==0 && tmv1.y==0)
      return mv;
   if(err1<=err2){
      step_size=1;
      *err=err1;
      tmv=tmv1;
      mv.x+=tmv.x;
      mv.y+=tmv.y;
      cx+=tmv.x;
      cy+=tmv.y;
      if(abs(tmv.x)==abs(tmv.y)){
         tmv=cir_search(prev,cur,cx,cy,x,y,err,mvmap[tmv.y+1][tmv.x+1],5,step_size);
         spt+=5;
      }
      else{
         tmv=cir_search(prev,cur,cx,cy,x,y,err,mvmap[tmv.y+1][tmv.x+1],3,step_size);
         spt+=3;
      }
      mv.x+=tmv.x;
      mv.y+=tmv.y;
      return mv;
   }
   step_size=step_size>>1;
   *err=err2;
   mv.x+=tmv.x;
   mv.y+=tmv.y;
   cx+=tmv.x;
   cy+=tmv.y;
   while(step_size>=1){
      tmv=cir_search(prev,cur,cx,cy,x,y,err,0,8,step_size);
      spt+=8;
      mv.x+=tmv.x;
      mv.y+=tmv.y;
      cx+=tmv.x;
      cy+=tmv.y;
      step_size=step_size>>1;
   }
   return mv;
}

MV four_step_search(u_char *prev,u_char *cur, int x, int y, int *err)
{
   int cx,cy,dx=0,dy=0;
   int step=1,step_size=cint(MAX_DISP)>>2;
   MV mv,tmv1,tmv2;
   *err=mean_abs_err(cur,prev,x,y,x,y,BLOCK_WIDTH,BLOCK_HEIGHT); 
   /* *err=npd_mean_abs_err(cur,prev,x,y,x,y,BLOCK_WIDTH,BLOCK_HEIGHT,MAX_INT); */
   spt++;
   cx=x;
   cy=y;
   tmv1.x=0;
   tmv1.y=0;
   tmv2=tmv1;
   while(step_size>=1){
      if((step==1)||(abs(cx-x)>MAX_DISP-step_size)||\
           (abs(cy-y)>MAX_DISP-step_size)){
         tmv2=cir_search(prev,cur,cx,cy,x,y,err,0,8,step_size);
         spt+=8;
      }
      else{
         if(abs(tmv1.x)==abs(tmv1.y)){
            tmv2=cir_search(prev,cur,cx,cy,x,y,err,\
                 mvmap[dy+1][dx+1],5,step_size);
            if((abs(tmv1.x)==abs(tmv1.y))&&(((tmv1.x+tmv2.x)==0)\
                 ||((tmv1.y+tmv2.y)==0))&&step==3)
               spt+=4;
            else
               spt+=5;
         }
         else{
            tmv2=cir_search(prev,cur,cx,cy,x,y,err,\
                      mvmap[dy+1][dx+1],3,step_size);
            spt+=3;
         }
      }
      cx+=tmv2.x;
      cy+=tmv2.y;
      dx=tmv2.x/step_size;
      dy=tmv2.y/step_size;
      tmv1=tmv2;
      if(step_size==1||step==3||(tmv2.x==0&&tmv2.y==0)){
         step_size=step_size>>1;
         step=1;
      }
      else
         step++;
   }
      mv.x=cx-x;
      mv.y=cy-y;
      return mv;
}


MV bbgd_search(u_char *prev, u_char *cur, int x, int y, int *err)
{
   int cx,cy;
   MV mv,tmv1,tmv2,tmv3;
   *err=mean_abs_err(cur,prev,x,y,x,y,BLOCK_WIDTH,BLOCK_HEIGHT);
   mv.x=mv.y=0;
   cx=x;
   cy=y;
   /* step 1 */
   tmv1=cir_search(prev,cur,cx,cy,x,y,err,0,8,1);
   spt+=9;
   if(tmv1.x==0 && tmv1.y==0)
       return tmv1;
   else{
      cx+=tmv1.x;
      cy+=tmv1.y;
   }
   /* step 2 */
   if(abs(tmv1.x)==abs(tmv1.y)){
      tmv2=cir_search(prev,cur,cx,cy,x,y,err,mvmap[tmv1.y+1][tmv1.x+1],5,1);
      spt+=5;
   }
   else{
      tmv2=cir_search(prev,cur,cx,cy,x,y,err,mvmap[tmv1.y+1][tmv1.x+1],3,1);
      spt+=3;
   }
   if(tmv2.x==0 && tmv2.y==0)
      return tmv1;
   cx+=tmv2.x;
   cy+=tmv2.y;
   mv.x=tmv1.x+tmv2.x;
   mv.y=tmv1.y+tmv2.y;
   /* step 3 */
   do{
      if(abs(tmv2.x)==abs(tmv2.y)){
         tmv3=cir_search(prev,cur,cx,cy,x,y,err,mvmap[tmv2.y+1][tmv2.x+1],5,1);
         if((abs(tmv1.x)==abs(tmv1.y))&&(((tmv1.x+tmv2.x)==0)||((tmv1.y+tmv2.y)==0)))
            spt+=4;
         else
            spt+=5;
      }
      else{
         tmv3=cir_search(prev,cur,cx,cy,x,y,err,mvmap[tmv2.y+1][tmv2.x+1],3,1);
         spt+=3;
      }
      if(tmv3.x==0 && tmv3.y==0)
         return mv;
      mv.x+=tmv3.x;
      mv.y+=tmv3.y;
      cx+=tmv3.x;
      cy+=tmv3.y;
      tmv1=tmv2;
      tmv2=tmv3;
   }while(abs(mv.x)!=MAX_DISP&&abs(mv.y)!=MAX_DISP);
   return mv;
}

MV hsa_search(u_char *prev, u_char *cur, int x, int y, int *err)
{
   MV mv;
   int D,Dd;
   float M,Md,nk,nc;
   static int Do=0;
   static float t,c=50.0*256,k=500.0,d=2.8284;
   static float u=0.002,v=0.002,Mo=0;
   mv.x=0;
   mv.y=0;
   t=k*d+c;
   *err=mean_abs_err(cur,prev,x,y,x,y,BLOCK_WIDTH,BLOCK_HEIGHT);
   D=*err;
   if((float)D<t)
      mv=bbgd_search(prev,cur,x,y,err); 
   else
      mv=four_step_search(prev,cur,x,y,err);
   M=sqrt(mv.x*mv.x+mv.y*mv.y);
   Dd=D-Do;
   Md=M-Mo;
   if(Dd*Md>0){
      nk=Dd/Md;
      k=(1-v)*k+v*nk;
   }
   else{
      nc=D-k*M;
      c=(1-u)*c+u*nc;
   }
   Do=D;
   Mo=M;
   return mv;
}

MV ucbd_search(u_char *prev, u_char *cur, int x, int y, int *err)
{
   int i,j,k,b,t,m,n,err0;
   MV mv,tmv;
   static MV dia[8]={{-2,0},{-1,-1},{0,-2},{1,-1},{2,0},{1,1},{0,2},{-1,1}};
   *err=mean_abs_err(cur,prev,x,y,x,y,BLOCK_WIDTH,BLOCK_HEIGHT);
   spt++;
   tmv.x=0;
   tmv.y=0;
   k=9;
   for(i=0;i<8;i++){
      m=x+dia[i].x;
      n=y+dia[i].y;
      if(bound_chk(m,n,x,y)){
         err0=mean_abs_err(cur,prev,x,y,m,n,BLOCK_WIDTH,BLOCK_HEIGHT);
#ifdef OPC
         op.c++;
#endif
         if(err0<(*err)){
            *err=err0;
            tmv=dia[i];
            k=i;
         }
      }
   }
   spt+=8;
   mv=tmv;
   while(1){
      if(k==9)
         break;
      else{
         j=k;k=9;
         tmv.x=0;tmv.y=0;
      }
      if(abs(dia[j].x)==1){
         t=3;b=-1;
      }else{
         t=5;b=-2;
      }
      j=(j+b)<0?(8+j+b):(j+b);
      for(i=0;i<t;i++){
         m=x+mv.x+dia[j].x;
         n=y+mv.y+dia[j].y;
         if(bound_chk(m,n,x,y)){
            err0=mean_abs_err(cur,prev,x,y,m,n,BLOCK_WIDTH,BLOCK_HEIGHT);
#ifdef OPC
            op.c++;
#endif
            if(err0<(*err)){
               *err=err0;
               tmv=dia[j];
               k=j;
            }
         }
         j=(j+1)>7?0:(j+1);
      }
      spt+=t;
      mv.x=mv.x+tmv.x;
      mv.y=mv.y+tmv.y;
   }
   tmv.x=0;tmv.y=0;
   for(i=0;i<8;i+=2){
      m=x+mv.x+(dia[i].x>>1);
      n=y+mv.y+(dia[i].y>>1);
      if(bound_chk(m,n,x,y)){
         err0=mean_abs_err(cur,prev,x,y,m,n,BLOCK_WIDTH,BLOCK_HEIGHT);
#ifdef OPC
         op.c++;
#endif
         if(err0<(*err)){
            *err=err0;
            tmv=dia[i];
         }
      }
   }
   spt+=4;
   mv.x=mv.x+(tmv.x>>1);
   mv.y=mv.y+(tmv.y>>1);
   return mv;
}
 
MV cd_search(u_char *prev, u_char *cur, int x, int y, int *err)
{
   int i,j,k,b,t,m,n,err0,c=9,ox=x,oy=y,step;
   MV mv,tmv;
   static MV dia[8]={{-2,0},{-1,-1},{0,-2},{1,-1},{2,0},{1,1},{0,2},{-1,1}};
   static MV crx[8]={{-2,0},{-1,0},{0,-2},{0,-1},{2,0},{1,0},{0,2},{0,1}};

   init_searchedpt();
   *err=mean_abs_err(cur,prev,x,y,x,y,BLOCK_WIDTH,BLOCK_HEIGHT);
   searchedpt[MAX_DISP][MAX_DISP]=1;

   tmv.x=0;
   tmv.y=0;
   k=9;
   step=1;
   for(i=0;i<8;i++){
      m=x+crx[i].x;
      n=y+crx[i].y;
      if(bound_chk(m,n,x,y)){
         err0=mean_abs_err(cur,prev,x,y,m,n,BLOCK_WIDTH,BLOCK_HEIGHT);
         searchedpt[MAX_DISP+m-ox][MAX_DISP+n-oy]=1;
#ifdef OPC
         op.c++;
#endif
         if(err0<(*err)){
            *err=err0;
            tmv=crx[i];
            k=i;
         }
      }
   }
   mv=tmv;
   if(k==9) {
     spt += count_searchedpt();
     printf("c%d ", count_searchedpt());
     return mv;  //1st-step-stop
   }

   if(k!=9) {
     step+=1;
     c=k; k=9;
     tmv.x=0; tmv.y=0; 
     if(c==0||c==1) j=7;
     else if(c==2||c==3) j=1; 
     else if(c==4||c==5) j=3;
     else if(c==6||c==7) j=5;
     t=4; //Once not the center of CSP, 4 new point anyway.
     for(i=0;i<t;i++){
        m=x+dia[j].x;
        n=y+dia[j].y;
        if(bound_chk(m,n,x,y)){
           err0=mean_abs_err(cur,prev,x,y,m,n,BLOCK_WIDTH,BLOCK_HEIGHT);
           searchedpt[MAX_DISP+m-ox][MAX_DISP+n-oy]=1;
#ifdef OPC
           op.c++;
#endif
           if(err0<(*err)){
             *err=err0;
             tmv=dia[j];
             k=j;
             mv=tmv;
           }
        }
        j=(j+2)>7?1:(j+2);
     }
   }

   if(k==9 && c%2==1) {
     spt += count_searchedpt();
     printf("s%d ", count_searchedpt());
     return mv;  //2nd-step-stop
   }

   if(k==9 && c%2==0) k=c;

   while(1){
      if(k==9)
         break;
      else{
         j=k;k=9;
         tmv.x=0;tmv.y=0;
      }
      step+=1;
      if(j%2==1){
         t=3;b=-1;
      } else{
         t=5;b=-2;
      }
      j=(j+b)<0?(8+j+b):(j+b);
      for(i=0;i<t;i++){
         m=x+mv.x+dia[j].x;
         n=y+mv.y+dia[j].y;
         if(bound_chk(m,n,x,y)){
            err0=mean_abs_err(cur,prev,x,y,m,n,BLOCK_WIDTH,BLOCK_HEIGHT);
            searchedpt[MAX_DISP+m-ox][MAX_DISP+n-oy]=1;
#ifdef OPC
            op.c++;
#endif
            if(err0<(*err)){
               *err=err0;
               tmv=dia[j];
               k=j;
            }
         }
         j=(j+1)>7?0:(j+1);
      }
      mv.x=mv.x+tmv.x;
      mv.y=mv.y+tmv.y;
   }

   tmv.x=0;tmv.y=0;
   for(i=0;i<8;i+=2){
      m=x+mv.x+(dia[i].x>>1);
      n=y+mv.y+(dia[i].y>>1);
      if(bound_chk(m,n,x,y)){
        err0=mean_abs_err(cur,prev,x,y,m,n,BLOCK_WIDTH,BLOCK_HEIGHT);