00001
00002 /***************************************************************************
00003  *  ht_lines.cpp - Implementation of a lines shape finder
00004  *                 with Randomized Hough Transform
00005  *
00006  *  Generated: Fri Jan 13 2006 12:42:53
00007  *  Copyright  2005-2006  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 <cmath>
00027 #include <sys/time.h>
00028 #include <models/shape/ht_lines.h>
00029 #include <utils/math/angle.h>
00030
00031 using namespace std;
00032 using namespace fawkes;
00033
00034 #define TEST_IF_IS_A_PIXEL(x) ((x)>230)
00035 
00036 /** @class HtLinesModel <models/shape/ht_lines.h>
00037  * Hough-Transform line matcher.
00038  */
00039 
00040 /** Constructor.
00041  * @param nr_candidates number of candidates
00042  * @param angle_from slope of lines from
00043  * @param angle_range angle range
00044  * @param r_scale r scale
00045  * @param min_votes_ratio min votes ratio
00046  * @param min_votes minimum number of votes for a candidate to consider
00047  */
00048 HtLinesModel::HtLinesModel(unsigned int nr_candidates, float angle_from, float angle_range, int r_scale, float min_votes_ratio, int min_votes)
00049 {
00050   RHT_NR_CANDIDATES   = nr_candidates;
00051
00052   RHT_R_SCALE         = r_scale;
00053
00054   RHT_MIN_VOTES       = min_votes;
00055   RHT_MIN_VOTES_RATIO = min_votes_ratio;
00056
00057   RHT_ANGLE_FROM      = angle_from -  (floor(angle_from  / (2 * M_PI )) * (2 * M_PI));
00058   RHT_ANGLE_RANGE     = angle_range - (floor(angle_range / (2 * M_PI )) * (2 * M_PI));
00059   RHT_ANGLE_INCREMENT = RHT_ANGLE_RANGE / RHT_NR_CANDIDATES;
00060 }
00061
00062 
00063 /** Destructor. */
00064 HtLinesModel::~HtLinesModel(void)
00065 {
00066   m_Lines.clear();
00067 }
00068
00069 int
00070 HtLinesModel::parseImage( unsigned char *buf,
00071                            ROI *roi            )
00072 {
00073   unsigned char *buffer = roi->get_roi_buffer_start(buf);
00074
00075   // clear the accumulator
00076   accumulator.reset();
00077
00078   // clear all the remembered lines
00079   m_Lines.clear();
00080
00081   // First, find all the edge pixels,
00082   // and store them in the 'pixels' vector.
00083   unsigned char *line_start = buffer;
00084   unsigned int     x, y;
00085   vector<point_t>  pixels;
00086
00087   for (y = 0; y < roi->height; ++y) {
00088     for (x = 0; x < roi->width; ++x) {
00089       if (TEST_IF_IS_A_PIXEL(*buffer)) {
00090         point_t pt={x, y};
00091         pixels.push_back(pt);
00092       }
00093       // NOTE: this assumes roi->pixel_step == 1
00094       ++buffer;
00095     }
00096     line_start += roi->line_step;
00097     buffer = line_start;
00098   }
00099
00100   // Then perform the RHT algorithm
00101   point_t p;
00102   float r, phi; // used for line representation
00103   vector< point_t >::iterator pos;
00104   if (pixels.size() == 0) {
00105     // No edge pixels found => no lines
00106     return 0;
00107   }
00108
00109
00110   while (pixels.size() > 0) {
00111     p = pixels.back();
00112     pixels.pop_back();
00113
00114     for (unsigned int i = 0; i < RHT_NR_CANDIDATES; ++i) {
00115       phi = RHT_ANGLE_FROM + i * RHT_ANGLE_INCREMENT;
00116       r   = p.x * cos( phi )  +   p.y * sin( phi );
00117
00118       int angle = (int)round(fawkes::rad2deg( phi ));
00119
00120       accumulator.accumulate( (int)round(r / RHT_R_SCALE),
00121                               angle,
00122                               0 );
00123     }
00124   }
00125
00126
00127   // Find the most dense region, and decide on the lines
00128   int max, r_max, phi_max, any_max;
00129   max = accumulator.getMax(r_max, phi_max, any_max);
00130
00131   roi_width = roi->width;
00132   roi_height = roi->height;
00133
00134   LineShape l(roi->width, roi->height);
00135   l.r   = r_max * RHT_R_SCALE;
00136   l.phi = phi_max;
00137   l.count = max;
00138   m_Lines.push_back( l );
00139
00140   return 1;
00141 }
00142
00143
00144 int
00145 HtLinesModel::getShapeCount(void) const
00146 {
00147   return m_Lines.size();
00148 }
00149
00150 LineShape *
00151 HtLinesModel::getShape(int id) const
00152 {
00153   if (id < 0 || (unsigned int)id >= m_Lines.size()) {
00154     return NULL;
00155   } else {
00156     return const_cast<LineShape*>(&m_Lines[id]); // or use const Shape* def?!...
00157   }
00158 }
00159
00160
00161 LineShape *
00162 HtLinesModel::getMostLikelyShape(void) const
00163 {
00164   if (m_Lines.size() == 0) {
00165     return NULL;
00166   } else if (m_Lines.size() == 1) {
00167     return const_cast<LineShape*>(&m_Lines[0]); // or use const Shape* def?!...
00168   } else {
00169     int cur=0;
00170     for (unsigned int i=1; i < m_Lines.size(); ++i) {
00171       if (m_Lines[i].count > m_Lines[cur].count) {
00172         cur = i;
00173       }
00174     }
00175     return const_cast<LineShape*>(&m_Lines[cur]); // or use const Shape* definition?!...
00176   }
00177 }
00178
00179 
00180 /** Get all lines found.
00181  * @return vector with all line shapes.
00182  */
00183 vector< LineShape > *
00184 HtLinesModel::getShapes()
00185 {
00186   int votes = (int)(accumulator.getNumVotes() * (float)RHT_MIN_VOTES_RATIO);
00187
00188   if ( RHT_MIN_VOTES > votes ) {
00189     votes = RHT_MIN_VOTES;
00190   }
00191
00192   vector< LineShape > * rv = new vector< LineShape >();
00193
00194   vector< vector< int > > *rht_nodes = accumulator.getNodes( votes );
00195   vector< vector< int > >::iterator node_it;
00196
00197   LineShape l(roi_width, roi_height);
00198
00199   for (node_it = rht_nodes->begin(); node_it != rht_nodes->end(); ++node_it) {
00200     l.r   = node_it->at(0) * RHT_R_SCALE;
00201     l.phi = node_it->at(1);
00202     // we do not use val 2 here!
00203     l.count = node_it->at(3);
00204     l.calcPoints();
00205     rv->push_back( l );
00206   }
00207
00208   return rv;
00209 }