k-d樹查詢算法的偽代碼_實際用法

    k-d樹查詢算法的偽代碼如下所示：

    讀者來信點評@yhxyhxyhx，在“將Kd_point壓入search_path堆棧；”這行代碼后，應該是調(diào)到步驟2再往下走二分搜索的邏輯一直到葉結(jié)點，我寫了一個遞歸版本的二維kd tree的搜索函數(shù)你對比的看看：

    下面，以兩個簡單的實例(例子來自圖像局部不變特性特征與描述一書)來描述最鄰近查找的基本思路。

2.5.2、舉例：點（2.1,3.1）

    星號表示要查詢的點（2.1,3.1）。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節(jié)點（2,3）。而找到的葉子節(jié)點并不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位于以查詢點為圓心且通過葉子節(jié)點的圓域內(nèi)。為了找到真正的最近鄰，還需要進行相關(guān)的‘回溯'操作。也就是說，算法首先沿搜索路徑反向查找是否有距離查詢點更近的數(shù)據(jù)點。

    以查詢（2.1,3.1）為例：

1. 二叉樹搜索：先從（7,2）點開始進行二叉查找，然后到達（5,4），最后到達（2,3），此時搜索路徑中的節(jié)點為<(7,2)，(5,4)，(2,3)>，首先以（2,3）作為當前最近鄰點，計算其到查詢點（2.1,3.1）的距離為0.1414，
2. 回溯查找：在得到（2,3）為查詢點的最近點之后，回溯到其父節(jié)點（5,4），并判斷在該父節(jié)點的其他子節(jié)點空間中是否有距離查詢點更近的數(shù)據(jù)點。以（2.1,3.1）為圓心，以0.1414為半徑畫圓，如下圖所示。發(fā)現(xiàn)該圓并不和超平面y = 4交割，因此不用進入（5,4）節(jié)點右子空間中(圖中灰色區(qū)域)去搜索；
3. 最后，再回溯到（7,2），以（2.1,3.1）為圓心，以0.1414為半徑的圓更不會與x = 7超平面交割，因此不用進入（7,2）右子空間進行查找。至此，搜索路徑中的節(jié)點已經(jīng)全部回溯完，結(jié)束整個搜索，返回最近鄰點（2,3），最近距離為0.1414。

2.5.3、舉例：查詢點（2，4.5）

    一個復雜點了例子如查找點為（2，4.5），具體步驟依次如下：

1. 同樣先進行二叉查找，先從（7,2）查找到（5,4）節(jié)點，在進行查找時是由y = 4為分割超平面的，由于查找點為y值為4.5，因此進入右子空間查找到（4,7），形成搜索路徑<(7,2)，(5,4)，(4,7)>，但（4,7）與目標查找點的距離為3.202，而（5,4）與查找點之間的距離為3.041，所以（5,4）為查詢點的最近點；
2. 以（2，4.5）為圓心，以3.041為半徑作圓，如下圖所示?？梢娫搱A和y = 4超平面交割，所以需要進入（5,4）左子空間進行查找，也就是將（2,3）節(jié)點加入搜索路徑中得<(7,2)，(2,3)>；于是接著搜索至（2,3）葉子節(jié)點，（2,3）距離（2,4.5）比（5,4）要近，所以最近鄰點更新為（2，3），最近距離更新為1.5；
3. 回溯查找至（5,4），直到最后回溯到根結(jié)點（7,2）的時候，以（2,4.5）為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如下圖所示。至此，搜索路徑回溯完，返回最近鄰點（2,3），最近距離1.5。

    上述兩次實例表明，當查詢點的鄰域與分割超平面兩側(cè)空間交割時，需要查找另一側(cè)子空間，導致檢索過程復雜，效率下降。

    一般來講，最臨近搜索只需要檢測幾個葉子結(jié)點即可，如下圖所示：　　

    但是，如果當實例點的分布比較糟糕時，幾乎要遍歷所有的結(jié)點，如下所示：

    研究表明N個節(jié)點的K維k-d樹搜索過程時間復雜度為：t_worst=O（kN^1-1/k）。

    同時，以上為了介紹方便，討論的是二維或三維情形。但在實際的應用中，如SIFT特征矢量128維，SURF特征矢量64維，維度都比較大，直接利用k-d樹快速檢索（維數(shù)不超過20）的性能急劇下降，幾乎接近貪婪線性掃描。假設數(shù)據(jù)集的維數(shù)為D，一般來說要求數(shù)據(jù)的規(guī)模N滿足N?2^D，才能達到高效的搜索。所以這就引出了一系列對k-d樹算法的改進：BBF算法，和一系列M樹、VP樹、MVP樹等高維空間索引樹(下文2.6節(jié)kd樹近鄰搜索算法的改進：BBF算法，與2.7節(jié)球樹、M樹、VP樹、MVP樹)。