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

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

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

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

2.5.2、舉例：點（2.1,3.1）

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

    以查詢（2.1,3.1）為例：

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

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

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

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

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

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

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

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

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