熱線電話：13121318867

登錄
首頁精彩閱讀KD樹的應用（3）BBF算法_數據分析師
KD樹的應用（3）BBF算法_數據分析師
2014-12-03
收藏

KD樹的應用（3）BBF算法_數據分析師

KD樹近鄰搜索改進之BBF算法

    原理在上文第二部分已經闡述明白，結合大頂堆找最近的K個近鄰思想，相關主體代碼如下：

  1. //KD樹近鄰搜索改進之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 ); //把根節點加入搜索序列中  
  21.   
  22.     //隊列有東西就繼續搜，同時控制在t<200步內  
  23.     while( min_pq->n > 0  &&  t < max_nn_chks )  
  24.     {                   
  25.         //剛進來時,從kd樹根節點搜索,exp1是根節點   
  26.         //后進來時,exp1是min_pq差值最小的未搜索節點入口  
  27.         //同時按min_pq中父,子順序依次檢驗,保證父節點的差值比子節點小.這樣減少返回搜索時間  
  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.         //從根節點(或差值最小節點)搜索,根據目標點與節點模值的差值(小)  
  37.         //確定在kd樹的搜索路徑,同時存儲各個節點另一入口地址\同級搜索路徑差值.  
  38.         //存儲時比較父節點的差值,如果子節點差值比父節點差值小,交換兩者存儲位置,  
  39.         //使未搜索節點差值小的存儲在min_pq的前面,減小返回搜索的時間.  
  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原因:如果是葉節點,exp1->n=1,如果是偽葉節點,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); //計算兩個關鍵點描述器差平方和  
  61.             tree_feat->feature_data = bbf_data;  
  62.   
  63.             //取前k個  
  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為何搞個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. }  

   依據上述函數kdtree_bbf_knn從上而下看下來，注意幾點：

    1、上述函數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 )  //由目標點描述器確定搜索向kd tree的左邊或右邊  
  20.         {                            //如果目標點模值比節點小，搜索向tree的左邊進行  
  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.         //把未搜索數分支入口,差值存儲在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、上述查找函數kdtree_bbf_knn中的參數k可調，代表的是要查找近鄰的個數，即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 );//點匹配函數(核心)  
  2.         if( k == 2 ) //只有進行2次以上匹配過程,才算是正常匹配過程  

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


CDA數據分析師考試相關入口一覽（建議收藏）：

? 想報名CDA認證考試，點擊>>>   “CDA報名” 了解CDA考試詳情；

? 想學習CDA考試教材，點擊>>> “CDA教材” 了解CDA考試詳情；

? 想加入CDA考試題庫，點擊>>> “CDA題庫” 了解CDA考試詳情；

? 想了解CDA考試含金量，點擊>>> “CDA含金量” 了解CDA考試詳情；

特征 數據分析

數據分析咨詢請掃描二維碼

若不方便掃碼，搜微信號：CDAshujufenxi

上一篇隨機森林 vs XGBoost vs 決策樹：算法選擇中的
下一篇圖論在大數據分析中的作用！
數據分析師考試動態
CDA報考指南
數據分析學習
數據分析師資訊
更多

CDA教育閉環

常見問題

關于我們

CDA數據分析師公眾號

  • CDA數據分析師公眾號

CDA考試中心小程序

  • CDA考試中心服務號

CDA數據分析師App下載

  • CDA數據分析師App下載
Copyright © 2015-2021, www.ruiqisteel.com All Rights Reserved. CDA數據分析師(北京國富如荷網絡科技有限公司) 版權所有 京ICP備11001960號-9 京公網安備 11010802034615號 經營許可證編號：京B2-20210330
聯系電話：13321103290 (微信同號)

OK
客服在線
立即咨詢
日韩人妻系列无码专区视频,先锋高清无码,无码免费视欧非,国精产品一区一区三区无码
客服在線
立即咨詢