Fawkes API  Fawkes Development Version
ht_lines.cpp
1 
2 /***************************************************************************
3  * ht_lines.cpp - Implementation of a lines shape finder
4  * with Randomized Hough Transform
5  *
6  * Created: Fri Jan 13 12:42:53 2006
7  * Copyright 2005-2006 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/ht_lines.h>
27 #include <sys/time.h>
28 #include <utils/math/angle.h>
29 
30 #include <cmath>
31 
32 using namespace std;
33 using namespace fawkes;
34 
35 namespace firevision {
36 
37 #define TEST_IF_IS_A_PIXEL(x) ((x) > 230)
38 
39 /** @class HtLinesModel <fvmodels/shape/ht_lines.h>
40  * Hough-Transform line matcher.
41  */
42 
43 /** Constructor.
44  * Creates a new HtLinesModel instance
45  * @param nr_candidates the nr of candidates that is considered per pixel (the hole angle
46  * range is devided in this many parts/lines
47  * @param angle_from The angle to start the candidates from, given in rad, 0 is straight up
48  * @param angle_range the angle range the candidates are taken from starting at angle_from,
49  * given in rad, can be used for example to only search for horizontal lines
50  * @param r_scale This can be done to reduce the size of the hough space and to map more lines
51  * to one line
52  * @param min_votes_ratio The minimum ratio num_votes_per_line/total_num_votes that we have to
53  * have before a point in the hough space is considered to be a line,
54  * this may actually be higher if you use min_votes and set it to a higher
55  * number (set min_votes to 0 to only use min_votes_ration)
56  * @param min_votes the minimum number of votes a point in the hough space has to have before it
57  * is considered to be a line. The number may actually be higher if min_votes_ratio
58  * is set too high (set min_votes_ration to 0 to use only min_votes)
59  */
60 HtLinesModel::HtLinesModel(unsigned int nr_candidates,
61  float angle_from,
62  float angle_range,
63  int r_scale,
64  float min_votes_ratio,
65  int min_votes)
66 {
67  RHT_NR_CANDIDATES = nr_candidates;
68 
69  RHT_R_SCALE = r_scale;
70 
71  RHT_MIN_VOTES = min_votes;
72  RHT_MIN_VOTES_RATIO = min_votes_ratio;
73 
74  RHT_ANGLE_FROM = angle_from - (floor(angle_from / (2 * M_PI)) * (2 * M_PI));
75  RHT_ANGLE_RANGE = angle_range - (floor(angle_range / (2 * M_PI)) * (2 * M_PI));
76  RHT_ANGLE_INCREMENT = RHT_ANGLE_RANGE / RHT_NR_CANDIDATES;
77 }
78 
79 /** Destructor. */
80 HtLinesModel::~HtLinesModel(void)
81 {
82  m_Lines.clear();
83 }
84 
85 int
86 HtLinesModel::parseImage(unsigned char *buf, ROI *roi)
87 {
88  unsigned char *buffer = roi->get_roi_buffer_start(buf);
89 
90  // clear the accumulator
91  accumulator.reset();
92 
93  // clear all the remembered lines
94  m_Lines.clear();
95 
96  // First, find all the edge pixels,
97  // and store them in the 'pixels' vector.
98  unsigned char * line_start = buffer;
99  unsigned int x, y;
100  vector<upoint_t> pixels;
101 
102  for (y = 0; y < roi->height; ++y) {
103  for (x = 0; x < roi->width; ++x) {
104  if (TEST_IF_IS_A_PIXEL(*buffer)) {
105  upoint_t pt = {x, y};
106  pixels.push_back(pt);
107  }
108  // NOTE: this assumes roi->pixel_step == 1
109  ++buffer;
110  }
111  line_start += roi->line_step;
112  buffer = line_start;
113  }
114 
115  // Then perform the RHT algorithm
116  upoint_t p;
117  float r, phi; // used for line representation
118  vector<upoint_t>::iterator pos;
119  if (pixels.size() == 0) {
120  // No edge pixels found => no lines
121  return 0;
122  }
123 
124  while (pixels.size() > 0) {
125  p = pixels.back();
126  pixels.pop_back();
127 
128  for (unsigned int i = 0; i < RHT_NR_CANDIDATES; ++i) {
129  phi = RHT_ANGLE_FROM + i * RHT_ANGLE_INCREMENT;
130  r = p.x * cos(phi) + p.y * sin(phi);
131 
132  int angle = (int)round(fawkes::rad2deg(phi));
133 
134  accumulator.accumulate((int)round(r / RHT_R_SCALE), angle, 0);
135  }
136  }
137 
138  // Find the most dense region, and decide on the lines
139  int max, r_max, phi_max, any_max;
140  max = accumulator.getMax(r_max, phi_max, any_max);
141 
142  roi_width = roi->width;
143  roi_height = roi->height;
144 
145  LineShape l(roi->width, roi->height);
146  l.r = r_max * RHT_R_SCALE;
147  l.phi = phi_max;
148  l.count = max;
149  m_Lines.push_back(l);
150 
151  return 1;
152 }
153 
154 int
155 HtLinesModel::getShapeCount(void) const
156 {
157  return m_Lines.size();
158 }
159 
161 HtLinesModel::getShape(int id) const
162 {
163  if (id < 0 || (unsigned int)id >= m_Lines.size()) {
164  return NULL;
165  } else {
166  return const_cast<LineShape *>(&m_Lines[id]); // or use const Shape* def?!...
167  }
168 }
169 
171 HtLinesModel::getMostLikelyShape(void) const
172 {
173  if (m_Lines.size() == 0) {
174  return NULL;
175  } else if (m_Lines.size() == 1) {
176  return const_cast<LineShape *>(&m_Lines[0]); // or use const Shape* def?!...
177  } else {
178  int cur = 0;
179  for (unsigned int i = 1; i < m_Lines.size(); ++i) {
180  if (m_Lines[i].count > m_Lines[cur].count) {
181  cur = i;
182  }
183  }
184  return const_cast<LineShape *>(&m_Lines[cur]); // or use const Shape* definition?!...
185  }
186 }
187 
188 /** Get all lines found.
189  * @return vector with all line shapes.
190  */
191 vector<LineShape> *
192 HtLinesModel::getShapes()
193 {
194  int votes = (int)(accumulator.getNumVotes() * (float)RHT_MIN_VOTES_RATIO);
195 
196  if (RHT_MIN_VOTES > votes) {
197  votes = RHT_MIN_VOTES;
198  }
199 
200  vector<LineShape> *rv = new vector<LineShape>();
201 
202  vector<vector<int>> * rht_nodes = accumulator.getNodes(votes);
203  vector<vector<int>>::iterator node_it;
204 
205  LineShape l(roi_width, roi_height);
206 
207  for (node_it = rht_nodes->begin(); node_it != rht_nodes->end(); ++node_it) {
208  l.r = node_it->at(0) * RHT_R_SCALE;
209  l.phi = node_it->at(1);
210  // we do not use val 2 here!
211  l.count = node_it->at(3);
212  l.calcPoints();
213  rv->push_back(l);
214  }
215 
216  return rv;
217 }
218 
219 } // end namespace firevision
firevision::LineShape::calcPoints
void calcPoints()
Calc points for line.
Definition: line.cpp:95
firevision::ROI::width
unsigned int width
ROI width.
Definition: roi.h:121
fawkes::upoint_t
Point with cartesian coordinates as unsigned integers.
Definition: types.h:33
firevision::ROI
Definition: roi.h:58
firevision::ROI::height
unsigned int height
ROI height.
Definition: roi.h:123
fawkes::rad2deg
float rad2deg(float rad)
Convert an angle given in radians to degrees.
Definition: angle.h:50
firevision::LineShape
Definition: line.h:45
fawkes
fawkes::upoint_t::y
unsigned int y
y coordinate
Definition: types.h:36
firevision::ROI::line_step
unsigned int line_step
line step
Definition: roi.h:129
fawkes::upoint_t::x
unsigned int x
x coordinate
Definition: types.h:35
firevision::ROI::get_roi_buffer_start
unsigned char * get_roi_buffer_start(unsigned char *buffer) const
Get ROI buffer start.
Definition: roi.cpp:525