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