目錄
一、概述
1.1kd樹原理
1.2kd樹搜索原理
1.3kd樹構建示例
二、常見的領域搜索方式
2.1K近鄰搜索（K-Nearest Neighbors, KNN Search）
2.2半徑搜索（Radius Search）
2.3混合搜索（Hybrid Search）
三、代碼實現
3.1關鍵函數
3.1.1K近鄰搜索
3.1.2半徑鄰域搜索
3.1.3混合搜索
3.2完整代碼
四、實現效果
一、概述
1.1kd樹原理
????????KD樹（K-Dimensional Tree）是一種用于組織k維空間數據的樹狀數據結構，特別適用于多維空間中的最近鄰搜索和范圍搜索。KD樹通過遞歸地將空間劃分為較小的子空間，從而實現高效的空間查詢。
KD樹的構建原理：
- 選擇分割維度從數據集中選擇一個維度進行分割。通常選擇當前維度上的方差最大的維度，以最大化分割的效果。這可以幫助平衡樹的結構。
- 選擇分割點：在選擇的分割維度上選擇中位數作為分割點。中位數確保每次分割后，兩個子空間包含的點數大致相等，從而保持樹的平衡。
- 遞歸構建子樹：對于每個子集，遞歸地選擇新的分割維度和分割點，直到達到某個終止條件，例如節點包含的點數小于某個閾值或樹的深度達到預定值。
1.2kd樹搜索原理
1.最近鄰搜索：
- 從根節點開始，根據查詢點在當前分割維度上的值，遞歸地搜索子樹，直到到達葉節點。
- 在回溯過程中，檢查當前節點是否比已知的最近鄰更近，如果是，則更新最近鄰。
- 還需檢查當前節點的另一子樹是否可能包含更近的點，如果可能，則進行搜索。
2.范圍搜索：
- 類似于最近鄰搜索，通過比較查詢點與分割點的關系，遞歸地搜索子樹，檢查節點是否在查詢范圍內。
1.3kd樹構建示例
我們將使用以下點構建一個KD樹：
A(2,3), B(5,4), C(9,6), D(4,7), E(8,1), F(7,2)第一層：
- 選擇 x 軸進行分割。
- 選擇 x 軸上的中位數作為分割點，這里是點 D(4,7)。
D(4,7)/ \第二層：
- 對于左子樹，選擇 y 軸進行分割。
- 左子樹的點為 A(2,3) 和 B(5,4)，選擇 y 軸上的中位數點 A(2,3) 作為分割點。
- 對于右子樹，選擇 y 軸進行分割。
- 右子樹的點為 C(9,6), E(8,1) 和 F(7,2)，選擇 y 軸上的中位數點 F(7,2) 作為分割點。
D(4,7)/ \A(2,3) F(7,2)\ / \B(5,4) E(8,1) C(9,6)
第三層：
- 對于左子樹的右子樹，選擇 x 軸分割。
- 對于右子樹的左右子樹，選擇 x 軸分割。
最終構建的KD樹結構如下：
D(4,7)/ \A(2,3) F(7,2)\ / \B(5,4) E(8,1) C(9,6)
二、常見的領域搜索方式
2.1K近鄰搜索（K-Nearest Neighbors, KNN Search）
K近鄰搜索是找到離查詢點最近的K個點的一種方法。K近鄰搜索基于歐幾里得距離度量，通過KD樹可以高效地實現。
過程：
- 從根節點開始，根據查詢點在當前分割維度上的值，遞歸地搜索子樹，直到到達葉節點。
- 在回溯過程中，檢查當前節點是否比已知的K個最近鄰點更近，如果是，則更新最近鄰集合。
- 還需檢查當前節點的另一子樹是否可能包含更近的點，如果可能，則進行搜索。
應用：
- 數據分類：KNN算法在分類問題中廣泛應用，通過查找最近的K個鄰居進行多數投票決定分類結果。
- 數據降噪：可以通過找到每個點的K個最近鄰來平滑數據。
2.2半徑搜索（Radius Search）
半徑搜索是找到所有在查詢點某個給定半徑范圍內的點的一種方法。與K近鄰搜索不同，半徑搜索返回的是所有在指定半徑范圍內的點。
過程：
- 從根節點開始，根據查詢點和分割點之間的距離，遞歸地搜索子樹。
- 檢查當前節點是否在查詢點的半徑范圍內，如果是，則將其加入結果集合。
- 檢查當前節點的另一子樹是否可能包含在半徑范圍內的點，如果可能，則進行搜索。
應用：
- 密度估計：通過找到某個區域內的所有點，可以估計該區域的點云密度。
- 空間聚類：在聚類算法中，半徑搜索用于找到每個點的鄰域，從而進行聚類。
2.3混合搜索（Hybrid Search）
混合搜索結合了K近鄰搜索和半徑搜索的特點，在進行K近鄰搜索的同時，還限制了搜索范圍在一個給定的半徑內。也就是說，它在指定半徑范圍內找到最多K個最近的點。
過程：
- 從根節點開始，根據查詢點在當前分割維度上的值和半徑約束，遞歸地搜索子樹，直到到達葉節點。
- 檢查當前節點是否在查詢點的半徑范圍內，并且是否屬于最近的K個點，如果是，則將其加入結果集合。
- 檢查當前節點的另一子樹是否可能包含在半徑范圍內并且屬于最近的K個點，如果可能，則進行搜索。
應用：
- 提高搜索效率：在處理大規模點云數據時，混合搜索可以限制搜索范圍，從而提高搜索效率。
- 平衡搜索結果：混合搜索可以在保證結果精確度的同時，限制搜索范圍，避免返回過多不相關的點。
三、代碼實現
3.1關鍵函數
3.1.1K近鄰搜索
??search_knn_vector_3d返回查詢點的k個最近鄰的索引列表。這些相鄰的點存儲在數組numpy中，使用pcd.colors對numpy數組內所有的點進行顏色渲染（渲染為綠色[0，1，0]）。這里跳過了第一個索引點，因為它是查詢點本身
#K近鄰搜索
pcd.colors[10000] = [1, 0, 0]#給定查詢點并渲染為紅色
[k, idx, _] = pcd_tree.search_knn_vector_3d(pcd.points[10000], 200)#K近鄰搜索
np.asarray(pcd.colors)[idx[1:], :] = [0, 1, 0]#K鄰域的點，渲染為綠色
3.1.2半徑鄰域搜索
??使用?search_radius_vector_3d查詢所有的和查詢點點距離小于給定半徑的點
#半徑搜索
pcd.colors[5000] = [1, 0, 0]#給定查詢點并渲染為紅色
[k1, idx1, _] = pcd_tree.search_radius_vector_3d(pcd.points[5000], 0.02)#半徑搜索
np.asarray(pcd.colors)[idx1[1:], :] = [0, 0, 1]#半徑搜索結果并渲染為藍色
3.1.3混合搜索
除了KNN搜索(search_knn_vector_3d)和RNN搜索(search_radius_vector_3d)以外,Open3d還提供了混合搜索函數(search_hybrid_vector_3d)。它最多返回K個和查詢點距離小于給定半徑的最鄰近點。這個函數結合了KNN和RNN的搜索條件，在某些文獻中也被稱作RKNN搜索。在許多情況下它有著性能優勢,并且在Open3d的函數中大量的使用.
#混合搜索
pcd.colors[30000] = [1, 1, 0]#給定查詢點并渲染為黃色
[k2, idx2, _] = pcd_tree.search_hybrid_vector_3d(pcd.points[30000], 0.05,200)#K近鄰搜索
np.asarray(pcd.colors)[idx2[1:], :] = [0, 1, 0.8]#半徑搜索結果并渲染為青色3.2完整代碼
import open3d as o3d
import numpy as np
pcd = o3d.io.read_point_cloud("Horse.pcd")
pcd.paint_uniform_color([0.5, 0.5, 0.5])#把所有點渲染為灰色
pcd_tree = o3d.geometry.KDTreeFlann(pcd)#建立KD樹索引#K近鄰搜索
pcd.colors[10000] = [1, 0, 0]#給定查詢點并渲染為紅色[k, idx, _] = pcd_tree.search_knn_vector_3d(pcd.points[10000], 200)#K近鄰搜索
np.asarray(pcd.colors)[idx[1:], :] = [0, 1, 0]#K鄰域的點，渲染為綠色#半徑搜索
pcd.colors[5000] = [1, 0, 0]#給定查詢點并渲染為紅色
[k1, idx1, _] = pcd_tree.search_radius_vector_3d(pcd.points[5000], 0.02)#半徑搜索
np.asarray(pcd.colors)[idx1[1:], :] = [0, 0, 1]#半徑搜索結果并渲染為藍色#混合搜索
pcd.colors[30000] = [1, 1, 0]#給定查詢點并渲染為黃色
[k2, idx2, _] = pcd_tree.search_hybrid_vector_3d(pcd.points[30000], 0.05,200)#K近鄰搜索
np.asarray(pcd.colors)[idx2[1:], :] = [0, 1, 0.8]#半徑搜索結果并渲染為青色
o3d.visualization.draw_geometries([pcd])四、實現效果
: Gradle 腳本最佳實踐)
 CSRF漏洞)
