CalculateOptimalROI.cpp

Go to the documentation of this file.
00001 // -*- c-basic-offset: 4 -*-
00025 #include "CalculateOptimalROI.h"
00026 #include <algorithm>
00027 
00028 namespace HuginBase {
00029 
00030 using namespace hugin_utils;
00031 
00033 bool CalculateOptimalROI::calcOptimalROI(PanoramaData& panorama)
00034 {
00035     activeImages=panorama.getActiveImages();
00036     if (activeImages.empty())
00037     {
00038         return false;
00039     };
00040 
00041     PanoramaOptions opt = panorama.getOptions();
00042     o_optimalSize=opt.getSize();
00043     if (o_optimalSize.x == 0 || o_optimalSize.y == 0)
00044     {
00045         return false;
00046     };
00047     m_bestRect = vigra::Rect2D();
00048     try
00049     {
00050         testedPixels.resize(o_optimalSize.x*o_optimalSize.y,false);
00051         pixels.resize(o_optimalSize.x*o_optimalSize.y,false);
00052     }
00053     catch(std::bad_alloc&)
00054     {
00055         //could not allocate enough memory
00056         return false;
00057     };
00058 
00059     for (UIntSet::const_iterator it=activeImages.begin(); it!=activeImages.end(); ++it)
00060     {
00061         const SrcPanoImage &img=panorama.getImage(*it);
00062         PTools::Transform *transf=new PTools::Transform();
00063         transf->createTransform(img,opt);
00064         transfMap.insert(std::pair<unsigned int,PTools::Transform*>(*it,transf));
00065     }
00066     
00067     if (!getProgressDisplay()->updateDisplay("Calculate the cropping region"))
00068     {
00069         CleanUp();
00070         return false;
00071     };
00072     if (!autocrop())
00073     {
00074         CleanUp();
00075         return false;
00076     };
00077     
00078     //clean up on demand
00079     CleanUp();
00080     return true;
00081 };
00082 
00083 void CalculateOptimalROI::CleanUp()
00084 {
00085     for (std::map<unsigned int, PTools::Transform*>::iterator it = transfMap.begin(); it != transfMap.end(); ++it)
00086     {
00087         delete (*it).second;
00088     };
00089 };
00090 
00091 //now you can do dynamic programming, look thinks up on fly
00092 bool CalculateOptimalROI::stackPixel(int i, int j, UIntSet &stack)
00093 {
00094     bool inside = intersection; // start with true for intersection mode and with false for union mode
00095     //check that pixel at each place
00096     for(UIntSet::const_iterator it=stack.begin();it!=stack.end();++it)
00097     {
00098         double xd,yd;
00099         if(transfMap[*it]->transformImgCoord(xd,yd,(double)i,(double)j))
00100         {
00101             if(o_panorama.getImage(*it).isInside(vigra::Point2D(xd,yd)))
00102             {
00103                 if (!intersection) {
00104                     //if found in a single image, short cut out
00105                     inside=true;
00106                     break;
00107                 }
00108             }
00109             else {
00110                 if (intersection) {
00111                     //outside of at least one image - return false
00112                     inside=false;
00113                     break;
00114                 }
00115             }
00116         }
00117     }
00118 
00119     return inside;
00120 }
00121 
00122 bool CalculateOptimalROI::imgPixel(int i, int j)
00123 {
00124     if(!testedPixels[j*o_optimalSize.x+i])
00125     {
00126         bool inside;
00127         
00128         if (stacks.empty())
00129         {
00130             // no stacks - test all images on union or intersection
00131             inside = stackPixel(i, j, activeImages);
00132         }
00133         else
00134         {
00135             inside = false;
00136             // pixel must be inside of at least one stack
00137             for (unsigned s=0; s < stacks.size(); s++)
00138             {
00139                 // images in each stack are tested on intersection
00140                 if (stackPixel(i, j, stacks[s]))
00141                 {
00142                     inside = true;
00143                     break;
00144                 }
00145             }
00146         }
00147 
00148         testedPixels[j*o_optimalSize.x + i] = true;
00149         pixels[j*o_optimalSize.x + i] = inside;
00150         
00151         return inside;
00152     }
00153     //else it is know if this pixel is covered by at least one image
00154     else
00155     {
00156         return pixels[j*o_optimalSize.x+i];
00157     }
00158 }
00159 
00161 void CalculateOptimalROI::AddCheckingRects(std::list<vigra::Rect2D>& testingRects, const vigra::Rect2D& rect, const long maxvalue)
00162 {
00163     if(rect.left()<0 || rect.top()<0 || rect.right()>o_optimalSize.x || rect.bottom()>o_optimalSize.y)
00164     {
00165         return;
00166     }
00167     
00168     if (rect.left() < rect.right() && rect.top() < rect.bottom())
00169     {
00170         //not big enough
00171         if(maxvalue>0 && rect.area()<maxvalue)
00172         {
00173             return;
00174         }
00175         // check if rect is already in list
00176         std::list<vigra::Rect2D>::iterator it=std::find(testingRects.begin(), testingRects.end(), rect);
00177         if (it == testingRects.end())
00178         {
00179             testingRects.push_back(rect);
00180         };
00181     }
00182 }
00183 
00185 bool CalculateOptimalROI::CheckRectCoversPano(const vigra::Rect2D& rect)
00186 {
00187     for (size_t i = rect.left(); i<rect.right(); i++)
00188     {
00189         if (imgPixel(i, rect.top()) == 0 || imgPixel(i, rect.bottom() - 1) == 0)
00190         {
00191             return false;
00192         }
00193     }
00194 
00195     for (size_t j = rect.top(); j<rect.bottom(); j++)
00196     {
00197         if (imgPixel(rect.left(), j) == 0 || imgPixel(rect.right() - 1, j) == 0)
00198         {
00199             return false;
00200         }
00201     }
00202     return true;
00203 };
00204 
00205 vigra::Rect2D ModifyRect(const vigra::Rect2D& rect, long deltaLeft, long deltaTop, long deltaRight, long deltaBottom)
00206 {
00207     vigra::Rect2D newRect(rect);
00208     newRect.moveBy(deltaLeft, deltaTop);
00209     newRect.addSize(vigra::Size2D(deltaRight - deltaLeft, deltaBottom - deltaTop));
00210     return newRect;
00211 };
00212 
00213 void CalculateOptimalROI::nonreccheck(const vigra::Rect2D& rect, int acc, int searchStrategy, long& maxvalue)
00214 {
00215     std::list<vigra::Rect2D> testRects;
00216     testRects.push_back(rect);
00217     
00218     while(!testRects.empty())
00219     {
00220         vigra::Rect2D testingRect = *testRects.begin();
00221         const bool rectCovers = CheckRectCoversPano(testingRect);
00222         switch(searchStrategy)
00223         {
00224             case 1:
00225                 if(!rectCovers)
00226                 {
00227                     //all directions (shrink only)
00228                     AddCheckingRects(testRects, ModifyRect(testingRect,   0, acc,    0,    0), maxvalue);
00229                     AddCheckingRects(testRects, ModifyRect(testingRect,   0,   0,    0, -acc), maxvalue);
00230                     AddCheckingRects(testRects, ModifyRect(testingRect, acc,   0,    0,    0), maxvalue);
00231                     AddCheckingRects(testRects, ModifyRect(testingRect,   0,   0, -acc,    0), maxvalue);
00232                 }
00233                 //it was good, stop recursing
00234                 else
00235                 {
00236                     if(maxvalue<testingRect.area())
00237                     {
00238                         maxvalue=testingRect.area();
00239                         m_bestRect = testingRect;
00240                     }
00241                 }
00242                 break;
00243             case 2:
00244                 if(!rectCovers)
00245                 {
00246                     //all directions (shrink only)
00247                     AddCheckingRects(testRects, ModifyRect(testingRect, acc >> 1, 0, -(acc >> 1), 0), maxvalue);
00248                     AddCheckingRects(testRects, ModifyRect(testingRect, 0, acc >> 1, 0, -(acc >> 1)), maxvalue);
00249                 }
00250                 //it was good, stop recursing
00251                 else
00252                 {
00253                     if(maxvalue<testingRect.area())
00254                     {
00255                         maxvalue = testingRect.area();
00256                         m_bestRect = testingRect;
00257                     }
00258                 }
00259                 break;
00260             case 0:
00261             default:
00262                 if(rectCovers)
00263                 {
00264                     //check growth in all 4 directions
00265                     AddCheckingRects(testRects, ModifyRect(testingRect, -acc, 0, 0, 0), maxvalue);
00266                     AddCheckingRects(testRects, ModifyRect(testingRect, 0, 0, acc, 0), maxvalue);
00267                     AddCheckingRects(testRects, ModifyRect(testingRect, 0, -acc, 0, 0), maxvalue);
00268                     AddCheckingRects(testRects, ModifyRect(testingRect, 0, 0, 0, acc), maxvalue);
00269                     //check if shrinking in one direction will allow more growth in other direction
00270                     AddCheckingRects(testRects, ModifyRect(testingRect, -2*acc, acc, 0, 0), maxvalue);
00271                     AddCheckingRects(testRects, ModifyRect(testingRect, -2*acc, 0, 0, -acc), maxvalue);
00272                     AddCheckingRects(testRects, ModifyRect(testingRect, 0, acc, 2*acc, 0), maxvalue);
00273                     AddCheckingRects(testRects, ModifyRect(testingRect, 0, 0, 2*acc, -acc), maxvalue);
00274                     AddCheckingRects(testRects, ModifyRect(testingRect, acc, -2 * acc, 0, 0), maxvalue);
00275                     AddCheckingRects(testRects, ModifyRect(testingRect, 0, -2*acc, -acc, 0), maxvalue);
00276                     AddCheckingRects(testRects, ModifyRect(testingRect, acc, 0, 0, 2*acc), maxvalue);
00277                     AddCheckingRects(testRects, ModifyRect(testingRect, 0, 0, -acc, 2*acc), maxvalue);
00278                     AddCheckingRects(testRects, ModifyRect(testingRect, -acc, acc, acc, 0), maxvalue);
00279                     AddCheckingRects(testRects, ModifyRect(testingRect, -acc, 0, acc, -acc), maxvalue);
00280                     AddCheckingRects(testRects, ModifyRect(testingRect, acc, -acc, 0, acc), maxvalue);
00281                     AddCheckingRects(testRects, ModifyRect(testingRect, 0, -acc, -acc, acc), maxvalue);
00282                     if(maxvalue<testingRect.area())
00283                     {
00284                         maxvalue = testingRect.area();
00285                         m_bestRect = testingRect;
00286                     }
00287                 }
00288         };
00289         testRects.pop_front();
00290     }
00291 }
00292 
00293 bool CalculateOptimalROI::autocrop()
00294 {
00295     long maxvalue=0;
00296 
00297     //put backwards at the start
00298     int startacc = pow(2.0, std::min((int)log2(o_optimalSize.x / 2 - 1), (int)log2(o_optimalSize.y / 2 - 1)) - 1);
00299     if (startacc < 1)
00300     {
00301         startacc = 1;
00302     };
00303 
00304     //start smaller to get biggest initial position
00305     if(startacc>64)
00306     {
00307         //we start searching with a symmetric decrease
00308         for(int acc=startacc;acc>=64;acc/=2)
00309         {
00310             nonreccheck(vigra::Rect2D(vigra::Point2D(), o_optimalSize), acc, 2, maxvalue);
00311             if (!getProgressDisplay()->updateDisplayValue())
00312             {
00313                 return false;
00314             };
00315             if(maxvalue>0)
00316             {
00317                 printf("Inner %d %ld: %d %d - %d %d\n", acc, maxvalue, m_bestRect.left(), m_bestRect.right(), m_bestRect.top(), m_bestRect.bottom());
00318                 break;
00319             }
00320         }
00321     };
00322 
00323     if(maxvalue==0)
00324     {
00325         // if the rough symmetric search failed we are using also an asymmetric strategy
00326         for(int acc=startacc;acc>=1;acc/=2)
00327         {
00328             nonreccheck(vigra::Rect2D(vigra::Point2D(), o_optimalSize), acc, 1, maxvalue);
00329             if (!getProgressDisplay()->updateDisplayValue())
00330             {
00331                 return false;
00332             };
00333             if (maxvalue>0)
00334             {
00335                 printf("Inner %d %ld: %d %d - %d %d\n", acc, maxvalue, m_bestRect.left(), m_bestRect.right(), m_bestRect.top(), m_bestRect.bottom());
00336                 break;
00337             }
00338         }
00339     };
00340     
00341     for(int acc=startacc;acc>=1;acc/=2)
00342     {
00343         printf("Starting %d: %d %d - %d %d\n", acc, m_bestRect.left(), m_bestRect.right(), m_bestRect.top(), m_bestRect.bottom());
00344         nonreccheck(m_bestRect, acc, 0, maxvalue);
00345         if (!getProgressDisplay()->updateDisplayValue())
00346         {
00347             return false;
00348         };
00349     }
00350 
00351     return true;
00352 }
00353 
00354 void CalculateOptimalROI::setStacks(std::vector<UIntSet> hdr_stacks)
00355 {
00356     stacks=hdr_stacks;
00357     intersection=true;
00358 };
00359 
00360 } //namespace

Generated on 31 Jul 2015 for Hugintrunk by  doxygen 1.4.7