LineGrouping.C

Go to the documentation of this file.
00001 /*!@file SceneUnderstanding/LineGrouping.C  */
00002 
00003 // //////////////////////////////////////////////////////////////////// //
00004 // The iLab Neuromorphic Vision C++ Toolkit - Copyright (C) 2000-2005   //
00005 // by the University of Southern California (USC) and the iLab at USC.  //
00006 // See http://iLab.usc.edu for information about this project.          //
00007 // //////////////////////////////////////////////////////////////////// //
00008 // Major portions of the iLab Neuromorphic Vision Toolkit are protected //
00009 // under the U.S. patent ``Computation of Intrinsic Perceptual Saliency //
00010 // in Visual Environments, and Applications'' by Christof Koch and      //
00011 // Laurent Itti, California Institute of Technology, 2001 (patent       //
00012 // pending; application number 09/912,225 filed July 23, 2001; see      //
00013 // http://pair.uspto.gov/cgi-bin/final/home.pl for current status).     //
00014 // //////////////////////////////////////////////////////////////////// //
00015 // This file is part of the iLab Neuromorphic Vision C++ Toolkit.       //
00016 //                                                                      //
00017 // The iLab Neuromorphic Vision C++ Toolkit is free software; you can   //
00018 // redistribute it and/or modify it under the terms of the GNU General  //
00019 // Public License as published by the Free Software Foundation; either  //
00020 // version 2 of the License, or (at your option) any later version.     //
00021 //                                                                      //
00022 // The iLab Neuromorphic Vision C++ Toolkit is distributed in the hope  //
00023 // that it will be useful, but WITHOUT ANY WARRANTY; without even the   //
00024 // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR      //
00025 // PURPOSE.  See the GNU General Public License for more details.       //
00026 //                                                                      //
00027 // You should have received a copy of the GNU General Public License    //
00028 // along with the iLab Neuromorphic Vision C++ Toolkit; if not, write   //
00029 // to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,   //
00030 // Boston, MA 02111-1307 USA.                                           //
00031 // //////////////////////////////////////////////////////////////////// //
00032 //
00033 // Primary maintainer for this file: Lior Elazary <elazary@usc.edu>
00034 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/plugins/SceneUnderstanding/LineGrouping.C $
00035 // $Id: LineGrouping.C 14181 2010-10-28 22:46:20Z lior $
00036 //
00037 
00038 #ifndef LineGrouping_C_DEFINED
00039 #define LineGrouping_C_DEFINED
00040 
00041 #include "plugins/SceneUnderstanding/LineGrouping.H"
00042 #include "Image/DrawOps.H"
00043 #include "Image/MathOps.H"
00044 #include "Image/Kernels.H"
00045 #include "Image/FilterOps.H"
00046 #include "Image/Transforms.H"
00047 #include "Image/fancynorm.H"
00048 #include "Image/Convolutions.H"
00049 #include "Image/MatrixOps.H"
00050 #include "Simulation/SimEventQueue.H"
00051 #include "GUI/DebugWin.H"
00052 #include <math.h>
00053 #include <fcntl.h>
00054 #include <limits>
00055 #include <string>
00056 #include <stack>
00057 
00058 const ModelOptionCateg MOC_LineGrouping = {
00059   MOC_SORTPRI_3,   "LineGrouping-Related Options" };
00060 
00061 // Used by: SimulationViewerEyeMvt
00062 const ModelOptionDef OPT_LineGroupingShowDebug =
00063   { MODOPT_ARG(bool), "LineGroupingShowDebug", &MOC_LineGrouping, OPTEXP_CORE,
00064     "Show debug img",
00065     "linegrouping-debug", '\0', "<true|false>", "false" };
00066 
00067 //Define the inst function name
00068 SIMMODULEINSTFUNC(LineGrouping);
00069 
00070 std::vector<Point2D<double> > getVel(const std::vector<Point2D<int> >& lines)
00071 {
00072   std::vector<Point2D<double> > vel;
00073 
00074   for(uint i=0; i<lines.size()-1; i++)
00075   {
00076     Point2D<int> dPos = lines[i+1]-lines[i];
00077     double mag = sqrt((dPos.i*dPos.i) + (dPos.j*dPos.j))/4;
00078     for(int j=0; j<int(mag+0.5); j++)
00079       vel.push_back(Point2D<double>(dPos/mag));
00080   }
00081 
00082   return vel;
00083 
00084 }
00085 
00086 int quantize(float x, float y, float z)
00087 {
00088     int val = 0;
00089 
00090     //Get the magnitude 
00091     double rho = sqrt(x*x+y*y+z*z);
00092 
00093     if (rho>3.0)
00094       val = 3<<3;
00095     else if (rho > 2.0)
00096       val = 2<<3;
00097     else if (rho>1.0)
00098       val = 1<<3;
00099     else
00100       val = 0;
00101 
00102     if (x>y) val |= 1<<2; 
00103     if (y>z) val |= 1<<1; 
00104     if (z>x) val |= 1; 
00105 
00106     return val;
00107 }
00108 
00109 
00110 
00111 // ######################################################################
00112 LineGrouping::LineGrouping(OptionManager& mgr, const std::string& descrName,
00113     const std::string& tagName) :
00114   SimModule(mgr, descrName, tagName),
00115   SIMCALLBACK_INIT(SimEventV2Output),
00116   SIMCALLBACK_INIT(SimEventSaveOutput),
00117   SIMCALLBACK_INIT(SimEventUserInput),
00118   itsShowDebug(&OPT_LineGroupingShowDebug, this)
00119   
00120 {
00121   //Add an hmm with 5 states and 32 possible observations
00122   std::vector<uint> states; //5 States
00123   for(uint i=0; i<5; i++) 
00124     states.push_back(i);
00125 
00126   std::vector<uint> posibleObservations; //32
00127   for(uint i=0; i<32; i++) 
00128     posibleObservations.push_back(i);
00129 
00130  itsHMM = HMM<uint>(states, posibleObservations, "Applelogo");
00131 
00132   std::vector<Point2D<int> > lines;
00133   lines.push_back(Point2D<int>(7, 71));
00134   lines.push_back(Point2D<int>(17, 88));
00135   lines.push_back(Point2D<int>(19, 90));
00136   lines.push_back(Point2D<int>(27, 95)); 
00137   lines.push_back(Point2D<int>(29, 95));
00138   lines.push_back(Point2D<int>(38, 91));
00139   lines.push_back(Point2D<int>(39, 91));
00140   lines.push_back(Point2D<int>(55, 95));
00141   lines.push_back(Point2D<int>(56, 95));
00142   lines.push_back(Point2D<int>(61, 93));
00143   lines.push_back(Point2D<int>(62, 93));
00144   lines.push_back(Point2D<int>(74, 73)); 
00145   lines.push_back(Point2D<int>(74, 72));
00146   lines.push_back(Point2D<int>(65, 62));
00147   lines.push_back(Point2D<int>(65, 61));
00148   lines.push_back(Point2D<int>(63, 57));
00149   lines.push_back(Point2D<int>(63, 56));
00150   lines.push_back(Point2D<int>(65, 42));
00151   lines.push_back(Point2D<int>(66, 42));
00152   lines.push_back(Point2D<int>(71, 36));
00153   lines.push_back(Point2D<int>(70, 35));
00154   lines.push_back(Point2D<int>(68, 33));
00155   lines.push_back(Point2D<int>(67, 32));
00156   lines.push_back(Point2D<int>(53, 29));
00157   lines.push_back(Point2D<int>(52, 30));
00158   lines.push_back(Point2D<int>(45, 32));
00159   lines.push_back(Point2D<int>(44, 27));
00160   lines.push_back(Point2D<int>(56, 15));
00161   lines.push_back(Point2D<int>(56, 14));
00162   lines.push_back(Point2D<int>(57, 7));
00163   lines.push_back(Point2D<int>(56, 6));
00164   lines.push_back(Point2D<int>(53, 7));
00165   lines.push_back(Point2D<int>(52, 7));
00166   lines.push_back(Point2D<int>(40, 19)); 
00167   lines.push_back(Point2D<int>(40, 20));
00168   lines.push_back(Point2D<int>(42, 26));
00169   lines.push_back(Point2D<int>(44, 33));
00170   lines.push_back(Point2D<int>(25, 29));
00171   lines.push_back(Point2D<int>(24, 29));
00172   lines.push_back(Point2D<int>(17, 31));
00173   lines.push_back(Point2D<int>(15, 32));
00174   lines.push_back(Point2D<int>(6, 43));
00175   lines.push_back(Point2D<int>(5, 45));
00176   lines.push_back(Point2D<int>(5, 64));
00177   lines.push_back(Point2D<int>(6, 65));
00178   lines.push_back(Point2D<int>(7, 70));
00179 
00180   //scale the lines
00181   for(uint i=0; i<lines.size(); i++)
00182     lines[i] *= 2;
00183  
00184 
00185   //Set the default transitions
00186   itsHMM.setStateTransition(0, 0, 0.5);
00187   itsHMM.setStateTransition(0, 1, 0.5);
00188   itsHMM.setStateTransition(1, 1, 0.5);
00189   itsHMM.setStateTransition(1, 2, 0.5);
00190   itsHMM.setStateTransition(2, 2, 0.5);
00191   itsHMM.setStateTransition(2, 3, 0.5);
00192   itsHMM.setStateTransition(3, 3, 0.5);
00193   itsHMM.setStateTransition(3, 4, 0.5);
00194   itsHMM.setStateTransition(4, 4, 1);
00195 
00196   //set the initial sstate
00197   itsHMM.setCurrentState(0, 1); //We start at the first state
00198 
00199   std::vector<Point2D<double> > vel = getVel(lines);
00200 
00201   std::vector< std::vector<uint> > observations;
00202   for(size_t j=0; j<vel.size(); j++)
00203   {
00204     std::vector<uint> observation;
00205     printf("InputValue ");
00206     for(size_t i=0; i<vel.size(); i++)
00207     {
00208       uint value = quantize(vel[(i+j)%vel.size()].i,
00209                           vel[(i+j)%vel.size()].j, 0);
00210       printf("%i ", value);
00211       observation.push_back(value);
00212     }
00213     printf("\n");
00214     observations.push_back(observation);
00215   }
00216   LINFO("Train");
00217   itsHMM.train(observations, 50);
00218   LINFO("Done");
00219 
00220 }
00221 
00222 // ######################################################################
00223 LineGrouping::~LineGrouping()
00224 {
00225 }
00226 
00227 // ######################################################################
00228 void LineGrouping::onSimEventUserInput(SimEventQueue& q, rutz::shared_ptr<SimEventUserInput>& e)
00229 {
00230 
00231   LINFO("Got event --%s-- %ix%i key=%i",
00232       e->getWinName(),
00233       e->getMouseClick().i,
00234       e->getMouseClick().j,
00235       e->getKey());
00236 
00237   if (strcmp(e->getWinName(), "LineGrouping"))
00238     return;
00239 
00240   switch(e->getKey())
00241   {
00242     case 111: //98: //111: //up
00243       break;
00244     case 116: //104: //116: //down
00245       break;
00246     case 113: //100: //113: //left
00247       break;
00248     case 114: //102: //114: //right
00249       break;
00250     case 21: //=
00251       break;
00252     case 20: //-
00253       break;
00254     case 38: //a
00255       break;
00256     case 52: //z
00257       break;
00258     case 39: //s
00259       break;
00260     case 53: //x
00261       break;
00262     case 40: //d
00263       break;
00264     case 54: //c
00265       break;
00266     case 10: //1
00267       break;
00268     case 24: //q
00269       break;
00270     case 11: //2
00271       break;
00272     case 25: //w
00273       break;
00274     case 12: //3
00275       break;
00276     case 26: //e
00277       break;
00278     case 13: //4
00279       break;
00280     case 27: //r
00281       break;
00282     case 14: //5
00283       break;
00284     case 28: //t
00285       break;
00286     case 15: //6
00287       break;
00288     case 29: //y
00289       break;
00290   }
00291 
00292 
00293   evolve(q);
00294 
00295 }
00296 
00297 
00298 // ######################################################################
00299 void LineGrouping::onSimEventV2Output(SimEventQueue& q, rutz::shared_ptr<SimEventV2Output>& e)
00300 {
00301   //Check if we have the smap
00302   //if (SeC<SimEventSMapOutput> smap = q.check<SimEventSMapOutput>(this))
00303   //  itsSMap = smap->getSMap();
00304 
00305   //Check if we have the corners
00306   itsLines = e->getLines();
00307   itsInputDims = e->getDims();
00308 
00309   evolve(q);
00310 
00311 }
00312 
00313 // ######################################################################
00314 void LineGrouping::onSimEventSaveOutput(SimEventQueue& q, rutz::shared_ptr<SimEventSaveOutput>& e)
00315 {
00316   if (itsShowDebug.getVal())
00317     {
00318       // get the OFS to save to, assuming sinfo is of type
00319       // SimModuleSaveInfo (will throw a fatal exception otherwise):
00320       nub::ref<FrameOstream> ofs =
00321         dynamic_cast<const SimModuleSaveInfo&>(e->sinfo()).ofs;
00322       Layout<PixRGB<byte> > disp = getDebugImage(q);
00323       if (disp.initialized())
00324         ofs->writeRgbLayout(disp, "LineGrouping", FrameInfo("LineGrouping", SRC_POS));
00325     }
00326 }
00327 
00328 
00329 // ######################################################################
00330 void LineGrouping::evolve(SimEventQueue& q)
00331 {
00332 
00333         Image<PixRGB<byte> > linesMask(itsInputDims, ZEROS);
00334   //Prepare an image with array of indexes to know where line are located quickly
00335   Image<std::vector<uint> > linesIndices(itsInputDims, NO_INIT);
00336   for(uint i=0; i<itsLines.size(); i++)
00337   {
00338     V2::LineSegment& ls = itsLines[i];
00339 
00340     Point2D<int> p1 = Point2D<int>(ls.p1);
00341     Point2D<int> p2 = Point2D<int>(ls.p2);
00342     linesIndices[p1].push_back(i);
00343     linesIndices[p2].push_back(i);
00344                 drawLine(linesMask, p1, p2, PixRGB<byte>(50,50,50));
00345   }
00346 
00347 
00348   //Mark if the line has been used or not
00349         std::vector<uint> lineColour(itsLines.size(), 0);
00350 
00351   while(1)
00352   {
00353     //LinesGroup linesGroup;
00354     std::stack<LineInfo> linesStack;
00355                 std::vector<LineInfo> linesGroup;
00356                 std::vector<uint> linesGroupLevel;
00357                 std::list<uint> linesGroupList;
00358 
00359     //Pick a line to group (sort by size)
00360                 uint idx = 2;
00361                 linesStack.push(LineInfo(idx));
00362                 //uint stackLevel = 0;
00363 
00364     while(!linesStack.empty())
00365                 {
00366       //Get the first line in the stack and pop it
00367                         LineInfo lineInfo = linesStack.top();
00368       linesGroup.push_back(lineInfo);
00369                         linesStack.pop();
00370 
00371       //Mark that line as used
00372                         lineColour[lineInfo.idx] = 1;
00373 
00374                         LINFO("Following line %d cost %f", lineInfo.idx, lineInfo.cost);
00375                         Point2D<int> p1 = (Point2D<int>)itsLines[lineInfo.idx].p1;
00376                         Point2D<int> p2 = (Point2D<int>)itsLines[lineInfo.idx].p2;
00377                         drawLine(linesMask, p1, p2, PixRGB<byte>(0,255,0));
00378 
00379                         int radius = 5;
00380       std::vector<LineInfo> lines;
00381                         //First End Point
00382                         //Find the nerest line endpoint to this line's p1 end point
00383       lines = getLocalLines(p1, radius, lineColour, linesIndices);
00384       std::vector<LineInfo> p2Lines = getLocalLines(p2, radius, lineColour, linesIndices);
00385       lines.insert(lines.end(), p2Lines.begin(), p2Lines.end());
00386 
00387       setTopDownCost(lines, linesGroup);
00388 
00389 
00390 
00391 
00392       //Sort by cost
00393       std::sort(lines.begin(), lines.end(), LineInfoCmp());
00394 
00395 
00396       //
00397       for(uint i=0; i<lines.size(); i++)
00398       {
00399         LineInfo line = lines[i];
00400         linesStack.push(line);
00401 
00402         //Show the line we are following
00403         Point2D<int> p1 = (Point2D<int>)itsLines[line.idx].p1;
00404         Point2D<int> p2 = (Point2D<int>)itsLines[line.idx].p2;
00405 
00406         LINFO("Found line %i at X %i y %i cost %f", line.idx, p1.i, p1.j, line.cost);
00407         drawLine(linesMask, p1, p2, PixRGB<byte>(255,0,0));
00408         SHOWIMG(linesMask);
00409       }
00410 
00411                         LINFO("Lines added %zu", lines.size());
00412                         if (lines.size() == 0)
00413                         {
00414                                 //No more lines; dump the stack to the group
00415                                 SHOWIMG(linesMask);
00416                                 LINFO("Showing Stack");
00417                                 Image<PixRGB<byte> > tmp(itsInputDims, NO_INIT);
00418                                 for(uint i=0; i<itsLines.size(); i++)
00419                                 {
00420                                         V2::LineSegment& ls = itsLines[i];
00421                                         Point2D<int> p1 = Point2D<int>(ls.p1);
00422                                         Point2D<int> p2 = Point2D<int>(ls.p2);
00423                                         drawLine(tmp, p1, p2, PixRGB<byte>(50,50,50));
00424                                 }
00425 
00426                                 for(uint i=0; i<linesGroup.size(); i++)
00427                                 {
00428                                         LINFO("Stack %i %i %f", i, linesGroup[i].idx, linesGroup[i].cost);
00429                                         V2::LineSegment& ls = itsLines[linesGroup[i].idx];
00430                                         Point2D<int> p1 = Point2D<int>(ls.p1);
00431                                         Point2D<int> p2 = Point2D<int>(ls.p2);
00432                                         drawLine(tmp, p1, p2, PixRGB<byte>(0,255,0));
00433                                 }
00434                                 linesGroup.pop_back();
00435                                 
00436                                 SHOWIMG(tmp);
00437                         } //else {
00438                         //      stackLevel++;
00439                         //      SHOWIMG(linesMask);
00440                         //}
00441                 }
00442                 LINFO("Done");
00443     getchar();
00444   }
00445 }
00446 
00447 
00448 void LineGrouping::setTopDownCost(std::vector<LineInfo>& newLines,const std::vector<LineInfo>& contour)
00449 {
00450 
00451   //Convert the current counter into velocities
00452   std::vector<Point2D<int> > locations;
00453 
00454   V2::LineSegment& ls = itsLines[contour[0].idx];
00455   Point2D<int> p1 = Point2D<int>(ls.p1);
00456   Point2D<int> p2 = Point2D<int>(ls.p2);
00457   locations.push_back(p1);
00458   locations.push_back(p2);
00459 
00460   for(uint i=1; i<contour.size(); i++)
00461   {
00462     V2::LineSegment& ls = itsLines[contour[i].idx];
00463     Point2D<int> p1 = Point2D<int>(ls.p1);
00464     Point2D<int> p2 = Point2D<int>(ls.p2);
00465 
00466     if (p2.distance(p1) > p2.distance(p2))
00467       locations.push_back(p1);
00468     else
00469       locations.push_back(p2);
00470   }
00471 
00472 
00473   Point2D<int> lastLoc = locations[locations.size()-2];
00474   //For each new line, check the probability that its in the model
00475   for(uint i=0; i<newLines.size(); i++)
00476   {
00477     //Add the new line
00478     std::vector<Point2D<int> > newLocations = locations;
00479     V2::LineSegment& ls = itsLines[newLines[i].idx];
00480     Point2D<int> p1 = Point2D<int>(ls.p1);
00481     Point2D<int> p2 = Point2D<int>(ls.p2);
00482 
00483     if (lastLoc.distance(p1) > lastLoc.distance(p2))
00484       newLocations.push_back(p1);
00485     else
00486       newLocations.push_back(p2);
00487 
00488     //Quantize the observations
00489     std::vector<Point2D<double> > vel = getVel(newLocations);
00490     std::vector<uint> observations; 
00491     for(size_t j=0; j<vel.size(); j++)
00492     {
00493       uint value = quantize(vel[j].i, vel[j].j, 0);
00494       observations.push_back(value);
00495     }
00496  
00497     //Set the prob from the top down model
00498     if (vel.size() > 10)
00499     {
00500       double prob = itsHMM.forward(observations);
00501       newLines[i].cost = prob;
00502       LINFO("Checking line %i idx %i cost %f", i, newLines[i].idx, prob);
00503     } else {
00504       LINFO("Follow bottom up line %i idx %i cost %f", i, newLines[i].idx, newLines[i].cost);
00505     }
00506     
00507 
00508     ////Show the Positions
00509     //Image<PixRGB<byte> > img(512,512, ZEROS);
00510     //Point2D<double> pos = (Point2D<double>)locations[0];
00511     //for(uint i=0; i<vel.size(); i++)
00512     //{
00513     //  if (img.coordsOk(Point2D<int>(pos)))
00514     //    img.setVal(Point2D<int>(pos), PixRGB<byte>(0,255,0));
00515     //  //LINFO("V: %f %f P: %f %f", vel[i].i, vel[i].j, pos.i, pos.j);
00516     //  pos += vel[i];
00517     //}
00518     //SHOWIMG(img);
00519 
00520   }
00521 
00522 }
00523 
00524 
00525 
00526 
00527 std::vector<LineGrouping::LineInfo>  LineGrouping::getLocalLines(const Point2D<int> loc,
00528     const int radius, 
00529     std::vector<uint>& lineColour,
00530     const Image<std::vector<uint> >& linesIndices)
00531 {
00532   std::vector<LineInfo> lines;
00533 
00534   for(int x=loc.i-radius; x<=loc.i+radius; x++)
00535     for(int y=loc.j-radius; y<=loc.j+radius; y++)
00536     {
00537       Point2D<int> lineLoc =Point2D<int>(x,y); 
00538 
00539       if (linesIndices.coordsOk(lineLoc) &&
00540           linesIndices.getVal(lineLoc).size() > 0) //We have some lines, add them
00541       {
00542         for(uint j=0; j<linesIndices[lineLoc].size(); j++)
00543         {
00544           uint idx = linesIndices[lineLoc][j];
00545           if (!lineColour[idx])
00546           {
00547             lineColour[idx] = 1;
00548             double cost = loc.distance(lineLoc);
00549             lines.push_back(LineInfo(idx,cost));
00550           }
00551         }
00552       }
00553     }
00554   return lines;
00555 }
00556 
00557 
00558 std::vector<V2::LineSegment>  LineGrouping::getAndRemoveLinesNearLoc(Image<std::vector<uint> >& linesIndices,
00559     const Point2D<int> loc, const int radius)
00560 {
00561   std::vector<V2::LineSegment> lines;
00562 
00563   for(int x=loc.i-radius; x<=loc.i+radius; x++)
00564     for(int y=loc.j-radius; y<=loc.j+radius; y++)
00565     {
00566       Point2D<int> lineLoc =Point2D<int>(x,y); 
00567       if (linesIndices.coordsOk(lineLoc) &&
00568           linesIndices.getVal(lineLoc).size() > 0) //We have some lines, add them
00569       {
00570         for(uint j=0; j<linesIndices[lineLoc].size(); j++)
00571         {
00572           uint idx = linesIndices[lineLoc][j];
00573           lines.push_back(itsLines[idx]);
00574         }
00575         linesIndices[lineLoc].clear(); //Remove that line from the list
00576       }
00577     }
00578 
00579   return lines;
00580 
00581 }
00582 
00583 Layout<PixRGB<byte> > LineGrouping::getDebugImage(SimEventQueue& q)
00584 {
00585   Layout<PixRGB<byte> > outDisp;
00586 
00587   Image<PixRGB<byte> > inputImg(itsInputDims,ZEROS); 
00588   for(uint i=0; i<itsLines.size(); i++)
00589   {
00590     V2::LineSegment& ls = itsLines[i];
00591     drawLine(inputImg, Point2D<int>(ls.p1), Point2D<int>(ls.p2), PixRGB<byte>(255,0,0));
00592   }
00593   
00594 
00595   outDisp = inputImg; 
00596 
00597   return outDisp;
00598 
00599 }
00600 
00601 
00602 // ######################################################################
00603 /* So things look consistent in everyone's emacs... */
00604 /* Local Variables: */
00605 /* indent-tabs-mode: nil */
00606 /* End: */
00607 
00608 #endif
00609 
Generated on Sun May 8 08:41:09 2011 for iLab Neuromorphic Vision Toolkit by  doxygen 1.6.3