热线电话：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考试详情；

▷ 想了解CDA院校合作，点击>>> “院校合作” 了解咨询CDA院校合作；

特征 数据分析

数据分析咨询请扫描二维码

若不方便扫码，搜微信号：CDAshujufenxi

上一篇随机森林 vs XGBoost vs 决策树：算法选择中的
下一篇图论在大数据分析中的作用！
数据分析师考试动态
CDA报考指南
数据分析学习
数据分析师资讯
更多

CDA教育闭环

常见问题

关于我们

CDA数据分析师公众号

  • CDA数据分析师公众号

CDA考试中心小程序

  • CDA考试中心服务号

CDA数据分析师App下载

  • CDA数据分析师App下载
Copyright © 2015-2021, www.cda.cn All Rights Reserved. CDA数据分析师(北京国富如荷网络科技有限公司) 版权所有 京ICP备11001960号-9 京公网安备 11010802034615号 经营许可证编号：京B2-20210330
联系电话：13321103290 (微信同号)

OK
客服在线
立即咨询
客服在线
立即咨询