Modules/ImageProcessor/ImageProcessorTools/SegmentationTools.h

Go to the documentation of this file.

/** 
* @file SegmentationTools.h
* Declaration of file SegmentationTools.h
*
* @author <A href=mailto:damd@free.fr>Damien DEOM</A>
*/


#ifndef _SEGMENTATION_TOOLS_
#define _SEGMENTATION_TOOLS_


/**
* @class file SegmentationTools.h
* This is a utility class for image processing.
* A special slist has been defined :it can be used in other domains
* than the little world of image processing ...
*/

#include "Tools/Math/Geometry.h"
#include "Tools/Math/Vector2.h"
#include "Tools/ColorClasses.h"

typedef Vector2<int> point;
typedef Vector2<double> direction;

struct LinePair2;

///////////////////////////////////////////////////////////
///               geometrical stuff
///////////////////////////////////////////////////////////


inline point mil(point& v1,point& v2) {
  return point ((v1.x+v2.x) / 2,(v1.y+v2.y) / 2);
};



/*! Gives a number between 0 and 360 with the same order as v.angle()*/
inline double theta2(point v1, point v2){
  double t = 0;
  int dx = v1.x - v2.x;
  int dy = v1.y - v2.y;
  int ax = abs(dx);
  int ay = abs(dy);
  if (dx == 0 && dy == 0) t = 0;
  else t = (double)dy /(double)(ax + ay);
  if (dx < 0) t = 2 - t;
  else if (dy < 0) t = 4 + t;

  return t*90;
}



/** 
*same principle as theta2, but using trigonoetric 
*functions (also more time consuming)
*/
inline double AngleRelativeToHorizontal(const point & pt1, const point& pt2) {
  double d1 =  abs(pt2.x - pt1.x);
  double d2 =  (pt2 - pt1).abs();
  if ((d2 == 0) || (d1/d2 < -1) || (d1/d2 > 1))
    return 0;
  else
    return acos(d1/d2);
}




/**
* implementation of slist : all the objects to be listed must
* derive from the template class "listed" (use the name of the class
* as template parameter for normal use) 
*/


template <class T> struct listed {

  T* next;

  listed(): next(0) {}

  ~listed() {}

  T* getNext() const {return next;}

  void insert(T* i) {
    if (!i) return;
    T* tmp = next;
    next = i;
    i->setNext(tmp);
  }

  void swapNext(T* toSwapWith) {  // swap the element after next with toSwapWith
    
    if (!(next && toSwapWith && toSwapWith->next)) return;
    T* tmp = this->next;
    T* tmp2 = toSwapWith->next->next;

    this->next = toSwapWith->next;
    toSwapWith->next->next = tmp;
    toSwapWith->next = tmp2;
  }

};


