網頁 貼吧 文章 作者 工作  
網頁搜尋
 
 愛PO吧 >> 591租房網 >> 瀏覽文章
回覆 加入我的最愛 與好友分享

[CS] K-d tree

本被文章 0 次, 共有回覆 2  
0
 
0


很久以前有跟各位介紹過Octree,我們可以利用Octree,為封閉的3D空間建立一個資料結構來管理空間中的每個元素。
如此我們可以在 O(log N) 的時間內對這3D空間進行搜尋。
3D空間可以用Octree,2D空間可以用Quadtree(四元樹,概念跟Octree一樣)。
那麼4D空間呢?5D空間呢? .... 遇到多維度的空間時,要怎麼去建立一個資料結構來有效管理呢?
K-d tree 可以解決這個問題,這是由 Bentley [1] 在 1975年所提出的概念並發表在ACM (Association for Computing Machinery)上。
K-d tree 是一個二元樹(binary tree),在此樹中除了樹葉外,每一節點皆代表此k維度空間中的某一點,且能平分某一維度的某個子平面空間。
K-d tree 也具有平衡的特質(balanced),即任兩樹葉的高度差皆不超過1。
若有一筆資料 f(x) 佈於 k 維度的空間內,其中 x代表 k 維度的向量,也就是該空間的位置。xyz軟體補給站
則建立K-d tree的演算法如下:
ConstructKdTree( f, k, d){
// 其中f 為輸入資料; k 為 f 所存在的空間之維度; d 為 tree 的 depth,初始值為 0
if( f = empty)
return NULL;
else
(1) i = d % k;
(2) y = f 在第 i 維度平面空間的中間元素(median);
(3) f' = 以y為中點,f的前半部;
(4) f'' = 以y為中點,f的後半部;
(5) 建立新的節點 p 存放 y;
(6) p.left = ConstructKdTree( f', k, d+1);
(7) p.right = ConstructKdTree( f'', k, d+1);
(8) return p;
}
下圖為一個K = 2的例子,輸入資料為[(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)] (圖片來源:wikipedia)
xyz軟體補給站
分析一下這個演算法,在步驟(2)中我們可以用quick sort來找median,這會花費O(n log n)的時間,則建立K-d tree的時間會是 :
T(n) = 2T(n/2) + O(n log n) = O(n log[sup]2[/sup] n)
演算法的課本中有介紹以O(n)的時間來找median之方法,時間可以改善為:
T(n) = 2T(n/2) + O(n) = O(n log n)
但是那 O(n)的常數項是非常大的,不是很實用的演算法,一般並不太建議用這方法。
我們可以把步驟(2)改成以隨機地選一筆資料來代替 median,要注意的是這有可能讓建出來的K-d tree不具有平衡的特性,但在時間複雜度上是會降為 θ(n)。考慮最佳狀況,也就是每次都能選到中間數,則:
T(n) = 2T(n/2) + θ(1) = θ(n)
考慮最差狀況,每次都能選到第一個或最後一個,則
T(n) = T(n - 1) + θ(1) = θ(n)
如果 K-d tree 為一個平衡二元數,則搜尋時間為 O(log n),若不為平衡則搜尋時間就會是 O(n)。接下來我就以平衡的K-d tree來討論進一步的動作。
插入一個新節點可以在 O(log n)時間內完成。我們先進行搜尋動作,若找到與新節點相同的節點就不進行新增,反之則會找到某一葉節點,再判斷新節點是位於此葉節點的左或右邊並加入
xyz軟體補給站欲刪除一個節點 p,同樣地也是必須先進行搜尋動作來找出 p 之位置然後再刪除,之後還要從右子樹找出最小者 q 來代替這位置,也就是找該節點之維度的下一個median,然後再以同樣地動作刪除 q,如此遞迴的進行直到遇見空節點為止。這動作會花費O(log n)的時間。
如果您使用K-d tree 只會用到以上這些基本動作,那麼請千萬不要用K-d tree!您可以把K維度的Key壓縮成一維度的Key,再以其他好用且經典的資料結構來管理,這絕對比K-d tree來得有效率!
那麼我們為甚麼要用 K-d tree?
K-d tree最常的應用就是:找最近點 (Nearest Neighbor Search)
給定一個 k 維空間 S 以及存在於S 中的某一點 p, D(x, y) 為計算S中任兩向量x, y的距離,則 p 的Nearest Neighbor q 之定義如下:
" x Î S, x ≠ q => D(x, p) ≧ D(q, p)

若指定一最大搜尋距離 d ,我們只要對 p點附近d距離的範圍進行搜尋就好,如此一來可以讓整體搜尋時間只有 O(log n)。
找最近點的演算法如下:
NearestNeighbor(x, p, d, h){
/* 其中 x 為樹中節點,我們將以x為起點進行搜尋,一開始我們從root開始;p 為欲搜尋的點;d為最大搜尋距離;h 為某一維度的矩形平面,一開始為第一維度的最大平面(能涵蓋該維度所有的點);用兩個公用變數 q 及 t 來存放nearest point 以及D(q, p)。*/
if( x = NULL ) {
t = ∞;
return;
}
i = x所在的維度 ;
if( p[i] ≦x[i] ){
nearer_x = x.left;
further_x = x.right;
nearer_h = 以x[i]為中心,h的前半部;
further_h = 以x[i]為中心,h的後半部;
}
else{
nearer_x = x.right;
further_x = x.left;
nearer_h = 以x[i]為中心,h的後半部;
further_h = 以x[i]為中心,h的前半部;
}
NearestNeighbor( nearer_x, p, nearer_h, d);
d = min(d, t);
d' = square root of d
if( further_h 在 p 的 d' 範圍內){
if( D(x, p) < t ){
q = x;
t = D(x, p);
}
temp_t = t;
temp_q = q;
NearestNeighbor( further_x, p, further_h , d);
if( t >= temp_t){
q = temp_q ;
t = temp_t;
}
}
} // End of procedure
這方法大致是這樣,先找到葉節點取得p所在空間,再往回找父節點,並判斷其分支是否有可能在範圍內。
K-d tree是蠻進階的資料結構,找最近點是K-d tree最大特色,很多地方都會用到這功能,像遊戲設計,doom-like的game 所常用的BSP tree就是K-d tree的special case。另外在影像自動拼貼(Image stitching),必須要先進行 feature points 的比對,此時就會用到 k-d tree來找出影像中某一點附近幾個feature points 來與另一張影像的feature points比對。其他還有很多應用,只要是找最近點,第一個想到的就是K-d tree。
K-d tree是蠻進階的資料結構,找最近點是K-d tree最大特色,很多地方都會用到這功能,像遊戲設計,doom-like的game 所常用的BSP tree就是K-d tree的special case。另外在影像自動拼貼(Image stitching),必須要先進行 feature points 的比對,此時就會用到 k-d tree來找出影像中某一點附近幾個feature points 來與另一張影像的feature points比對。其他還有很多應用,只要是找最近點,第一個想到的就是K-d tree。
Referencs:
[1] J.L. Bentley, "Multidimensional Binary Search Trees Used for Associative Searching," Communications of the ACM, 18 (1975), pp. 509-517.
[2] A. Moore, "An introductory tutorial on kd-trees," tech. report Technical Report No. 209, Computer Laboratory, University of Cambridge, , Carnegie Mellon University, 1991
[3] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to Algorithms, 2edxyz軟體補給站
," The MIT Press, 2001.
[4] M. Brown, D. G. Lowe, "Recognising Panoramas," Ninth IEEE International Conference on Computer Vision (ICCV'03) - Volume 2, pp.1218, 2003.
[5] Wikipedia

逛上一篇:   逛下一篇:

作者: ozlksvoat
  (2010-06-24 08:10)
推薦文章: 將本文章推薦到【百度收藏】 將本文章推薦到【YouPush】 將本文章推薦到【udn共享書籤】 將本文章推薦到【Fiigo】書籤

 本文章共有回覆 2 篇,分 1 頁
 聲明:以上內容不代表本站立場,且內容由網友發表提供,若有爭議或違法由發表者承擔,本站將不負責連帶責任,謝謝。

 IPoBar  愛PK  愛遊戲  愛online
新手教學 客服中心 站務公告 交換連結 合作提案 關於我們
 
版權所有©ipobar Ltd., All Rights Reserved.
論壇內會員言論僅代表個人觀點,不代表本站同意其說法,本討論區不承擔由該言論所引起的法律責任