itkKdTree.h

Go to the documentation of this file.

/*=========================================================================
 *
 *  Copyright Insight Software Consortium
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         http://www.apache.org/licenses/LICENSE-2.0.txt
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 *
 *=========================================================================*/
#ifndef __itkKdTree_h
#define __itkKdTree_h

#include <queue>
#include <vector>

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

#include "itkSubsample.h"

#include "itkEuclideanDistanceMetric.h"

namespace itk
{
namespace Statistics
{
template<class TSample>

struct KdTreeNode
  {
  typedef KdTreeNode<TSample> Self;

  typedef typename TSample::MeasurementType MeasurementType;

  typedef Array<double> CentroidType;

  typedef typename TSample::InstanceIdentifier InstanceIdentifier;

  virtual bool IsTerminal() const = 0;

  virtual void GetParameters( unsigned int &, MeasurementType & ) const = 0;

  virtual Self * Left() = 0;

  virtual const Self * Left() const = 0;

  virtual Self * Right() = 0;

  virtual const Self * Right() const = 0;

  virtual unsigned int Size() const = 0;

  virtual void GetWeightedCentroid( CentroidType & ) = 0;

  virtual void GetCentroid( CentroidType & ) = 0;

  virtual InstanceIdentifier GetInstanceIdentifier( InstanceIdentifier ) const = 0;

  virtual void AddInstanceIdentifier( InstanceIdentifier ) = 0;

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

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, MeasurementType, Superclass *,
    Superclass * );

  virtual ~KdTreeNonterminalNode() {}

  virtual bool IsTerminal() const
  {
    return false;
  }

  void GetParameters( unsigned int &, MeasurementType & ) 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 & ) {}

  void GetCentroid( CentroidType & ) {}

  InstanceIdentifier GetInstanceIdentifier( InstanceIdentifier ) 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

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, MeasurementType,
    Superclass *, Superclass *, CentroidType &, unsigned int );

  virtual ~KdTreeWeightedCentroidNonterminalNode() {}

  virtual bool IsTerminal() const
  {
    return false;
  }

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

  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(InstanceIdentifier) 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

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()
  {
    this->m_InstanceIdentifiers.clear();
  }

  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 & ) {}

  void GetCentroid( CentroidType & ) {}

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

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

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

template<class TSample>
class ITK_EXPORT KdTree:public Object
{
public:
  typedef KdTree                     Self;
  typedef Object                     Superclass;
  typedef SmartPointer< Self >       Pointer;
  typedef SmartPointer< const Self > ConstPointer;

  itkTypeMacro(KdTree, Object);

  itkNewMacro(Self);

  typedef TSample                                 SampleType;
  typedef typename TSample::MeasurementVectorType MeasurementVectorType;
  typedef typename TSample::MeasurementType       MeasurementType;
  typedef typename TSample::InstanceIdentifier    InstanceIdentifier;
  typedef typename TSample::AbsoluteFrequencyType AbsoluteFrequencyType;

  typedef unsigned int MeasurementVectorSizeType;

  itkGetConstMacro( MeasurementVectorSize, MeasurementVectorSizeType );

  typedef EuclideanDistanceMetric< MeasurementVectorType > DistanceMetricType;

  typedef KdTreeNode<TSample> KdTreeNodeType;

  typedef std::pair< InstanceIdentifier, double > NeighborType;

  typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType;

  class NearestNeighbors
  {
  public:
    NearestNeighbors() {}

    ~NearestNeighbors() {}

    void resize( unsigned int k )
    {
      m_Identifiers.clear();
      m_Identifiers.resize( k, NumericTraits< IdentifierType >::max() );
      m_Distances.clear();
      m_Distances.resize( k, NumericTraits<double>::max() );
      m_FarthestNeighborIndex = 0;
    }

    double GetLargestDistance()
    {
      return m_Distances[m_FarthestNeighborIndex];
    }

    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;
          }
        }
    }

    const InstanceIdentifierVectorType & GetNeighbors() const
    {
      return m_Identifiers;
    }

    InstanceIdentifier GetNeighbor(unsigned int index) const
    {
      return m_Identifiers[index];
    }

    const std::vector<double> & GetDistances() const
    {
      return m_Distances;
    }

  private:
    unsigned int m_FarthestNeighborIndex;

    InstanceIdentifierVectorType m_Identifiers;

    std::vector<double> m_Distances;
  };

  void SetBucketSize( unsigned int );

  void SetSample( const TSample * );

  const TSample * GetSample() const
  {
    return m_Sample;
  }

  SizeValueType Size() const
  {
    return m_Sample->Size();
  }

  KdTreeNodeType * GetEmptyTerminalNode()
  {
    return m_EmptyTerminalNode;
  }

  void SetRoot(KdTreeNodeType *root)
  {
    if ( this->m_Root )
      {
      this->DeleteNode( this->m_Root );
      }
    this->m_Root = root;
  }

  KdTreeNodeType * GetRoot()
  {
    return m_Root;
  }

  const MeasurementVectorType & GetMeasurementVector( InstanceIdentifier id )
    const
  {
    return m_Sample->GetMeasurementVector( id );
  }

  AbsoluteFrequencyType GetFrequency(InstanceIdentifier id ) const
  {
    return m_Sample->GetFrequency( id );
  }

  DistanceMetricType * GetDistanceMetric()
  {
    return m_DistanceMetric.GetPointer();
  }

  void Search( const MeasurementVectorType &, unsigned int,
    InstanceIdentifierVectorType & ) const;

  void Search( const MeasurementVectorType &, double,
    InstanceIdentifierVectorType & ) const;

  bool BallWithinBounds( const MeasurementVectorType &,
    MeasurementVectorType &, MeasurementVectorType &, double ) const;

  bool BoundsOverlapBall( const MeasurementVectorType &,
    MeasurementVectorType &, MeasurementVectorType &, double) const;

  void DeleteNode( KdTreeNodeType * );

  void PrintTree( std::ostream & ) const;

  void PrintTree( KdTreeNodeType *, unsigned int, unsigned int,
    std::ostream & os = std::cout ) const;

  void PlotTree( std::ostream & os ) const;

  void PlotTree( KdTreeNodeType *node, std::ostream & os = std::cout ) const;

  typedef typename TSample::Iterator      Iterator;
  typedef typename TSample::ConstIterator ConstIterator;

protected:
  KdTree();

  virtual ~KdTree();

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

  int NearestNeighborSearchLoop( const KdTreeNodeType *,
    const MeasurementVectorType &, MeasurementVectorType &,
    MeasurementVectorType &, NearestNeighbors & ) const;

  int SearchLoop( const KdTreeNodeType *, const MeasurementVectorType &,
    double, MeasurementVectorType &, MeasurementVectorType &,
    InstanceIdentifierVectorType & ) const;

private:
  KdTree( const Self & );         //purposely not implemented
  void operator=( const Self & ); //purposely not implemented

  const TSample *m_Sample;

  int m_BucketSize;

  KdTreeNodeType *m_Root;

  KdTreeNodeType *m_EmptyTerminalNode;

  typename DistanceMetricType::Pointer m_DistanceMetric;

  MeasurementVectorSizeType m_MeasurementVectorSize;
};  // end of class
} // end of namespace Statistics
} // end of namespace itk

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

#endif