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

Generated on 12 Feb 2016 for Hugintrunk by  doxygen 1.4.7