Fawkes API Fawkes Development Version

hough_transform.cpp

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 }
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends