itkkdtree.h

DTMK软件开发包,此为开源软件,是一款很好的医学图像开发资源.

/*=========================================================================

  Program:   Insight Segmentation & Registration Toolkit
  Module:    $RCSfile: itkKdTree.h,v $
  Language:  C++
  Date:      $Date: 2008-04-26 00:08:19 $
  Version:   $Revision: 1.27 $

  Copyright (c) Insight Software Consortium. All rights reserved.
  See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notices for more information.

=========================================================================*/
#ifndef __itkKdTree_h
#define __itkKdTree_h

#include <queue>
#include <vector>

#include "itkMacro.h"
#include "itkPoint.h"
#include "itkSize.h"
#include "itkObject.h"
#include "itkNumericTraits.h"
#include "itkArray.h"

#include "itkSample.h"
#include "itkSubsample.h"

#include "itkEuclideanDistance.h"

namespace itk{
namespace Statistics{

/** \class KdTreeNode
 *  \brief This class defines the interface of its derived classes.
 *
 * The methods defined in this class are a superset of the methods
 * defined in its subclases. Therefore, the subclasses implements only
 * part of the methods. The template argument, TSample, can be any
 * subclass of the Sample class.
 *
 * There are two categories for the subclasses, terminal and nonterminal
 * nodes. The terminal nodes stores the instance identifiers beloging to
 * them, while the nonterminal nodes don't. Therefore, the
 * AddInstanceIdentifier and the GetInstanceIdentifier have meaning only
 * with the terminal ones. The terminal nodes don't have any child (left
 * or right). For terminal nodes, the GetParameters method is void.
 *
 * <b>Recent API changes:</b>
 * The static const macro to get the length of a measurement vector,
 * \c MeasurementVectorSize  has been removed to allow the length of a measurement
 * vector to be specified at run time. The \c typedef for \c CentroidType has
 * been changed from Array to FixedArray.
 *
 * \sa KdTreeNonterminalNode, KdTreeWeightedCentroidNonterminalNode,
 * KdTreeTerminalNode
 */
template< class TSample >
struct KdTreeNode
{
  /** type alias for itself */
  typedef KdTreeNode< TSample> Self;

  /** Measurement type, not the measurement vector type */
  typedef typename TSample::MeasurementType MeasurementType;

  /** Centroid type */
  typedef Array< double > CentroidType;

  /** Instance identifier type (index value type for the measurement
   * vector in a sample */
  typedef typename TSample::InstanceIdentifier InstanceIdentifier;

  /** Returns true if the node is a terminal node, that is a node that
   * doesn't have any child. */
  virtual bool IsTerminal() const = 0;

  /** Fills the partitionDimension (the dimension that was chosen to
   * split the measurement vectors belong to this node to the left and the
   * right child among k dimensions) and the partitionValue (the
   * measurement value on the partitionDimension divides the left and the
   * right child */
  virtual void GetParameters(unsigned int &partitionDimension,
                             MeasurementType &partitionValue) const = 0;

  /** Returns the pointer to the left child of this node */
  virtual       Self* Left()       = 0;
  virtual const Self* Left() const = 0;

  /** Returns the pointer to the right child of this node */
  virtual       Self* Right()       = 0;
  virtual const Self* Right() const = 0;

  /** Returs the number of measurement vectors under this node including
   * its children */
  virtual unsigned int Size() const = 0;

  /** Returns the vector sum of the all measurement vectors under this node */
  virtual void GetWeightedCentroid(CentroidType &centroid) = 0;

  /** Returns the centroid. weighted centroid divided by the size */
  virtual void GetCentroid(CentroidType &centroid) = 0;

  /** Retuns the instance identifier of the index-th measurement vector */
  virtual InstanceIdentifier GetInstanceIdentifier(size_t index) const = 0;

  /** Add an instance to this node */
  virtual void AddInstanceIdentifier(InstanceIdentifier id) = 0;

  /** Destructor */
  virtual ~KdTreeNode() {}; // needed to subclasses will actually be deleted
}; // end of class

/** \class KdTreeNonterminalNode
 *  \brief This is a subclass of the KdTreeNode.
 *
 * KdTreeNonterminalNode doesn't store the information related with the
 * centroids. Therefore, the GetWeightedCentroid and the GetCentroid
 * methods are void. This class should have the left and the right
 * children. If we have a sample and want to generate a KdTree without
 * the centroid related information, we can use the KdTreeGenerator.
 *
 * \sa KdTreeNode, KdTreeWeightedCentroidNonterminalNode, KdTreeGenerator
 */
template< class TSample >
struct KdTreeNonterminalNode: public KdTreeNode< TSample >
{
  typedef KdTreeNode< TSample > Superclass;
  typedef typename Superclass::MeasurementType MeasurementType;
  typedef typename Superclass::CentroidType CentroidType;
  typedef typename Superclass::InstanceIdentifier InstanceIdentifier;

  KdTreeNonterminalNode(unsigned int partitionDimension,
                        MeasurementType partitionValue,
                        Superclass* left,
                        Superclass* right);

  virtual ~KdTreeNonterminalNode() {}

  virtual bool IsTerminal() const
  { return false; }

  void GetParameters(unsigned int &partitionDimension,
                     MeasurementType &partitionValue) const;

  Superclass* Left()
  { return m_Left; }

  Superclass* Right()
  { return m_Right; }

  const Superclass* Left() const
  { return m_Left; }

  const Superclass* Right() const
  { return m_Right; }

  unsigned int Size() const
  { return 0; }

  void GetWeightedCentroid( CentroidType & )
  { /* do nothing */ }

  void GetCentroid( CentroidType & )
  { /* do nothing */ }

