CalculateOptimalROI.cpp

Go to the documentation of this file.
00001 // -*- c-basic-offset: 4 -*-
00025 #include "CalculateOptimalROI.h"
00026 
00027 namespace HuginBase {
00028 
00029 using namespace hugin_utils;
00030 
00031 //uses the area as that major searching factor
00032 //else uses width+heigh like the perimeter
00033 #define USEAREA
00034 
00036 bool CalculateOptimalROI::calcOptimalROI(PanoramaData& panorama)
00037 {
00038     activeImages=panorama.getActiveImages();
00039     if (activeImages.size() == 0)
00040         return false;
00041 
00042     printf("Down to Algorithm\n");
00043     PanoramaOptions opt = panorama.getOptions();
00044     
00045     o_optimalSize=opt.getSize();
00046     if(o_optimalSize.x==0 || o_optimalSize.y==0)
00047         return false;
00048     o_optimalROI=vigra::Rect2D(0,0,o_optimalSize.x,o_optimalSize.y);
00049     try
00050     {
00051         testedPixels.resize(o_optimalSize.x*o_optimalSize.y,false);
00052         pixels.resize(o_optimalSize.x*o_optimalSize.y,false);
00053     }
00054     catch(std::bad_alloc&)
00055     {
00056         //could not allocate enough memory
00057         return false;
00058     };
00059 
00060     for (UIntSet::const_iterator it=activeImages.begin(); it!=activeImages.end(); it++)
00061     {
00062         const SrcPanoImage &img=panorama.getImage(*it);
00063         PTools::Transform *transf=new PTools::Transform();
00064         transf->createTransform(img,opt);
00065         transfMap.insert(std::pair<unsigned int,PTools::Transform*>(*it,transf));
00066     }
00067     
00068     printf("Calculate the cropping region\n");
00069     autocrop();
00070     
00071     o_optimalROI=vigra::Rect2D(best.left,best.top,best.right,best.bottom);
00072     printf("Crop %dx%d - %dx%d\n",o_optimalROI.left(),o_optimalROI.top(),o_optimalROI.right(),o_optimalROI.bottom());
00073     printf("Crop Size %dx%d\n",o_optimalROI.width(),o_optimalROI.height());
00074     
00075 //debug image of the region calculated
00076 #if 0
00077     FILE *outstream=fopen("/tmp/test.pgm","wb");
00078     fprintf(outstream,"P5\n");
00079     fprintf(outstream,"%d %d\n",o_optimalSize.x,o_optimalSize.y);
00080     fprintf(outstream,"255\n");
00081     fwrite(tmp,o_optimalSize.x*o_optimalSize.y,1,outstream);
00082     fclose(outstream);
00083 #endif
00084 
00085     //clean up on demand
00086     for(std::map<unsigned int,PTools::Transform*>::iterator it=transfMap.begin();it!=transfMap.end();it++)
00087     {
00088         delete (*it).second;
00089     };
00090 
00091     return true;
00092 }
00093 
00094 //now you can do dynamic programming, look thinks up on fly
00095 bool CalculateOptimalROI::stackPixel(int i, int j, UIntSet &stack)
00096 {
00097     bool inside = intersection; // start with true for intersection mode and with false for union mode
00098     //check that pixel at each place
00099     for(UIntSet::const_iterator it=stack.begin();it!=stack.end();it++)
00100     {
00101         double xd,yd;
00102         if(transfMap[*it]->transformImgCoord(xd,yd,(double)i,(double)j))
00103         {
00104             if(o_panorama.getImage(*it).isInside(vigra::Point2D(xd,yd)))
00105             {
00106                 if (!intersection) {
00107                     //if found in a single image, short cut out
00108                     inside=true;
00109                     break;
00110                 }
00111             }
00112             else {
00113                 if (intersection) {
00114                     //outside of at least one image - return false
00115                     inside=false;
00116                     break;
00117                 }
00118             }
00119         }
00120     }
00121 
00122     return inside;
00123 }
00124 
00125 bool CalculateOptimalROI::imgPixel(int i, int j)
00126 {
00127     if(testedPixels[j*o_optimalSize.x+i]==0)
00128     {
00129         bool inside;
00130         
00131         if (stacks.empty())
00132         {
00133             // no stacks - test all images on union or intersection
00134             inside = stackPixel(i, j, activeImages);
00135         }
00136         else
00137         {
00138             inside = false;
00139             // pixel must be inside of at least one stack
00140             for (unsigned s=0; s < stacks.size(); s++)
00141             {
00142                 // images in each stack are tested on intersection
00143                 if (stackPixel(i, j, stacks[s]))
00144                 {
00145                     inside = true;
00146                     break;
00147                 }
00148             }
00149         }
00150 
00151         testedPixels[j*o_optimalSize.x+i]=1;
00152         pixels[j*o_optimalSize.x+i]=inside;
00153         
00154         return inside;
00155     }
00156     //else it is know if this pixel is covered by at least one image
00157     else
00158     {
00159         return pixels[j*o_optimalSize.x+i];
00160     }
00161 }
00162 
00163 void CalculateOptimalROI::makecheck(int left,int top,int right,int bottom)
00164 {
00165     if(left<0 || top<0 || right>o_optimalSize.x || bottom>o_optimalSize.y)
00166     {
00167         return;
00168     }
00169     
00170     if(left<right && top<bottom)
00171     {
00172         //big enough
00173 #ifdef USEAREA
00174         if(maxvalue>0 && (right-left)*(bottom-top)<maxvalue)
00175 #else
00176         if(maxvalue>0 && (right-left)+(bottom-top)<maxvalue)
00177 #endif
00178         {
00179             return;
00180         }
00181         
00182         nonrec *tmp=head;
00183         //check if exists
00184         while(tmp!=NULL)
00185         {
00186             if(tmp->left==left && tmp->right==right && tmp->top==top && tmp->bottom==bottom)
00187             {
00188                 //printf("found dupe\n");
00189                 return;
00190             }
00191             tmp=tmp->next;
00192         }
00193         
00194         //make
00195         tmp=new nonrec;
00196         tmp->left=left;
00197         tmp->top=top;
00198         tmp->right=right;
00199         tmp->bottom=bottom;
00200         tmp->next=NULL;
00201         
00202         count++;
00203         tail->next=tmp;
00204         tail=tmp;
00205     }
00206     return;
00207 }
00208 
00209 void CalculateOptimalROI::nonreccheck(int left,int top,int right,int bottom,int acc,int searchStrategy)
00210 {
00211     nonrec *tmp;
00212     tmp=new nonrec;
00213     tmp->left=left;
00214     tmp->top=top;
00215     tmp->right=right;
00216     tmp->bottom=bottom;
00217     tmp->next=NULL;
00218     
00219     head=tmp;
00220     tail=tmp;
00221     count=0;
00222     count++;
00223     
00224     while(count>0)
00225     {
00226         count--;
00227         left=head->left;
00228         top=head->top;
00229         right=head->right;
00230         bottom=head->bottom;
00231         
00232         //do lasso, check if failed
00233         int i,j,flag;
00234         flag=0;
00235         for(i=left;i<right && flag==0;i++)
00236         {
00237             if(imgPixel(i,top)==0 || imgPixel(i,bottom-1)==0)
00238             {
00239                 flag=1;
00240             }
00241         }
00242         
00243         for(j=top;j<bottom && flag==0;j++)
00244         {
00245             if(imgPixel(left,j)==0 || imgPixel(right-1,j)==0)
00246             {
00247                 flag=1;
00248             }
00249         }
00250 
00251         //if failed, then recurse
00252 
00253         switch(searchStrategy)
00254         {
00255             case 1:
00256                 if(flag==1)
00257                 {
00258                     //all directions (shrink only)
00259                     makecheck(left,top+acc,right,bottom);
00260                     makecheck(left,top,right,bottom-acc);
00261                     makecheck(left+acc,top,right,bottom);
00262                     makecheck(left,top,right-acc,bottom);
00263                 }
00264                 //it was good, stop recursing
00265                 else
00266                 {
00267                     //printf("\nGood\n");
00268 #ifdef USEAREA
00269                     if(maxvalue<(right-left)*(bottom-top))
00270 #else
00271                     if(maxvalue<(right-left)+(bottom-top))
00272 #endif
00273                     {
00274 #ifdef USEAREA
00275                         maxvalue=(right-left)*(bottom-top);
00276 #else
00277                         maxvalue=(right-left)+(bottom-top);
00278 #endif
00279                         best.right=right;
00280                         best.left=left;
00281                         best.top=top;
00282                         best.bottom=bottom;
00283                     }
00284                 }
00285                 break;
00286             case 2:
00287                 if(flag==1)
00288                 {
00289                     //all directions (shrink only)
00290                     makecheck(left+(acc>>1),top,right-(acc>>1),bottom);
00291                     makecheck(left,top+(acc>>1),right,bottom-(acc>>1));
00292                 }
00293                 //it was good, stop recursing
00294                 else
00295                 {
00296                     //printf("\nGood\n");
00297 #ifdef USEAREA
00298                     if(maxvalue<(right-left)*(bottom-top))
00299 #else
00300                     if(maxvalue<(right-left)+(bottom-top))
00301 #endif
00302                     {
00303 #ifdef USEAREA
00304                         maxvalue=(right-left)*(bottom-top);
00305 #else
00306                         maxvalue=(right-left)+(bottom-top);
00307 #endif
00308                         best.right=right;
00309                         best.left=left;
00310                         best.top=top;
00311                         best.bottom=bottom;
00312                     }
00313                 }
00314                 break;
00315             case 0:
00316             default:
00317                 if(flag==0)
00318                 {
00319                     //check growth in all 4 directions
00320                     makecheck(left-acc,top,right,bottom);
00321                     makecheck(left,top,right+acc,bottom);
00322                     makecheck(left,top-acc,right,bottom);
00323                     makecheck(left,top,right,bottom+acc);
00324                     //check if shrinking in one direction will allow more growth in other direction
00325                     makecheck(left-acc*2,top+acc,right,bottom);
00326                     makecheck(left-acc*2,top,right,bottom-acc);
00327                     makecheck(left,top+acc,right+acc*2,bottom);
00328                     makecheck(left,top,right+acc*2,bottom-acc);
00329                     makecheck(left+acc,top-acc*2,right,bottom);
00330                     makecheck(left,top-acc*2,right-acc,bottom);
00331                     makecheck(left+acc,top,right,bottom+acc*2);
00332                     makecheck(left,top,right-acc,bottom+acc*2);
00333                     makecheck(left-acc,top+acc,right+acc,bottom);
00334                     makecheck(left-acc,top,right+acc,bottom-acc);
00335                     makecheck(left+acc,top-acc,right,bottom+acc);
00336                     makecheck(left,top-acc,right-acc,bottom+acc);
00337 #ifdef USEAREA
00338                     if(maxvalue<(right-left)*(bottom-top))
00339 #else
00340                     if(maxvalue<(right-left)+(bottom-top))
00341 #endif
00342                     {
00343 #ifdef USEAREA
00344                         maxvalue=(right-left)*(bottom-top);
00345 #else
00346                         maxvalue=(right-left)+(bottom-top);
00347 #endif
00348                         best.right=right;
00349                         best.left=left;
00350                         best.top=top;
00351                         best.bottom=bottom;
00352                     }
00353                 }
00354         };
00355         
00356         tmp=head->next;
00357         if(tmp!=NULL)
00358         {
00359             //experiment with no deletion
00360             delete head;
00361             head=tmp;
00362         }
00363     }
00364     
00365     //no delete test 
00366     while(head!=NULL)
00367     {
00368         tmp=head->next;
00369         delete head;
00370         head=tmp;
00371     }
00372     
00373     if(maxvalue>0 && acc==1 && searchStrategy==0)
00374     {
00375         printf("Found Solution: %d %d %d %d\n",best.left,best.top,best.right,best.bottom);
00376     }
00377 }
00378 
00379 int CalculateOptimalROI::autocrop()
00380 {
00381     printf("Original Image: %dx%d\n",o_optimalSize.x,o_optimalSize.y);
00382     
00383     maxvalue=0;
00384     count=0;
00385     head=NULL;
00386     tail=NULL;
00387 
00388     //put backwards at the start
00389     int startacc=pow(2.0,std::min((int)log2(o_optimalSize.x/2-1),(int)log2(o_optimalSize.y/2-1))-1);
00390     if(startacc<1)
00391         startacc=1;
00392 
00393     //start smaller to get biggest initial position
00394     if(startacc>64)
00395     {
00396         //we start searching with a symmetric decrease
00397         for(int acc=startacc;acc>=64;acc/=2)
00398         {
00399             nonreccheck(0,0,o_optimalSize.x,o_optimalSize.y,acc,2);
00400             if(maxvalue>0)
00401             {
00402                 printf("Inner %d %ld: %d %d - %d %d\n",acc,maxvalue,best.left,best.right,best.top,best.bottom);
00403                 break;
00404             }
00405         }
00406     };
00407 
00408     if(maxvalue==0)
00409     {
00410         // if the rough symmetric search failed we are using also an asymmetric strategy
00411         for(int acc=startacc;acc>=1;acc/=2)
00412         {
00413             nonreccheck(0,0,o_optimalSize.x,o_optimalSize.y,acc,1);
00414             if(maxvalue>0)
00415             {
00416                 printf("Inner %d %ld: %d %d - %d %d\n",acc,maxvalue,best.left,best.right,best.top,best.bottom);
00417                 break;
00418             }
00419         }
00420     };
00421     
00422     for(int acc=startacc;acc>=1;acc/=2)
00423     {
00424         printf("Starting %d: %d %d - %d %d\n",acc,best.left,best.right,best.top,best.bottom);
00425         nonreccheck(best.left,best.top,best.right,best.bottom,acc,0);
00426     }
00427 
00428     //printf("Final Image: %dx%d\n",outpano->width,outpano->height);
00429     return 0;
00430 }
00431 
00432 void CalculateOptimalROI::setStacks(std::vector<UIntSet> hdr_stacks)
00433 {
00434     stacks=hdr_stacks;
00435     intersection=true;
00436 };
00437 
00438 } //namespace

Generated on Mon Jul 28 01:25:38 2014 for Hugintrunk by  doxygen 1.3.9.1