Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

# Modules/ImageProcessor/ImageProcessorTools/SegmentationTools.h

Go to the documentation of this file.

    00001 /**
    00002 * @file SegmentationTools.h
    00003 * Declaration of file SegmentationTools.
    00004 *
    00005 * @author <A href=mailto:damdāfree.fr>Damien DEOM</A>
    00006 */
    00007
    00008 #ifndef _SEGMENTATION_TOOLS_
    00009 #define _SEGMENTATION_TOOLS_
    00010
    00011
    00012
    00013 #include "Tools/Math/Geometry.h"
    00014 #include "Tools/Math/Vector2.h"
    00015 #include "Tools/ColorClasses.h"
    00016 #include "MSH2004EdgeDetection.h"
    00017
    00018
    00019 typedef Vector2<int> point;
    00020
    00021 typedef Vector2<double> direction;
    00022
    00023 inline point mil(point& v1,point& v2) {
    00024   return point ((v1.x+v2.x) / 2,(v1.y+v2.y) / 2);
    00025 };
    00026
    00027
    00028 template <class T> class listed {
    00029 protected:
    00030
    00031   T* next;
    00032
    00033 public:
    00034   listed(): next(0) {}
    00035   //~listed() {if(next)delete next;}
    00036
    00037   T* getNext(){return next;}
    00038
    00039   void setNext(T* f) {next = f;}
    00040
    00041   void insert(T* i) {
    00042     if (!i) return;
    00043     T* tmp = next;
    00044     next = i;
    00045     i->setNext(tmp);
    00046   }
    00047
    00048   void swapNext(T* toSwapWith) {
    00049
    00050     if (!(next && toSwapWith)) return;
    00051     T* tmp = this->next;
    00052     T* tmp2 = toSwapWith->next->next;
    00053
    00054     this->next = toSwapWith->next;
    00055     toSwapWith->next->next = tmp;
    00056     toSwapWith->next = tmp2;
    00057
    00058   }
    00059
    00060 };
    00061
    00062
    00063 struct figure : public listed<figure> {
    00064
    00065   figure() : listed<figure>() {}
    00066
    00067   virtual unsigned short getId() = 0;
    00068   virtual point toConsider() = 0;
    00069   virtual double size() {return 0;}
    00070 };
    00071
    00072
    00073 class edge : public figure {
    00074 private:
    00075   point pt;
    00076   unsigned short id;
    00077 public:
    00078
    00079   edge(point& p, unsigned short i) : figure(), pt(p) , id(i) {}
    00080   edge(int& x, int& y, unsigned short i) :  figure(), id(i) {
    00081
    00082     pt.x = x; pt.y = y;
    00083   }
    00084
    00085   point toConsider() {;return pt;}
    00086   unsigned short getId() {return id;}
    00087
    00088 };
    00089
    00090
    00091
    00092 struct LinePair2 : public figure {
    00093   virtual point pt1() = 0;
    00094   virtual point pt2() = 0;
    00095   virtual direction getDirection() = 0;
    00096 };
    00097
    00098 class horLinePair2 : public LinePair2 {
    00099
    00100   point p1;
    00101   int p2x;
    00102
    00103   point center;
    00104 public:
    00105   horLinePair2(point p1, int p2x)  {
    00106     this->p1 = p1;
    00107     this->p2x = p2x;
    00108     center = point((p1.x+p2x)/2, p1.y);
    00109   }
    00110
    00111   horLinePair2(point p1, point p2)  {
    00112     this->p1 = p1;
    00113     this->p2x = p2.x;
    00114     center = point((p1.x+p2.x)/2, p1.y);
    00115   }
    00116
    00117   unsigned short getId() {return (unsigned short)p1.y;}
    00118   point toConsider() {return center;}
    00119   point pt1() {return p1;}
    00120   point pt2() {return point(p2x, p1.y);}
    00121   double size() {return (double) (p2x - p1.x);}
    00122   direction getDirection() {return direction(1,0);}
    00123
    00124
    00125 };
    00126
    00127 struct extLinePair2 : public LinePair2 {
    00128
    00129   point p1, p2;
    00130   point center;
    00131   unsigned short id;
    00132
    00133   extLinePair2(point& p1, point& p2, unsigned short id)  {
    00134     this->p1 = p1;
    00135     this->p2 = p2;
    00136     this->id = id;
    00137     center = mil(p1, p2);
    00138   }
    00139
    00140   point pt1()  {return p1;}
    00141   point pt2()  {return p2;}
    00142   double size() {return (p2 - p1).abs();}
    00143   point toConsider() {return center;}
    00144   unsigned short getId() {return id;}
    00145   direction getDirection() {
    00146     return direction((double)(p2.x - p1.x),(double)(p2.y - p1.y));
    00147   }
    00148
    00149
    00150 };
    00151
    00152 struct coloredLinePair2 : public extLinePair2 {
    00153   colorClass color;
    00154
    00155   coloredLinePair2(point& v1,point& v2,unsigned short id, colorClass c) :
    00156     extLinePair2(v1, v2, id), color(c) {}
    00157
    00158 };
    00159
    00160
    00161
    00162 struct coloredHorLinePair2 : public horLinePair2 {
    00163
    00164   colorClass color;
    00165
    00166   coloredHorLinePair2(point& v1,point& v2, colorClass c) :
    00167     horLinePair2(v1, v2), color(c) {}
    00168
    00169 };
    00170
    00171
    00172 template <class T> class slist {
    00173
    00174 private:
    00175   unsigned int size;
    00176   T* first, *last;
    00177
    00178 public:
    00179
    00180   class iterator {
    00181
    00182   private:
    00183
    00184     T* elt;
    00185
    00186   public:
    00187
    00188     iterator(T* l = 0) : elt(l) {}
    00189     //~iterator() {delete elt;}
    00190
    00191     T* get() const {return elt;}
    00192     T* getNext() const {return elt == 0 ? 0 : elt->getNext();}
    00193     bool end() const {return  elt == 0;}
    00194
    00195     T* operator++() {
    00196
    00197       if (end()) return 0;
    00198       elt= elt->getNext();
    00199       return elt;
    00200     }
    00201
    00202     T* operator++(int) {
    00203       if (end()) return 0;
    00204       T* old = elt;
    00205       elt = elt->getNext();
    00206       return old;
    00207     }
    00208
    00209     T*operator+=(const int n) {
    00210       T* tmp = elt;
    00211       int i;
    00212       for (i = 0; i<n;++i)
    00213         if (tmp) tmp = tmp->getNext();
    00214         else return 0;
    00215
    00216       elt = tmp;
    00217       return elt;
    00218     }
    00219
    00220   };
    00221
    00222
    00223   T* front()  {return first;}
    00224   T* back()  {return last;}
    00225   void setLast(T* l) {last = l;}
    00226
    00227   void cutFront() { first = last = 0;size = 0;}
    00228
    00229   slist() : size(0), first(0), last(0){}
    00230   ~slist() {delete first, delete last;}
    00231
    00232   void push_front(T* lp) {
    00233     if (lp==0) return;
    00234     if (!last) last = lp;
    00235
    00236     lp->setNext(first);
    00237     first = lp;
    00238     ++size;
    00239   }
    00240
    00241   void push_back(slist<T>& lst) {
    00242     if (last) {
    00243       last->setNext(lst.front());
    00244       last = lst.back();
    00245     } else {
    00246       first = lst.front();
    00247       last = lst.back();
    00248     }
    00249     size+= lst.getSize();
    00250     lst.cutFront();
    00251   }
    00252
    00253   unsigned getSize() const {return size;}
    00254   bool empty() {return size==0;}
    00255   void incSize(unsigned int n) {if (n>0) size+=n;}
    00256
    00257   void clear() {
    00258
    00259     while (first) {
    00260       T* tmp = first->getNext();
    00261       delete first;
    00262       first = tmp;
    00263     }
    00264
    00265     last = 0;
    00266     size = 0;
    00267
    00268   }
    00269
    00270
    00271   T* pop_front() {
    00272
    00273     if (!first) return 0;
    00274     T* tmp = first->getNext();
    00275     delete first;
    00276     first = tmp;
    00277     if (size==1) last = first;
    00278     --size;
    00279     return first;
    00280   }
    00281
    00282   void insert(T*  pos, T* i) {
    00283     if (!pos) return;
    00284     T* tmp = pos->getNext();
    00285
    00286     if (!tmp) {
    00287       pos->setNext(i);
    00288       i->setNext(0);
    00289       last = i;
    00290     } else {
    00291       pos->setNext(i);
    00292       i->setNext(tmp);
    00293     }
    00294
    00295     if (pos==last) last = i;
    00296   }
    00297
    00298   void erase(T* e) {
    00299
    00300     if (e->getNext()==last) last = e;
    00301
    00302     T* n = e->getNext()->getNext();
    00303     delete e->getNext();
    00304     e->setNext(n);
    00305     --size;
    00306
    00307   }
    00308
    00309 };
    00310
    00311
    00312 struct lineOnField : public listed<lineOnField> {
    00313
    00314   point p1, p2;
    00315
    00316   lineOnField(point& p1, point& p2) : listed<lineOnField>() {
    00317     this->p1 = p1;
    00318     this->p2 = p2;
    00319   }
    00320
    00321   point pt1()  {return p1;}
    00322   point pt2()  {return p2;}
    00323   double size() {return (p2 - p1).abs();}
    00324
    00325   Geometry::Line getLine() {
    00326
    00327     Geometry::Line l;
    00328
    00329     l.base = Vector2<double> ((double)p1.x, (double)p1.y);
    00330     l.direction = Vector2<double> ((double)p2.x, (double)p2.y) - l.base;
    00331
    00332     return l;
    00333
    00334   }
    00335
    00336 };
    00337
    00338
    00339
    00340 /* adds a new scan line between two line pairs */
    00341
    00342
    00343 inline bool DoubleScanLinesNumber(slist<figure>& lst, MSH2004EdgeDetection& edgeScanner) {
    00344
    00345   if (lst.getSize()<2) return false;
    00346
    00347   edgeScanner.threshold = 12;
    00348
    00349   int stepY;
    00350
    00351   slist<figure>::iterator it(lst.front());
    00352
    00353   unsigned int c = 0;
    00354
    00355   do {
    00356
    00357     LinePair2 *lp = (LinePair2 *)it.get();
    00358     LinePair2 *next = (LinePair2 *)lp->getNext();
    00359     int f1x = lp->pt1().x,
    00360       f2x = lp->pt2().x;
    00361     int n1x = next->pt1().x,
    00362       n2x = next->pt2().x;
    00363     int n1y = next->pt1().y,
    00364       f1y = lp->pt1().y;
    00365
    00366     stepY = (int)(n1y - f1y)/2;
    00367
    00368     //  OUTPUT(idText,text, "step " << stepY);
    00369
    00370     if (n1x<f2x && n2x>f1x /*&& n2x-n1x <20 */&& n1y!=f1y && stepY>0) {
    00371
    00372       int leftCorner = (f1x<n1x) ? f1x : n1x,
    00373         rightCorner = (f2x>n2x) ? f2x : n2x;
    00374
    00375       point center ((int)(leftCorner+rightCorner)/2, f1y+stepY);
    00376
    00377       DOT(imageProcessor_ground, center.x,center.y,Drawings::red, Drawings::white);
    00378
    00379
    00380       point left = center, right = center;
    00381
    00382       edgeScanner.scanWest(left.x,left.y);
    00383       edgeScanner.scanEast(right.x,right.y);
    00384
    00385       extLinePair2* lp = new extLinePair2(left,right,0);
    00386
    00387       LINE(imageProcessor_ground,
    00388           lp->pt1().x,lp->pt1().y, lp->pt2().x,lp->pt2().y,
    00389           0.5, Drawings::ps_solid, Drawings::red);
    00390
    00391       if ((lp->pt2().x - lp->pt1().x)<=3*(f2x-f1x)) {
    00392         it.get()->insert(lp);++c;
    00393       }
    00394
    00395     }
    00396
    00397
    00398
    00399   } while (++it && !it.end());
    00400
    00401   lst.incSize(c);
    00402   return true;
    00403
    00404 };
    00405
    00406
    00407 inline figure* getMin (figure * lp) {
    00408
    00409   figure * min = lp, *cur;
    00410   slist<figure>::iterator it(lp);
    00411
    00412   double d_min = 10000.0;
    00413   unsigned short cur_id;
    00414
    00415   do {
    00416
    00417     cur = it.get();
    00418
    00419     if (!cur->getNext()) break;
    00420
    00421     double d =Geometry::distance(lp->toConsider(), cur->getNext()->toConsider());
    00422     cur_id = cur->getId();
    00423
    00424     if (d<d_min) { d_min = d; min = cur;}
    00425
    00426     //OUTPUT(idText,text, "id = " << cur_id);
    00427
    00428   } while (++it /*&& it.get()->getId()==cur_id*/);
    00429
    00430   return min;
    00431 }
    00432
    00433
    00434 /* join the nearest LinePairs in order to make the interpretation of the shape possible */
    00435
    00436 inline void createLinearSegment(slist<figure>& lst) {
    00437
    00438   if (lst.getSize()<3)return;
    00439
    00440   slist<figure>::iterator start(lst.front());
    00441
    00442   do {
    00443     //if (start.get()->getId() == start.getNext()->getId()) {
    00444       figure* min = getMin(start.get());
    00445       if (min != start.get()) start.get()->swapNext(min);
    00446     //}
    00447
    00448       //OUTPUT(idText,text, "min : " << min->toConsider().x << " " <<min->toConsider().y);
    00449     //}
    00450
    00451   } while (++start && start.getNext());
    00452
    00453   //lst.setLast(start.get());
    00454 }
    00455
    00456 /*
    00457 inline double AngleBetweenLines(lineOnField* l1, lineOnField* l2)  {
    00458
    00459   Vector2<double> pt1();
    00460   Geometry::getIntersectionOfLines(l1->line,l2->line,pt1());
    00461   Vector2<double> v2(l1->line.direction.x,l1->line.direction.y);
    00462   double d =  Geometry::getDistanceToLine(l2->line,v2);
    00463
    00464   return asin(d/(l1->line.direction-l1->line.base).abs());
    00465 }
    00466
    00467 */
    00468
    00469
    00470
    00471 /** Gives a number between 0 and 360 with the same order as v.angle()*/
    00472 inline double theta2(point v1, point v2){
    00473   double t = 0;
    00474   int dx = v1.x - v2.x;
    00475   int dy = v1.y - v2.y;
    00476   int ax = abs(dx);
    00477   int ay = abs(dy);
    00478   if (dx == 0 && dy == 0) t = 0;
    00479   else t = (double)dy /(double)(ax + ay);
    00480   if (dx < 0) t = 2 - t;
    00481   else if (dy < 0) t = 4 + t;
    00482   return t*90; // multiplication with 90 is not really needed for correct ordering
    00483 }
    00484
    00485 inline double theta2(lineOnField* l1, lineOnField* l2) {
    00486
    00487   double angle1 = theta2(l1->pt1(),l1->pt2());
    00488   double angle = theta2(l2->pt1(), l2->pt2()) - angle1;
    00489
    00490   while (angle<0) angle+=180;
    00491
    00492   return angle;
    00493
    00494 }
    00495
    00496 inline double AngleRelativeToHorizontal(const point & pt1, const point& pt2) {
    00497   double d1 =  abs(pt2.x - pt1.x);
    00498   double d2 =  (pt2 - pt1).abs();
    00499   return acos(d1/d2);
    00500 }
    00501
    00502
    00503
    00504
    00505 #endif
    00506