Fawkes API  Fawkes Development Version
rht_lines.cpp
1 
2 /***************************************************************************
3  * rht_lines.cpp - Implementation of a lines shape finder
4  * with Randomized Hough Transform
5  *
6  * Created: Mon Sep 26 2005 09:52:00
7  * Copyright 2005 Tim Niemueller [www.niemueller.de]
8  * Hu Yuxiao <Yuxiao.Hu@rwth-aachen.de>
9  *
10  ****************************************************************************/
11 
12 /* This program is free software; you can redistribute it and/or modify
13  * it under the terms of the GNU General Public License as published by
14  * the Free Software Foundation; either version 2 of the License, or
15  * (at your option) any later version. A runtime exception applies to
16  * this software (see LICENSE.GPL_WRE file mentioned below for details).
17  *
18  * This program is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21  * GNU Library General Public License for more details.
22  *
23  * Read the full text in the LICENSE.GPL_WRE file in the doc directory.
24  */
25 
26 #include <utils/math/angle.h>
27 #include <sys/time.h>
28 #include <fvmodels/shape/rht_lines.h>
29 
30 using namespace std;
31 using namespace fawkes;
32 
33 #define TEST_IF_IS_A_PIXEL(x) ((x)>230)
34 
35 namespace firevision {
36 #if 0 /* just to make Emacs auto-indent happy */
37 }
38 #endif
39 
40 /** @class RhtLinesModel <fvmodels/shape/rht_lines.h>
41  * Randomized Hough-Transform line model.
42  */
43 
44 /** Constructor. */
45 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)
46 {
47  RHT_MAX_TIME = max_time; // max_time is given in ms but we need microseconds, thus * 1000
48  RHT_MAX_ITER = max_iter; // Maximal number of iterations.
49 
50  RHT_NR_CANDIDATES = nr_candidates;
51 
52  RHT_R_SCALE = r_scale;
53 
54  RHT_MIN_VOTES = min_votes;
55  RHT_MIN_VOTES_RATIO = min_votes_ratio;
56 
57  RHT_ANGLE_FROM = angle_from - (floor(angle_from / (2 * M_PI )) * (2 * M_PI));
58  RHT_ANGLE_RANGE = angle_range - (floor(angle_range / (2 * M_PI )) * (2 * M_PI));
59  RHT_ANGLE_INCREMENT = RHT_ANGLE_RANGE / RHT_NR_CANDIDATES;
60 }
61 
62 
63 /** Destructor. */
64 RhtLinesModel::~RhtLinesModel(void)
65 {
66  m_Lines.clear();
67 }
68 
69 /**************************************************************
70  * In this function we implement a lines detection algorithm
71  **************************************************************/
72 int
73 RhtLinesModel::parseImage( unsigned char *buf,
74  ROI *roi )
75 {
76  unsigned char *buffer = roi->get_roi_buffer_start(buf);
77 
78  struct timeval start, now;
79 
80  // clear the accumulator
81  accumulator.reset();
82 
83  // clear all the remembered lines
84  m_Lines.clear();
85 
86  // First, find all the edge pixels,
87  // and store them in the 'pixels' vector.
88  unsigned char *line_start = buffer;
89  unsigned int x, y;
90  vector<upoint_t> pixels;
91 
92  gettimeofday(&start, NULL);
93 
94  for (y = 0; y < roi->height; ++y) {
95  for (x = 0; x < roi->width; ++x) {
96  if (TEST_IF_IS_A_PIXEL(*buffer)) {
97  upoint_t pt={x, y};
98  pixels.push_back(pt);
99  }
100  // NOTE: this assumes roi->pixel_step == 1
101  ++buffer;
102  }
103  line_start += roi->line_step;
104  buffer = line_start;
105  }
106 
107  // Then perform the RHT algorithm
108  upoint_t p;
109  float r, phi; // used for line representation
110  vector< upoint_t >::iterator pos;
111  int num_iter = 0;
112  if (pixels.size() == 0) {
113  // No edge pixels found => no lines
114  return 0;
115  }
116 
117 
118 
119  do {
120  // in order to prevent float exception, pixels.size() must be non-zero
121  if (pixels.size() > 0) {
122  int ri = rand() % pixels.size();
123  pos = pixels.begin() + ri;
124  p = *pos;
125  pixels.erase(pos);
126 
127  for (unsigned int i = 0; i < RHT_NR_CANDIDATES; ++i) {
128  phi = RHT_ANGLE_FROM + i * RHT_ANGLE_INCREMENT;
129  r = p.x * cos( phi ) + p.y * sin( phi );
130 
131  int angle = (int)round(fawkes::rad2deg( phi ));
132 
133  accumulator.accumulate( (int)round(r / RHT_R_SCALE),
134  angle,
135  0 );
136  }
137 
138  gettimeofday(&now, NULL);
139 
140  diff_sec = now.tv_sec - start.tv_sec;
141  diff_usec = now.tv_usec - start.tv_usec;
142  if (diff_usec < 0) {
143  diff_sec -= 1;
144  diff_usec += 1000000;
145  }
146 
147  f_diff_sec = diff_sec + diff_usec / 1000000.f;
148 
149  } // end if
150  } while( ( ++num_iter < RHT_MAX_ITER) &&
151  ( f_diff_sec < RHT_MAX_TIME) );
152 
153  // Find the most dense region, and decide on the lines
154  int max, r_max, phi_max, any_max;
155  max = accumulator.getMax(r_max, phi_max, any_max);
156 
157  roi_width = roi->width;
158  roi_height = roi->height;
159 
160  LineShape l(roi->width, roi->height);
161  l.r = r_max * RHT_R_SCALE;
162  l.phi = phi_max;
163  l.count = max;
164  m_Lines.push_back( l );
165 
166  return 1;
167 }
168 
169 
170 int
171 RhtLinesModel::getShapeCount(void) const
172 {
173  return m_Lines.size();
174 }
175 
176 LineShape *
177 RhtLinesModel::getShape(int id) const
178 {
179  if (id < 0 || (unsigned int)id >= m_Lines.size()) {
180  return NULL;
181  } else {
182  return const_cast<LineShape*>(&m_Lines[id]); // or use const Shape* def?!...
183  }
184 }
185 
186 
187 LineShape *
188 RhtLinesModel::getMostLikelyShape(void) const
189 {
190  if (m_Lines.size() == 0) {
191  return NULL;
192  } else if (m_Lines.size() == 1) {
193  return const_cast<LineShape*>(&m_Lines[0]); // or use const Shape* def?!...
194  } else {
195  int cur=0;
196  for (unsigned int i=1; i < m_Lines.size(); ++i) {
197  if (m_Lines[i].count > m_Lines[cur].count) {
198  cur = i;
199  }
200  }
201  return const_cast<LineShape*>(&m_Lines[cur]); // or use const Shape* definition?!...
202  }
203 }
204 
205 
206 /** Get shapes.
207  * @return vector of shapes
208  */
209 vector< LineShape > *
210 RhtLinesModel::getShapes()
211 {
212  int votes = (int)(accumulator.getNumVotes() * (float)RHT_MIN_VOTES_RATIO);
213 
214  if ( RHT_MIN_VOTES > votes ) {
215  votes = RHT_MIN_VOTES;
216  }
217 
218  vector< LineShape > * rv = new vector< LineShape >();
219 
220  vector< vector< int > > *rht_nodes = accumulator.getNodes( votes );
221  vector< vector< int > >::iterator node_it;
222 
223  LineShape l(roi_width, roi_height);
224 
225  for (node_it = rht_nodes->begin(); node_it != rht_nodes->end(); ++node_it) {
226  l.r = node_it->at(0) * RHT_R_SCALE;
227  l.phi = node_it->at(1);
228  // we do not use val 2 here!
229  l.count = node_it->at(3);
230  l.calcPoints();
231  rv->push_back( l );
232  }
233 
234  return rv;
235 }
236 
237 } // end namespace firevision
Fawkes library namespace.
unsigned int y
y coordinate
Definition: types.h:36
STL namespace.
unsigned int x
x coordinate
Definition: types.h:35
unsigned int width
ROI width.
Definition: roi.h:121
Region of interest.
Definition: roi.h:58
void calcPoints()
Calc points for line.
Definition: line.cpp:104
unsigned char * get_roi_buffer_start(unsigned char *buffer) const
Get ROI buffer start.
Definition: roi.cpp:556
Line shape.
Definition: line.h:40
Point with cartesian coordinates as unsigned integers.
Definition: types.h:34
float rad2deg(float rad)
Convert an angle given in radians to degrees.
Definition: angle.h:48
unsigned int height
ROI height.
Definition: roi.h:123
unsigned int line_step
line step
Definition: roi.h:129