Menü Kapat

OCTree

 

 

K-d tree gibi, oktree, aramalarda yararlı olan hiyerarşik bir ağaç veri yapısıdır, ancak aynı zamanda sıkıştırma veya aşağı örnekleme de vardır. Her oktree düğüm sekiz alt düğüme sahiptir ya da hiç sahip değildir. Kök düğüm tüm noktaları kapsülleyen bir kübik sınırlama kutusu tanımlar. Her seviyede, artan bir voksel çözünürlüğe neden olan 2 faktörü ile bölünür. Böylelikle, belirli bölgelere seçici bir şekilde daha fazla çözünürlük verebiliriz.

Octree aciklama

Kod

#include <pcl/point_cloud.h>
#include <pcl/octree/octree_search.h>

#include
#include <vector>
#include <ctime>

int
main (int argc, char** argv)
{
  srand ((unsigned int) time (NULL));

  pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);

  // Generate pointcloud data
  cloud->width = 1000;
  cloud->height = 1;
  cloud->points.resize (cloud->width * cloud->height);

  for (size_t i = 0; i < cloud->points.size (); ++i)
  {
    cloud->points[i].x = 1024.0f * rand () / (RAND_MAX + 1.0f);
    cloud->points[i].y = 1024.0f * rand () / (RAND_MAX + 1.0f);
    cloud->points[i].z = 1024.0f * rand () / (RAND_MAX + 1.0f);
  }

  float resolution = 128.0f;

  pcl::octree::OctreePointCloudSearch<pcl::PointXYZ> octree (resolution);

  octree.setInputCloud (cloud);
  octree.addPointsFromInputCloud ();

  pcl::PointXYZ searchPoint;

  searchPoint.x = 1024.0f * rand () / (RAND_MAX + 1.0f);
  searchPoint.y = 1024.0f * rand () / (RAND_MAX + 1.0f);
  searchPoint.z = 1024.0f * rand () / (RAND_MAX + 1.0f);

  // Neighbors within voxel search

  std::vector pointIdxVec;

  if (octree.voxelSearch (searchPoint, pointIdxVec))
  {
    std::cout << "Neighbors within voxel search at (" << searchPoint.x
     << " " << searchPoint.y
     << " " << searchPoint.z << ")"
     << std::endl;

    for (size_t i = 0; i < pointIdxVec.size (); ++i)
   std::cout << "    " << cloud->points[pointIdxVec[i]].x
       << " " << cloud->points[pointIdxVec[i]].y
       << " " << cloud->points[pointIdxVec[i]].z << std::endl;
  }

  // K nearest neighbor search

  int K = 10;

  std::vector pointIdxNKNSearch;
  std::vector<float> pointNKNSquaredDistance;

  std::cout << "K nearest neighbor search at (" << searchPoint.x
            << " " << searchPoint.y
            << " " << searchPoint.z
            << ") with K=" << K << std::endl;

  if (octree.nearestKSearch (searchPoint, K, pointIdxNKNSearch, pointNKNSquaredDistance) > 0)
  {
    for (size_t i = 0; i < pointIdxNKNSearch.size (); ++i)
      std::cout << "    "  <<   cloud->points[ pointIdxNKNSearch[i] ].x
                << " " << cloud->points[ pointIdxNKNSearch[i] ].y
                << " " << cloud->points[ pointIdxNKNSearch[i] ].z
                << " (squared distance: " << pointNKNSquaredDistance[i] << ")" << std::endl;
  }

  // Neighbors within radius search

  std::vector pointIdxRadiusSearch;
  std::vector<float> pointRadiusSquaredDistance;

  float radius = 256.0f * rand () / (RAND_MAX + 1.0f);

  std::cout << "Neighbors within radius search at (" << searchPoint.x
      << " " << searchPoint.y
      << " " << searchPoint.z
      << ") with radius=" << radius << std::endl;

  if (octree.radiusSearch (searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance) > 0)
  {
    for (size_t i = 0; i < pointIdxRadiusSearch.size (); ++i)
      std::cout << "    "  <<   cloud->points[ pointIdxRadiusSearch[i] ].x
                << " " << cloud->points[ pointIdxRadiusSearch[i] ].y
                << " " << cloud->points[ pointIdxRadiusSearch[i] ].z
                << " (squared distance: " << pointRadiusSquaredDistance[i] << ")" << std::endl;
  }

}

Kod Açıklaması

Burada bir PointCloud Yapısı oluşturduk ve bunu random olarak oluşturulan noktalarla doldurduk.

 pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);

  // Generate pointcloud data
  cloud->width = 1000;
  cloud->height = 1;
  cloud->points.resize (cloud->width * cloud->height);

  for (size_t i = 0; i < cloud->points.size (); ++i)
  {
    cloud->points[i].x = 1024.0f * rand () / (RAND_MAX + 1.0f);
    cloud->points[i].y = 1024.0f * rand () / (RAND_MAX + 1.0f);
    cloud->points[i].z = 1024.0f * rand () / (RAND_MAX + 1.0f);
  }

Ardından bir octree oluşturduk. Bu octree, yaprak düğümleri içinde bir nokta indisleri vektörü tutar. Çözünürlük parametresi, en küçük oktree seviyesindeki küçük voksellerin uzunluğunu tanımlar. Oktree’nin derinliği bu nedenle çözünürlük ve pointcloud’un uzaysal boyutunun bir fonksiyonudur. Pointcloud’un sınırlayıcı bir kutusu biliniyorsa, defineBoundingBox yöntemini kullanarak oktree’ye atanmalıdır. Sonra PointCloud’a bir işaretçi atadık ve tüm noktaları oktree’ye ekledik.

 float resolution = 128.0f;

  pcl::octree::OctreePointCloudSearch<pcl::PointXYZ> octree (resolution);

  octree.setInputCloud (cloud);
  octree.addPointsFromInputCloud ();

