degate  0.1.2
LineSegmentExtraction.h
Go to the documentation of this file.
00001 #ifndef __LINESEGMENTEXTRACTION_H__
00002 #define __LINESEGMENTEXTRACTION_H__
00003 
00004 #include <Image.h>
00005 #include <ImageManipulation.h>
00006 #include <Line.h>
00007 #include <memory>
00008 #include <fstream>
00009 
00010 #include <boost/foreach.hpp>
00011 
00012 namespace degate{
00013 
00014   // ----------------------------------------------------------------------------------
00015 
00016   /**
00017    * Lineare primitive
00018    */
00019 
00020   class LinearPrimitive : public Line {
00021   public:
00022     enum ORIENTATION {  HORIZONTAL, VERTICAL };
00023 
00024   private:
00025     ORIENTATION orientation;
00026 
00027   public:
00028 
00029     LinearPrimitive(int from_x, int from_y, int to_x, int to_y) :
00030       Line(from_x, from_y, to_x, to_y, 1) {
00031       orientation = abs(from_x - to_x) > abs(from_y - to_y) ? HORIZONTAL : VERTICAL;
00032     }
00033 
00034     ORIENTATION get_orientation() const { return orientation; }
00035 
00036     void print() {
00037       debug(TM, "%d,%d --- %d,%d : %d",
00038             get_from_x(), get_from_y(), get_to_x(), get_to_y(), get_length());
00039     }
00040 
00041   };
00042 
00043   typedef std::shared_ptr<LinearPrimitive> LinearPrimitive_shptr;
00044 
00045   // ----------------------------------------------------------------------------------
00046 
00047   class LineSegment;
00048   typedef std::shared_ptr<LineSegment> LineSegment_shptr;
00049 
00050   /**
00051    * Line segment
00052    */
00053 
00054   class LineSegment : public LinearPrimitive {
00055   private:
00056     std::list<LinearPrimitive_shptr> segments;
00057   public:
00058     LineSegment(LinearPrimitive_shptr lp) :
00059       LinearPrimitive(lp->get_from_x(), lp->get_from_y(), lp->get_to_x(), lp->get_to_y()) {
00060     }
00061 
00062     void merge(LineSegment_shptr seg) {
00063       //std::cout << "merging lines:" << std::endl;
00064       //print();
00065       //seg->print();
00066 
00067       Point a1 = get_p1();
00068       Point a2 = get_p2();
00069       Point b1 = seg->get_p1();
00070       Point b2 = seg->get_p2();
00071 
00072       unsigned int a1b1 = a1.get_distance(b1);
00073       unsigned int a1b2 = a1.get_distance(b2);
00074       unsigned int a2b1 = a2.get_distance(b1);
00075       unsigned int a2b2 = a2.get_distance(b2);
00076 
00077       // +-----------------+       +--------------+
00078       // A1                A2      B1             B2
00079 
00080       if(a2b1 <= a1b1 && a2b1 <= a1b2 && a2b1 <= a2b2) {
00081         set_p1(a1);set_p2(b2);
00082       }
00083 
00084       // +-----------------+       +--------------+
00085       // A2                A1      B1             B2
00086 
00087       else if(a1b1 <= a1b2 && a1b1 <= a2b1 && a1b1 <= a2b2) {
00088         set_p1(a2); set_p2(b2);
00089       }
00090 
00091       // +-----------------+       +--------------+
00092       // A2                A1      B2             B1
00093 
00094       else if(a1b2 <= a1b1 && a1b2 <= a2b1 && a1b2 <= a2b2) {
00095         set_p1(a2);set_p2(b1);
00096       }
00097 
00098       // +-----------------+       +--------------+
00099       // A1                A2      B2             B1
00100 
00101       else if(a2b2 <= a1b1 && a2b2 <= a1b2 && a2b2 <= a2b1) {
00102         set_p1(a1);set_p2(b1);
00103       }
00104 
00105       //std::cout << "Result: " << std::endl;
00106       //print();
00107 
00108     }
00109 
00110   };
00111 
00112 
00113   // ----------------------------------------------------------------------------------
00114 
00115   /**
00116    * Line segment map.
00117    */
00118   class LineSegmentMap {
00119   public:
00120 
00121     typedef std::list<LineSegment_shptr> list_type;
00122     typedef list_type::iterator iterator;
00123     typedef list_type::const_iterator const_iterator;
00124 
00125   private:
00126 
00127     list_type lines;
00128 
00129   public:
00130 
00131     LineSegmentMap() { }
00132 
00133     void erase(iterator iter) {
00134       lines.erase(iter);
00135     }
00136 
00137     size_t size() const {
00138       return lines.size();
00139     }
00140 
00141 
00142     void add(LineSegment_shptr segment) {
00143       lines.push_back(segment);
00144     }
00145 
00146     void erase(LineSegment_shptr segment) {
00147       iterator iter = find(lines.begin(), lines.end(), segment);
00148       if(iter != lines.end())
00149         lines.erase(iter);
00150     }
00151 
00152     iterator begin() { return lines.begin(); }
00153     iterator end() { return lines.end(); }
00154     const_iterator begin() const { return lines.begin(); }
00155     const_iterator end() const { return lines.end(); }
00156 
00157     LineSegment_shptr find_adjacent(LineSegment_shptr elem,
00158                                     unsigned int search_radius_along,
00159                                     unsigned int search_radius_across) const {
00160 
00161       BOOST_FOREACH(LineSegment_shptr elem2, *this) {
00162         if(elem != elem2 && elem2->get_orientation() == elem->get_orientation()) {
00163 
00164           Point a1 = elem->get_p1();
00165           Point a2 = elem->get_p2();
00166           Point b1 = elem2->get_p1();
00167           Point b2 = elem2->get_p2();
00168 
00169 
00170           if(a1.get_distance(b1) <= search_radius_along ||
00171              a1.get_distance(b2) <= search_radius_along ||
00172              a2.get_distance(b1) <= search_radius_along ||
00173              a2.get_distance(b2) <= search_radius_along) {
00174 
00175             if(elem->get_orientation() == LineSegment::HORIZONTAL) {
00176               int _min = std::min(a1.get_y(),
00177                                   std::min(a2.get_y(),
00178                                            std::min(b1.get_y(), b2.get_y())));
00179               int _max = std::max(a1.get_y(),
00180                                   std::max(a2.get_y(),
00181                                            std::max(b1.get_y(), b2.get_y())));
00182               if((unsigned int)(_max - _min) < search_radius_across) return elem2;
00183             }
00184             else {
00185               int _min = std::min(a1.get_x(),
00186                                   std::min(a2.get_x(),
00187                                            std::min(b1.get_x(), b2.get_x())));
00188               int _max = std::max(a1.get_x(),
00189                                   std::max(a2.get_x(),
00190                                            std::max(b1.get_x(), b2.get_x())));
00191 
00192               if((unsigned int)(_max - _min) < search_radius_across) return elem2;
00193             }
00194           }
00195         }
00196       }
00197       return LineSegment_shptr();
00198     }
00199 
00200     void merge(unsigned int search_radius_along,
00201                unsigned int search_radius_across) {
00202 
00203       unsigned int counter = 0;
00204       unsigned int max_rounds = lines.size();
00205       int distance = 1;
00206       int max_distance = search_radius_along;
00207       bool running = lines.size() > 0;
00208 
00209       while(running) {
00210         debug(TM, "#segments: %d", lines.size());
00211         running = false;
00212 
00213         LineSegment_shptr ls = lines.front();
00214         lines.pop_front();
00215 
00216         LineSegment_shptr ls2 = find_adjacent(ls, distance, search_radius_across);
00217         if(ls2 != NULL) {
00218           running = true;
00219           // We could check here if line segments differ in their angles
00220           ls->merge(ls2);
00221 
00222           iterator found = find(lines.begin(), lines.end(), ls2);
00223           assert(found != lines.end());
00224           lines.erase(found);
00225 
00226         }
00227         else {
00228           if(counter++ < max_rounds)
00229             running = true;
00230           else {
00231             if(distance <= max_distance) {
00232               distance++;
00233               counter = 0;
00234               running = true;
00235             }
00236             else running = false;
00237           }
00238         }
00239 
00240         lines.push_back(ls);
00241       }
00242 
00243 
00244     }
00245 
00246     void write() const {
00247       std::ofstream myfile;
00248       myfile.open ("/tmp/example.txt");
00249 
00250       BOOST_FOREACH(LineSegment_shptr e, *this) {
00251         if(e->get_length() > 0) {
00252           myfile << "line "
00253                  << e->get_from_x() << "," << e->get_from_y()
00254                  << " "
00255                  << e->get_to_x() << "," << e->get_to_y()
00256                  << std::endl;
00257         }
00258 
00259       }
00260       myfile.close();
00261     }
00262 
00263   };
00264 
00265   typedef std::shared_ptr<LineSegmentMap> LineSegmentMap_shptr;
00266 
00267   // ----------------------------------------------------------------------------------
00268 
00269   template<typename ImageType>
00270   class LineSegmentExtraction {
00271 
00272   private:
00273 
00274     unsigned int width, height;
00275     std::shared_ptr<ImageType> img;
00276     std::shared_ptr<ImageType> processed;
00277     LineSegmentMap_shptr line_segments;
00278     unsigned int search_radius_along;
00279     unsigned int search_radius_across;
00280     unsigned int border;
00281 
00282   public:
00283   LineSegmentExtraction(std::shared_ptr<ImageType> _img,
00284                         unsigned int _search_radius_along,
00285                         unsigned int _search_radius_across,
00286                         unsigned int _border) :
00287       width(_img->get_width()),
00288       height(_img->get_height()),
00289       img(_img),
00290       processed(new ImageType(width, height)),
00291       line_segments(new LineSegmentMap()),
00292       search_radius_along(_search_radius_along),
00293       search_radius_across(_search_radius_across),
00294       border(_border) {
00295 
00296       copy_image<ImageType, ImageType>(processed, img);
00297     }
00298 
00299     LineSegmentMap_shptr run() {
00300       extract_primitives();
00301       line_segments->merge(search_radius_along, search_radius_across);
00302       line_segments->write();
00303       return line_segments;
00304     }
00305 
00306   private:
00307     void extract_primitives() {
00308       for(unsigned int y = border; y < height - border; y++)
00309         for(unsigned int x = border; x < width - border; x++) {
00310 
00311           if(processed->get_pixel(x, y) > 0) {
00312             LinearPrimitive_shptr lp = trace_line_primitive(processed, x, y);
00313             if(lp != NULL) {
00314               LineSegment_shptr segment(new LineSegment(lp));
00315               //segment->print();
00316               line_segments->add(segment);
00317             }
00318           }
00319         }
00320     }
00321 
00322     LinearPrimitive_shptr trace_line_primitive(std::shared_ptr<ImageType> img,
00323                                                unsigned int x, unsigned int y) {
00324 
00325       LinearPrimitive_shptr segment;
00326 
00327       unsigned int _x = x;
00328       while(_x < width && img->get_pixel(_x, y) > 0) _x++;
00329 
00330       if(_x - x > 1) {
00331         segment = LinearPrimitive_shptr(new LinearPrimitive(x, y, _x, y));
00332         _x = x;
00333         while(_x < width && img->get_pixel(_x, y) > 0) {
00334           img->set_pixel(_x, y, 0);
00335           _x++;
00336         }
00337         return segment;
00338       }
00339 
00340       unsigned int _y = y;
00341       while(_y < height && img->get_pixel(x, _y) > 0) _y++;
00342 
00343       if(_y - y > 1) {
00344         segment = LinearPrimitive_shptr(new LinearPrimitive(x, y, x, _y));
00345         _y = y;
00346         while(_y < height && img->get_pixel(x, _y) > 0) {
00347             img->set_pixel(x, _y, 0);
00348             _y++;
00349           }
00350           return segment;
00351       }
00352 
00353       return segment;
00354     }
00355 
00356   };
00357 }
00358 
00359 #endif