PCL學習八叉樹

建立空間索引在點云數據處理中有著廣泛的應用，常見的空間索引一般是自頂而下逐級劃分空間的各種空間索引結構，比較有代表性的包括BSP樹，KD樹，KDB樹，R樹，四叉樹，八叉樹等索引結構，而這些結構中，KD樹和八叉樹使用比較廣泛

八叉樹（Octree）是一種用于描述三維空間的樹狀數據結構。八叉樹的每個節點表示一個正方體的體積元素，每個節點有八個子節點，這八個子節點所表示的體積元素加在一起就等于父節點的體積。一般中心點作為節點的分叉中心。

百度百科釋義：八叉樹（Octree）的定義是：若不為空樹的話，樹中任一節點的子節點恰好只會有八個，或零個，也就是子節點不會有0與8以外的數目。那么，這要用來做什么？想象一個立方體，我們最少可以切成多少個相同等分的小立方體？答案就是8個。再想象我們有一個房間，房間里某個角落藏著一枚金幣，我們想很快的把金幣找出來，聰明的你會怎么做？我們可以把房間當成一個立方體，先切成八個小立方體，然后排除掉沒有放任何東西的小立方體，再把有可能藏金幣的小立方體繼續切八等份….如此下去，平均在Log8(房間內的所有物品數)的時間內就可找到金幣。因此，八叉樹就是用在3D空間中的場景管理，可以很快地知道物體在3D場景中的位置，或偵測與其它物體是否有碰撞以及是否在可視范圍內。

實現八叉樹的原理?

　　(1). 設定最大遞歸深度。

　　(2). 找出場景的最大尺寸，并以此尺寸建立第一個立方體。

　　(3). 依序將單位元元素丟入能被包含且沒有子節點的立方體。

　　(4). 若沒達到最大遞歸深度，就進行細分八等份，再將該立方體所裝的單位元元素全部分擔給八個子立方體。

　　(5). 若發現子立方體所分配到的單位元元素數量不為零且跟父立方體是一樣的，則該子立方體停止細分，因為跟據空間分割理論，細分的空間所得到的分配必定較少，若是一樣數目，則再怎么切數目還是一樣，會造成無窮切割的情形。

　　(6). 重復3，直到達到最大遞歸深度。

八叉樹的邏輯結構如下：

假設要表示的形體V可以放在一個充分大的正方體C內，C的邊長為2n，形體V=C，它的八叉樹可以用以下的遞歸方法來定義：八叉樹的每個節點與C的一個子立方體對應，

樹根與C本身相對應，如果V＝C，那么V的八叉樹僅有樹根，如果V≠C，則將C等分為八個子立方體，每個子立方體與樹根的一個子節點相對應。只要某個子立方體不是完

全空白或完全為V所占據，就要被八等分，從而對應的節點也就有了八個子節點。這樣的遞歸判斷、分割一直要進行到節點所對應的立方體或是完全空白，或是完全為V占

據，或是其大小已是預先定義的體素大小，并且對它與V之交作一定的“舍入”，使體素或認為是空白的，或認為是V占據的。

? ?? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

PCL中Octree模塊及類介紹

pcl::octree::Octree2BufBase< LeafContainerT, BranchContainerT >??? 實現了同時存儲管理兩個八叉樹與內存中，可以十分高效的實現八叉樹的建立管理等操作，并且節點實現對臨近樹節點的結構的探測，對應到空間點云，其就可以對空間曲面的動態變化進行探測，在進行空間動態變化探測中非常有用