  // Returns the identifier of the only MeasurementVector associated with 
  // this node in the tree. This MeasurementVector will be used later during
  // the distance computation when querying the tree.
  InstanceIdentifier GetInstanceIdentifier(size_t) const
  { return this->m_InstanceIdentifier; }

  void AddInstanceIdentifier(InstanceIdentifier valueId) 
  { this->m_InstanceIdentifier = valueId; }

private:
  unsigned int          m_PartitionDimension;
  MeasurementType       m_PartitionValue;
  InstanceIdentifier    m_InstanceIdentifier;
  Superclass* m_Left;
  Superclass* m_Right;
}; // end of class

/** \class KdTreeWeightedCentroidNonterminalNode
 *  \brief This is a subclass of the KdTreeNode.
 *
 * KdTreeNonterminalNode does have the information related with the
 * centroids. Therefore, the GetWeightedCentroid and the GetCentroid
 * methods returns meaningful values. This class should have the left
 * and right children. If we have a sample and want to generate a KdTree
 * with the centroid related information, we can use the
 * WeightedCentroidKdTreeGenerator. The centroid, the weighted
 * centroid, and the size (the number of measurement vectors) can be
 * used to accelate the k-means estimation.
 *
 * \sa KdTreeNode, KdTreeNonterminalNode, WeightedCentroidKdTreeGenerator
 */
template< class TSample >
struct KdTreeWeightedCentroidNonterminalNode: public KdTreeNode< TSample >
{
  typedef KdTreeNode< TSample > Superclass;
  typedef typename Superclass::MeasurementType MeasurementType;
  typedef typename Superclass::CentroidType CentroidType;
  typedef typename Superclass::InstanceIdentifier InstanceIdentifier;
  typedef typename TSample::MeasurementVectorSizeType MeasurementVectorSizeType;

  KdTreeWeightedCentroidNonterminalNode(unsigned int partitionDimension,
                                         MeasurementType partitionValue,
                                         Superclass* left,
                                         Superclass* right,
                                         CentroidType &centroid,
                                         unsigned int size);
  virtual ~KdTreeWeightedCentroidNonterminalNode() {}

  virtual bool IsTerminal() const
  { return false; }

  void GetParameters(unsigned int &partitionDimension,
                     MeasurementType &partitionValue) const;

  /** Return the length of a measurement vector */
  MeasurementVectorSizeType GetMeasurementVectorSize() const
    {
    return m_MeasurementVectorSize;
    }

  Superclass* Left()
  { return m_Left; }

  Superclass* Right()
  { return m_Right; }


  const Superclass* Left() const
  { return m_Left; }

  const Superclass* Right() const
  { return m_Right; }

  unsigned int Size() const
  { return m_Size; }

  void GetWeightedCentroid(CentroidType &centroid)
  { centroid = m_WeightedCentroid; }

  void GetCentroid(CentroidType &centroid)
  { centroid = m_Centroid; }

  InstanceIdentifier GetInstanceIdentifier(size_t) const
  { return this->m_InstanceIdentifier; }

  void AddInstanceIdentifier(InstanceIdentifier valueId) 
  { this->m_InstanceIdentifier = valueId; }

private:
  MeasurementVectorSizeType   m_MeasurementVectorSize;
  unsigned int                m_PartitionDimension;
  MeasurementType             m_PartitionValue;
  CentroidType                m_WeightedCentroid;
  CentroidType                m_Centroid;
  InstanceIdentifier          m_InstanceIdentifier;
  unsigned int                m_Size;
  Superclass*                 m_Left;
  Superclass*                 m_Right;
}; // end of class


/** \class KdTreeTerminalNode
 *  \brief This class is the node that doesn't have any child node. The
 *  IsTerminal method returns true for this class. This class stores the
 *  instance identifiers belonging to this node, while the nonterminal
 *  nodes do not store them. The AddInstanceIdentifier and
 *  GetInstanceIdentifier are storing and retrieving the instance
 *  identifiers belonging to this node.
 *
 * \sa KdTreeNode, KdTreeNonterminalNode,
 * KdTreeWeightedCentroidNonterminalNode
 */
template< class TSample >
struct KdTreeTerminalNode: public KdTreeNode< TSample >
{
  typedef KdTreeNode< TSample > Superclass;
  typedef typename Superclass::MeasurementType MeasurementType;
  typedef typename Superclass::CentroidType CentroidType;
  typedef typename Superclass::InstanceIdentifier InstanceIdentifier;

  KdTreeTerminalNode() {}

  virtual ~KdTreeTerminalNode() {}

  bool IsTerminal() const
  { return true; }

  void GetParameters(unsigned int &,
                     MeasurementType &) const {}

  Superclass* Left()
  { return 0; }

  Superclass* Right()
  { return 0; }


  const Superclass* Left() const
  { return 0; }

  const Superclass* Right() const
  { return 0; }

  unsigned int Size() const
  { return static_cast<unsigned int>( m_InstanceIdentifiers.size() ); }

  void GetWeightedCentroid(CentroidType &)
  { /* do nothing */ }

  void GetCentroid(CentroidType &)
  { /* do nothing */ }

  InstanceIdentifier GetInstanceIdentifier(size_t index) const
  { return m_InstanceIdentifiers[index]; }

  void AddInstanceIdentifier(InstanceIdentifier id)
  { m_InstanceIdentifiers.push_back(id);}

private:
  std::vector< InstanceIdentifier > m_InstanceIdentifiers;
}; // end of class

/** \class KdTree
 *  \brief This class provides methods for k-nearest neighbor search and
 *  related data structures for a k-d tree.
 *
 * An object of this class stores instance identifiers in a k-d tree
 * that is a binary tree with childrens split along a dimension among
 * k-dimensions. The dimension of the split (or partition) is determined
 * for each nonterminal node that has two children. The split process is
 * terminated when the node has no children (when the number of