[每天一个数据分析师] KD树近邻搜索改进之BBF算法 [推广有奖]

4关注
124
粉丝

管理员

已卖：189份资源

泰斗

还不是VIP/贵宾

威望: 3 级
论坛币: 117887 个
通用积分: 10251.9608
学术水平: 278 点
热心指数: 286 点
信用等级: 253 点
经验: 228049 点
帖子: 6913
精华: 19
在线时间: 4375 小时
注册时间: 2019-9-13
最后登录: 2026-1-4

楼主

CDA网校

发表于 2022-6-29 15:44:57 |AI写论文

是否 +2 论坛币

k人参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

KD树近邻搜索改进之BBF算法

原理在上文第二部分已经阐述明白，结合大顶堆找最近的K个近邻思想，相关主体代码如下：

//KD树近邻搜索改进之BBF算法
int kdtree_bbf_knn( struct kd_node* kd_root, struct feature* feat, int k,
struct feature*** nbrs, int max_nn_chks ) //2
{ //200
struct kd_node* expl;
struct min_pq* min_pq;
struct feature* tree_feat, ** _nbrs;
struct bbf_data* bbf_data;
int i, t = 0, n = 0;
if( ! nbrs || ! feat || ! kd_root )
{
fprintf( stderr, "Warning: NULL pointer error, %s, line %d\n",
__FILE__, __LINE__ );
return -1;
}
_nbrs = (feature**)(calloc( k, sizeof( struct feature* ) )); //2
min_pq = minpq_init();
minpq_insert( min_pq, kd_root, 0 ); //把根节点加入搜索序列中
//队列有东西就继续搜，同时控制在t<200步内
while( min_pq->n > 0 && t < max_nn_chks )
{
//刚进来时,从kd树根节点搜索,exp1是根节点
//后进来时,exp1是min_pq差值最小的未搜索节点入口
//同时按min_pq中父,子顺序依次检验,保证父节点的差值比子节点小.这样减少返回搜索时间
expl = (struct kd_node*)minpq_extract_min( min_pq );
if( ! expl )
{
fprintf( stderr, "Warning: PQ unexpectedly empty, %s line %d\n",
__FILE__, __LINE__ );
goto fail;
}
//从根节点(或差值最小节点)搜索,根据目标点与节点模值的差值(小)
//确定在kd树的搜索路径,同时存储各个节点另一入口地址\同级搜索路径差值.
//存储时比较父节点的差值,如果子节点差值比父节点差值小,交换两者存储位置,
//使未搜索节点差值小的存储在min_pq的前面,减小返回搜索的时间.
expl = explore_to_leaf( expl, feat, min_pq );
if( ! expl )
{
fprintf( stderr, "Warning: PQ unexpectedly empty, %s line %d\n",
__FILE__, __LINE__ );
goto fail;
}
for( i = 0; i < expl->n; i++ )
{
//使用exp1->n原因:如果是叶节点,exp1->n=1,如果是伪叶节点,exp1->n=0.
tree_feat = &expl->features[i];
bbf_data = (struct bbf_data*)(malloc( sizeof( struct bbf_data ) ));
if( ! bbf_data )
{
fprintf( stderr, "Warning: unable to allocate memory,"
" %s line %d\n", __FILE__, __LINE__ );
goto fail;
}
bbf_data->old_data = tree_feat->feature_data;
bbf_data->d = descr_dist_sq(feat, tree_feat); //计算两个关键点描述器差平方和
tree_feat->feature_data = bbf_data;
//取前k个
n += insert_into_nbr_array( tree_feat, _nbrs, n, k );//
} //2
t++;
}
minpq_release( &min_pq );
for( i = 0; i < n; i++ ) //bbf_data为何搞个old_data?
{
bbf_data = (struct bbf_data*)(_nbrs[i]->feature_data);
_nbrs[i]->feature_data = bbf_data->old_data;
free( bbf_data );
}
*nbrs = _nbrs;
return n;
fail:
minpq_release( &min_pq );
for( i = 0; i < n; i++ )
{
bbf_data = (struct bbf_data*)(_nbrs[i]->feature_data);
_nbrs[i]->feature_data = bbf_data->old_data;
free( bbf_data );
}
free( _nbrs );
*nbrs = NULL;
return -1;
}
依据上述函数kdtree_bbf_knn从上而下看下来，注意几点：
1、上述函数kdtree_bbf_knn中，explore_to_leaf的代码如下：
static struct kd_node* explore_to_leaf( struct kd_node* kd_node, struct feature* feat,
struct min_pq* min_pq ) //kd tree //the before
{
struct kd_node* unexpl, * expl = kd_node;
double kv;
int ki;
while( expl && ! expl->leaf )
{ //0
ki = expl->ki;
kv = expl->kv;
if( ki >= feat->d )
{
fprintf( stderr, "Warning: comparing imcompatible descriptors, %s" \
" line %d\n", __FILE__, __LINE__ );
return NULL;
}
if( feat->descr[ki] <= kv ) //由目标点描述器确定搜索向kd tree的左边或右边
{ //如果目标点模值比节点小，搜索向tree的左边进行
unexpl = expl->kd_right;
expl = expl->kd_left;
}
else
{
unexpl = expl->kd_left; //else
expl = expl->kd_right;
}
//把未搜索数分支入口,差值存储在min_pq,
if( minpq_insert( min_pq, unexpl, ABS( kv - feat->descr[ki] ) ) )
{
fprintf( stderr, "Warning: unable to insert into PQ, %s, line %d\n",
__FILE__, __LINE__ );
return NULL;
}
}
return expl;
}

复制代码

2、上述查找函数kdtree_bbf_knn中的参数k可调，代表的是要查找近邻的个数，即number of neighbors to find，在sift特征匹配中，k一般取2

k = kdtree_bbf_knn( kd_root_0, feat, 2, &nbrs, KDTREE_BBF_MAX_NN_CHKS_0 );//点匹配函数(核心)
if( k == 2 ) //只有进行2次以上匹配过程,才算是正常匹配过程
3、上述函数kdtree_bbf_knn中“bbf_data->d = descr_dist_sq(feat, tree_feat); //计算两个关键点描述器差平方和”，使用的计算方法是本文第一部分1.2节中所述的欧氏距离。

相关帖子DA内容精选