Public Types
typedef Octree2BufBase< LeafContainerT, BranchContainerT >?	OctreeT
typedef BufferedBranchNode< BranchContainerT >?	BranchNode
typedef OctreeLeafNode< LeafContainerT >?	LeafNode
typedef BranchContainerT?	BranchContainer
typedef LeafContainerT?	LeafContainer
typedef OctreeDepthFirstIterator< OctreeT >?	Iterator
typedef const OctreeDepthFirstIterator< OctreeT >?	ConstIterator
typedef OctreeLeafNodeIterator< OctreeT >?	LeafNodeIterator
typedef const OctreeLeafNodeIterator< OctreeT >?	ConstLeafNodeIterator
typedef OctreeDepthFirstIterator< OctreeT >?	DepthFirstIterator
typedef const OctreeDepthFirstIterator< OctreeT >?	ConstDepthFirstIterator
typedef OctreeBreadthFirstIterator< OctreeT >?	BreadthFirstIterator
typedef const OctreeBreadthFirstIterator< OctreeT >?	ConstBreadthFirstIterator

Public Member Functions
void?	setMaxVoxelIndex (unsigned int max_voxel_index_arg)
?	Set the maximum amount of voxels per dimension. 設置在各個維度的最大的體素個數
void?	setTreeDepth (unsigned int depth_arg)
?	Set the maximum depth of the octree. 設置八叉樹的深度，需要在初始化八叉樹時設置
unsigned int?	getTreeDepth () const
?	Get the maximum depth of the octree? 獲得八叉樹的深度
LeafContainerT *?	createLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
?	Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg). 創建葉節點
LeafContainerT *?	findLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
?	Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg). 找出頁節點
bool?	existLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg) const
?	Check for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg). 判斷在（idx_x_arg, idx_y_arg, idx_z_arg）對應的葉子節點是否存在
void?	removeLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
?	Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg). 移除在（。。。）的節點
std::size_t?	getLeafCount () const
?	Return the amount of existing leafs in the octree.返回八叉樹葉子的個數
std::size_t?	getBranchCount () const?
?	Return the amount of existing branches in the octree. 返回八叉樹分支的個數
void?	deleteTree ()
?	Delete the octree structure and its leaf nodes. 刪除八叉樹結構包括節點
void?	deletePreviousBuffer ()
?	Delete octree structure of previous buffer. 刪除另一個緩存區對應的八叉樹的結構及其字節點
void?	deleteCurrentBuffer ()
?	Delete the octree structure in the current buffer刪除當前緩存區對應的八叉樹的結構及其字節點
void?	switchBuffers ()
?	Switch buffers and reset current octree structure. 交換緩存區中對應的八叉樹的結構和其葉子節點
void?	serializeTree (std::vector< char > &binary_tree_out_arg, bool do_XOR_encoding_arg=false)
?	Serialize octree into a binary output vector describing its branch node structure.
void?	serializeTree (std::vector< char > &binary_tree_out_arg, std::vector< LeafContainerT * > &leaf_container_vector_arg, bool do_XOR_encoding_arg=false)
?	Serialize octree into a binary output vector describing its branch node structure and and push all DataT elements stored in the octree to a vector.串行化輸出八叉樹結構
void?	serializeLeafs (std::vector< LeafContainerT * > &leaf_container_vector_arg)
?	Outputs a vector of all DataT elements that are stored within the octree leaf nodes.
void?	serializeNewLeafs (std::vector< LeafContainerT * > &leaf_container_vector_arg)
?	Outputs a vector of all DataT elements from leaf nodes, that do not exist in the previous octree buffer
void?	deserializeTree (std::vector< char > &binary_tree_in_arg, bool do_XOR_decoding_arg=false)
?	Deserialize a binary octree description vector and create a corresponding octree structure.
void?	deserializeTree (std::vector< char > &binary_tree_in_arg, std::vector< LeafContainerT * > &leaf_container_vector_arg, bool do_XOR_decoding_arg=false)
?	Deserialize a binary octree description and create a corresponding octree structure.

?更多詳細查看? docs.pointclouds.org/trunk/classpcl_1_1octree_1_1_octree2_buf_base.html#aeea7ecfd6ebe82e93d3c7bb869355502

應用實例

