itkkdtree.h

InsightToolkit-1.4.0(有大量的优化算法程序)

 * nature and in implementation. This implementation doesn't support
 * dynamic insert and delete operations for the tree. Instead, we can
 * use the KdTreeGenerator or WeightedCentroidKdTreeGenerator to
 * generate a static KdTree object. 
 *
 * To search k-nearest neighbor, call the Search method with the query
 * point in a k-d space and the number of nearest neighbors. The
 * GetSearchResult method returns a pointer to a NearestNeighbors object
 * with k-nearest neighbors.
 *
 * \sa KdTreeNode, KdTreeNonterminalNode,
 * KdTreeWeightedCentroidNonterminalNode, KdTreeTerminalNode,
 * KdTreeGenerator, WeightedCentroidKdTreeNode
 */

template < class TSample >
class ITK_EXPORT KdTree : public Object
{
public:
  /** Standard class typedefs */
  typedef KdTree Self ;
  typedef Object Superclass ;
  typedef SmartPointer<Self> Pointer;

  /** Run-time type information (and related methods) */
  itkTypeMacro(KdTree, Object);

  /** Method for creation through the object factory. */
  itkNewMacro(Self) ;

  /** typedef alias for the source data container */ 
  typedef TSample SampleType ;
  typedef typename TSample::MeasurementVectorType MeasurementVectorType ;
  typedef typename TSample::MeasurementType MeasurementType ;
  typedef typename TSample::InstanceIdentifier InstanceIdentifier ;
  typedef typename TSample::FrequencyType FrequencyType ;

  /** Length of the measurement vector. k in the k-d tree */
  itkStaticConstMacro(MeasurementVectorSize, unsigned int, 
                      TSample::MeasurementVectorSize) ;

  /** DistanceMetric type for the distance calculation and comparison */
  typedef EuclideanDistance< MeasurementVectorType > DistanceMetricType ;

  /** Node type of the KdTree */
  typedef KdTreeNode< TSample > KdTreeNodeType ;

  /** Neighbor type. The first element of the std::pair is the instance
   * identifier and the second one is the distance between the measurement
   * vector identified by the first element and the query point. */
  typedef std::pair< InstanceIdentifier, double > NeighborType ;

  typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType ;

  /** \class NearestNeighbors
   * \brief data structure for storing k-nearest neighbor search result
   * (k number of Neighbors)
   * 
   * This class stores the instance identifiers and the distance values
   * of k-nearest neighbors. We can also query the farthest neighbor's
   * distance from the query point using the GetLargestDistance
   * method. 
   */
  class NearestNeighbors
  {
  public:
    /** Constructor */
    NearestNeighbors() {}
    
    /** Destructor */
    ~NearestNeighbors() {} 
    
    /** Initialize the internal instance identifier and distance holders
     * with the size, k */
    void resize(unsigned int k)
    {
      m_Identifiers.clear() ;
      m_Identifiers.resize(k, NumericTraits< unsigned long >::max()) ;
      m_Distances.clear() ;
      m_Distances.resize(k, NumericTraits< double >::max()) ;
      m_FarthestNeighborIndex = 0 ;
    }

    /** Returns the distance of the farthest neighbor from the query point */
    double GetLargestDistance() 
    { return m_Distances[m_FarthestNeighborIndex] ; }

    /** Replaces the farthest neighbor's instance identifier and
     * distance value with the id and the distance */
    void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance) 
    {
      m_Identifiers[m_FarthestNeighborIndex] = id ;
      m_Distances[m_FarthestNeighborIndex] = distance ;
      double farthestDistance = NumericTraits< double >::min() ;
      const unsigned int size = static_cast<unsigned int>( m_Distances.size() );
      for ( unsigned int i = 0 ; i < size; i++ )
        {
        if ( m_Distances[i] > farthestDistance )
          {
          farthestDistance = m_Distances[i] ;
          m_FarthestNeighborIndex = i ;
          }
        }
    }

    /** Returns the vector of k-neighbors' instance identifiers */
    InstanceIdentifierVectorType GetNeighbors()
    { return m_Identifiers ; }

    /** Returns the instance identifier of the index-th neighbor among
     * k-neighbors */
    InstanceIdentifier GetNeighbor(unsigned int index)
    { return m_Identifiers[index] ; }

    /** Returns the vector of k-neighbors' instance identifiers */
    std::vector< double >& GetDistances()
    { return m_Distances ; }

  private:
    /** The index of the farthest neighbor among k-neighbors */
    unsigned int m_FarthestNeighborIndex ;
    
    /** Storage for the instance identifiers of k-neighbors */
    InstanceIdentifierVectorType m_Identifiers ;

