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 ht hough transform the node belongs to 00172 * @param dims number of remaining dimensions (including the own) 00173 * @param value the initial value of the node 00174 */ 00175 HoughTransform::Node::Node(HoughTransform *ht, unsigned int dims, int value) 00176 { 00177 __ht = ht; 00178 __dims = dims; 00179 __value = value; 00180 __count = 0; 00181 __parent = NULL; 00182 __left = __right = __dim_next = __filter_next = __reuse_next = 0; 00183 } 00184 00185 /** Constructor with parent node. 00186 * @param parent parent node of the new node 00187 * @param dims number of remaining dimensions (including the own) 00188 * @param value the initial value of the node 00189 */ 00190 HoughTransform::Node::Node(HoughTransform *ht, 00191 Node *parent, unsigned int dims, int value) 00192 { 00193 __ht = ht; 00194 __parent = parent; 00195 __dims = dims; 00196 __value = value; 00197 __count = 0; 00198 __left = __right = __dim_next = __filter_next = __reuse_next = 0; 00199 } 00200 00201 /** Constructor. */ 00202 HoughTransform::Node::Node(HoughTransform *ht) 00203 { 00204 __ht = ht; 00205 __dims = 1; 00206 __value = 0; 00207 __count = 0; 00208 __parent = NULL; 00209 __left = __right = __dim_next = __filter_next = __reuse_next = 0; 00210 } 00211 00212 /** Destructor. */ 00213 HoughTransform::Node::~Node() 00214 { 00215 // sub-nodes delete by HoughTransform 00216 } 00217 00218 00219 /** Insert new values. 00220 * @param values array with new values, must be of the size of the number 00221 * of dimensions 00222 * @return number of votes of bucket the values have been inserted to 00223 */ 00224 unsigned int 00225 HoughTransform::Node::insert(int *values) 00226 { 00227 if (values[0] == __value) { 00228 if ( __dims > 1) { 00229 if (! __dim_next) { 00230 __dim_next = __ht->create_node(this, __dims - 1, values[1]); 00231 } 00232 00233 return __dim_next->insert(&(values[1])); 00234 } else { 00235 return ++__count; 00236 } 00237 } else if (values[0] < __value) { 00238 if (! __left) { 00239 __left = __ht->create_node(__parent, __dims, values[0]); 00240 } 00241 return __left->insert(values); 00242 } else { // values[0] > __value 00243 if (! __right) { 00244 __right = __ht->create_node(__parent, __dims, values[0]); 00245 } 00246 return __right->insert(values); 00247 } 00248 } 00249 00250 00251 /** Get number of nodes. 00252 * @return number of nodes 00253 */ 00254 unsigned int 00255 HoughTransform::Node::num_nodes() 00256 { 00257 unsigned int rv = 1; 00258 if (__left) rv += __left->num_nodes(); 00259 if (__right) rv += __right->num_nodes(); 00260 if (__dim_next) rv += __dim_next->num_nodes(); 00261 return rv; 00262 } 00263 00264 00265 /** Depth of the tree. 00266 * @return maximum depth of tree 00267 */ 00268 unsigned int 00269 HoughTransform::Node::depth() 00270 { 00271 unsigned int d = 0; 00272 if (__left) d = std::max(d, __left->depth()); 00273 if (__right) d = std::max(d, __right->depth()); 00274 if (__dim_next) d = std::max(d, __dim_next->depth()); 00275 return d + 1; 00276 } 00277 00278 00279 /** Get length of filtered list. 00280 * @return length of filtered list 00281 */ 00282 unsigned int 00283 HoughTransform::Node::filtered_length() 00284 { 00285 Node *t = this; 00286 // do not count first, is unused head element 00287 unsigned int rv = 0; 00288 while (t->__filter_next) { 00289 ++rv; 00290 t = t->__filter_next; 00291 } 00292 return rv; 00293 } 00294 00295 00296 /** Filter values by number of votes. 00297 * This method filters all created buckets and returns only the ones which 00298 * have at least @p min_count votes 00299 * @param values upon return points to a newly allocated array of values with the 00300 * size of number of values * number of dimensions. The memory must be freed 00301 * when done by using free(). 00302 * @param min_count minimum number of votes required to consider a bucket 00303 * @return number of values found 00304 */ 00305 unsigned int 00306 HoughTransform::Node::filter(int **values, unsigned int min_count) 00307 { 00308 Node *filtered_root = new Node(); 00309 filter(filtered_root, min_count); 00310 unsigned int flen = filtered_root->filtered_length(); 00311 00312 int *fvals = (int *)calloc(flen, __dims * sizeof(int)); 00313 Node *t = filtered_root; 00314 unsigned int f = 0; 00315 while ((t = t->__filter_next) != NULL) { 00316 Node *s = t; 00317 for (unsigned int i = 1; i <= __dims; ++i) { 00318 fvals[ __dims * (f + 1) - i ] = s->__value; 00319 s = s->__parent; 00320 } 00321 ++f; 00322 } 00323 00324 delete filtered_root; 00325 00326 *values = fvals; 00327 return flen; 00328 } 00329 00330 00331 /** Internal filter recursion function. 00332 * @param tail current tail 00333 * @param min_count minimum number of votes required to consider a bucket 00334 * @return new tail node 00335 */ 00336 HoughTransform::Node * 00337 HoughTransform::Node::filter(Node *tail, unsigned int min_count) 00338 { 00339 if (__dims == 1) { 00340 if (__count >= min_count) { 00341 // add this node 00342 this->__filter_next = NULL; 00343 tail->__filter_next = this; 00344 tail = this; 00345 } 00346 if (__left) tail = __left->filter(tail, min_count); 00347 if (__right) tail = __right->filter(tail, min_count); 00348 00349 } else { 00350 if (__dim_next) tail = __dim_next->filter(tail, min_count); 00351 if (__left) tail = __left->filter(tail, min_count); 00352 if (__right) tail = __right->filter(tail, min_count); 00353 } 00354 00355 return tail; 00356 }