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 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 }