/*! the slist itself*/
template <class T> class slist {

private:
  unsigned int size;
  T* first, *last;

public:

  class iterator {

  private:
    T* elt;
  public:
  
    iterator(T* l = 0) : elt(l) {}

    T* operator++() {
      if (!elt) return 0;
      elt= elt->next;
      return elt;
    }
    T* operator++(int) {
      if (!elt) return 0;
      T* old = elt;
      elt = elt->next;
      return old;
    }
    T*operator+=(int n) {
      T* tmp = elt;
      int i;
      for (i = 0; i<n;++i) 
        if (tmp) tmp = tmp->next;
        else return 0;
      elt = tmp;
      return elt;
    }
    T* operator = (T* e) {
      elt = e;
      return elt;
    }
    bool operator != (const T* e) const {
      return (elt != e);
    }

    T* operator ->() const {return elt;}
    T* operator *() const {return elt;}
    bool end() {return !elt;}
  };

  T* front() const {return first;}
  T* back() const {return last;}
  void setLast(T* l) {last = l;}
  
  void cutFront() { first = last = 0;size = 0;}

  slist() : size(0), first(0), last(0){}
  
  void push_front(T* lp) {
    if (!lp) return;
    if (!last) last = lp; 

    lp->next = first;
    first = lp;
    ++size;
  }

  void push_back(const T* lp) {
    if (!lp) return;
    if (!first) {first = last = lp;} else last->next = lp; 
    last = lp;
    ++size;
  }

  void push_back(slist<T>& lst) {
    if (last) {
      last->next = lst.front();
      last = lst.back();
    } else {
      first = lst.front();
      last = lst.back();
    }
    size+= lst.getSize();
    lst.cutFront();
  }

  unsigned getSize() const {return size;}
  bool empty() {return size==0;}

  void clear() {
    while (first) {
      T* tmp = first->next;
      delete first;
      first = tmp;
    }
    last = 0;
    size = 0;
  }

  T* pop_front() {
    if (!first) return 0;
    T* tmp = first->next;
    delete first;
    first = tmp;
    if (size==1) last = first;
    --size;
    return first;
  }

  void insert(T*  pos, T* i) {
    if (!pos) return;
    T* tmp = pos->next;

    if (!tmp) {
      pos->next = i;
      i->next = 0;
      last = i;
    } else {
      pos->next = i;
      i->next = tmp;
    }
    if (pos==last) last = i;
    ++size;
  }

  void erase(T* e) {

    if (e->next = last) last = e;
    T* n = e->next->next;

    delete e->next;
    e->next = n;
    --size;
  }

};



/**
* definition of an edge and a linePair : very convenient for mixing both 
* in a list.
* If you only want to use linePairs, please use the
* LinePair2 struct defined below
*/

struct figure : public listed<figure> {


  figure() : listed<figure>() {}
  virtual ~figure() {}

  virtual unsigned short getId() = 0;
  virtual point toConsider() = 0;
  virtual double size() {return 0;}
};

class edge : public figure {
private:
  point pt;
  unsigned short id;
public:

  edge(point& p, unsigned short i) : figure(), pt(p) , id(i) {}
  edge(int& x, int& y, unsigned short i) :  figure(), id(i) {
    pt.x = x; pt.y = y;
  }

  point toConsider() {;return pt;}
  unsigned short getId() {return id;}
};

struct LinePair : public figure {
  virtual point pt1() = 0;
  virtual point pt2() = 0;
  virtual direction getDirection() = 0;
};

class horLinePair : public LinePair {
  point p1;
  int p2x;
public:

  horLinePair(point p1, int p2x)  {
    this->p1 = p1;
    this->p2x = p2x;
  }

  ~horLinePair() {}

  horLinePair(point& p1, point& p2)  {
    this->p1 = p1;
    this->p2x = p2.x;
  }

  unsigned short getId() {return (unsigned short)p1.y;}
  point toConsider() {return point((p1.x+p2x)/2, p1.y);}
  point pt1() {return p1;}
  point pt2() {return point(p2x, p1.y);}
  double size() {return (double) (p2x - p1.x);}
  direction getDirection() {return direction(1,0);}


};



struct extLinePair : public LinePair {

  point p1, p2;
  unsigned short id;

  extLinePair(point& p1, point& p2, unsigned short id = 0)  {
    this->p1 = p1;
    this->p2 = p2;
    this->id = id;
  }

  extLinePair()  {
    this->p1 = point();
    this->p2 = point();
    this->id = 0;
  }

  point pt1() {return p1;}
  point pt2() {return p2;}
  double size() {return (p2 - p1).abs();}

  point toConsider() {return mil(p1, p2);}

  unsigned short getId() {return id;}
  direction getDirection() {
    return direction((double)(p2.x - p1.x),(double)(p2.y - p1.y));
  }


};



struct LinePair2 : public listed<LinePair2> {


  point p1, p2;

  LinePair2(point& p1, point& p2) : listed<LinePair2>() {
    this->p1 = p1;
    this->p2 = p2;
  }

  
  /** defines the default order for LinePairs.
  *order is lexigographical in v1 (v1.y,v1.x).
  */