PointCloud bir octree ile ilişkilendirildiğinde, arama işlemlerini gerçekleştirebiliriz. Burada kullanılan ilk arama yöntemi “Neighbors within Voxel Search” dır. Arama noktasını ilgili yaprak düğüm vokseline atar ve bir nokta indisleri vektörü döndürür. Bu endeksler, aynı voksel içinde yer alan noktalar ile ilgilidir. Arama noktası ile arama sonucu arasındaki mesafe, oktree’nin çözünürlük parametresine bağlıdır.

  std::vector pointIdxVec;

  if (octree.voxelSearch (searchPoint, pointIdxVec))
  {
    std::cout << "Neighbors within voxel search at (" << searchPoint.x
     << " " << searchPoint.y
     << " " << searchPoint.z << ")"
     << std::endl;

    for (size_t i = 0; i < pointIdxVec.size (); ++i)
   std::cout << "    " << cloud->points[pointIdxVec[i]].x
       << " " << cloud->points[pointIdxVec[i]].y
       << " " << cloud->points[pointIdxVec[i]].z << std::endl;
  }

Daha sonra, bir K en yakın komşu arama işlemi yapılır. Bu örnekte, K, 10’a ayarlanmıştır. “K En Yakın Komşu Arama” yöntemi, arama sonuçlarını iki ayrı vektöre yazar. Birincisi pointIdxNKNSearch, arama sonucunu içerecektir (ilgili PointCloud veri setine atıfta bulunan indeksler). İkinci vektör, arama noktası ile en yakın komşular arasındaki karşılık gelen kareler uzaklıklarını tutar.

// K nearest neighbor search

  int K = 10;

  std::vector pointIdxNKNSearch;
  std::vector<float> pointNKNSquaredDistance;

  std::cout << "K nearest neighbor search at (" << searchPoint.x
            << " " << searchPoint.y
            << " " << searchPoint.z
            << ") with K=" << K << std::endl;

  if (octree.nearestKSearch (searchPoint, K, pointIdxNKNSearch, pointNKNSquaredDistance) > 0)
  {
    for (size_t i = 0; i < pointIdxNKNSearch.size (); ++i)
      std::cout << "    "  <<   cloud->points[ pointIdxNKNSearch[i] ].x
                << " " << cloud->points[ pointIdxNKNSearch[i] ].y
                << " " << cloud->points[ pointIdxNKNSearch[i] ].z
                << " (squared distance: " << pointNKNSquaredDistance[i] << ")" << std::endl;
  }

“Radius Aramasında Komşular”, “K En Yakın Komşu Arama” algoritmasına çok benzer çalışır. Arama sonuçları, nokta indekslerini ve kareler arama noktası mesafelerini tanımlayan iki ayrı vektöre yazılır.

std::vector pointIdxRadiusSearch;
  std::vector<float> pointRadiusSquaredDistance;

  float radius = 256.0f * rand () / (RAND_MAX + 1.0f);

  std::cout << "Neighbors within radius search at (" << searchPoint.x
      << " " << searchPoint.y
      << " " << searchPoint.z
      << ") with radius=" << radius << std::endl;

  if (octree.radiusSearch (searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance) > 0)
  {
    for (size_t i = 0; i < pointIdxRadiusSearch.size (); ++i)
      std::cout << "    "  <<   cloud->points[ pointIdxRadiusSearch[i] ].x
                << " " << cloud->points[ pointIdxRadiusSearch[i] ].y
                << " " << cloud->points[ pointIdxRadiusSearch[i] ].z
                << " (squared distance: " << pointRadiusSquaredDistance[i] << ")" << std::endl;

Derleme ve Çalıştırma

CMakeLists.txt İçeriği:

cmake_minimum_required(VERSION 2.8 FATAL_ERROR)

project(octree_search)

find_package(PCL 1.2 REQUIRED)

include_directories(${PCL_INCLUDE_DIRS})
link_directories(${PCL_LIBRARY_DIRS})
add_definitions(${PCL_DEFINITIONS})

add_executable (octree_search octree_search.cpp)
target_link_libraries (octree_search ${PCL_LIBRARIES})

Çalıştıralım

$ ./octreesearch

Şunun gibi bir çıktı alacağız:

Neighbors within voxel search at (974.82 188.793 138.779)
    903.656 82.8158 162.392
    1007.34 191.035 61.7727
    896.88 155.711 58.1942
K nearest neighbor search at (974.82 188.793 138.779) with K=10
    903.656 82.8158 162.392 (squared distance: 16853.1)
    903.18 247.058 54.3528 (squared distance: 15655)
    861.595 149.96 135.199 (squared distance: 14340.7)
    896.88 155.711 58.1942 (squared distance: 13663)
    995.889 116.224 219.077 (squared distance: 12157.9)
    885.852 238.41 160.966 (squared distance: 10869.5)
    900.807 220.317 77.1432 (squared distance: 10270.7)
    1002.46 117.236 184.594 (squared distance: 7983.59)
    1007.34 191.035 61.7727 (squared distance: 6992.54)
    930.13 223.335 174.763 (squared distance: 4485.15)
Neighbors within radius search at (974.82 188.793 138.779) with radius=109.783
    1007.34 191.035 61.7727 (squared distance: 6992.54)
    900.807 220.317 77.1432 (squared distance: 10270.7)
    885.852 238.41 160.966 (squared distance: 10869.5)
    1002.46 117.236 184.594 (squared distance: 7983.59)
    930.13 223.335 174.763 (squared distance: 4485.15)

 

Ayrıntı İçin

Bir yorum yazınız. Yorumlarınız bizim için değerlidir.