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

熱線電話：13121318867

登錄
首頁(yè)精彩閱讀KD樹的應(yīng)用（3）BBF算法_數(shù)據(jù)分析師
KD樹的應(yīng)用（3）BBF算法_數(shù)據(jù)分析師
2014-12-03
收藏

KD樹的應(yīng)用（3）BBF算法_數(shù)據(jù)分析師

KD樹近鄰搜索改進(jìn)之BBF算法

    原理在上文第二部分已經(jīng)闡述明白，結(jié)合大頂堆找最近的K個(gè)近鄰思想，相關(guān)主體代碼如下：

  1. //KD樹近鄰搜索改進(jìn)之BBF算法  
  2. int kdtree_bbf_knn( struct kd_node* kd_root, struct feature* feat, int k,  
  3.                     struct feature*** nbrs, int max_nn_chks )                  //2  
  4. {                                               //200  
  5.     struct kd_node* expl;  
  6.     struct min_pq* min_pq;  
  7.     struct feature* tree_feat, ** _nbrs;  
  8.     struct bbf_data* bbf_data;  
  9.     int i, t = 0, n = 0;  
  10.   
  11.     if( ! nbrs  ||  ! feat  ||  ! kd_root )  
  12.     {  
  13.         fprintf( stderr, "Warning: NULL pointer error, %s, line %d\n",  
  14.                 __FILE__, __LINE__ );  
  15.         return -1;  
  16.     }  
  17.   
  18.     _nbrs = (feature**)(calloc( k, sizeof( struct feature* ) )); //2  
  19.     min_pq = minpq_init();   
  20.     minpq_insert( min_pq, kd_root, 0 ); //把根節(jié)點(diǎn)加入搜索序列中  
  21.   
  22.     //隊(duì)列有東西就繼續(xù)搜，同時(shí)控制在t<200步內(nèi)  
  23.     while( min_pq->n > 0  &&  t < max_nn_chks )  
  24.     {                   
  25.         //剛進(jìn)來時(shí),從kd樹根節(jié)點(diǎn)搜索,exp1是根節(jié)點(diǎn)   
  26.         //后進(jìn)來時(shí),exp1是min_pq差值最小的未搜索節(jié)點(diǎn)入口  
  27.         //同時(shí)按min_pq中父,子順序依次檢驗(yàn),保證父節(jié)點(diǎn)的差值比子節(jié)點(diǎn)小.這樣減少返回搜索時(shí)間  
  28.         expl = (struct kd_node*)minpq_extract_min( min_pq );  
  29.         if( ! expl )                                          
  30.         {                                                     
  31.             fprintf( stderr, "Warning: PQ unexpectedly empty, %s line %d\n",  
  32.                     __FILE__, __LINE__ );                           
  33.             goto fail;  
  34.         }  
  35.   
  36.         //從根節(jié)點(diǎn)(或差值最小節(jié)點(diǎn))搜索,根據(jù)目標(biāo)點(diǎn)與節(jié)點(diǎn)模值的差值(小)  
  37.         //確定在kd樹的搜索路徑,同時(shí)存儲(chǔ)各個(gè)節(jié)點(diǎn)另一入口地址\同級(jí)搜索路徑差值.  
  38.         //存儲(chǔ)時(shí)比較父節(jié)點(diǎn)的差值,如果子節(jié)點(diǎn)差值比父節(jié)點(diǎn)差值小,交換兩者存儲(chǔ)位置,  
  39.         //使未搜索節(jié)點(diǎn)差值小的存儲(chǔ)在min_pq的前面,減小返回搜索的時(shí)間.  
  40.         expl = explore_to_leaf( expl, feat, min_pq );   
  41.         if( ! expl )                                    
  42.         {                                               
  43.             fprintf( stderr, "Warning: PQ unexpectedly empty, %s line %d\n",  
  44.                     __FILE__, __LINE__ );                     
  45.             goto fail;                                    
  46.         }                                               
  47.   
  48.         for( i = 0; i < expl->n; i++ )  
  49.         {   
  50.             //使用exp1->n原因:如果是葉節(jié)點(diǎn),exp1->n=1,如果是偽葉節(jié)點(diǎn),exp1->n=0.  
  51.             tree_feat = &expl->features[i];  
  52.             bbf_data = (struct bbf_data*)(malloc( sizeof( struct bbf_data ) ));  
  53.             if( ! bbf_data )  
  54.             {  
  55.                 fprintf( stderr, "Warning: unable to allocate memory,"  
  56.                     " %s line %d\n", __FILE__, __LINE__ );  
  57.                 goto fail;  
  58.             }  
  59.             bbf_data->old_data = tree_feat->feature_data;  
  60.             bbf_data->d = descr_dist_sq(feat, tree_feat); //計(jì)算兩個(gè)關(guān)鍵點(diǎn)描述器差平方和  
  61.             tree_feat->feature_data = bbf_data;  
  62.   
  63.             //取前k個(gè)  
  64.             n += insert_into_nbr_array( tree_feat, _nbrs, n, k );//  
  65.         }                                                  //2  
  66.         t++;  
  67.     }  
  68.   
  69.     minpq_release( &min_pq );  
  70.     for( i = 0; i < n; i++ ) //bbf_data為何搞個(gè)old_data?  
  71.     {  
  72.         bbf_data = (struct bbf_data*)(_nbrs[i]->feature_data);  
  73.         _nbrs[i]->feature_data = bbf_data->old_data;  
  74.         free( bbf_data );  
  75.     }  
  76.     *nbrs = _nbrs;  
  77.     return n;  
  78.   
  79. fail:  
  80.     minpq_release( &min_pq );  
  81.     for( i = 0; i < n; i++ )  
  82.     {  
  83.         bbf_data = (struct bbf_data*)(_nbrs[i]->feature_data);  
  84.         _nbrs[i]->feature_data = bbf_data->old_data;  
  85.         free( bbf_data );  
  86.     }  
  87.     free( _nbrs );  
  88.     *nbrs = NULL;  
  89.     return -1;  
  90. }  

   依據(jù)上述函數(shù)kdtree_bbf_knn從上而下看下來，注意幾點(diǎn)：

    1、上述函數(shù)kdtree_bbf_knn中，explore_to_leaf的代碼如下：

  1. static struct kd_node* explore_to_leaf( struct kd_node* kd_node, struct feature* feat,  
  2.                                         struct min_pq* min_pq )       //kd tree          //the before   
  3. {  
  4.     struct kd_node* unexpl, * expl = kd_node;  
  5.     double kv;  
  6.     int ki;  
  7.   
  8.     while( expl  &&  ! expl->leaf )  
  9.     {                    //0  
  10.         ki = expl->ki;  
  11.         kv = expl->kv;  
  12.   
  13.         if( ki >= feat->d )  
  14.         {  
  15.             fprintf( stderr, "Warning: comparing imcompatible descriptors, %s" \  
  16.                     " line %d\n", __FILE__, __LINE__ );  
  17.             return NULL;  
  18.         }  
  19.         if( feat->descr[ki] <= kv )  //由目標(biāo)點(diǎn)描述器確定搜索向kd tree的左邊或右邊  
  20.         {                            //如果目標(biāo)點(diǎn)模值比節(jié)點(diǎn)小，搜索向tree的左邊進(jìn)行  
  21.             unexpl = expl->kd_right;  
  22.             expl = expl->kd_left;  
  23.         }  
  24.         else  
  25.         {  
  26.             unexpl = expl->kd_left;    //else   
  27.             expl = expl->kd_right;  
  28.         }  
  29.   
  30.         //把未搜索數(shù)分支入口,差值存儲(chǔ)在min_pq,  
  31.         if( minpq_insert( min_pq, unexpl, ABS( kv - feat->descr[ki] ) ) )  
  32.         {                                       
  33.             fprintf( stderr, "Warning: unable to insert into PQ, %s, line %d\n",  
  34.                     __FILE__, __LINE__ );  
  35.             return NULL;  
  36.         }  
  37.     }  
  38.     return expl;  
  39. }  

    2、上述查找函數(shù)kdtree_bbf_knn中的參數(shù)k可調(diào)，代表的是要查找近鄰的個(gè)數(shù)，即number of neighbors to find，在sift特征匹配中，k一般取2

  1. k = kdtree_bbf_knn( kd_root_0, feat, 2, &nbrs, KDTREE_BBF_MAX_NN_CHKS_0 );//點(diǎn)匹配函數(shù)(核心)  
  2.         if( k == 2 ) //只有進(jìn)行2次以上匹配過程,才算是正常匹配過程  

    3、上述函數(shù)kdtree_bbf_knn中“bbf_data->d = descr_dist_sq(feat, tree_feat); //計(jì)算兩個(gè)關(guān)鍵點(diǎn)描述器差平方和”，使用的計(jì)算方法是本文第一部分1.2節(jié)中所述的歐氏距離。

數(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); }