PCL中Kd树理论
k-d樹（k-dimensional樹的簡稱），是一種分割k維數據空間的數據結構。主要應用于多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。
? ?01? ?Kd簡介
? ?
? ? ?K-D樹是二進制空間分割樹的特殊的情況。用來組織表示K維空間中點的幾何，是一種帶有其他約束的二分查找樹，為了達到目的，通常只在三個維度中進行處理因此所有的kd_tree都將是三維的kd_tree,kd_tree的每一維在指定維度上分開所有的字節點，在樹的根部所有子節點是以第一個指定的維度上被分開。
? ? ?K-D樹算法可以分為兩大部分，一部分是有關k-d樹本身這種數據結構建立的算法，另一部分是在建立的k-d樹上如何進行最鄰近查找的算法。
? ?02? ?應用背景
? ? ?
? ? ? ?比如SIFT算法中做特征點匹配的時候就會利用到k-d樹。而特征點匹配實際上就是一個通過距離函數在高維矢量之間進行相似性檢索的問題。針對如何快速而準確地找到查詢點的近鄰，現在提出了很多高維空間索引結構和近似查詢的算法，k-d樹就是其中一種。
索引結構中相似性查詢有兩種基本的方式：一種是范圍查詢（range searches），另一種是K近鄰查詢（K-neighbor searches）。范圍查詢就是給定查詢點和查詢距離的閾值，從數據集中找出所有與查詢點距離小于閾值的數據；K近鄰查詢是給定查詢點及正整數K，從數據集中找到距離查詢點最近的K個數據，當K=1時，就是最近鄰查詢（nearest neighbor searches）。
? ?03? ?實例
? ? ??
? ? ? ?先以一個簡單直觀的實例來介紹k-d樹算法。假設有6個二維數據點{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，數據點位于二維空間內（如圖1中黑點所示）。k-d樹算法就是要確定圖1中這些分割空間的分割線（多維空間即為分割平面，一般為超平面）。下面就要通過一步步展示k-d樹是如何確定這些分割線的。
? ? ?k-d樹算法可以分為兩大部分，一部分是有關k-d樹本身這種數據結構建立的算法，另一部分是在建立的k-d樹上如何進行最鄰近查找的算法。
? ?03? ?構建算法
? ? ? k-d樹是一個二叉樹，每個節點表示一個空間范圍。表1給出的是k-d樹每個節點中主要包含的數據結構。
? ? ?從上面對k-d樹節點的數據類型的描述可以看出構建k-d樹是一個逐級展開的遞歸過程。表2給出的是構建k-d樹的偽碼。
?以上述舉的實例來看，過程如下：
由于此例簡單，數據維度只有2維，所以可以簡單地給x，y兩個方向軸編號為0,1，也即split={0,1}。
（1）確定split域的首先該取的值。分別計算x，y方向上數據的方差得知x方向上的方差最大，所以split域值首先取0，也就是x軸方向；
（2）確定Node-data的域值。根據x軸方向的值2,5,9,4,8,7排序選出中值為7，所以Node-data = （7,2）。這樣，該節點的分割超平面就是通過（7,2）并垂直于split = 0（x軸）的直線x = 7；
（3）確定左子空間和右子空間。分割超平面x = 7將整個空間分為兩部分，如圖2所示。x < =? 7的部分為左子空間，包含3個節點{（2,3），（5,4），（4,7）}；另一部分為右子空間，包含2個節點{（9,6），（8,1）}。
? ? ? ?如算法所述，k-d樹的構建是一個遞歸的過程。然后對左子空間和右子空間內的數據重復根節點的過程就可以得到下一級子節點（5,4）和（9,6）（也就是左右子空間的'根'節點），同時將空間和數據集進一步細分。如此反復直到空間中只包含一個數據點，如圖1所示。最后生成的k-d樹如圖3所示。
? ?04? ?PCL中k-d樹的最鄰近查找
? ? ? 在k-d樹中進行數據的查找也是特征匹配的重要環節，其目的是檢索在k-d樹中與查詢點距離最近的數據點。這里先以一個簡單的實例來描述最鄰近查找的基本思路。
星號表示要查詢的點（2.1,3.1）。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點并不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位于以查詢點為圓心且通過葉子節點的圓域內。為了找到真正的最近鄰，還需要進行'回溯'操作：算法沿搜索路徑反向查找是否有距離查詢點更近的數據點。此例中先從（7,2）點開始進行二叉查找，然后到達（5,4），最后到達（2,3），此時搜索路徑中的節點為<（7,2），（5,4），（2,3）>，首先以（2,3）作為當前最近鄰點，計算其到查詢點（2.1,3.1）的距離為0.1414，然后回溯到其父節點（5,4），并判斷在該父節點的其他子節點空間中是否有距離查詢點更近的數據點。以（2.1,3.1）為圓心，以0.1414為半徑畫圓，如圖4所示。發現該圓并不和超平面y = 4交割，因此不用進入（5,4）節點右子空間中去搜索。
? ? ?再回溯到（7,2），以（2.1,3.1）為圓心，以0.1414為半徑的圓更不會與x = 7超平面交割，因此不用進入（7,2）右子空間進行查找。至此，搜索路徑中的節點已經全部回溯完，結束整個搜索，返回最近鄰點（2,3），最近距離為0.1414。
一個復雜點了例子如查找點為（2，4.5）。同樣先進行二叉查找，先從（7,2）查找到（5,4）節點，在進行查找時是由y = 4為分割超平面的，由于查找點為y值為4.5，因此進入右子空間查找到（4,7），形成搜索路徑<（7,2），（5,4），（4,7）>，取（4,7）為當前最近鄰點，計算其與目標查找點的距離為3.202。然后回溯到（5,4），計算其與查找點之間的距離為3.041。以（2，4.5）為圓心，以3.041為半徑作圓，如圖5所示。可見該圓和y = 4超平面交割，所以需要進入（5,4）左子空間進行查找。此時需將（2,3）節點加入搜索路徑中得<（7,2），（2,3）>?；厮葜?#xff08;2,3）葉子節點，（2,3）距離（2,4.5）比（5,4）要近，所以最近鄰點更新為（2，3），最近距離更新為1.5?；厮葜?#xff08;7,2），以（2,4.5）為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如圖6所示。至此，搜索路徑回溯完。返回最近鄰點（2,3），最近距離1.5。k-d樹查詢算法的偽代碼如表3所示。
? ?那么各種編程語言實現Kd tree的代碼網址：
https://rosettacode.org/wiki/K-d_tree
PCL中關于K-D樹的算法已經實現，是實現其他算法的基礎，比如在使用濾波算法，配準等算法都會使用該接口。既然有輪子，就不要自己造輪子了。
資源
三維點云論文及相關應用分享
【點云論文速讀】基于激光雷達的里程計及3D點云地圖中的定位方法
3D目標檢測：MV3D-Net
三維點云分割綜述（上）
3D-MiniNet: 從點云中學習2D表示以實現快速有效的3D LIDAR語義分割（2020）
win下使用QT添加VTK插件實現點云可視化GUI
JSNet：3D點云的聯合實例和語義分割
大場景三維點云的語義分割綜述
PCL中outofcore模塊---基于核外八叉樹的大規模點云的顯示
基于局部凹凸性進行目標分割
基于三維卷積神經網絡的點云標記
點云的超體素(SuperVoxel)
基于超點圖的大規模點云分割
更多文章可查看：點云學習歷史文章大匯總
SLAM及AR相關分享
【開源方案共享】ORB-SLAM3開源啦！
【論文速讀】AVP-SLAM：自動泊車系統中的語義SLAM
【點云論文速讀】StructSLAM:結構化線特征SLAM
SLAM和AR綜述
常用的3D深度相機
AR設備單目視覺慣導SLAM算法綜述與評價
SLAM綜述(4)激光與視覺融合SLAM
Kimera實時重建的語義SLAM系統
SLAM綜述(3)-視覺與慣導，視覺與深度學習SLAM
易擴展的SLAM框架-OpenVSLAM
高翔：非結構化道路激光SLAM中的挑戰
SLAM綜述之Lidar SLAM
基于魚眼相機的SLAM方法介紹
往期線上分享錄播匯總
第一期B站錄播之三維模型檢索技術
第二期B站錄播之深度學習在3D場景中的應用
第三期B站錄播之CMake進階學習
第四期B站錄播之點云物體及六自由度姿態估計
第五期B站錄播之點云深度學習語義分割拓展
第六期B站錄播之Pointnetlk解讀
[線上分享錄播]點云配準概述及其在激光SLAM中的應用
[線上分享錄播]cloudcompare插件開發
[線上分享錄播]基于點云數據的?Mesh重建與處理
[線上分享錄播]機器人力反饋遙操作技術及機器人視覺分享
[線上分享錄播]地面點云配準與機載點云航帶平差
點云PCL更多活動請查看：點云PCL活動之應屆生校招群
掃描下方微信視頻號二維碼可查看最新研究成果及相關開源方案的演示：
如果你對本文感興趣，請點擊“原文閱讀”獲取知識星球二維碼，務必按照“姓名+學校/公司+研究方向”備注加入免費知識星球，免費下載pdf文檔，和更多熱愛分享的小伙伴一起交流吧！
以上內容如有錯誤請留言評論，歡迎指正交流。如有侵權，請聯系刪除
掃描二維碼
? ? ? ? ? ? ? ? ? ?關注我們
讓我們一起分享一起學習吧！期待有想法，樂于分享的小伙伴加入免費星球注入愛分享的新鮮活力。分享的主題包含但不限于三維視覺，點云，高精地圖，自動駕駛，以及機器人等相關的領域。
分享及合作方式：群主微信“920177957”（需要按要求備注） 聯系郵箱：dianyunpcl@163.com，歡迎企業來聯系公眾號展開合作。
點一下“在看”你會更好看耶
總結
- 上一篇： pcl_filters模块api代码解析
- 下一篇： Open3d 学习计划—12（Jupyt