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 <fvmodels/shape/rht_lines.h>
27 #include <sys/time.h>
28 #include <utils/math/angle.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 
37 /** @class RhtLinesModel <fvmodels/shape/rht_lines.h>
38  * Randomized Hough-Transform line model.
39  */
40 
41 /** Constructor. */
42 RhtLinesModel::RhtLinesModel(float max_time,
43  int max_iter,
44  unsigned int nr_candidates,
45  float angle_from,
46  float angle_range,
47  int r_scale,
48  float min_votes_ratio,
49  int min_votes)
50 {
51  RHT_MAX_TIME = max_time; // max_time is given in ms but we need microseconds, thus * 1000
52  RHT_MAX_ITER = max_iter; // Maximal number of iterations.
53 
54  RHT_NR_CANDIDATES = nr_candidates;
55 
56  RHT_R_SCALE = r_scale;
57 
58  RHT_MIN_VOTES = min_votes;
59  RHT_MIN_VOTES_RATIO = min_votes_ratio;
60 
61  RHT_ANGLE_FROM = angle_from - (floor(angle_from / (2 * M_PI)) * (2 * M_PI));
62  RHT_ANGLE_RANGE = angle_range - (floor(angle_range / (2 * M_PI)) * (2 * M_PI));
63  RHT_ANGLE_INCREMENT = RHT_ANGLE_RANGE / RHT_NR_CANDIDATES;
64 }
65 
66 /** Destructor. */
67 RhtLinesModel::~RhtLinesModel(void)
68 {
69  m_Lines.clear();
70 }
71 
72 /**************************************************************
73  * In this function we implement a lines detection algorithm
74  **************************************************************/
75 int
76 RhtLinesModel::parseImage(unsigned char *buf, ROI *roi)
77 {
78  unsigned char *buffer = roi->get_roi_buffer_start(buf);
79 
80  struct timeval start, now;
81 
82  // clear the accumulator
83  accumulator.reset();
84 
85  // clear all the remembered lines
86  m_Lines.clear();
87 
88  // First, find all the edge pixels,
89  // and store them in the 'pixels' vector.
90  unsigned char * line_start = buffer;
91  unsigned int x, y;
92  vector<upoint_t> pixels;
93 
94  gettimeofday(&start, NULL);
95 
96  for (y = 0; y < roi->height; ++y) {
97  for (x = 0; x < roi->width; ++x) {
98  if (TEST_IF_IS_A_PIXEL(*buffer)) {
99  upoint_t pt = {x, y};
100  pixels.push_back(pt);
101  }
102  // NOTE: this assumes roi->pixel_step == 1
103  ++buffer;
104  }
105  line_start += roi->line_step;
106  buffer = line_start;
107  }
108 
109  // Then perform the RHT algorithm
110  upoint_t p;
111  float r, phi; // used for line representation
112  vector<upoint_t>::iterator pos;
113  int num_iter = 0;
114  if (pixels.size() == 0) {
115  // No edge pixels found => no lines
116  return 0;
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), angle, 0);
134  }
135 
136  gettimeofday(&now, NULL);
137 
138  diff_sec = now.tv_sec - start.tv_sec;
139  diff_usec = now.tv_usec - start.tv_usec;
140  if (diff_usec < 0) {
141  diff_sec -= 1;
142  diff_usec += 1000000;
143  }
144 
145  f_diff_sec = diff_sec + diff_usec / 1000000.f;
146 
147  } // end if
148  } while ((++num_iter < RHT_MAX_ITER) && (f_diff_sec < RHT_MAX_TIME));
149 
150  // Find the most dense region, and decide on the lines
151  int max, r_max, phi_max, any_max;
152  max = accumulator.getMax(r_max, phi_max, any_max);
153 
154  roi_width = roi->width;
155  roi_height = roi->height;
156 
157  LineShape l(roi->width, roi->height);
158  l.r = r_max * RHT_R_SCALE;
159  l.phi = phi_max;
160  l.count = max;
161  m_Lines.push_back(l);
162 
163  return 1;
164 }
165 
166 int
167 RhtLinesModel::getShapeCount(void) const
168 {
169  return m_Lines.size();
170 }
171 
172 LineShape *
173 RhtLinesModel::getShape(int id) const
174 {
175  if (id < 0 || (unsigned int)id >= m_Lines.size()) {
176  return NULL;
177  } else {
178  return const_cast<LineShape *>(&m_Lines[id]); // or use const Shape* def?!...
179  }
180 }
181 
182 LineShape *
183 RhtLinesModel::getMostLikelyShape(void) const
184 {
185  if (m_Lines.size() == 0) {
186  return NULL;
187  } else if (m_Lines.size() == 1) {
188  return const_cast<LineShape *>(&m_Lines[0]); // or use const Shape* def?!...
189  } else {
190  int cur = 0;
191  for (unsigned int i = 1; i < m_Lines.size(); ++i) {
192  if (m_Lines[i].count > m_Lines[cur].count) {
193  cur = i;
194  }
195  }
196  return const_cast<LineShape *>(&m_Lines[cur]); // or use const Shape* definition?!...
197  }
198 }
199 
200 /** Get shapes.
201  * @return vector of shapes
202  */
203 vector<LineShape> *
204 RhtLinesModel::getShapes()
205 {
206  int votes = (int)(accumulator.getNumVotes() * (float)RHT_MIN_VOTES_RATIO);
207 
208  if (RHT_MIN_VOTES > votes) {
209  votes = RHT_MIN_VOTES;
210  }
211 
212  vector<LineShape> *rv = new vector<LineShape>();
213 
214  vector<vector<int>> * rht_nodes = accumulator.getNodes(votes);
215  vector<vector<int>>::iterator node_it;
216 
217  LineShape l(roi_width, roi_height);
218 
219  for (node_it = rht_nodes->begin(); node_it != rht_nodes->end(); ++node_it) {
220  l.r = node_it->at(0) * RHT_R_SCALE;
221  l.phi = node_it->at(1);
222  // we do not use val 2 here!
223  l.count = node_it->at(3);
224  l.calcPoints();
225  rv->push_back(l);
226  }
227 
228  return rv;
229 }
230 
231 } // end namespace firevision
firevision::LineShape::calcPoints
void calcPoints()
Calc points for line.
Definition: line.cpp:96
firevision::ROI::width
unsigned int width
ROI width.
Definition: roi.h:117
fawkes::upoint_t
Point with cartesian coordinates as unsigned integers.
Definition: types.h:35
firevision::ROI
Region of interest.
Definition: roi.h:55
firevision::ROI::height
unsigned int height
ROI height.
Definition: roi.h:119
fawkes::rad2deg
float rad2deg(float rad)
Convert an angle given in radians to degrees.
Definition: angle.h:46
firevision::LineShape
Line shape.
Definition: line.h:41
fawkes
Fawkes library namespace.
fawkes::upoint_t::y
unsigned int y
y coordinate
Definition: types.h:37
firevision::ROI::line_step
unsigned int line_step
line step
Definition: roi.h:125
fawkes::upoint_t::x
unsigned int x
x coordinate
Definition: types.h:36
firevision::ROI::get_roi_buffer_start
unsigned char * get_roi_buffer_start(unsigned char *buffer) const
Get ROI buffer start.
Definition: roi.cpp:526