本節(jié)將介紹Open3D開源庫：KDTree的原理及構(gòu)建，將無序點(diǎn)云變?yōu)橛行螯c(diǎn)云，實(shí)現(xiàn)點(diǎn)云的快速鄰近搜索。
1.KDTree 概述
Open3D使用FLANN構(gòu)建KDTrees，將無序點(diǎn)云變?yōu)橛行螯c(diǎn)云，以便快速檢索最近鄰。
在激光雷達(dá)中，一般使用的是三維點(diǎn)云。所以，kd-tree的維度是3。
KDTree（k 維樹）是一種空間分區(qū)數(shù)據(jù)結(jié)構(gòu)，它將一組 k 維點(diǎn)存儲(chǔ)在樹結(jié)構(gòu)中，從而實(shí)現(xiàn)高效的范圍搜索和最近鄰搜索。最近鄰搜索是處理點(diǎn)云數(shù)據(jù)時(shí)的核心操作，可用于查找點(diǎn)組或要素描述符之間的對(duì)應(yīng)關(guān)系，或定義一個(gè)或多個(gè)點(diǎn)周圍的局部鄰域。
具體KD-Tree原理詳解參考以下文章：
- KD-Tree原理詳解：https://zhuanlan.zhihu.com/p/112246942
-
三維點(diǎn)云學(xué)習(xí)（2）中-Kd-tree (k-dimensional tree)：https://blog.csdn.net/weixin_41281151
2.KDTree 算法流程
2.1 構(gòu)建KDtree
首先，讀取點(diǎn)云并渲染為灰色便于后面顯示搜索到的點(diǎn)云，通過o3d.geometry.KDTreeFlann函數(shù)建立樹結(jié)構(gòu)
pcd = o3d.io.read_point_cloud("./tree/Tree_singel.pcd")
o3d.visualization.draw_geometries([pcd],width = 700, height = 900)
pcd.paint_uniform_color([0.5, 0.5, 0.5]) # 渲染為灰色
o3d.visualization.draw_geometries([pcd],width = 700, height = 900)
pcd_tree = o3d.geometry.KDTreeFlann(pcd) # 建立樹結(jié)構(gòu)
2.2 搜索相鄰點(diǎn)
將第480000個(gè)點(diǎn)作為錨點(diǎn)并渲染成紅色
pcd.colors[48000] = [1, 0, 0] # 將該點(diǎn)作為錨點(diǎn)并渲染為紅色
2.3 鄰近搜索
法1：KNN最近鄰近搜索
采用search_knn_vector_3d函數(shù)實(shí)現(xiàn)，返回錨點(diǎn)的 k 個(gè)最近鄰的索引列表。使用np.asarray轉(zhuǎn)換為 numpy 數(shù)組以批量訪問點(diǎn)顏色，將相鄰點(diǎn)渲染成藍(lán)色。搜索時(shí)會(huì)跳過第一個(gè)索引，因?yàn)樗清^點(diǎn)本身。
# 方法1：KNN領(lǐng)域搜索
pcd.colors[48000] = [1, 0, 0] # 將該點(diǎn)作為錨點(diǎn)并渲染為紅色
[k, idx, _] = pcd_tree.search_knn_vector_3d(pcd.points[48000], 300)
np.asarray(pcd.colors)[idx[1:], :] = [0, 0, 1] # 渲染成藍(lán)色
法2：RNN半徑鄰近搜索
采用search_radius_vector_3d函數(shù)查詢到錨點(diǎn)的距離小于給定半徑的所有點(diǎn)。
# 方法2：RNN半徑領(lǐng)域搜索
pcd.colors[2500] = [1, 0, 0] # 將該點(diǎn)作為錨點(diǎn)并渲染為紅色
[k1, idx1, _] = pcd_tree.search_radius_vector_3d(pcd.points[2500], 0.2) # 半徑搜索
np.asarray(pcd.colors)[idx1[1:], :] = [0, 1, 0] # 半徑搜索結(jié)果并渲染為綠色
o3d.visualization.draw_geometries([pcd], width = 700, height = 900)
法3：RKNN混合搜索
采用search_hybrid_vector_3d函數(shù)實(shí)現(xiàn)，結(jié)合 KNN 搜索和 RNN 搜索的條件最多返回K個(gè)和錨點(diǎn)距離小于給定半徑的最鄰近點(diǎn)。在許多實(shí)際情況下具有性能優(yōu)勢(shì)，并在Open3D的許多函數(shù)中大量使用。
# 法3：混合搜索
pcd.colors[222] = [1, 0, 0]
[k2, idx2, _] = pcd_tree.search_hybrid_vector_3d(pcd.points[222], 0.5,200) # RKNN混合搜索
np.asarray(pcd.colors)[idx2[1:], :] = [0, 1, 0.8]#半徑搜索結(jié)果并渲染為青色
o3d.visualization.draw_geometries([pcd], width = 700, height = 900)
總結(jié)
本節(jié)介紹采用開源點(diǎn)云處理庫Open3D之構(gòu)建KDtree樹實(shí)現(xiàn)點(diǎn)云的快速鄰近搜索。文章來源：http://www.zghlxwxcb.cn/news/detail-446172.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-446172.html
到了這里，關(guān)于激光雷達(dá)（LiDAR）| Open3D：第二節(jié) 鄰近搜索之構(gòu)建KDTree的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
