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
32using namespace std;
33using namespace fawkes;
34
35namespace 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 */
60HtLinesModel::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. */
81{
82 m_Lines.clear();
83}
84
85int
86HtLinesModel::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
154int
156{
157 return m_Lines.size();
158}
159
160LineShape *
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
170LineShape *
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 */
191vector<LineShape> *
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
virtual ~HtLinesModel(void)
Destructor.
Definition: ht_lines.cpp:80
LineShape * getMostLikelyShape(void) const
Get best candidate.
Definition: ht_lines.cpp:171
LineShape * getShape(int id) const
Get specific shape.
Definition: ht_lines.cpp:161
int getShapeCount(void) const
Get number of shapes.
Definition: ht_lines.cpp:155
int parseImage(unsigned char *buffer, ROI *roi)
Parse image for given ROI.
Definition: ht_lines.cpp:86
HtLinesModel(unsigned int nr_candidates=40, float angle_from=0, float angle_range=2 *M_PI, int r_scale=1, float min_votes_ratio=0.2f, int min_votes=-1)
Constructor.
Definition: ht_lines.cpp:60
std::vector< LineShape > * getShapes()
Get all lines found.
Definition: ht_lines.cpp:192
Line shape.
Definition: line.h:41
void calcPoints()
Calc points for line.
Definition: line.cpp:96
Region of interest.
Definition: roi.h:55
unsigned int height
ROI height.
Definition: roi.h:119
unsigned char * get_roi_buffer_start(unsigned char *buffer) const
Get ROI buffer start.
Definition: roi.cpp:526
unsigned int line_step
line step
Definition: roi.h:125
unsigned int width
ROI width.
Definition: roi.h:117
unsigned int getNumVotes() const
Get number of votes.
Definition: ht_accum.cpp:513
int getMax(int &x, int &y, int &r) const
Get maximum.
Definition: ht_accum.cpp:491
void reset(void)
Reset.
Definition: ht_accum.cpp:451
std::vector< std::vector< int > > * getNodes(int min_count)
Get nodes.
Definition: ht_accum.cpp:523
int accumulate(int x, int y, int r)
Accumulate new candidate.
Definition: ht_accum.cpp:468
Fawkes library namespace.
float rad2deg(float rad)
Convert an angle given in radians to degrees.
Definition: angle.h:46
Point with cartesian coordinates as unsigned integers.
Definition: types.h:35
unsigned int x
x coordinate
Definition: types.h:36
unsigned int y
y coordinate
Definition: types.h:37