  bool operator <(const LinePair2& other){
    return p1.y < other.p1.y || 
         p1.y == other.p1.y && p1.x < other.p1.y ;
  }

  virtual colorClass getColor() {return noColor;}
  virtual double getLength() {return (p2 - p1).abs();}

};

/*
* same as the LinePair2, exept the length: the value is stored
* in case this parameter is frequently calcultaed 
*/

class LinePair3 : public LinePair2 {
private:
  double length;
  bool updated;

public:

  void setP1(point& p) {
    updated = false;
    p1 = p;
  }
  void setP2(point& p) {
    updated = false;
    p2 = p;
  }


  LinePair3(point& p1, point& p2) : LinePair2(p1, p2), length(0), updated(false) {}

  void updateLength() { 
    length = (p2 - p1).abs();
    updated = true;
  }
  double getLength() {
    if (!updated) updateLength();
    return length;
  }

};


struct coloredLinePair2 : public LinePair2 {
private :
  colorClass color;
public:


  coloredLinePair2(point& v1,point& v2, colorClass c = noColor) :
    LinePair2(v1, v2), color(c) {}

  colorClass getColor() {return color;}
};



/*! calculate the angle between two lines using theta2*/

inline double theta2(LinePair2* l1,LinePair2* l2) {

  double angle1 = theta2(l1->p1,l1->p2);
  double angle = theta2(l2->p1, l2->p2) - angle1;

  while (angle<0) angle+=360;

  return angle;

}

/*
* Line detection related algorithms
*/


/**
*  finds the nearest point starting from lp
*  @param lp the starting point
*  @return the nearest point
*/
inline figure* getMin (figure * lp) {
  
  figure * min = lp->getNext();

  if (!min) return 0;

  slist<figure>::iterator it = min;

  double d_min = Geometry::distance(
    lp->toConsider(),
    it->toConsider());

  unsigned short cur_id = min->getId();

  while(++it && cur_id == it->getId()) {
    
    double d = Geometry::distance(
      lp->toConsider(),
      it->toConsider());

    if (d <d_min) {
      d_min = d;
      min = *it;
    }
  } 

  return min;
}


/**
* join the nearest LinePairs in order to make the
* interpretation of the shape possible 
*/

inline void createLinearSegment(slist<figure>& lst) {

  if (lst.getSize()<3)return;
  slist<figure>::iterator start = lst.front();

  do {
    figure* min = getMin(*start);
    if (min != *start) start->swapNext(min);
  } while (++start && start->getNext());

  lst.setLast(*start);
}




/* ! return the middle point of the line*/
inline Vector2<double> mil(LinePair2& lp)  {
  return Vector2<double> ((lp.p1.x+lp.p2.x)/2, (lp.p1.y+lp.p2.y)/2);
};

/*! transform a line pair into a line defined into the Geometry library */ 
inline Geometry::Line makeLine(LinePair2* lp) {
  Geometry::Line l;

  l.base = Vector2<double> ((double)lp->p1.x, (double)lp->p1.y);
  l.direction = Vector2<double> ((double)lp->p2.x, (double)lp->p2.y) - l.base;

  return l;
};


#endif

/*
 * Change log :
 * $Log: SegmentationTools.h,v $
 * Revision 1.4  2004/09/07 16:01:15  deom
 * Documentation corrected
 *
 * Revision 1.3  2004/09/02 09:30:53  deom
 * commented segmentation tools
 *
 * Revision 1.15  2004/08/14 08:39:20  deom
 * optimized
 *
 * Revision 1.14  2004/06/17 14:18:22  kerdels
 * fixed bug in rfieldspecialist, changed threshold for bridge-detection
 *
 * Revision 1.13  2004/06/17 11:55:31  serwe
 * added changelog
 *
 */

---