Fawkes API  Fawkes Development Version
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
hough_transform.cpp
1 
2 /***************************************************************************
3  * hough_transform.cpp - Hough Transform
4  *
5  * Created: Mon Dec 28 2009 18:56:04
6  * Copyright 2009 Tim Niemueller [www.niemueller.de]
7  *
8  ****************************************************************************/
9 
10 /* This program is free software; you can redistribute it and/or modify
11  * it under the terms of the GNU General Public License as published by
12  * the Free Software Foundation; either version 2 of the License, or
13  * (at your option) any later version. A runtime exception applies to
14  * this software (see LICENSE.GPL_WRE file mentioned below for details).
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU Library General Public License for more details.
20  *
21  * Read the full text in the LICENSE.GPL_WRE file in the doc directory.
22  */
23 
24 #include "hough_transform.h"
25 
26 #include <algorithm>
27 #include <cstdio>
28 #include <cstdlib>
29 
30 /** @class HoughTransform "hough_transform.h"
31  * Hough Transformation for N-dimensional representations.
32  * This class implements a generic Hough transformation, which can operate
33  * on representations of arbitrary dimension (at least in theory ignoring
34  * computational feasibility).
35  * The implementation uses a tree structure to represent the buckets in the
36  * Hough space, to reduce the amount of memory required on sparse data
37  * sets and to allow fast insertion of new samples.
38  * The code is based on ideas from a Hough transform implemented in
39  * FireVision, but eliminating some of its limitations.
40  * @author Tim Niemueller
41  *
42  * @fn inline Node * HoughTransform::create_node(Node *parent, unsigned int dims, int value = 0)
43  * Create a new node.
44  * @param parent parent node of the new node
45  * @param dims Dimensions remaining
46  * @param value initial value
47  * @return new node with given parent, dimensions, and initial value
48  */
49 
50 /** Constructor.
51  * @param num_dims number of dimensions
52  */
53 HoughTransform::HoughTransform(unsigned int num_dims)
54 {
55  __root = new Node(this, num_dims);
56 
57  __num_dims = num_dims;
58 
59  __reuse_head = new Node(this);
60  __reuse_cur = __reuse_head;
61  __reuse_tail = __reuse_head;
62 
63  __max_count = 0;
64  __max_values = new int[num_dims];
65 }
66 
67 /** Destructor. */
69 {
70  while (__reuse_head) {
71  Node *n = __reuse_head;
72  __reuse_head = __reuse_head->__reuse_next;
73  delete n;
74  }
75 
76  delete[] __max_values;
77 }
78 
79 /** Process some samples.
80  * @param values two dimensional array of values. The first index determines
81  * the sample index, the second index the dimension index. Thus its an
82  * array with the length of number of values of arrays with the length of
83  * the number of dimensions.
84  * @param num_values number of rows in values
85  */
86 void
87 HoughTransform::process(int **values, unsigned int num_values)
88 {
89  for (unsigned int i = 0; i < num_values; ++i) {
90  unsigned int count = __root->insert(values[i]);
91  if (count > __max_count) {
92  __max_count = count;
93  for (unsigned int d = 0; d < __num_dims; ++d) {
94  __max_values[d] = values[i][d];
95  }
96  }
97  }
98 }
99 
100 /** Get maximum values.
101  * During processing the maximum values, i.e. the candidate with the
102  * maximum number of votes or the most filled bucket, is stored and can
103  * be retrieved with this method.
104  * @param values upon return contains the maximum voted values
105  * @return number of votes of the values
106  */
107 unsigned int
108 HoughTransform::max(int *values) const
109 {
110  for (unsigned int d = 0; d < __num_dims; ++d) {
111  values[d] = __max_values[d];
112  }
113  return __max_count;
114 }
115 
116 
117 /** Filter values by number of votes.
118  * This method filters all created buckets and returns only the ones which
119  * have at least @p min_count votes
120  * @param values upon return points to a newly allocated array of values with
121  * the size of number of values * number of dimensions. The memory must be
122  * freed when done by using free().
123  * @param min_count minimum number of votes required to consider a bucket
124  * @return number of values found
125  */
126 unsigned int
127 HoughTransform::filter(int **values, unsigned int min_count)
128 {
129  return __root->filter(values, min_count);
130 }
131 
132 
133 /** Get root node.
134  * @return root node of internal tree, meant for debugging and performance
135  * evaluation
136  */
137 HoughTransform::Node *
139 {
140  return __root;
141 }
142 
143 /** Reset Hough transform.
144  * This deletes the internal tree and creates a new empty one. */
145 void
147 {
148  __reuse_cur = __reuse_head;
149  __root = create_node(NULL, __num_dims);
150  __max_count = 0;
151  for (unsigned int d = 0; d < __num_dims; ++d) {
152  __max_values[d] = 0;
153  }
154 }
155 
156 /** @class HoughTransform::Node "hough_transform.h"
157  * Hough transform tree node.
158  * The nodes are used to form a tree. The tree is organized as stacked
159  * binary trees. At a certain stack level, a value of a specific dimension
160  * is stored, with the left and right sub-trees pointing to smaller or
161  * higher values respectively.
162  * Nodes with a stack level of 1 (e.g. the bottom-most level) have a field
163  * to count the number of votes (these are the bucket nodes). Nodes on
164  * higher levels have a pointer to another node on a stack level one lower
165  * than the own, which represents the next dimension of the values.
166  * @author Tim Niemueller
167  * @author Hu Yuxiao
168  */
169 
170 /** Constructor.
171  * @param ht hough transform the node belongs to
172  * @param dims number of remaining dimensions (including the own)
173  * @param value the initial value of the node
174  */
175 HoughTransform::Node::Node(HoughTransform *ht, unsigned int dims, int value)
176 {
177  __ht = ht;
178  __dims = dims;
179  __value = value;
180  __count = 0;
181  __parent = NULL;
182  __left = __right = __dim_next = __filter_next = __reuse_next = 0;
183 }
184 
185 /** Constructor with parent node.
186  * @param parent parent node of the new node
187  * @param dims number of remaining dimensions (including the own)
188  * @param value the initial value of the node
189  */
190 HoughTransform::Node::Node(HoughTransform *ht,
191  Node *parent, unsigned int dims, int value)
192 {
193  __ht = ht;
194  __parent = parent;
195  __dims = dims;
196  __value = value;
197  __count = 0;
198  __left = __right = __dim_next = __filter_next = __reuse_next = 0;
199 }
200 
201 /** Constructor. */
202 HoughTransform::Node::Node(HoughTransform *ht)
203 {
204  __ht = ht;
205  __dims = 1;
206  __value = 0;
207  __count = 0;
208  __parent = NULL;
209  __left = __right = __dim_next = __filter_next = __reuse_next = 0;
210 }
211 
212 /** Destructor. */
213 HoughTransform::Node::~Node()
214 {
215  // sub-nodes delete by HoughTransform
216 }
217 
218 
219 /** Insert new values.
220  * @param values array with new values, must be of the size of the number
221  * of dimensions
222  * @return number of votes of bucket the values have been inserted to
223  */
224 unsigned int
225 HoughTransform::Node::insert(int *values)
226 {
227  if (values[0] == __value) {
228  if ( __dims > 1) {
229  if (! __dim_next) {
230  __dim_next = __ht->create_node(this, __dims - 1, values[1]);
231  }
232 
233  return __dim_next->insert(&(values[1]));
234  } else {
235  return ++__count;
236  }
237  } else if (values[0] < __value) {
238  if (! __left) {
239  __left = __ht->create_node(__parent, __dims, values[0]);
240  }
241  return __left->insert(values);
242  } else { // values[0] > __value
243  if (! __right) {
244  __right = __ht->create_node(__parent, __dims, values[0]);
245  }
246  return __right->insert(values);
247  }
248 }
249 
250 
251 /** Get number of nodes.
252  * @return number of nodes
253  */
254 unsigned int
255 HoughTransform::Node::num_nodes()
256 {
257  unsigned int rv = 1;
258  if (__left) rv += __left->num_nodes();
259  if (__right) rv += __right->num_nodes();
260  if (__dim_next) rv += __dim_next->num_nodes();
261  return rv;
262 }
263 
264 
265 /** Depth of the tree.
266  * @return maximum depth of tree
267  */
268 unsigned int
269 HoughTransform::Node::depth()
270 {
271  unsigned int d = 0;
272  if (__left) d = std::max(d, __left->depth());
273  if (__right) d = std::max(d, __right->depth());
274  if (__dim_next) d = std::max(d, __dim_next->depth());
275  return d + 1;
276 }
277 
278 
279 /** Get length of filtered list.
280  * @return length of filtered list
281  */
282 unsigned int
283 HoughTransform::Node::filtered_length()
284 {
285  Node *t = this;
286  // do not count first, is unused head element
287  unsigned int rv = 0;
288  while (t->__filter_next) {
289  ++rv;
290  t = t->__filter_next;
291  }
292  return rv;
293 }
294 
295 
296 /** Filter values by number of votes.
297  * This method filters all created buckets and returns only the ones which
298  * have at least @p min_count votes
299  * @param values upon return points to a newly allocated array of values with the
300  * size of number of values * number of dimensions. The memory must be freed
301  * when done by using free().
302  * @param min_count minimum number of votes required to consider a bucket
303  * @return number of values found
304  */
305 unsigned int
306 HoughTransform::Node::filter(int **values, unsigned int min_count)
307 {
308  Node *filtered_root = new Node();
309  filter(filtered_root, min_count);
310  unsigned int flen = filtered_root->filtered_length();
311 
312  int *fvals = (int *)calloc(flen, __dims * sizeof(int));
313  Node *t = filtered_root;
314  unsigned int f = 0;
315  while ((t = t->__filter_next) != NULL) {
316  Node *s = t;
317  for (unsigned int i = 1; i <= __dims; ++i) {
318  fvals[ __dims * (f + 1) - i ] = s->__value;
319  s = s->__parent;
320  }
321  ++f;
322  }
323 
324  delete filtered_root;
325 
326  *values = fvals;
327  return flen;
328 }
329 
330 
331 /** Internal filter recursion function.
332  * @param tail current tail
333  * @param min_count minimum number of votes required to consider a bucket
334  * @return new tail node
335  */
336 HoughTransform::Node *
337 HoughTransform::Node::filter(Node *tail, unsigned int min_count)
338 {
339  if (__dims == 1) {
340  if (__count >= min_count) {
341  // add this node
342  this->__filter_next = NULL;
343  tail->__filter_next = this;
344  tail = this;
345  }
346  if (__left) tail = __left->filter(tail, min_count);
347  if (__right) tail = __right->filter(tail, min_count);
348 
349  } else {
350  if (__dim_next) tail = __dim_next->filter(tail, min_count);
351  if (__left) tail = __left->filter(tail, min_count);
352  if (__right) tail = __right->filter(tail, min_count);
353  }
354 
355  return tail;
356 }
~HoughTransform()
Destructor.
Node * root()
Get root node.
void reset()
Reset Hough transform.
HoughTransform(unsigned int num_dims)
Constructor.
Hough Transformation for N-dimensional representations.
void process(int **values, unsigned int num_values)
Process some samples.
unsigned int filter(int **values, unsigned int min_count)
Filter values by number of votes.
Node * create_node(Node *parent, unsigned int dims, int value=0)
Create a new node.
unsigned int max(int *values) const
Get maximum values.