99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話：13121318867

登錄
首頁精彩閱讀k-d樹查詢算法的偽代碼_實(shí)際用法
k-d樹查詢算法的偽代碼_實(shí)際用法
2014-12-03
收藏

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

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

  1. 算法：k-d樹最鄰近查找  
  2. 輸入：Kd，    //k-d tree類型  
  3.      target  //查詢數(shù)據(jù)點(diǎn)  
  4. 輸出：nearest， //最鄰近數(shù)據(jù)點(diǎn)  
  5.      dist      //最鄰近數(shù)據(jù)點(diǎn)和查詢點(diǎn)間的距離  
  6.   
  7. 1. If Kd為NULL，則設(shè)dist為infinite并返回  
  8. 2. //進(jìn)行二叉查找，生成搜索路徑  
  9.    Kd_point = &Kd；                   //Kd-point中保存k-d tree根節(jié)點(diǎn)地址  
  10.    nearest = Kd_point -> Node-data；  //初始化最近鄰點(diǎn)  
  11.   
  12.    while（Kd_point）  
  13.    　　push（Kd_point）到search_path中； //search_path是一個(gè)堆棧結(jié)構(gòu)，存儲(chǔ)著搜索路徑節(jié)點(diǎn)指針  
  14.   
  15.       If Dist（nearest，target） > Dist（Kd_point -> Node-data，target）  
  16.    　　　　nearest  = Kd_point -> Node-data；    //更新最近鄰點(diǎn)  
  17.    　　　　Min_dist = Dist(Kd_point，target）；  //更新最近鄰點(diǎn)與查詢點(diǎn)間的距離  ***/  
  18.    　　s = Kd_point -> split；                       //確定待分割的方向  
  19.   
  20.    　　If target[s] <= Kd_point -> Node-data[s]     //進(jìn)行二叉查找  
  21.    　　　　Kd_point = Kd_point -> left；  
  22.    　　else  
  23.    　　　　Kd_point = Kd_point ->right；  
  24.    End while  
  25.   
  26. 3. //回溯查找  
  27.    while（search_path != NULL）  
  28.    　　back_point = 從search_path取出一個(gè)節(jié)點(diǎn)指針；   //從search_path堆棧彈棧  
  29.    　　s = back_point -> split；                      //確定分割方向  
  30.   
  31.    　　If Dist（target[s]，back_point -> Node-data[s]） < Max_dist   //判斷還需進(jìn)入的子空間  
  32.    　　　　If target[s] <= back_point -> Node-data[s]  
  33.    　　　　　　Kd_point = back_point -> right；  //如果target位于左子空間，就應(yīng)進(jìn)入右子空間  
  34.    　　　　else  
  35.    　　　　　　Kd_point = back_point -> left;    //如果target位于右子空間，就應(yīng)進(jìn)入左子空間  
  36.    　　　　將Kd_point壓入search_path堆棧；  
  37.   
  38.    　　If Dist（nearest，target） > Dist（Kd_Point -> Node-data，target）  
  39.    　　　　nearest  = Kd_point -> Node-data；                 //更新最近鄰點(diǎn)  
  40.    　　　　Min_dist = Dist（Kd_point -> Node-data,target）；  //更新最近鄰點(diǎn)與查詢點(diǎn)間的距離的  
  41.    End while   

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

  1. void innerGetClosest(NODE* pNode, PT point, PT& res, int& nMinDis)  
  2. {  
  3.     if (NULL == pNode)  
  4.         return;  
  5.     int nCurDis = abs(point.x - pNode->pt.x) + abs(point.y - pNode->pt.y);  
  6.     if (nMinDis < 0 || nCurDis < nMinDis)  
  7.     {  
  8.         nMinDis = nCurDis;  
  9.         res = pNode->pt;  
  10.     }  
  11.     if (pNode->splitX && point.x <= pNode->pt.x || !pNode->splitX && point.y <= pNode->pt.y)  
  12.         innerGetClosest(pNode->pLft, point, res, nMinDis);  
  13.     else  
  14.         innerGetClosest(pNode->pRgt, point, res, nMinDis);  
  15.     int rang = pNode->splitX ? abs(point.x - pNode->pt.x) : abs(point.y - pNode->pt.y);  
  16.     if (rang > nMinDis)  
  17.         return;  
  18.     NODE* pGoInto = pNode->pLft;  
  19.     if (pNode->splitX && point.x > pNode->pt.x || !pNode->splitX && point.y > pNode->pt.y)  
  20.         pGoInto = pNode->pRgt;  
  21.     innerGetClosest(pGoInto, point, res, nMinDis);  
  22. }  

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

2.5.2、舉例：點(diǎn)（2.1,3.1）

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

    以查詢（2.1,3.1）為例：

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


2.5.3、舉例：查詢點(diǎn)（2，4.5）

    一個(gè)復(fù)雜點(diǎn)了例子如查找點(diǎn)為（2，4.5），具體步驟依次如下：

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

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

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

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

    研究表明N個(gè)節(jié)點(diǎn)的K維k-d樹搜索過程時(shí)間復(fù)雜度為：tworst=O（kN1-1/k）。

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

數(shù)據(jù)分析咨詢請(qǐng)掃描二維碼

若不方便掃碼，搜微信號(hào)：CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1：配置參數(shù) // 參數(shù)2：回調(diào)，回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對(duì)象，之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須，不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺(tái)檢測(cè)極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式，包括：float，popup width: "280px", https: true // 更多配置參數(shù)說明請(qǐng)參見：http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請(qǐng)輸入'+oInput.attr('placeholder')+'！'; var errTxt = '請(qǐng)輸入正確的'+oInput.attr('placeholder')+'！'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }