00001
00002 /***************************************************************************
00003  *  rht_lines.cpp - Implementation of a lines shape finder
00004  *                   with Randomized Hough Transform
00005  *
00006  *  Generated: Mon Sep 26 2005 09:52:00
00007  *  Copyright  2005  Tim Niemueller [www.niemueller.de]
00008  *                   Hu Yuxiao      <Yuxiao.Hu@rwth-aachen.de>
00009  *
00010  ****************************************************************************/
00011
00012 /*  This program is free software; you can redistribute it and/or modify
00013  *  it under the terms of the GNU General Public License as published by
00014  *  the Free Software Foundation; either version 2 of the License, or
00015  *  (at your option) any later version. A runtime exception applies to
00016  *  this software (see LICENSE.GPL_WRE file mentioned below for details).
00017  *
00018  *  This program is distributed in the hope that it will be useful,
00019  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00020  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00021  *  GNU Library General Public License for more details.
00022  *
00023  *  Read the full text in the LICENSE.GPL_WRE file in the doc directory.
00024  */
00025
00026 #include <utils/math/angle.h>
00027 #include <sys/time.h>
00028 #include <models/shape/rht_lines.h>
00029
00030 using namespace std;
00031 using namespace fawkes;
00032
00033 #define TEST_IF_IS_A_PIXEL(x) ((x)>230)
00034 
00035 
00036 /** @class RhtLinesModel <models/shape/rht_lines.h>
00037  * Randomized Hough-Transform line model.
00038  */
00039 
00040 /** Constructor. */
00041 RhtLinesModel::RhtLinesModel(float max_time, int max_iter, unsigned int nr_candidates, float angle_from, float angle_range, int r_scale, float min_votes_ratio, int min_votes)
00042 {
00043   RHT_MAX_TIME =  max_time; // max_time is given in ms but we need microseconds, thus * 1000
00044   RHT_MAX_ITER =  max_iter; // Maximal number of iterations.
00045
00046   RHT_NR_CANDIDATES   = nr_candidates;
00047
00048   RHT_R_SCALE         = r_scale;
00049
00050   RHT_MIN_VOTES       = min_votes;
00051   RHT_MIN_VOTES_RATIO = min_votes_ratio;
00052
00053   RHT_ANGLE_FROM      = angle_from -  (floor(angle_from  / (2 * M_PI )) * (2 * M_PI));
00054   RHT_ANGLE_RANGE     = angle_range - (floor(angle_range / (2 * M_PI )) * (2 * M_PI));
00055   RHT_ANGLE_INCREMENT = RHT_ANGLE_RANGE / RHT_NR_CANDIDATES;
00056 }
00057
00058 
00059 /** Destructor. */
00060 RhtLinesModel::~RhtLinesModel(void)
00061 {
00062   m_Lines.clear();
00063 }
00064
00065 /**************************************************************
00066  * In this function we implement a lines detection algorithm
00067  **************************************************************/
00068 int
00069 RhtLinesModel::parseImage( unsigned char *buf,
00070                            ROI *roi            )
00071 {
00072   unsigned char *buffer = roi->get_roi_buffer_start(buf);
00073
00074   struct timeval   start, now;
00075
00076   // clear the accumulator
00077   accumulator.reset();
00078
00079   // clear all the remembered lines
00080   m_Lines.clear();
00081
00082   // First, find all the edge pixels,
00083   // and store them in the 'pixels' vector.
00084   unsigned char *line_start = buffer;
00085   unsigned int     x, y;
00086   vector<point_t>  pixels;
00087
00088   gettimeofday(&start, NULL);
00089
00090   for (y = 0; y < roi->height; ++y) {
00091     for (x = 0; x < roi->width; ++x) {
00092       if (TEST_IF_IS_A_PIXEL(*buffer)) {
00093         point_t pt={x, y};
00094         pixels.push_back(pt);
00095       }
00096       // NOTE: this assumes roi->pixel_step == 1
00097       ++buffer;
00098     }
00099     line_start += roi->line_step;
00100     buffer = line_start;
00101   }
00102
00103   // Then perform the RHT algorithm
00104   point_t p;
00105   float r, phi; // used for line representation
00106   vector< point_t >::iterator pos;
00107   int num_iter = 0;
00108   if (pixels.size() == 0) {
00109     // No edge pixels found => no lines
00110     return 0;
00111   }
00112
00113
00114
00115   do {
00116     // in order to prevent float exception, pixels.size() must be non-zero
00117     if (pixels.size() > 0) {
00118       int ri = rand() % pixels.size();
00119       pos = pixels.begin() + ri;
00120       p = *pos;
00121       pixels.erase(pos);
00122
00123       for (unsigned int i = 0; i < RHT_NR_CANDIDATES; ++i) {
00124         phi = RHT_ANGLE_FROM + i * RHT_ANGLE_INCREMENT;
00125         r   = p.x * cos( phi )  +   p.y * sin( phi );
00126
00127         int angle = (int)round(fawkes::rad2deg( phi ));
00128
00129         accumulator.accumulate( (int)round(r / RHT_R_SCALE),
00130                                 angle,
00131                                 0 );
00132       }
00133
00134       gettimeofday(&now, NULL);
00135
00136       diff_sec  = now.tv_sec  - start.tv_sec;
00137       diff_usec = now.tv_usec - start.tv_usec;
00138       if (diff_usec < 0) {
00139         diff_sec  -= 1;
00140         diff_usec += 1000000;
00141       }
00142
00143       f_diff_sec = diff_sec + diff_usec / 1000000.f;
00144
00145     } // end if
00146   } while( ( ++num_iter < RHT_MAX_ITER) &&
00147            ( f_diff_sec < RHT_MAX_TIME) );
00148
00149   // Find the most dense region, and decide on the lines
00150   int max, r_max, phi_max, any_max;
00151   max = accumulator.getMax(r_max, phi_max, any_max);
00152
00153   roi_width = roi->width;
00154   roi_height = roi->height;
00155
00156   LineShape l(roi->width, roi->height);
00157   l.r   = r_max * RHT_R_SCALE;
00158   l.phi = phi_max;
00159   l.count = max;
00160   m_Lines.push_back( l );
00161
00162   return 1;
00163 }
00164
00165
00166 int
00167 RhtLinesModel::getShapeCount(void) const
00168 {
00169   return m_Lines.size();
00170 }
00171
00172 LineShape *
00173 RhtLinesModel::getShape(int id) const
00174 {
00175   if (id < 0 || (unsigned int)id >= m_Lines.size()) {
00176     return NULL;
00177   } else {
00178     return const_cast<LineShape*>(&m_Lines[id]); // or use const Shape* def?!...
00179   }
00180 }
00181
00182
00183 LineShape *
00184 RhtLinesModel::getMostLikelyShape(void) const
00185 {
00186   if (m_Lines.size() == 0) {
00187     return NULL;
00188   } else if (m_Lines.size() == 1) {
00189     return const_cast<LineShape*>(&m_Lines[0]); // or use const Shape* def?!...
00190   } else {
00191     int cur=0;
00192     for (unsigned int i=1; i < m_Lines.size(); ++i) {
00193       if (m_Lines[i].count > m_Lines[cur].count) {
00194         cur = i;
00195       }
00196     }
00197     return const_cast<LineShape*>(&m_Lines[cur]); // or use const Shape* definition?!...
00198   }
00199 }
00200
00201 
00202 /** Get shapes.
00203  * @return vector of shapes
00204  */
00205 vector< LineShape > *
00206 RhtLinesModel::getShapes()
00207 {
00208   int votes = (int)(accumulator.getNumVotes() * (float)RHT_MIN_VOTES_RATIO);
00209
00210   if ( RHT_MIN_VOTES > votes ) {
00211     votes = RHT_MIN_VOTES;
00212   }
00213
00214   vector< LineShape > * rv = new vector< LineShape >();
00215
00216   vector< vector< int > > *rht_nodes = accumulator.getNodes( votes );
00217   vector< vector< int > >::iterator node_it;
00218
00219   LineShape l(roi_width, roi_height);
00220
00221   for (node_it = rht_nodes->begin(); node_it != rht_nodes->end(); ++node_it) {
00222     l.r   = node_it->at(0) * RHT_R_SCALE;
00223     l.phi = node_it->at(1);
00224     // we do not use val 2 here!
00225     l.count = node_it->at(3);
00226     l.calcPoints();
00227     rv->push_back( l );
00228   }
00229
00230   return rv;
00231 }