kdtree.hpp

dysii是一款非常出色的滤波函数库

#ifndef INDII_ML_AUX_KDTREE_HPP
#define INDII_ML_AUX_KDTREE_HPP

#include "KDTreeNode.hpp"
#include "DiracMixturePdf.hpp"
#include "VariancePartitioner.hpp"

#include "boost/serialization/split_member.hpp"

#include <vector>

namespace indii {
  namespace ml {
    namespace aux {
/**
 * KD (kernel density) tree based on @ref Gray2001 "Gray & Moore (2001)".
 *
 * @author Lawrence Murray <[e-mail]>
 * @version $Rev: 404 $
 * @date $Date: 2008-03-05 14:52:55 +0000 (Wed, 05 Mar 2008) $
 *
 * @param S A space partitioner.
 *
 * @section KDTree_references References
 *
 * @anchor Gray2001
 * Gray, A. G. & Moore, A. W. `N-Body' Problems in Statistical
 * Learning. <i>Advances in Neural Information Processing Systems</i>,
 * <b>2001</b>, <i>13</i>.
 */
template <class S = VariancePartitioner>
class KDTree {
public:
  /**
   * Constructor.
   *
   * @param p Weighted sample set from which to build the KD tree.
   */
  KDTree(DiracMixturePdf& p);

  /**
   * Destructor.
   */
  virtual ~KDTree();
  
  /**
   * Calculate density at a single point.
   *
   * @param x \f$\mathbf{x}\f$; vector.
   * @param N \f$\|\mathbf{x}\|_p\f$; a norm.
   * @param K \f$K(\|\mathbf{x}\|_p)\f$; density kernel.
   *
   * @return Density at \f$\mathbf{x}\f$ for the given normed vector space
   * and kernel.
   */
  virtual double densityAt(const vector& x, Norm& N, Kernel& K);

  /**
   * Sample from the density.
   *
   * @param N \f$\|\mathbf{x}\|_p\f$; a norm.
   * @param K \f$K(\|\mathbf{x}\|_p)\f$; density kernel from which to
   * sample.
   *
   * @return Sample from the distribution defined by the tree, given normed
   * vector space and kernel.
   */
  virtual vector sample(Norm& N, Kernel& K);

private:
  /**
   * Root node of the tree.
   */
  KDTreeNode* root;

  /**
   * Create KD tree node.
   *
   * @param xwp Weighted sample subset from which to build the node.
   * 
   * @return The density tree node. Caller claims ownership.
   */
  KDTreeNode* build(Partitioner::points& xws) const;

  /**
   * Serialize.
   */
  template<class Archive>
  void save(Archive& ar, const unsigned int version) const;

  /**
   * Restore from serialization.
   */
  template<class Archive>
  void load(Archive& ar, const unsigned int version);

  /*
   * Boost.Serialization requirements.
   */
  BOOST_SERIALIZATION_SPLIT_MEMBER()
  friend class boost::serialization::access;

};
   
    }
  }
}

#include "KDTreeInternalNode.hpp"
#include "KDTreeLeafNode.hpp"

template<class S>
indii::ml::aux::KDTree<S>::KDTree(DiracMixturePdf& p) {
  DiracMixturePdf::weighted_component_iterator iter, end;
  Partitioner::points xws;

  xws.reserve(p.getNumComponents());  
  iter = p.getComponents().begin();
  end = p.getComponents().end();
  while (iter != end) {
    xws.push_back(&*iter);
    iter++;
  }
  
  root = build(xws);
}

template<class S>
indii::ml::aux::KDTree<S>::~KDTree() {
  delete root;
}

template<class S>
double indii::ml::aux::KDTree<S>::densityAt(const vector& x, Norm& N,
    Kernel& K) {
  double result = 0.0;
  double W;
  
  if (root != NULL) {
    W = root->getWeight();
    if (W > 0.0) {
      result = root->densityAt(x, N, K) / W;
    }
  }
  return result;
}

template<class S>
indii::ml::aux::vector indii::ml::aux::KDTree<S>::sample(Norm& N,
    Kernel& K) {
  /* pre-condition */
  assert (root != NULL);
  
  return root->sample(Random::uniform(0.0, root->getWeight()), N, K);
}

template<class S>
indii::ml::aux::KDTreeNode* indii::ml::aux::KDTree<S>::build(
    Partitioner::points& xws) const {    
  KDTreeNode* result;
  if (xws.size() == 0) {
    result = NULL;
  } else if (xws.size() == 1) {
    /* create leaf node */
    result = new KDTreeLeafNode(xws.front()->x, xws.front()->w);
  } else {
    /* create internal node */
    S partitioner;
    Partitioner::points::iterator iter, end;
    Partitioner::points leftPoints, rightPoints;
    KDTreeNode *left, *right;

    partitioner.init(xws);
    iter = xws.begin();
    end = xws.end();
    while (iter != end) {
      if (partitioner.assign((*iter)->x) == Partitioner::LEFT) {
        leftPoints.push_back(*iter);
      } else {
        rightPoints.push_back(*iter);
      }
      iter++;
    }
    
    left = build(leftPoints);
    right = build(rightPoints);
    
    result = new KDTreeInternalNode(left, right);
  }

  return result;
}

template<class S>
template<class Archive>
void indii::ml::aux::KDTree<S>::save(Archive& ar,
    const unsigned int version) const {
  if (typeid(*root) == typeid(KDTreeInternalNode)) {
    const bool isLeaf = false;
    const KDTreeInternalNode* node =
        static_cast<KDTreeInternalNode*>(root);
    ar & isLeaf;
    ar & node;
  } else if (typeid(*root) == typeid(KDTreeLeafNode)) {
    const bool isLeaf = true;
    const KDTreeLeafNode* node =
        static_cast<KDTreeLeafNode*>(root);
    ar & isLeaf;
    ar & node;
  } else {
    assert(false);
  }
}

template<class S>
template<class Archive>
void indii::ml::aux::KDTree<S>::load(Archive& ar,
    const unsigned int version) {
  bool isLeaf;

  if (root != NULL) {
    delete root;
    root = NULL;
  }

  ar & isLeaf;  
  if (isLeaf) {
    KDTreeLeafNode* node = new KDTreeLeafNode();
    ar & node;
    root = node;
  } else {
    KDTreeInternalNode* node = new KDTreeInternalNode();
    ar & node;
    root = node;
  }
}

#endif