Fawkes API
Fawkes Development Version
|
00001 00002 /*************************************************************************** 00003 * hough_transform.cpp - Hough Transform 00004 * 00005 * Created: Mon Dec 28 2009 18:56:04 00006 * Copyright 2009 Tim Niemueller [www.niemueller.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 "hough_transform.h" 00025 00026 #include <algorithm> 00027 #include <cstdio> 00028 #include <cstdlib> 00029 00030 /** @class HoughTransform "hough_transform.h" 00031 * Hough Transformation for N-dimensional representations. 00032 * This class implements a generic Hough transformation, which can operate 00033 * on representations of arbitrary dimension (at least in theory ignoring 00034 * computational feasibility). 00035 * The implementation uses a tree structure to represent the buckets in the 00036 * Hough space, to reduce the amount of memory required on sparse data 00037 * sets and to allow fast insertion of new samples. 00038 * The code is based on ideas from a Hough transform implemented in 00039 * FireVision, but eliminating some of its limitations. 00040 * @author Tim Niemueller 00041 * 00042 * @fn inline Node * HoughTransform::create_node(Node *parent, unsigned int dims, int value = 0) 00043 * Create a new node. 00044 * @param parent parent node of the new node 00045 * @param dims Dimensions remaining 00046 * @param value initial value 00047 * @return new node with given parent, dimensions, and initial value 00048 */ 00049 00050 /** Constructor. 00051 * @param num_dims number of dimensions 00052 */ 00053 HoughTransform::HoughTransform(unsigned int num_dims) 00054 { 00055 __root = new Node(this, num_dims); 00056 00057 __num_dims = num_dims; 00058 00059 __reuse_head = new Node(this); 00060 __reuse_cur = __reuse_head; 00061 __reuse_tail = __reuse_head; 00062 00063 __max_count = 0; 00064 __max_values = new int[num_dims]; 00065 } 00066 00067 /** Destructor. */ 00068 HoughTransform::~HoughTransform() 00069 { 00070 while (__reuse_head) { 00071 Node *n = __reuse_head; 00072 __reuse_head = __reuse_head->__reuse_next; 00073 delete n; 00074 } 00075 00076 delete[] __max_values; 00077 } 00078 00079 /** Process some samples. 00080 * @param values two dimensional array of values. The first index determines 00081 * the sample index, the second index the dimension index. Thus its an 00082 * array with the length of number of values of arrays with the length of 00083 * the number of dimensions. 00084 * @param num_values number of rows in values 00085 */ 00086 void 00087 HoughTransform::process(int **values, unsigned int num_values) 00088 { 00089 for (unsigned int i = 0; i < num_values; ++i) { 00090 unsigned int count = __root->insert(values[i]); 00091 if (count > __max_count) { 00092 __max_count = count; 00093 for (unsigned int d = 0; d < __num_dims; ++d) { 00094 __max_values[d] = values[i][d]; 00095 } 00096 } 00097 } 00098 } 00099 00100 /** Get maximum values. 00101 * During processing the maximum values, i.e. the candidate with the 00102 * maximum number of votes or the most filled bucket, is stored and can 00103 * be retrieved with this method. 00104 * @param values upon return contains the maximum voted values 00105 * @return number of votes of the values 00106 */ 00107 unsigned int 00108 HoughTransform::max(int *values) const 00109 { 00110 for (unsigned int d = 0; d < __num_dims; ++d) { 00111 values[d] = __max_values[d]; 00112 } 00113 return __max_count; 00114 } 00115 00116 00117 /** Filter values by number of votes. 00118 * This method filters all created buckets and returns only the ones which 00119 * have at least @p min_count votes 00120 * @param values upon return points to a newly allocated array of values with 00121 * the size of number of values * number of dimensions. The memory must be 00122 * freed when done by using free(). 00123 * @param min_count minimum number of votes required to consider a bucket 00124 * @return number of values found 00125 */ 00126 unsigned int 00127 HoughTransform::filter(int **values, unsigned int min_count) 00128 { 00129 return __root->filter(values, min_count); 00130 } 00131 00132 00133 /** Get root node. 00134 * @return root node of internal tree, meant for debugging and performance 00135 * evaluation 00136 */ 00137 HoughTransform::Node * 00138 HoughTransform::root() 00139 { 00140 return __root; 00141 } 00142 00143 /** Reset Hough transform. 00144 * This deletes the internal tree and creates a new empty one. */ 00145 void 00146 HoughTransform::reset() 00147 { 00148 __reuse_cur = __reuse_head; 00149 __root = create_node(NULL, __num_dims); 00150 __max_count = 0; 00151 for (unsigned int d = 0; d < __num_dims; ++d) { 00152 __max_values[d] = 0; 00153 } 00154 } 00155 00156 /** @class HoughTransform::Node "hough_transform.h" 00157 * Hough transform tree node. 00158 * The nodes are used to form a tree. The tree is organized as stacked 00159 * binary trees. At a certain stack level, a value of a specific dimension 00160 * is stored, with the left and right sub-trees pointing to smaller or 00161 * higher values respectively. 00162 * Nodes with a stack level of 1 (e.g. the bottom-most level) have a field 00163 * to count the number of votes (these are the bucket nodes). Nodes on 00164 * higher levels have a pointer to another node on a stack level one lower 00165 * than the own, which represents the next dimension of the values. 00166 * @author Tim Niemueller 00167 * @author Hu Yuxiao 00168 */ 00169 00170 /** Constructor. 00171 * @param dims number of remaining dimensions (including the own) 00172 * @param value the initial value of the node 00173 */ 00174 HoughTransform::Node::Node(HoughTransform *ht, unsigned int dims, int value) 00175 { 00176 __ht = ht; 00177 __dims = dims; 00178 __value = value; 00179 __count = 0; 00180 __parent = NULL; 00181 __left = __right = __dim_next = __filter_next = __reuse_next = 0; 00182 } 00183 00184 /** Constructor with parent node. 00185 * @param parent parent node of the new node 00186 * @param dims number of remaining dimensions (including the own) 00187 * @param value the initial value of the node 00188 */ 00189 HoughTransform::Node::Node(HoughTransform *ht, 00190 Node *parent, unsigned int dims, int value) 00191 { 00192 __ht = ht; 00193 __parent = parent; 00194 __dims = dims; 00195 __value = value; 00196 __count = 0; 00197 __left = __right = __dim_next = __filter_next = __reuse_next = 0; 00198 } 00199 00200 /** Constructor. */ 00201 HoughTransform::Node::Node(HoughTransform *ht) 00202 { 00203 __ht = ht; 00204 __dims = 1; 00205 __value = 0; 00206 __count = 0; 00207 __parent = NULL; 00208 __left = __right = __dim_next = __filter_next = __reuse_next = 0; 00209 } 00210 00211 /** Destructor. */ 00212 HoughTransform::Node::~Node() 00213 { 00214 // sub-nodes delete by HoughTransform 00215 } 00216 00217 00218 /** Insert new values. 00219 * @param values array with new values, must be of the size of the number 00220 * of dimensions 00221 * @return number of votes of bucket the values have been inserted to 00222 */ 00223 unsigned int 00224 HoughTransform::Node::insert(int *values) 00225 { 00226 if (values[0] == __value) { 00227 if ( __dims > 1) { 00228 if (! __dim_next) { 00229 __dim_next = __ht->create_node(this, __dims - 1, values[1]); 00230 } 00231 00232 return __dim_next->insert(&(values[1])); 00233 } else { 00234 return ++__count; 00235 } 00236 } else if (values[0] < __value) { 00237 if (! __left) { 00238 __left = __ht->create_node(__parent, __dims, values[0]); 00239 } 00240 return __left->insert(values); 00241 } else { // values[0] > __value 00242 if (! __right) { 00243 __right = __ht->create_node(__parent, __dims, values[0]); 00244 } 00245 return __right->insert(values); 00246 } 00247 } 00248 00249 00250 /** Get number of nodes. 00251 * @return number of nodes 00252 */ 00253 unsigned int 00254 HoughTransform::Node::num_nodes() 00255 { 00256 unsigned int rv = 1; 00257 if (__left) rv += __left->num_nodes(); 00258 if (__right) rv += __right->num_nodes(); 00259 if (__dim_next) rv += __dim_next->num_nodes(); 00260 return rv; 00261 } 00262 00263 00264 /** Depth of the tree. 00265 * @return maximum depth of tree 00266 */ 00267 unsigned int 00268 HoughTransform::Node::depth() 00269 { 00270 unsigned int d = 0; 00271 if (__left) d = std::max(d, __left->depth()); 00272 if (__right) d = std::max(d, __right->depth()); 00273 if (__dim_next) d = std::max(d, __dim_next->depth()); 00274 return d + 1; 00275 } 00276 00277 00278 /** Get length of filtered list. 00279 * @return length of filtered list 00280 */ 00281 unsigned int 00282 HoughTransform::Node::filtered_length() 00283 { 00284 Node *t = this; 00285 // do not count first, is unused head element 00286 unsigned int rv = 0; 00287 while (t->__filter_next) { 00288 ++rv; 00289 t = t->__filter_next; 00290 } 00291 return rv; 00292 } 00293 00294 00295 /** Filter values by number of votes. 00296 * This method filters all created buckets and returns only the ones which 00297 * have at least @p min_count votes 00298 * @param values upon return points to a newly allocated array of values with the 00299 * size of number of values * number of dimensions. The memory must be freed 00300 * when done by using free(). 00301 * @param min_count minimum number of votes required to consider a bucket 00302 * @return number of values found 00303 */ 00304 unsigned int 00305 HoughTransform::Node::filter(int **values, unsigned int min_count) 00306 { 00307 Node *filtered_root = new Node(); 00308 filter(filtered_root, min_count); 00309 unsigned int flen = filtered_root->filtered_length(); 00310 00311 int *fvals = (int *)calloc(flen, __dims * sizeof(int)); 00312 Node *t = filtered_root; 00313 unsigned int f = 0; 00314 while ((t = t->__filter_next) != NULL) { 00315 Node *s = t; 00316 for (unsigned int i = 1; i <= __dims; ++i) { 00317 fvals[ __dims * (f + 1) - i ] = s->__value; 00318 s = s->__parent; 00319 } 00320 ++f; 00321 } 00322 00323 delete filtered_root; 00324 00325 *values = fvals; 00326 return flen; 00327 } 00328 00329 00330 /** Internal filter recursion function. 00331 * @param tail current tail 00332 * @param min_count minimum number of votes required to consider a bucket 00333 * @return new tail node 00334 */ 00335 HoughTransform::Node * 00336 HoughTransform::Node::filter(Node *tail, unsigned int min_count) 00337 { 00338 if (__dims == 1) { 00339 if (__count >= min_count) { 00340 // add this node 00341 this->__filter_next = NULL; 00342 tail->__filter_next = this; 00343 tail = this; 00344 } 00345 if (__left) tail = __left->filter(tail, min_count); 00346 if (__right) tail = __right->filter(tail, min_count); 00347 00348 } else { 00349 if (__dim_next) tail = __dim_next->filter(tail, min_count); 00350 if (__left) tail = __left->filter(tail, min_count); 00351 if (__right) tail = __right->filter(tail, min_count); 00352 } 00353 00354 return tail; 00355 }