Download this example

Spatial Search

Synopsis

Spatial search.

Results

Output:

K-Neighbor search:
[9, 9]
[7, 7]
[8, 8]
Radius search:
There are 4 neighbors.
[7, 7]
[8, 8]
[9, 9]
[10, 10]

Code

C++

#include "itkVector.h"
#include "itkListSample.h"
#include "itkWeightedCentroidKdTreeGenerator.h"
#include "itkEuclideanDistanceMetric.h"

int
main()
{
  using MeasurementVectorType = itk::Vector<float, 2>;

  using SampleType = itk::Statistics::ListSample<MeasurementVectorType>;
  auto sample = SampleType::New();
  sample->SetMeasurementVectorSize(2);

  MeasurementVectorType mv;
  for (unsigned int i = 0; i < 100; ++i)
  {
    mv[0] = static_cast<float>(i);
    mv[1] = static_cast<float>(i);
    sample->PushBack(mv);
  }

  using TreeGeneratorType = itk::Statistics::KdTreeGenerator<SampleType>;
  auto treeGenerator = TreeGeneratorType::New();
  treeGenerator->SetSample(sample);
  treeGenerator->SetBucketSize(16);
  treeGenerator->Update();

  using TreeType = TreeGeneratorType::KdTreeType;

  TreeType::Pointer tree = treeGenerator->GetOutput();

  MeasurementVectorType queryPoint;
  queryPoint[0] = 10.0;
  queryPoint[1] = 7.0;

  // K-Neighbor search
  std::cout << "K-Neighbor search:" << std::endl;
  unsigned int                           numberOfNeighbors = 3;
  TreeType::InstanceIdentifierVectorType neighbors;
  tree->Search(queryPoint, numberOfNeighbors, neighbors);

  for (unsigned long neighbor : neighbors)
  {
    std::cout << tree->GetMeasurementVector(neighbor) << std::endl;
  }

  // Radius search
  std::cout << "Radius search:" << std::endl;
  double radius = 4.0;
  tree->Search(queryPoint, radius, neighbors);
  std::cout << "There are " << neighbors.size() << " neighbors." << std::endl;
  for (unsigned long neighbor : neighbors)
  {
    std::cout << tree->GetMeasurementVector(neighbor) << std::endl;
  }

  return EXIT_SUCCESS;
}

Classes demonstrated

template<typename TSample>
class KdTreeGenerator : public itk::Object

This class generates a KdTree object without centroid information.

The KdTree object stores measurement vectors in a k-d tree structure that is a binary tree. The partition value is the median value of one of the k dimension (partition dimension). The partition dimension is determined by the spread of measurement values in each dimension. The partition dimension is the dimension has the widest spread. Our implementation of k-d tree doesn’t have any construction or insertion logic. Users should use this class or the WeightedCentroidKdTreeGenerator class.

The number of the measurement vectors in a terminal node is set by the SetBucketSize method. If we use too small number for this, it might cause computational overhead to calculate bound conditions. However, too large number will cause more distance calculation between the measurement vectors in a terminal node and the query point.

To run this generator, users should provides the bucket size (SetBucketSize method) and the input sample (SetSample method). The Update method will run this generator. To get the resulting KdTree object, call the GetOutput method.

Recent API changes: The static const macro to get the length of a measurement vector, ‘MeasurementVectorSize’ has been removed to allow the length of a measurement vector to be specified at run time. It is now obtained from the sample set as input. You may query this length using the function GetMeasurementVectorSize().

See

KdTree, KdTreeNode, KdTreeNonterminalNode, KdTreeTerminalNode, WeightedCentroidKdTreeGenerator

ITK Sphinx Examples:

• All ITK Sphinx Examples

• Spatial Search

Subclassed by itk::Statistics::WeightedCentroidKdTreeGenerator< TSample >

See itk::Statistics::KdTreeGenerator for additional documentation.