    /** Storage for the distance values of k-neighbors from the query
     * point */
    std::vector< double > m_Distances ;
  } ;

  /** Sets the number of measurement vectors that can be stored in a
   * terminal node */
  void SetBucketSize(unsigned int size) ;

  /** Sets the input sample that provides the measurement vectors to the k-d
   * tree */
  void SetSample(TSample* sample) ;

  /** Returns the pointer to the input sample */
  TSample* GetSample()
  { return m_Sample ; }

  unsigned long Size()
  { return m_Sample->Size() ; }

  /** Returns the pointer to the empty terminal node. A KdTree object
   * has a single empty terminal node in memory. when the split process
   * has to create an empty terminal node, the single instance is reused
   * for this case */
  KdTreeNodeType* GetEmptyTerminalNode()
  { return m_EmptyTerminalNode ; } 

  /** Sets the root node of the KdTree that is a result of
   * KdTreeGenerator or WeightedCentroidKdTreeGenerator. */
  void SetRoot(KdTreeNodeType* root) 
  { m_Root = root ; } 

  /** Returns the pointer to the root node. */
  KdTreeNodeType* GetRoot() 
  { return m_Root ; } 

  /** Returns the measurement vector identified by the instance
   * identifier that is an identifier defiend for the input sample */
  MeasurementVectorType GetMeasurementVector(InstanceIdentifier id)
  { return m_Sample->GetMeasurementVector(id) ; }

  /** Returns the frequency of the measurement vector identified by 
   * the instance identifier */
  FrequencyType GetFrequency(InstanceIdentifier id)
  { return m_Sample->GetFrequency( id ) ; }

  /** Get the pointer to the distance metric. */
  DistanceMetricType* GetDistanceMetric()
  { return m_DistanceMetric.GetPointer() ; }

  /** Searches the k-nearest neighbors */
  void Search(MeasurementVectorType &query, 
              unsigned int k,
              InstanceIdentifierVectorType& result) ;

  /** Searches the neighbors fallen into a hypersphere */
  void Search(MeasurementVectorType &query,
              double radius, 
              InstanceIdentifierVectorType& result) ;

  /** Returns the number of measurement vectors that have been visited
   * to find the k-nearest neighbors. */
  int GetNumberOfVisits()
  { return m_NumberOfVisits ; }

  /** Returns true if the intermediate k-nearest neighbors exist within
   * the the bounding box defined by the lowerBound and the
   * upperBound. Otherwise returns false. Returns false if the ball
   * defined by the distance between the query point and the farthest
   * neighbor touch the surface of the bounding box.*/
  bool BallWithinBounds(MeasurementVectorType &query, 
                        MeasurementVectorType &lowerBound,
                        MeasurementVectorType &upperBound,
                        double radius) ;

  /** Returns true if the ball defined by the distance between the query
   * point and the farthest neighbor overlaps with the bounding box
   * defined by the lower and the upper bounds.*/
  bool BoundsOverlapBall(MeasurementVectorType &query, 
                         MeasurementVectorType &lowerBound,
                         MeasurementVectorType &upperBound,
                         double radius) ;

  /** Deletes the node recursively */
  void DeleteNode(KdTreeNodeType *node) ;

  /** Prints out the tree information */
  void PrintTree(KdTreeNodeType *node, int level, 
                 unsigned int activeDimension) ;

  typedef typename TSample::Iterator Iterator ;

  Iterator Begin()
  {
    typename TSample::Iterator iter = m_Sample->Begin() ;
    return iter; 
  }

  Iterator End() 
  {
    Iterator iter = m_Sample->End() ;
    return iter; 
  }

protected:
  /** Constructor */
  KdTree() ;
  
  /** Destructor: deletes the root node and the empty terminal node. */
  virtual ~KdTree() ;

  void PrintSelf(std::ostream& os, Indent indent) const ;

  /** search loop */ 
  int NearestNeighborSearchLoop(KdTreeNodeType* node,
                                MeasurementVectorType &query,
                                MeasurementVectorType &lowerBound,
                                MeasurementVectorType &upperBound) ;

  /** search loop */ 
  int SearchLoop(KdTreeNodeType* node, MeasurementVectorType &query,
                 MeasurementVectorType &lowerBound,
                 MeasurementVectorType &upperBound) ;
private:
  KdTree(const Self&) ; //purposely not implemented
  void operator=(const Self&) ; //purposely not implemented

  /** Pointer to the input sample */
  TSample* m_Sample ;
  
  /** Number of measurement vectors can be stored in a terminal node. */
  int m_BucketSize ;

  /** Pointer to the root node */
  KdTreeNodeType* m_Root ;

  /** Pointer to the empty terminal node */
  KdTreeNodeType* m_EmptyTerminalNode ;

  /** Distance metric smart pointer */
  typename DistanceMetricType::Pointer m_DistanceMetric ;

  bool m_IsNearestNeighborSearch ;
 
  double m_SearchRadius ;

  InstanceIdentifierVectorType m_Neighbors ;

  /** k-nearest neighbors */
  NearestNeighbors m_NearestNeighbors ;

  /** Temporary lower bound in the SearchLoop. */
  MeasurementVectorType m_LowerBound ;

  /** Temporary upper bound in the SearchLoop. */
  MeasurementVectorType m_UpperBound ;

  /** Number of measurment vectors to find k-nearest neighbors. */ 
  int m_NumberOfVisits ;

  /** Flag to stop the SearchLoop. */
  bool m_StopSearch ;

  /** Temporary neighbor */
  NeighborType m_TempNeighbor ;
} ; // end of class

} // end of namespace Statistics
} // end of namespace itk

#ifndef ITK_MANUAL_INSTANTIATION
#include "itkKdTree.txx"
#endif

#endif