00001
00002 /***************************************************************************
00003  *  ht_accum.cpp - Accumulator class for HoughTransform
00004  *
00005  *  Generated: Tue Jun 28 2005
00006  *  Copyright  2005  Hu Yuxiao      <Yuxiao.Hu@rwth-aachen.de>
00007  *
00008  ****************************************************************************/
00009
00010 /*  This program is free software; you can redistribute it and/or modify
00011  *  it under the terms of the GNU General Public License as published by
00012  *  the Free Software Foundation; either version 2 of the License, or
00013  *  (at your option) any later version. A runtime exception applies to
00014  *  this software (see LICENSE.GPL_WRE file mentioned below for details).
00015  *
00016  *  This program is distributed in the hope that it will be useful,
00017  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019  *  GNU Library General Public License for more details.
00020  *
00021  *  Read the full text in the LICENSE.GPL_WRE file in the doc directory.
00022  */
00023
00024 #include "models/shape/accumulators/ht_accum.h"
00025
00026 using namespace std;
00027
00028 RhtXNode* RhtXNode::reuse_head = NULL;
00029 RhtYNode* RhtYNode::reuse_head = NULL;
00030 RhtRNode* RhtRNode::reuse_head = NULL;
00031
00032 RhtXNode* RhtXNode::reuse_tail = NULL;
00033 RhtYNode* RhtYNode::reuse_tail = NULL;
00034 RhtRNode* RhtRNode::reuse_tail = NULL;
00035 
00036 /** @class RhtAccNode <models/shape/accumulators/ht_accum.h>
00037  * Hough-Transform accumulator node.
00038  */
00039 
00040 /** @class RhtRNode <models/shape/accumulators/ht_accum.h>
00041  * Hough-Transform accumulator node.
00042  */
00043 
00044 /** @class RhtXNode <models/shape/accumulators/ht_accum.h>
00045  * Hough-Transform accumulator node.
00046  */
00047 
00048 /** @class RhtYNode <models/shape/accumulators/ht_accum.h>
00049  * Hough-Transform accumulator node.
00050  */
00051 
00052 /** @class RhtAccumulator <models/shape/accumulators/ht_accum.h>
00053  * Hough-Transform accumulator.
00054  */
00055 
00056 /** Constructor. */
00057 RhtAccNode::RhtAccNode()
00058 {
00059   left = right = next = NULL;
00060 }
00061
00062 
00063 /** Destructor. */
00064 RhtAccNode::~RhtAccNode()
00065 {
00066 }
00067 
00068 /** Clear.
00069  * @param ignore ignored
00070  */
00071 void
00072 RhtAccNode::clear(int ignore)
00073 {
00074   left = right = NULL;
00075 }
00076
00077 
00078 /** Constructor.
00079  * @param x x
00080  */
00081 RhtXNode::RhtXNode(int x)
00082   : RhtAccNode()
00083 {
00084   this->x=x;
00085   y_root = NULL;
00086 }
00087
00088 
00089 /** Insert node.
00090  * @param x0 x
00091  * @param y0 y
00092  * @param r0 r
00093  * @return ?
00094  */
00095 int
00096 RhtXNode::insert(int x0, int y0, int r0)
00097 {
00098   if (x == x0)
00099     {
00100       if (!y_root)
00101         y_root = RhtYNode::generate(y0);
00102       return y_root->insert(y0, r0);
00103     }
00104   else if (x0 < x)
00105     {
00106       if (!left)
00107         left = generate(x0);
00108       return ((RhtXNode*)left)->insert(x0, y0, r0);
00109     }
00110   else
00111     {
00112       if (!right)
00113         right = generate(x0);
00114       return ((RhtXNode*)right)->insert(x0, y0, r0);
00115     }
00116 }
00117 
00118 /** Get nodes.
00119  * @param rv return value
00120  * @param min_votes minimum nomber of votes
00121  */
00122 void
00123 RhtXNode::getNodes(std::vector< std::vector< int > > *rv, int min_votes)
00124 {
00125   if (left) {
00126     ((RhtXNode*)left)->getNodes(rv, min_votes);
00127   }
00128
00129   if (y_root) {
00130     y_root->getNodes(rv, min_votes, x);
00131   }
00132
00133   if (right) {
00134     ((RhtXNode*)right)->getNodes(rv, min_votes);
00135   }
00136 }
00137 
00138 /** Dump to stream.
00139  * @param s stream to dump to.
00140  */
00141 void
00142 RhtXNode::dump(std::ostream& s)
00143 {
00144   if (left)
00145     ((RhtXNode*)left)->dump(s);
00146   y_root->dump(s, x);
00147   if (right)
00148     ((RhtXNode*)right)->dump(s);
00149 }
00150 
00151 /** Generate.
00152  * @param x ?
00153  * @return node
00154  */
00155 RhtXNode *
00156 RhtXNode::generate(int x)
00157 {
00158   if (reuse_tail == NULL)
00159     {
00160       RhtXNode* p=new RhtXNode(x);
00161       p->next = reuse_head;
00162       reuse_head = p;
00163       return reuse_head;
00164     }
00165   else
00166     {
00167       RhtXNode* p=reuse_tail;
00168       reuse_tail = (RhtXNode*)(reuse_tail->next);
00169       p->clear(x);
00170       return p;
00171     }
00172 }
00173
00174 
00175 /** Clear.
00176  * @param x x to clear
00177  */
00178 void
00179 RhtXNode::clear(int x)
00180 {
00181   RhtAccNode::clear(x);
00182   this->x = x;
00183   y_root = NULL;
00184 }
00185 
00186 /** Reset. */
00187 void
00188 RhtXNode::reset(void)
00189 {
00190   reuse_tail = reuse_head;
00191 }
00192
00193 
00194 /** Cleanup. */
00195 void
00196 RhtXNode::cleanup(void)
00197 {
00198   while(reuse_head)
00199     {
00200       reuse_tail = (RhtXNode*)reuse_head->next;
00201       delete reuse_head;
00202       reuse_head = reuse_tail;
00203     }
00204 }
00205
00206 
00207 /** Constructor.
00208  * @param y y
00209  */
00210 RhtYNode::RhtYNode(int y)
00211   : RhtAccNode()
00212 {
00213   this->y=y;
00214   r_root = NULL;
00215 }
00216 
00217 /** Insert.
00218  * @param y0 y
00219  * @param r0 r
00220  */
00221 int
00222 RhtYNode::insert(int y0, int r0)
00223 {
00224   if (y == y0)
00225     {
00226       if (!r_root)
00227         r_root = RhtRNode::generate(r0);
00228       return r_root->insert(r0);
00229     }
00230   else if (y0 < y)
00231     {
00232       if (!left)
00233         left = generate(y0);
00234       return ((RhtYNode*)left)->insert(y0, r0);
00235     }
00236   else
00237     {
00238       if (!right)
00239         right = generate(y0);
00240       return ((RhtYNode*)right)->insert(y0, r0);
00241     }
00242 }
00243 
00244 /** Get nodes.
00245  * @param rv return value
00246  * @param min_votes min votes
00247  * @param x x
00248  */
00249 void
00250 RhtYNode::getNodes(std::vector< std::vector< int > > *rv, int min_votes, int x)
00251 {
00252   if (left) {
00253     ((RhtYNode*)left)->getNodes(rv, min_votes, x);
00254   }
00255
00256   if (r_root) {
00257     r_root->getNodes(rv, min_votes, x, y);
00258   }
00259
00260   if (right) {
00261     ((RhtYNode*)right)->getNodes(rv, min_votes, x);
00262   }
00263 }
00264
00265 
00266 /** Dump.
00267  * @param s dump to s
00268  * @param x x
00269  */
00270 void
00271 RhtYNode::dump(std::ostream& s, int x)
00272 {
00273   if (left)
00274     ((RhtYNode*)left)->dump(s, x);
00275   r_root->dump(s, x, y);
00276   if (right)
00277     ((RhtYNode*)right)->dump(s, x);
00278 }
00279
00280 
00281 /** Generate.
00282  * @param y y
00283  * @return node
00284  */
00285 RhtYNode *
00286 RhtYNode::generate(int y)
00287 {
00288   if (reuse_tail == NULL)
00289     {
00290       RhtYNode* p=new RhtYNode(y);
00291       p->next = reuse_head;
00292       reuse_head = p;
00293       return reuse_head;
00294     }
00295   else
00296     {
00297       RhtYNode* p=reuse_tail;
00298       reuse_tail = (RhtYNode*)(reuse_tail->next);
00299       p->clear(y);
00300       return p;
00301     }
00302 }
00303
00304 
00305 /** Clear.
00306  * @param y y
00307  */
00308 void
00309 RhtYNode::clear(int y)
00310 {
00311   RhtAccNode::clear(y);
00312   this->y = y;
00313   r_root = NULL;
00314 }
00315 
00316 /** Reset. */
00317 void
00318 RhtYNode::reset(void)
00319 {
00320   reuse_tail = reuse_head;
00321 }
00322
00323 
00324 /** Cleanup. */
00325 void
00326 RhtYNode::cleanup(void)
00327 {
00328   while(reuse_head)
00329     {
00330       reuse_tail = (RhtYNode*)reuse_head->next;
00331       delete reuse_head;
00332       reuse_head = reuse_tail;
00333     }
00334 }
00335 
00336 /** Constructor.
00337  * @param r r
00338  */
00339 RhtRNode::RhtRNode(int r)
00340   : RhtAccNode()
00341 {
00342   this->r=r; count = 0;
00343 }
00344
00345 
00346 /** Clear. */
00347 void
00348 RhtRNode::clear(void)
00349 {
00350   count = 0;
00351 }
00352
00353
00354 
00355 /** Insert.
00356  * @param r0 r
00357  * @return ?
00358  */
00359 int RhtRNode::insert(int r0)
00360 {
00361   if (r == r0)
00362     {
00363       return ++count;
00364     }
00365   else if (r0 < r)
00366     {
00367       if (!left)
00368         left = generate(r0);
00369       return ((RhtRNode*)left)->insert(r0);
00370     }
00371   else
00372     {
00373       if (!right)
00374         right = generate(r0);
00375       return ((RhtRNode*)right)->insert(r0);
00376     }
00377 }
00378 
00379 /** Get nodes.
00380  * @param rv return value
00381  * @param min_votes min votes
00382  * @param x x
00383  * @param y y
00384  */
00385 void
00386 RhtRNode::getNodes(std::vector< std::vector< int > > *rv, int min_votes, int x, int y)
00387 {
00388   if (left) {
00389     ((RhtRNode*)left)->getNodes(rv, min_votes, x, y);
00390   }
00391   if (count >= min_votes) {
00392     vector< int > node;
00393     node.push_back( x );
00394     node.push_back( y );
00395     node.push_back( r );
00396     node.push_back( count );
00397     rv->push_back( node );
00398   }
00399   if (right) {
00400     ((RhtRNode*)right)->getNodes(rv, min_votes, x, y);
00401   }
00402 }
00403
00404 
00405 /** Dump.
00406  * @param s dump to s
00407  * @param x x
00408  * @param y y
00409  */
00410 void
00411 RhtRNode::dump(std::ostream& s, int x, int y)
00412 {
00413   if (left)
00414     ((RhtRNode*)left)->dump(s, x, y);
00415   s << "("<<x<<","<<y<<","<<r<<") with vote "<<count<<endl;
00416   if (right)
00417     ((RhtRNode*)right)->dump(s, x, y);
00418 }
00419
00420 
00421 /** Generate.
00422  * @param r r
00423  * @return node
00424  */
00425 RhtRNode *
00426 RhtRNode::generate(int r)
00427 {
00428   if (reuse_tail == NULL)
00429     {
00430       RhtRNode* p=new RhtRNode(r);
00431       p->next = reuse_head;
00432       reuse_head = p;
00433       return reuse_head;
00434     }
00435   else
00436     {
00437       RhtRNode* p=reuse_tail;
00438       reuse_tail = (RhtRNode*)(reuse_tail->next);
00439       p->clear(r);
00440       return p;
00441     }
00442 }
00443 
00444 /** Clear.
00445  * @param r r
00446  */
00447 void
00448 RhtRNode::clear(int r)
00449 {
00450   RhtAccNode::clear(r);
00451   this->r = r;
00452   count = 0;
00453 }
00454 
00455 /** Reset. */
00456 void
00457 RhtRNode::reset(void)
00458 {
00459   reuse_tail = reuse_head;
00460 }
00461 
00462 /** Cleanup. */
00463 void
00464 RhtRNode::cleanup(void)
00465 {
00466   while(reuse_head)
00467     {
00468       reuse_tail = (RhtRNode*)reuse_head->next;
00469       delete reuse_head;
00470       reuse_head = reuse_tail;
00471     }
00472 }
00473
00474 
00475 /** Constructor. */
00476 RhtAccumulator::RhtAccumulator()
00477 {
00478   root = NULL;
00479   max=0;
00480 }
00481
00482 
00483 /** Destructor. */
00484 RhtAccumulator::~RhtAccumulator()
00485 {
00486   RhtXNode::cleanup();
00487   RhtYNode::cleanup();
00488   RhtRNode::cleanup();
00489 }
00490
00491 
00492 /** Reset. */
00493 void
00494 RhtAccumulator::reset(void)
00495 {
00496   max = 0;
00497   root = NULL;
00498   num_votes = 0;
00499   RhtXNode::reset();
00500   RhtYNode::reset();
00501   RhtRNode::reset();
00502 }
00503
00504 
00505 /** Accumulate new candidate.
00506  * @param x x
00507  * @param y y
00508  * @param r r
00509  * @return count
00510  */
00511 int
00512 RhtAccumulator::accumulate(int x, int y, int r)
00513 {
00514   ++num_votes;
00515
00516   if (!root)
00517     root = RhtXNode::generate(x);
00518   int count = root->insert(x, y, r);
00519   if (count > max) {
00520     max = count;
00521     x_max = x;
00522     y_max = y;
00523     r_max = r;
00524   }
00525   return count;
00526 }
00527
00528 
00529 /** Get maximum
00530  * @param x x return value
00531  * @param y y return value
00532  * @param r r return value
00533  * @return max
00534  */
00535 int
00536 RhtAccumulator::getMax(int &x, int &y, int &r) const
00537 {
00538   x = x_max;
00539   y = y_max;
00540   r = r_max;
00541   return max;
00542 }
00543 
00544 /** Dump.
00545  * @param s stream
00546  */
00547 void
00548 RhtAccumulator::dump(std::ostream& s)
00549 {
00550   if (root)
00551     root->dump(s);
00552 }
00553
00554 
00555 /** Get number of votes.
00556  * @return number of votes
00557  */
00558 unsigned int
00559 RhtAccumulator::getNumVotes() const
00560 {
00561   return num_votes;
00562 }
00563
00564 
00565 /** Get nodes.
00566  * @param min_votes min votes
00567  * @return nodes
00568  */
00569 vector< vector< int > > *
00570 RhtAccumulator::getNodes(int min_votes)
00571 {
00572   vector< vector< int > > *rv = new vector< vector< int > >();
00573
00574   if ( (min_votes <= num_votes) && (root != NULL) ) {
00575     root->getNodes( rv, min_votes );
00576   }
00577
00578   return rv;
00579 }