Fawkes API  Fawkes Development Version
ht_accum.cpp
1 
2 /***************************************************************************
3  * ht_accum.cpp - Accumulator class for HoughTransform
4  *
5  * Generated: Tue Jun 28 2005
6  * Copyright 2005 Hu Yuxiao <Yuxiao.Hu@rwth-aachen.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 <fvmodels/shape/accumulators/ht_accum.h>
25 
26 using namespace std;
27 
28 namespace firevision {
29 
30 RhtXNode *RhtXNode::reuse_head = NULL;
31 RhtYNode *RhtYNode::reuse_head = NULL;
32 RhtRNode *RhtRNode::reuse_head = NULL;
33 
34 RhtXNode *RhtXNode::reuse_tail = NULL;
35 RhtYNode *RhtYNode::reuse_tail = NULL;
36 RhtRNode *RhtRNode::reuse_tail = NULL;
37 
38 /** @class RhtAccNode <fvmodels/shape/accumulators/ht_accum.h>
39  * Hough-Transform accumulator node.
40  */
41 
42 /** @class RhtRNode <fvmodels/shape/accumulators/ht_accum.h>
43  * Hough-Transform accumulator node.
44  */
45 
46 /** @class RhtXNode <fvmodels/shape/accumulators/ht_accum.h>
47  * Hough-Transform accumulator node.
48  */
49 
50 /** @class RhtYNode <fvmodels/shape/accumulators/ht_accum.h>
51  * Hough-Transform accumulator node.
52  */
53 
54 /** @class RhtAccumulator <fvmodels/shape/accumulators/ht_accum.h>
55  * Hough-Transform accumulator.
56  */
57 
58 /** Constructor. */
59 RhtAccNode::RhtAccNode()
60 {
61  left = right = next = NULL;
62 }
63 
64 /** Destructor. */
65 RhtAccNode::~RhtAccNode()
66 {
67 }
68 
69 /** Clear.
70  * @param ignore ignored
71  */
72 void
73 RhtAccNode::clear(int ignore)
74 {
75  left = right = NULL;
76 }
77 
78 /** Constructor.
79  * @param x x
80  */
81 RhtXNode::RhtXNode(int x) : RhtAccNode()
82 {
83  this->x = x;
84  y_root = NULL;
85 }
86 
87 /** Insert node.
88  * @param x0 x
89  * @param y0 y
90  * @param r0 r
91  * @return ?
92  */
93 int
94 RhtXNode::insert(int x0, int y0, int r0)
95 {
96  if (x == x0) {
97  if (!y_root)
99  return y_root->insert(y0, r0);
100  } else if (x0 < x) {
101  if (!left)
102  left = generate(x0);
103  return ((RhtXNode *)left)->insert(x0, y0, r0);
104  } else {
105  if (!right)
106  right = generate(x0);
107  return ((RhtXNode *)right)->insert(x0, y0, r0);
108  }
109 }
110 
111 /** Get nodes.
112  * @param rv return value
113  * @param min_votes minimum nomber of votes
114  */
115 void
116 RhtXNode::getNodes(std::vector<std::vector<int>> *rv, int min_votes)
117 {
118  if (left) {
119  ((RhtXNode *)left)->getNodes(rv, min_votes);
120  }
121 
122  if (y_root) {
123  y_root->getNodes(rv, min_votes, x);
124  }
125 
126  if (right) {
127  ((RhtXNode *)right)->getNodes(rv, min_votes);
128  }
129 }
130 
131 /** Dump to stream.
132  * @param s stream to dump to.
133  */
134 void
135 RhtXNode::dump(std::ostream &s)
136 {
137  if (left)
138  ((RhtXNode *)left)->dump(s);
139  y_root->dump(s, x);
140  if (right)
141  ((RhtXNode *)right)->dump(s);
142 }
143 
144 /** Generate.
145  * @param x ?
146  * @return node
147  */
149 RhtXNode::generate(int x)
150 {
151  if (reuse_tail == NULL) {
152  RhtXNode *p = new RhtXNode(x);
153  p->next = reuse_head;
154  reuse_head = p;
155  return reuse_head;
156  } else {
157  RhtXNode *p = reuse_tail;
158  reuse_tail = (RhtXNode *)(reuse_tail->next);
159  p->clear(x);
160  return p;
161  }
162 }
163 
164 /** Clear.
165  * @param x x to clear
166  */
167 void
168 RhtXNode::clear(int x)
169 {
171  this->x = x;
172  y_root = NULL;
173 }
174 
175 /** Reset. */
176 void
177 RhtXNode::reset(void)
178 {
179  reuse_tail = reuse_head;
180 }
181 
182 /** Cleanup. */
183 void
184 RhtXNode::cleanup(void)
185 {
186  while (reuse_head) {
187  reuse_tail = (RhtXNode *)reuse_head->next;
188  delete reuse_head;
189  reuse_head = reuse_tail;
190  }
191 }
192 
193 /** Constructor.
194  * @param y y
195  */
197 {
198  this->y = y;
199  r_root = NULL;
200 }
201 
202 /** Insert.
203  * @param y0 y
204  * @param r0 r
205  * @return number of sub-elements
206  */
207 int
208 RhtYNode::insert(int y0, int r0)
209 {
210  if (y == y0) {
211  if (!r_root)
213  return r_root->insert(r0);
214  } else if (y0 < y) {
215  if (!left)
216  left = generate(y0);
217  return ((RhtYNode *)left)->insert(y0, r0);
218  } else {
219  if (!right)
220  right = generate(y0);
221  return ((RhtYNode *)right)->insert(y0, r0);
222  }
223 }
224 
225 /** Get nodes.
226  * @param rv return value
227  * @param min_votes min votes
228  * @param x x
229  */
230 void
231 RhtYNode::getNodes(std::vector<std::vector<int>> *rv, int min_votes, int x)
232 {
233  if (left) {
234  ((RhtYNode *)left)->getNodes(rv, min_votes, x);
235  }
236 
237  if (r_root) {
238  r_root->getNodes(rv, min_votes, x, y);
239  }
240 
241  if (right) {
242  ((RhtYNode *)right)->getNodes(rv, min_votes, x);
243  }
244 }
245 
246 /** Dump.
247  * @param s dump to s
248  * @param x x
249  */
250 void
251 RhtYNode::dump(std::ostream &s, int x)
252 {
253  if (left)
254  ((RhtYNode *)left)->dump(s, x);
255  r_root->dump(s, x, y);
256  if (right)
257  ((RhtYNode *)right)->dump(s, x);
258 }
259 
260 /** Generate.
261  * @param y y
262  * @return node
263  */
265 RhtYNode::generate(int y)
266 {
267  if (reuse_tail == NULL) {
268  RhtYNode *p = new RhtYNode(y);
269  p->next = reuse_head;
270  reuse_head = p;
271  return reuse_head;
272  } else {
273  RhtYNode *p = reuse_tail;
274  reuse_tail = (RhtYNode *)(reuse_tail->next);
275  p->clear(y);
276  return p;
277  }
278 }
279 
280 /** Clear.
281  * @param y y
282  */
283 void
284 RhtYNode::clear(int y)
285 {
287  this->y = y;
288  r_root = NULL;
289 }
290 
291 /** Reset. */
292 void
293 RhtYNode::reset(void)
294 {
295  reuse_tail = reuse_head;
296 }
297 
298 /** Cleanup. */
299 void
300 RhtYNode::cleanup(void)
301 {
302  while (reuse_head) {
303  reuse_tail = (RhtYNode *)reuse_head->next;
304  delete reuse_head;
305  reuse_head = reuse_tail;
306  }
307 }
308 
309 /** Constructor.
310  * @param r r
311  */
313 {
314  this->r = r;
315  count = 0;
316 }
317 
318 /** Clear. */
319 void
320 RhtRNode::clear(void)
321 {
322  count = 0;
323 }
324 
325 /** Insert.
326  * @param r0 r
327  * @return ?
328  */
329 int
330 RhtRNode::insert(int r0)
331 {
332  if (r == r0) {
333  return ++count;
334  } else if (r0 < r) {
335  if (!left)
336  left = generate(r0);
337  return ((RhtRNode *)left)->insert(r0);
338  } else {
339  if (!right)
340  right = generate(r0);
341  return ((RhtRNode *)right)->insert(r0);
342  }
343 }
344 
345 /** Get nodes.
346  * @param rv return value
347  * @param min_votes min votes
348  * @param x x
349  * @param y y
350  */
351 void
352 RhtRNode::getNodes(std::vector<std::vector<int>> *rv, int min_votes, int x, int y)
353 {
354  if (left) {
355  ((RhtRNode *)left)->getNodes(rv, min_votes, x, y);
356  }
357  if (count >= min_votes) {
358  vector<int> node;
359  node.push_back(x);
360  node.push_back(y);
361  node.push_back(r);
362  node.push_back(count);
363  rv->push_back(node);
364  }
365  if (right) {
366  ((RhtRNode *)right)->getNodes(rv, min_votes, x, y);
367  }
368 }
369 
370 /** Dump.
371  * @param s dump to s
372  * @param x x
373  * @param y y
374  */
375 void
376 RhtRNode::dump(std::ostream &s, int x, int y)
377 {
378  if (left)
379  ((RhtRNode *)left)->dump(s, x, y);
380  s << "(" << x << "," << y << "," << r << ") with vote " << count << endl;
381  if (right)
382  ((RhtRNode *)right)->dump(s, x, y);
383 }
384 
385 /** Generate.
386  * @param r r
387  * @return node
388  */
390 RhtRNode::generate(int r)
391 {
392  if (reuse_tail == NULL) {
393  RhtRNode *p = new RhtRNode(r);
394  p->next = reuse_head;
395  reuse_head = p;
396  return reuse_head;
397  } else {
398  RhtRNode *p = reuse_tail;
399  reuse_tail = (RhtRNode *)(reuse_tail->next);
400  p->clear(r);
401  return p;
402  }
403 }
404 
405 /** Clear.
406  * @param r r
407  */
408 void
409 RhtRNode::clear(int r)
410 {
412  this->r = r;
413  count = 0;
414 }
415 
416 /** Reset. */
417 void
418 RhtRNode::reset(void)
419 {
420  reuse_tail = reuse_head;
421 }
422 
423 /** Cleanup. */
424 void
425 RhtRNode::cleanup(void)
426 {
427  while (reuse_head) {
428  reuse_tail = (RhtRNode *)reuse_head->next;
429  delete reuse_head;
430  reuse_head = reuse_tail;
431  }
432 }
433 
434 /** Constructor. */
436 {
437  root = NULL;
438  max = 0;
439 }
440 
441 /** Destructor. */
443 {
447 }
448 
449 /** Reset. */
450 void
452 {
453  max = 0;
454  root = NULL;
455  num_votes = 0;
456  RhtXNode::reset();
457  RhtYNode::reset();
458  RhtRNode::reset();
459 }
460 
461 /** Accumulate new candidate.
462  * @param x x
463  * @param y y
464  * @param r r
465  * @return count
466  */
467 int
468 RhtAccumulator::accumulate(int x, int y, int r)
469 {
470  ++num_votes;
471 
472  if (!root)
473  root = RhtXNode::generate(x);
474  int count = root->insert(x, y, r);
475  if (count > max) {
476  max = count;
477  x_max = x;
478  y_max = y;
479  r_max = r;
480  }
481  return count;
482 }
483 
484 /** Get maximum
485  * @param x x return value
486  * @param y y return value
487  * @param r r return value
488  * @return max
489  */
490 int
491 RhtAccumulator::getMax(int &x, int &y, int &r) const
492 {
493  x = x_max;
494  y = y_max;
495  r = r_max;
496  return max;
497 }
498 
499 /** Dump.
500  * @param s stream
501  */
502 void
503 RhtAccumulator::dump(std::ostream &s)
504 {
505  if (root)
506  root->dump(s);
507 }
508 
509 /** Get number of votes.
510  * @return number of votes
511  */
512 unsigned int
514 {
515  return num_votes;
516 }
517 
518 /** Get nodes.
519  * @param min_votes min votes
520  * @return nodes
521  */
522 vector<vector<int>> *
523 RhtAccumulator::getNodes(int min_votes)
524 {
525  vector<vector<int>> *rv = new vector<vector<int>>();
526 
527  if ((min_votes <= num_votes) && (root != NULL)) {
528  root->getNodes(rv, min_votes);
529  }
530 
531  return rv;
532 }
533 
534 } // end namespace firevision
firevision::RhtRNode::getNodes
void getNodes(std::vector< std::vector< int >> *rv, int min_votes, int x, int y)
Get nodes.
Definition: ht_accum.cpp:351
firevision::RhtYNode::cleanup
static void cleanup(void)
Cleanup.
Definition: ht_accum.cpp:299
firevision::RhtYNode::insert
int insert(int y, int r)
Insert.
Definition: ht_accum.cpp:207
firevision::RhtXNode::clear
void clear(int x)
Clear.
Definition: ht_accum.cpp:167
firevision::RhtAccNode::left
RhtAccNode * left
left
Definition: ht_accum.h:51
firevision::RhtAccumulator::getNumVotes
unsigned int getNumVotes() const
Get number of votes.
Definition: ht_accum.cpp:512
firevision::RhtYNode::r_root
RhtRNode * r_root
r_root
Definition: ht_accum.h:93
firevision::RhtAccumulator::reset
void reset(void)
Reset.
Definition: ht_accum.cpp:450
firevision::RhtRNode
Definition: ht_accum.h:53
firevision::RhtRNode::clear
void clear(void)
Clear.
Definition: ht_accum.cpp:319
firevision::RhtAccNode::next
RhtAccNode * next
used for recycling
Definition: ht_accum.h:55
firevision::RhtAccumulator::accumulate
int accumulate(int x, int y, int r)
Accumulate new candidate.
Definition: ht_accum.cpp:467
firevision::RhtYNode
Definition: ht_accum.h:78
firevision::RhtXNode::cleanup
static void cleanup(void)
Cleanup.
Definition: ht_accum.cpp:183
firevision::RhtAccumulator::getNodes
std::vector< std::vector< int > > * getNodes(int min_count)
Get nodes.
Definition: ht_accum.cpp:522
firevision::RhtRNode::r
int r
r
Definition: ht_accum.h:69
firevision::RhtRNode::dump
void dump(std::ostream &, int x, int y)
Dump.
Definition: ht_accum.cpp:375
firevision::RhtXNode::generate
static RhtXNode * generate(int x)
Generate.
Definition: ht_accum.cpp:148
firevision::RhtAccNode::clear
virtual void clear(int ignore)
Clear.
Definition: ht_accum.cpp:72
firevision::RhtYNode::dump
void dump(std::ostream &, int x)
Dump.
Definition: ht_accum.cpp:250
firevision::RhtXNode::x
int x
x
Definition: ht_accum.h:116
firevision::RhtRNode::count
int count
count
Definition: ht_accum.h:71
firevision::RhtYNode::generate
static RhtYNode * generate(int y)
Generate.
Definition: ht_accum.cpp:264
firevision::RhtYNode::clear
void clear(int y)
Clear.
Definition: ht_accum.cpp:283
firevision::RhtRNode::RhtRNode
RhtRNode(int r)
Constructor.
Definition: ht_accum.cpp:311
firevision::RhtYNode::getNodes
void getNodes(std::vector< std::vector< int >> *rv, int min_votes, int x)
Get nodes.
Definition: ht_accum.cpp:230
firevision::RhtRNode::reset
static void reset(void)
Reset.
Definition: ht_accum.cpp:417
firevision::RhtAccNode
Definition: ht_accum.h:37
firevision::RhtAccumulator::getMax
int getMax(int &x, int &y, int &r) const
Get maximum.
Definition: ht_accum.cpp:490
firevision::RhtXNode
Definition: ht_accum.h:103
firevision::RhtXNode::dump
void dump(std::ostream &)
Dump to stream.
Definition: ht_accum.cpp:134
firevision::RhtXNode::insert
int insert(int x, int y, int r)
Insert node.
Definition: ht_accum.cpp:93
firevision::RhtRNode::insert
int insert(int r)
Insert.
Definition: ht_accum.cpp:329
firevision::RhtAccumulator::~RhtAccumulator
~RhtAccumulator()
Destructor.
Definition: ht_accum.cpp:441
firevision::RhtXNode::y_root
RhtYNode * y_root
y root
Definition: ht_accum.h:118
firevision::RhtXNode::getNodes
void getNodes(std::vector< std::vector< int >> *rv, int min_votes)
Get nodes.
Definition: ht_accum.cpp:115
firevision::RhtYNode::reset
static void reset(void)
Reset.
Definition: ht_accum.cpp:292
firevision::RhtYNode::y
int y
y
Definition: ht_accum.h:91
firevision::RhtXNode::RhtXNode
RhtXNode(int x)
Constructor.
Definition: ht_accum.cpp:80
firevision::RhtAccumulator::dump
void dump(std::ostream &)
Dump.
Definition: ht_accum.cpp:502
firevision::RhtRNode::cleanup
static void cleanup(void)
Cleanup.
Definition: ht_accum.cpp:424
firevision::RhtAccNode::right
RhtAccNode * right
right
Definition: ht_accum.h:53
firevision::RhtAccumulator::RhtAccumulator
RhtAccumulator()
Constructor.
Definition: ht_accum.cpp:434
firevision::RhtRNode::generate
static RhtRNode * generate(int r)
Generate.
Definition: ht_accum.cpp:389
firevision::RhtYNode::RhtYNode
RhtYNode(int y)
Constructor.
Definition: ht_accum.cpp:195
firevision::RhtXNode::reset
static void reset(void)
Reset.
Definition: ht_accum.cpp:176