[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

rf_nodeproxy.hxx VIGRA

1 /************************************************************************/
2 /* */
3 /* Copyright 2008-2009 by Ullrich Koethe and Rahul Nair */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35 
36 #ifndef VIGRA_RANDOM_FOREST_NP_HXX
37 #define VIGRA_RANDOM_FOREST_NP_HXX
38 
39 #include <algorithm>
40 #include <map>
41 #include <numeric>
42 #include "vigra/mathutil.hxx"
43 #include "vigra/array_vector.hxx"
44 #include "vigra/sized_int.hxx"
45 #include "vigra/matrix.hxx"
46 #include "vigra/random.hxx"
47 #include "vigra/functorexpression.hxx"
48 
49 
50 namespace vigra
51 {
52 
53 
54 
55 enum NodeTags
56 {
57  UnFilledNode = 42,
58  AllColumns = 0x00000000,
59  ToBePrunedTag = 0x80000000,
60  LeafNodeTag = 0x40000000,
61 
62  i_ThresholdNode = 0,
63  i_HyperplaneNode = 1,
64  i_HypersphereNode = 2,
65  e_ConstProbNode = 0 | LeafNodeTag,
66  e_LogRegProbNode = 1 | LeafNodeTag
67 };
68 
69 /** NodeBase class.
70 
71  \ingroup DecicionTree
72 
73  This class implements common features of all nodes.
74  Memory Structure:
75  Int32 Array: TypeID, ParameterAddr, Child0, Child1, [ColumnData]0_
76  double Array: NodeWeight, [Parameters]1_
77 
78  TODO: Throw away the crappy iterators and use vigra::ArrayVectorView
79  it is not like anybody else is going to use this NodeBase class
80  is it?
81 
82  TODO: use the RF_Traits::ProblemSpec_t to specify the external
83  parameters instead of the options.
84 */
85 
86 
87 class NodeBase
88 {
89  public:
90  typedef Int32 INT;
91  typedef ArrayVector<INT> T_Container_type;
92  typedef ArrayVector<double> P_Container_type;
93  typedef T_Container_type::iterator Topology_type;
94  typedef P_Container_type::iterator Parameter_type;
95 
96 
97  mutable Topology_type topology_;
98  int topology_size_;
99 
100  mutable Parameter_type parameters_;
101  int parameter_size_ ;
102 
103  // Tree Parameters
104  int featureCount_;
105  int classCount_;
106 
107  // Node Parameters
108  bool hasData_;
109 
110 
111 
112 
113  /** get Node Weight
114  */
115  double & weights()
116  {
117  return parameters_begin()[0];
118  }
119 
120  double const & weights() const
121  {
122  return parameters_begin()[0];
123  }
124 
125  /** has the data been set?
126  * todo: throw this out - bad design
127  */
128  bool data() const
129  {
130  return hasData_;
131  }
132 
133  /** get the node type id
134  * \sa NodeTags
135  */
136  INT& typeID()
137  {
138  return topology_[0];
139  }
140 
141  INT const & typeID() const
142  {
143  return topology_[0];
144  }
145 
146  /** Where in the parameter_ array are the weights?
147  */
148  INT & parameter_addr()
149  {
150  return topology_[1];
151  }
152 
153  INT const & parameter_addr() const
154  {
155  return topology_[1];
156  }
157 
158  /** Column Range **/
159  Topology_type column_data() const
160  {
161  return topology_ + 4 ;
162  }
163 
164  /** get the start iterator to the columns
165  * - once again - throw out - static members are crap.
166  */
167  Topology_type columns_begin() const
168  {
169  return column_data()+1;
170  }
171 
172  /** how many columns?
173  */
174  int columns_size() const
175  {
176  if(*column_data() == AllColumns)
177  return featureCount_;
178  else
179  return *column_data();;
180  }
181 
182  /** end iterator to the columns
183  */
184  Topology_type columns_end() const
185  {
186  return columns_begin() + columns_size();
187  }
188 
189  /** Topology Range - gives access to the raw Topo memory
190  * the size_ member was added as a result of premature
191  * optimisation.
192  */
193  Topology_type topology_begin() const
194  {
195  return topology_;
196  }
197  Topology_type topology_end() const
198  {
199  return topology_begin() + topology_size();
200  }
201  int topology_size() const
202  {
203  return topology_size_;
204  }
205 
206  /** Parameter Range **/
207  Parameter_type parameters_begin() const
208  {
209  return parameters_;
210  }
211  Parameter_type parameters_end() const
212  {
213  return parameters_begin() + parameters_size();
214  }
215 
216  int parameters_size() const
217  {
218  return parameter_size_;
219  }
220 
221 
222  /** where are the child nodes?
223  */
224  INT & child(Int32 l)
225  {
226  return topology_begin()[2+l];
227  }
228 
229  /** where are the child nodes?
230  */
231  INT const & child(Int32 l) const
232  {
233  return topology_begin()[2+l];
234  }
235 
236  /** Default Constructor**/
237  NodeBase()
238  :
239  hasData_(false)
240  {}
241  void copy(const NodeBase& o)
242  {
243  vigra_precondition(topology_size_==o.topology_size_,"Cannot copy nodes of different sizes");
244  vigra_precondition(featureCount_==o.featureCount_,"Cannot copy nodes with different feature count");
245  vigra_precondition(classCount_==o.classCount_,"Cannot copy nodes with different class counts");
246  vigra_precondition(parameters_size() ==o.parameters_size(),"Cannot copy nodes with different parameter sizes");
247  std::copy(o.topology_begin(), o.topology_end(), topology_);
248  std::copy(o.parameters_begin(),o.parameters_end(), parameters_);
249  }
250 
251  /** create ReadOnly Base Node at position n (actual length is unknown)
252  * only common features i.e. children etc are accessible.
253  */
254  NodeBase( T_Container_type const & topology,
255  P_Container_type const & parameter,
256  INT n)
257  :
258  topology_ (const_cast<Topology_type>(topology.begin()+ n)),
259  topology_size_(4),
260  parameters_ (const_cast<Parameter_type>(parameter.begin() + parameter_addr())),
261  parameter_size_(1),
262  featureCount_(topology[0]),
263  classCount_(topology[1]),
264  hasData_(true)
265  {
266  /*while((int)xrange.size() < featureCount_)
267  xrange.push_back(xrange.size());*/
268  }
269 
270  /** create ReadOnly node with known length (the parameter range is valid)
271  */
272  NodeBase( int tLen,
273  int pLen,
274  T_Container_type const & topology,
275  P_Container_type const & parameter,
276  INT n)
277  :
278  topology_ (const_cast<Topology_type>(topology.begin()+ n)),
279  topology_size_(tLen),
280  parameters_ (const_cast<Parameter_type>(parameter.begin() + parameter_addr())),
281  parameter_size_(pLen),
282  featureCount_(topology[0]),
283  classCount_(topology[1]),
284  hasData_(true)
285  {
286  /*while((int)xrange.size() < featureCount_)
287  xrange.push_back(xrange.size());*/
288  }
289  /** create ReadOnly node with known length
290  * from existing Node
291  */
292  NodeBase( int tLen,
293  int pLen,
294  NodeBase & node)
295  :
296  topology_ (node.topology_),
297  topology_size_(tLen),
298  parameters_ (node.parameters_),
299  parameter_size_(pLen),
300  featureCount_(node.featureCount_),
301  classCount_(node.classCount_),
302  hasData_(true)
303  {
304  /*while((int)xrange.size() < featureCount_)
305  xrange.push_back(xrange.size());*/
306  }
307 
308 
309  /** create new Node at end of vector
310  * \param tLen number of integers needed in the topolog vector
311  * \param pLen number of parameters needed (this includes the node
312  * weight)
313  * \param topology reference to Topology array of decision tree.
314  * \param parameter reference to Parameter array of decision tree.
315  **/
316  NodeBase( int tLen,
317  int pLen,
318  T_Container_type & topology,
319  P_Container_type & parameter)
320  :
321  topology_size_(tLen),
322  parameter_size_(pLen),
323  featureCount_(topology[0]),
324  classCount_(topology[1]),
325  hasData_(true)
326  {
327  /*while((int)xrange.size() < featureCount_)
328  xrange.push_back(xrange.size());*/
329 
330  size_t n = topology.size();
331  for(int ii = 0; ii < tLen; ++ii)
332  topology.push_back(0);
333  //topology.resize (n + tLen);
334 
335  topology_ = topology.begin()+ n;
336  typeID() = UnFilledNode;
337 
338  parameter_addr() = static_cast<int>(parameter.size());
339 
340  //parameter.resize(parameter.size() + pLen);
341  for(int ii = 0; ii < pLen; ++ii)
342  parameter.push_back(0);
343 
344  parameters_ = parameter.begin()+ parameter_addr();
345  weights() = 1;
346  }
347 
348 
349  /** PseudoCopy Constructor -
350  *
351  * Copy Node to the end of a container.
352  * Since each Node views on different data there can't be a real
353  * copy constructor (unless both objects should point to the
354  * same underlying data.
355  */
356  NodeBase( NodeBase const & toCopy,
357  T_Container_type & topology,
358  P_Container_type & parameter)
359  :
360  topology_size_(toCopy.topology_size()),
361  parameter_size_(toCopy.parameters_size()),
362  featureCount_(topology[0]),
363  classCount_(topology[1]),
364  hasData_(true)
365  {
366  /*while((int)xrange.size() < featureCount_)
367  xrange.push_back(xrange.size());*/
368 
369  size_t n = topology.size();
370  for(int ii = 0; ii < toCopy.topology_size(); ++ii)
371  topology.push_back(toCopy.topology_begin()[ii]);
372 // topology.insert(topology.end(), toCopy.topology_begin(), toCopy.topology_end());
373  topology_ = topology.begin()+ n;
374  parameter_addr() = static_cast<int>(parameter.size());
375  for(int ii = 0; ii < toCopy.parameters_size(); ++ii)
376  parameter.push_back(toCopy.parameters_begin()[ii]);
377 // parameter.insert(parameter.end(), toCopy.parameters_begin(), toCopy.parameters_end());
378  parameters_ = parameter.begin()+ parameter_addr();
379  }
380 };
381 
382 
383 template<NodeTags NodeType>
384 class Node;
385 
386 template<>
387 class Node<i_ThresholdNode>
388 : public NodeBase
389 {
390 
391 
392  public:
393  typedef NodeBase BT;
394 
395  /**constructors **/
396 
397  Node( BT::T_Container_type & topology,
398  BT::P_Container_type & param)
399  : BT(5,2,topology, param)
400  {
401  BT::typeID() = i_ThresholdNode;
402  }
403 
404  Node( BT::T_Container_type const & topology,
405  BT::P_Container_type const & param,
406  INT n )
407  : BT(5,2,topology, param, n)
408  {}
409 
410  Node( BT & node_)
411  : BT(5, 2, node_)
412  {}
413 
414  double& threshold()
415  {
416  return BT::parameters_begin()[1];
417  }
418 
419  double const & threshold() const
420  {
421  return BT::parameters_begin()[1];
422  }
423 
424  BT::INT& column()
425  {
426  return BT::column_data()[0];
427  }
428  BT::INT const & column() const
429  {
430  return BT::column_data()[0];
431  }
432 
433  template<class U, class C>
434  BT::INT next(MultiArrayView<2,U,C> const & feature) const
435  {
436  return (feature(0, column()) < threshold())? child(0):child(1);
437  }
438 };
439 
440 
441 template<>
442 class Node<i_HyperplaneNode>
443 : public NodeBase
444 {
445  public:
446 
447  typedef NodeBase BT;
448 
449  /**constructors **/
450 
451  Node( int nCol,
452  BT::T_Container_type & topology,
453  BT::P_Container_type & split_param)
454  : BT(nCol + 5,nCol + 2,topology, split_param)
455  {
456  BT::typeID() = i_HyperplaneNode;
457  }
458 
459  Node( BT::T_Container_type const & topology,
460  BT::P_Container_type const & split_param,
461  int n )
462  : NodeBase(5 , 2,topology, split_param, n)
463  {
464  //TODO : is there a more elegant way to do this?
465  BT::topology_size_ += BT::column_data()[0]== AllColumns ?
466  0
467  : BT::column_data()[0];
468  BT::parameter_size_ += BT::columns_size();
469  }
470 
471  Node( BT & node_)
472  : BT(5, 2, node_)
473  {
474  //TODO : is there a more elegant way to do this?
475  BT::topology_size_ += BT::column_data()[0]== AllColumns ?
476  0
477  : BT::column_data()[0];
478  BT::parameter_size_ += BT::columns_size();
479  }
480 
481 
482  double const & intercept() const
483  {
484  return BT::parameters_begin()[1];
485  }
486  double& intercept()
487  {
488  return BT::parameters_begin()[1];
489  }
490 
491  BT::Parameter_type weights() const
492  {
493  return BT::parameters_begin()+2;
494  }
495 
496  BT::Parameter_type weights()
497  {
498  return BT::parameters_begin()+2;
499  }
500 
501 
502  template<class U, class C>
503  BT::INT next(MultiArrayView<2,U,C> const & feature) const
504  {
505  double result = -1 * intercept();
506  if(*(BT::column_data()) == AllColumns)
507  {
508  for(int ii = 0; ii < BT::columns_size(); ++ii)
509  {
510  result +=feature[ii] * weights()[ii];
511  }
512  }
513  else
514  {
515  for(int ii = 0; ii < BT::columns_size(); ++ii)
516  {
517  result +=feature[BT::columns_begin()[ii]] * weights()[ii];
518  }
519  }
520  return result < 0 ? BT::child(0)
521  : BT::child(1);
522  }
523 };
524 
525 
526 
527 template<>
528 class Node<i_HypersphereNode>
529 : public NodeBase
530 {
531  public:
532 
533  typedef NodeBase BT;
534 
535  /**constructors **/
536 
537  Node( int nCol,
538  BT::T_Container_type & topology,
539  BT::P_Container_type & param)
540  : NodeBase(nCol + 5,nCol + 1,topology, param)
541  {
542  BT::typeID() = i_HypersphereNode;
543  }
544 
545  Node( BT::T_Container_type const & topology,
546  BT::P_Container_type const & param,
547  int n )
548  : NodeBase(5, 1,topology, param, n)
549  {
550  BT::topology_size_ += BT::column_data()[0]== AllColumns ?
551  0
552  : BT::column_data()[0];
553  BT::parameter_size_ += BT::columns_size();
554  }
555 
556  Node( BT & node_)
557  : BT(5, 1, node_)
558  {
559  BT::topology_size_ += BT::column_data()[0]== AllColumns ?
560  0
561  : BT::column_data()[0];
562  BT::parameter_size_ += BT::columns_size();
563 
564  }
565 
566  double const & squaredRadius() const
567  {
568  return BT::parameters_begin()[1];
569  }
570 
571  double& squaredRadius()
572  {
573  return BT::parameters_begin()[1];
574  }
575 
576  BT::Parameter_type center() const
577  {
578  return BT::parameters_begin()+2;
579  }
580 
581  BT::Parameter_type center()
582  {
583  return BT::parameters_begin()+2;
584  }
585 
586  template<class U, class C>
587  BT::INT next(MultiArrayView<2,U,C> const & feature) const
588  {
589  double result = -1 * squaredRadius();
590  if(*(BT::column_data()) == AllColumns)
591  {
592  for(int ii = 0; ii < BT::columns_size(); ++ii)
593  {
594  result += (feature[ii] - center()[ii])*
595  (feature[ii] - center()[ii]);
596  }
597  }
598  else
599  {
600  for(int ii = 0; ii < BT::columns_size(); ++ii)
601  {
602  result += (feature[BT::columns_begin()[ii]] - center()[ii])*
603  (feature[BT::columns_begin()[ii]] - center()[ii]);
604  }
605  }
606  return result < 0 ? BT::child(0)
607  : BT::child(1);
608  }
609 };
610 
611 
612 /** ExteriorNodeBase class.
613 
614  \ingroup DecicionTree
615 
616  This class implements common features of all interior nodes.
617  All interior nodes are derived classes of ExteriorNodeBase.
618 */
619 
620 
621 
622 
623 
624 
625 template<>
626 class Node<e_ConstProbNode>
627 : public NodeBase
628 {
629  public:
630 
631  typedef NodeBase BT;
632 
633  Node( BT::T_Container_type & topology,
634  BT::P_Container_type & param)
635  :
636  BT(2,topology[1]+1, topology, param)
637 
638  {
639  BT::typeID() = e_ConstProbNode;
640  }
641 
642 
643  Node( BT::T_Container_type const & topology,
644  BT::P_Container_type const & param,
645  int n )
646  : BT(2, topology[1]+1,topology, param, n)
647  { }
648 
649 
650  Node( BT & node_)
651  : BT(2, node_.classCount_ +1, node_)
652  {}
653  BT::Parameter_type prob_begin() const
654  {
655  return BT::parameters_begin()+1;
656  }
657  BT::Parameter_type prob_end() const
658  {
659  return prob_begin() + prob_size();
660  }
661  int prob_size() const
662  {
663  return BT::classCount_;
664  }
665 };
666 
667 template<>
668 class Node<e_LogRegProbNode>;
669 
670 } // namespace vigra
671 
672 #endif //RF_nodeproxy
vigra::NodeBase::column_data
Topology_type column_data() const
Definition: rf_nodeproxy.hxx:159
vigra::ArrayVectorView::begin
const_iterator begin() const
Definition: array_vector.hxx:223
vigra::NodeBase::NodeBase
NodeBase()
Definition: rf_nodeproxy.hxx:237
vigra::NodeBase::NodeBase
NodeBase(T_Container_type const &topology, P_Container_type const &parameter, INT n)
Definition: rf_nodeproxy.hxx:254
vigra::NodeBase::columns_begin
Topology_type columns_begin() const
Definition: rf_nodeproxy.hxx:167
vigra::NodeBase::child
INT & child(Int32 l)
Definition: rf_nodeproxy.hxx:224
vigra::NodeBase::columns_size
int columns_size() const
Definition: rf_nodeproxy.hxx:174
vigra::NodeBase::NodeBase
NodeBase(int tLen, int pLen, NodeBase &node)
Definition: rf_nodeproxy.hxx:292
vigra::NodeBase::columns_end
Topology_type columns_end() const
Definition: rf_nodeproxy.hxx:184
vigra::NodeBase::NodeBase
NodeBase(int tLen, int pLen, T_Container_type const &topology, P_Container_type const &parameter, INT n)
Definition: rf_nodeproxy.hxx:272
vigra::NodeBase
Definition: rf_nodeproxy.hxx:87
vigra::NodeBase::data
bool data() const
Definition: rf_nodeproxy.hxx:128
vigra::Int32
detail::SelectIntegerType< 32, detail::SignedIntTypes >::type Int32
32-bit signed int
Definition: sized_int.hxx:175
vigra::NodeBase::parameters_begin
Parameter_type parameters_begin() const
Definition: rf_nodeproxy.hxx:207
vigra::NodeBase::typeID
INT & typeID()
Definition: rf_nodeproxy.hxx:136
vigra::NodeBase::NodeBase
NodeBase(int tLen, int pLen, T_Container_type &topology, P_Container_type &parameter)
Definition: rf_nodeproxy.hxx:316
vigra::NodeBase::parameter_addr
INT & parameter_addr()
Definition: rf_nodeproxy.hxx:148
vigra::ArrayVectorView::size
size_type size() const
Definition: array_vector.hxx:358
vigra::NodeBase::child
INT const & child(Int32 l) const
Definition: rf_nodeproxy.hxx:231
vigra::NodeBase::topology_begin
Topology_type topology_begin() const
Definition: rf_nodeproxy.hxx:193
vigra::NodeBase::weights
double & weights()
Definition: rf_nodeproxy.hxx:115
vigra::NodeBase::NodeBase
NodeBase(NodeBase const &toCopy, T_Container_type &topology, P_Container_type &parameter)
Definition: rf_nodeproxy.hxx:356

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.11.1 (Fri May 19 2017)