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