Fawkes API  Fawkes Development Version
hough_transform.h
00001 
00002 /***************************************************************************
00003  *  hough_transform.h - Hough Transform
00004  *
00005  *  Created: Mon Dec 28 2009 18:65:04 (based on FireVision's HtAccum)
00006  *  Copyright  2009  Tim Niemueller [www.niemueller.de]
00007  *             2005  Hu Yuxiao      <Yuxiao.Hu@rwth-aachen.de> (FireVision)
00008  *
00009  ****************************************************************************/
00010 
00011 /*  This program is free software; you can redistribute it and/or modify
00012  *  it under the terms of the GNU General Public License as published by
00013  *  the Free Software Foundation; either version 2 of the License, or
00014  *  (at your option) any later version. A runtime exception applies to
00015  *  this software (see LICENSE.GPL_WRE file mentioned below for details).
00016  *
00017  *  This program is distributed in the hope that it will be useful,
00018  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00019  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00020  *  GNU Library General Public License for more details.
00021  *
00022  *  Read the full text in the LICENSE.GPL_WRE file in the doc directory.
00023  */
00024 
00025 #ifndef __PLUGINS_LASERHT_HT_ACCUM_H_
00026 #define __PLUGINS_LASERHT_HT_ACCUM_H_
00027 
00028 class HoughTransform {
00029  private:
00030   class Node {
00031     friend class HoughTransform;
00032   public:
00033     Node(HoughTransform *ht, unsigned int dims, int value = 0);
00034     ~Node();
00035 
00036     unsigned int insert(int *values);
00037 
00038     unsigned int num_nodes();
00039     unsigned int depth();
00040 
00041     unsigned int filter(int **values, unsigned int min_count);
00042 
00043   private:
00044     Node(HoughTransform *ht, Node *parent, unsigned int dims, int value = 0);
00045     Node(HoughTransform *ht = 0);
00046 
00047     void reinit(Node *parent, unsigned int dims, int value) {
00048       __parent = parent;
00049       __left = __right  = __dim_next = 0;
00050       __value = value;
00051       __dims = dims;
00052     }    
00053 
00054     Node * filter(Node *tail, unsigned int min_count);
00055     unsigned int filtered_length();
00056 
00057   private:
00058     unsigned int __dims;
00059 
00060     unsigned int __count;
00061     int   __value;
00062 
00063     HoughTransform *__ht;
00064 
00065     Node *__parent; // that is the "value parent", not necessarily tree parent
00066     Node *__left;
00067     Node *__right;
00068     Node *__dim_next;
00069 
00070     Node *__filter_next;
00071 
00072     // for re-use (avoiding re-allocations)
00073     Node *__reuse_next;
00074   };
00075 
00076  public:
00077   HoughTransform(unsigned int num_dims);
00078   ~HoughTransform();
00079 
00080   void process(int **values, unsigned int num_values);
00081   unsigned int max(int *values) const;
00082 
00083   unsigned int filter(int **values, unsigned int min_count);
00084 
00085   void reset();
00086 
00087   Node *  root();
00088 
00089   inline Node * create_node(Node *parent, unsigned int dims, int value = 0)
00090   {
00091     if (__reuse_cur != 0) {
00092       Node *rv = __reuse_cur;
00093       rv->reinit(parent, dims, value);
00094       __reuse_cur = __reuse_cur->__reuse_next;
00095       return rv;
00096     } else {
00097       Node *rv = new Node(this, parent, dims, value);
00098       __reuse_tail->__reuse_next = rv;
00099       __reuse_tail = rv;
00100       return rv;
00101     }
00102   }
00103 
00104  private:
00105   Node *__root;
00106   Node *__reuse_head;
00107   Node *__reuse_cur;
00108   Node *__reuse_tail;
00109 
00110   unsigned int __num_dims;
00111   unsigned int __max_count;
00112   int *__max_values;
00113 };
00114 
00115 
00116 #endif