點云由海量的數據集組成，這些數據集通過距離顏色? 法線? 等附加信息來描述空間的三維點，此外，點云還能易非常高的速度被創建出來，因此需要占用相當大的存儲資源，一旦點云需要存儲或者通過速率受限制的通信信道進行傳輸，提供針對這種數據的壓縮方法就變得十分有用，PCL 提供了點云的壓縮功能，它允許編碼壓縮所有類型的點云，

點云壓縮示意圖：

???????????????????????????????????????????????????????????? octreeCompression

新建工程ch3_2,新建文件 point_cloud_compression.cpp

#include <pcl/point_cloud.h>                         // 點云類型
#include <pcl/point_types.h>                          //點數據類型
#include <pcl/io/openni_grabber.h>                    //點云獲取接口類
#include <pcl/visualization/cloud_viewer.h>            //點云可視化類

#include <pcl/compression/octree_pointcloud_compression.h>   //點云壓縮類

#include <stdio.h>
#include <sstream>
#include <stdlib.h>#ifdef WIN32
# define sleep(x) Sleep((x)*1000)
#endifclass SimpleOpenNIViewer
{
public:SimpleOpenNIViewer () :viewer (" Point Cloud Compression Example"){}
/************************************************************************************************在OpenNIGrabber采集循環執行的回調函數cloud_cb_中，首先把獲取的點云壓縮到stringstream緩沖區，下一步就是解壓縮，它對壓縮了的二進制數據進行解碼，存儲在新的點云中解碼了點云被發送到點云可視化對象中進行實時可視化
*************************************************************************************************/void  cloud_cb_ (const pcl::PointCloud<pcl::PointXYZRGBA>::ConstPtr &cloud){if (!viewer.wasStopped ()){// 存儲壓縮點云的字節流對象
      std::stringstream compressedData;// 存儲輸出點云pcl::PointCloud<pcl::PointXYZRGBA>::Ptr cloudOut (new pcl::PointCloud<pcl::PointXYZRGBA> ());// 壓縮點云PointCloudEncoder->encodePointCloud (cloud, compressedData);// 解壓縮點云PointCloudDecoder->decodePointCloud (compressedData, cloudOut);// 可視化解壓縮的點云
      viewer.showCloud (cloudOut);}}
/**************************************************************************************************************在函數中創建PointCloudCompression類的對象來編碼和解碼，這些對象把壓縮配置文件作為配置壓縮算法的參數所提供的壓縮配置文件為OpenNI兼容設備采集到的點云預先確定的通用參數集，本例中使用MED_RES_ONLINE_COMPRESSION_WITH_COLOR配置參數集，用于快速在線的壓縮，壓縮配置方法可以在文件/io/include/pcl/compression/compression_profiles.h中找到，在PointCloudCompression構造函數中使用MANUAL——CONFIGURATION屬性就可以手動的配置壓縮算法的全部參數
******************************************************************************************************************/void run (){bool showStatistics = true;  //設置在標準設備上輸出打印出壓縮結果信息// 壓縮選項詳情在: /io/include/pcl/compression/compression_profiles.hpcl::io::compression_Profiles_e compressionProfile = pcl::io::MED_RES_ONLINE_COMPRESSION_WITH_COLOR;// 初始化壓縮和解壓縮對象  其中壓縮對象需要設定壓縮參數選項，解壓縮按照數據源自行判斷PointCloudEncoder = new pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA> (compressionProfile, showStatistics);PointCloudDecoder = new pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA> ();/***********************************************************************************************************下面的代碼為OpenNI兼容設備實例化一個新的采樣器，并且啟動循環回調接口，每從設備獲取一幀數據就回調函數一次，，這里的回調函數就是實現數據壓縮和可視化解壓縮結果。************************************************************************************************************///創建從OpenNI獲取點云的抓取對象pcl::Grabber* interface = new pcl::OpenNIGrabber ();// 建立回調函數boost::function<void(const pcl::PointCloud<pcl::PointXYZRGBA>::ConstPtr&)> f = boost::bind (&SimpleOpenNIViewer::cloud_cb_, this, _1);//建立回調函數和回調信息的綁定boost::signals2::connection c = interface->registerCallback (f);// 開始接受點云的數據流interface->start ();while (!viewer.wasStopped ()){sleep (1);}interface->stop ();// 刪除壓縮與解壓縮的實例delete (PointCloudEncoder);delete (PointCloudDecoder);}pcl::visualization::CloudViewer viewer;pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA>* PointCloudEncoder;pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA>* PointCloudDecoder;};int
main (int argc, char **argv)
{SimpleOpenNIViewer v;  //創建一個新的SimpleOpenNIViewer  實例并調用他的run方法
  v.run ();return (0);
}

?編譯后運行的結果如下：

圖示為帶有RGB紋理信息的實時可視化結果，縮放可視化結果看到經過壓縮后點云進行了重采樣，紋理信息有所丟失，但數據量有所減小，在實際應用中需要折中取舍

同時在壓縮和解壓縮的過程中? 因為設置compressedData為true所以在標準輸出上打印處壓縮率幀數等信息：

壓縮配置文件：壓縮配置文件為PCL點云編碼器定義了參數集，并針對壓縮從openNI采集器獲取的普通點云進行了優化設置，注意，解碼對象不需要用參數表示，因為它在解碼是檢測并獲取對應編碼參數配置，例如下面的壓縮配置文件

LOW_RES_ONLINE_COMPRESSION_WITHOUT_COLOR,???????????? //分別率為? 1?? cm^3?? 無顏色????? 快速在線編碼
????? LOW_RES_ONLINE_COMPRESSION_WITH_COLOR,????????????? ?? //分別率為? 1??? cm^3?? 有顏色????? 快速在線編碼

????? MED_RES_ONLINE_COMPRESSION_WITHOUT_COLOR,????????? ?? //分別率為? 5??? mm^3?? 無顏色????? 快速在線編碼
????? MED_RES_ONLINE_COMPRESSION_WITH_COLOR,??????????????????? //分別率為? 5??? mm^3?? 有顏色????? 快速在線編碼

????? HIGH_RES_ONLINE_COMPRESSION_WITHOUT_COLOR,???????? //分別率為? 1 ?? mm^3?? 無顏色????? 快速在線編碼
????? HIGH_RES_ONLINE_COMPRESSION_WITH_COLOR,???????????????? //分別率為? 1 ?? mm^3?? 有顏色????? 快速在線編碼

????? LOW_RES_OFFLINE_COMPRESSION_WITHOUT_COLOR,??? ?? //分別率為? 1 ?? cm^3?? 無顏色????? 高效離線編碼
????? LOW_RES_OFFLINE_COMPRESSION_WITH_COLOR,????????????? //分別率為? 1 ?? cm^3?? 有顏色????? 高效離線編碼

????? MED_RES_OFFLINE_COMPRESSION_WITHOUT_COLOR,????? //分別率為? 5 ?? mm^3?? 無顏色????? 高效離線編碼
????? MED_RES_OFFLINE_COMPRESSION_WITH_COLOR,???????????? //分別率為? 5 ?? mm^3?? 有顏色????? 高效離線編碼

????? HIGH_RES_OFFLINE_COMPRESSION_WITHOUT_COLOR,???? //分別率為? 1 ?? mm^3?? 無顏色????? 高效離線編碼
????? HIGH_RES_OFFLINE_COMPRESSION_WITH_COLOR,????????????? //分別率為? 1 ?? mm^3?? 有顏色????? 高效離線編碼
????? MANUAL_CONFIGURATION?????????????????????????????????????????????????? //允許為高級參數化進行手工配置

微信公眾號號可掃描二維碼一起共同學習交流