`
jgsj
  • 浏览: 1001447 次
文章分类
社区版块
存档分类
最新评论

SIFT特征点匹配中KD-tree与Ransac算法的使用

 
阅读更多

转自:http://blog.csdn.net/ijuliet/article/details/4471311

Step1:BBF算法,在KD-tree上找KNN。第一步做匹配咯~

1.什么是KD-treefromwiki

K-Dimension tree,实际上是一棵平衡二叉树。

一般的KD-tree构造过程:

functionkdtree (list of points pointList, int depth)

{

ifpointList is empty

returnnil;

else {

// Select axis based on depth so thataxis cycles through all valid values

varint axis := depth mod k;

// Sort point list and choose medianas pivot element

selectmedian by axis from pointList;

// Create node and construct subtrees

vartree_node node;

node.location:= median;

node.leftChild:= kdtree(points in pointList before median, depth+1);

node.rightChild:= kdtree(points in pointList after median, depth+1);

returnnode;

}

}

2.BBF算法,在KD-tree上找KNN ( K-nearest neighbor)

BBF(BestBin First)算法,借助优先队列(这里用最小堆)实现。从根开始,在KD-tree上找路子的时候,错过的点先塞到优先队列里,自己先一个劲儿扫到leaf;然后再从队列里取出目前key值最小的(这里是是ki维上的距离最小者),重复上述过程,一个劲儿扫到leaf;直到队列找空了,或者已经重复了200遍了停止。

Step1:img2featuresKD-tree; kd_root = kdtree_build( feat2,n2 );在这里,ki是选取均方差最大的那个维度,kv是各特征点在那个维度上的median值,features是你率领的整个儿子孙子特征大军,n是你儿子孙子个数。

/** a node in a k-d tree */

struct kd_node{

int ki; /**< partition key index */

double kv; /**< partition key value */

int leaf; /**< 1 if node is a leaf, 0 otherwise */

struct feature* features; /**< features at this node */

int n; /**< number of features */

struct kd_node* kd_left; /**< left child */

struct kd_node* kd_right; /**< right child */

};

Step2: img1的每个featKD-tree里找k个最近邻,这里k=2

k= kdtree_bbf_knn( kd_root, feat, 2, &nbrs, KDTREE_BBF_MAX_NN_CHKS );

min_pq = minpq_init();

minpq_insert( min_pq, kd_root, 0 );

while( min_pq->n > 0 && t < max_nn_chks ) //队列里有东西就继续搜,同时控制在t<200(即200步内)

{

expl = (struct kd_node*)minpq_extract_min( min_pq ); //取出最小的,front & pop

expl = explore_to_leaf( expl, feat, min_pq ); //从该点开始,explore到leaf,路过的“有意义的点”就塞到最小队列min_pq中。

for( i = 0; i < expl->n; i++ ) //

{

tree_feat = &expl->features[i];

bbf_data->old_data = tree_feat->feature_data;

bbf_data->d = descr_dist_sq(feat, tree_feat); //两feat均方差

tree_feat->feature_data = bbf_data;

n += insert_into_nbr_array( tree_feat, _nbrs, n, k ); //按从小到大塞到neighbor数组里,到时候取前k个就是 KNN 咯~ n 每次加1或0,表示目前已有的元素个数

}

t++;

}

对“有意义的点”的解释:

struct kd_node* explore_to_leaf( struct kd_node* kd_node, struct feature* feat,

struct min_pq* min_pq )//expl, feat, min_pq

{

struct kd_node* unexpl, * expl = kd_node;

double kv;

int ki;

while( expl && ! expl->leaf )

{

ki = expl->ki;

kv = expl->kv;

if( feat->descr[ki] <= kv ) {

unexpl = expl->kd_right;

expl = expl->kd_left; //走左边,右边点将被记下来

}

else{

unexpl = expl->kd_left;

expl = expl->kd_right; //走右边,左边点将被记下来

}

minpq_insert( min_pq, unexpl, ABS( kv - feat->descr[ki] ) ) ;//将这些点插入进来,key键值为|kv - feat->descr[ki]| 即第ki维上的差值

}

return expl;

}

Step3: 如果k近邻找到了(k=2),那么判断是否能作为有效特征,d0/d1<0.49就算是咯~

d0 = descr_dist_sq( feat, nbrs[0] );//计算两特征间squared Euclidian distance

d1 = descr_dist_sq( feat, nbrs[1] );

if( d0 < d1 * NN_SQ_DIST_RATIO_THR )//如果d0/d1小于阈值0.49

{

pt1 = cvPoint( cvRound( feat->x ), cvRound( feat->y ) );

pt2 = cvPoint( cvRound( nbrs[0]->x ), cvRound( nbrs[0]->y ) );

pt2.y += img1->height;

cvLine( stacked, pt1, pt2, CV_RGB(255,0,255), 1, 8, 0 );//画线

m++;//matches个数

feat1[i].fwd_match = nbrs[0];

}

Step2:通过RANSAC算法来消除错配,什么是RANSAC先?

1.RANSAC(Random Sample Consensus, 随机抽样一致)(from wiki)

该算法做什么呢?呵呵,用一堆数据去搞定一个待定模型,这里所谓的搞定就是一反复测试、迭代的过程,找出一个error最小的模型及其对应的同盟军(consensusset)。用在我们的SIFT特征匹配里,就是说找一个变换矩阵出来,使得尽量多的特征点间都符合这个变换关系。

算法思想:

input:

data - a set of observations

model - a model that can be fitted todata

n - the minimum number of datarequired to fit the model

k - the maximum number of iterationsallowed in the algorithm

t - a threshold value for determiningwhen a datum fits a model

d - the number of close data valuesrequired to assert that a model fits well to data

output:

best_model - model parameters whichbest fit the data (or nil if no good model is found)

best_consensus_set - data point fromwhich this model has been estimated

best_error - the error of this modelrelative to the data

iterations:= 0

best_model:= nil

best_consensus_set:= nil

best_error:= infinity

whileiterations < k //进行K次迭代

maybe_inliers:= n randomly selected values from data

maybe_model:= model parameters fitted to maybe_inliers

consensus_set:= maybe_inliers

forevery point in data not in maybe_inliers

ifpoint fits maybe_model with an error smaller than t //错误小于阈值t

addpoint to consensus_set //成为同盟,加入consensus set

if thenumber of elements in consensus_set is > d //同盟军已经大于d个人,够了

(thisimplies that we may have found a good model,

nowtest how good it is)

better_model:= model parameters fitted to all points in consensus_set

this_error:= a measure of how well better_model fits these points

ifthis_error < best_error

(wehave found a model which is better than any of the previous ones,

keepit until a better one is found)

best_model:= better_model

best_consensus_set:= consensus_set

best_error:= this_error

incrementiterations

returnbest_model, best_consensus_set, best_error

2.RANSAC去除错配:

H= ransac_xform( feat1, n1, FEATURE_FWD_MATCH, lsq_homog, 4,0.01,homog_xfer_err, 3.0, NULL, NULL );

nm = get_matched_features( features, n, mtype, &matched );

/* initialize random number generator */

rng = gsl_rng_alloc( gsl_rng_mt19937 );

gsl_rng_set( rng, time(NULL) );

in_min = calc_min_inliers( nm, m, RANSAC_PROB_BAD_SUPP, p_badxform ); //符合这一要求的内点至少得有多少个

p = pow( 1.0 - pow( in_frac, m ), k );

i = 0;

while( p > p_badxform )//p>0.01

{

sample = draw_ransac_sample( matched, nm, m, rng );

extract_corresp_pts( sample, m, mtype, &pts, &mpts );

M = xform_fn( pts, mpts, m );

if( ! M )

goto iteration_end;

in = find_consensus( matched, nm, mtype, M, err_fn, err_tol, &consensus);

if( in > in_max ) {

if( consensus_max )

free( consensus_max );

consensus_max = consensus;

in_max = in;

in_frac = (double)in_max / nm;

}

else

free( consensus );

cvReleaseMat( &M );

iteration_end:

release_mem( pts, mpts, sample );

p = pow( 1.0 - pow( in_frac, m ), ++k );

}

/* calculate final transform based on best consensus set */

if( in_max >= in_min )

{

extract_corresp_pts( consensus_max, in_max, mtype, &pts, &mpts );

M = xform_fn( pts, mpts, in_max );

in = find_consensus( matched, nm, mtype, M, err_fn, err_tol, &consensus);

cvReleaseMat( &M );

release_mem( pts, mpts, consensus_max );

extract_corresp_pts( consensus, in, mtype, &pts, &mpts );

M = xform_fn( pts, mpts, in );

思考中的一些问题:

features间的对应关系,记录在features->fwd_match里(matching feature from forward

imge)。

1.数据是nm个特征点间的对应关系,由它们产生一个3*3变换矩阵(xform_fn= hsq_homog函数,此要>=4对的对应才可能计算出来咯~),此乃模型model

2.然后开始找同盟军(find_consensus函数),判断除了sample的其它对应关系是否满足这个模型(err_fn= homog_xfer_err函数,<=err_tolOK~),满足则留下。

3.一旦大于当前的in_max,那么该模型就升级为目前最牛的模型。(最最原始的RANSAC是按错误率最小走的,我们这会儿已经保证了错误率在err_tol范围内,按符合要求的对应数最大走,尽量多的特征能匹配地上)

4.重复以上3步,直到(1-wm)k <=p_badxform (0.01),模型就算找定~

5.最后再把模型和同盟军定一下,齐活儿~

声明:以上代码参考Rob HessSIFT实现。

其它参考文献:

1、http://www.cnblogs.com/slysky/archive/2011/11/08/2241247.html

2、http://en.wikipedia.org/wiki/Kd_tree

3、http://www.cnblogs.com/tjulxh/archive/2011/12/31/2308921.html

4、http://grunt1223.iteye.com/blog/961063

分享到:
评论

相关推荐

    OpenCV实现SIFT+KD tree+RANSAC图像拼接

    在这个项目中,我们将详细探讨如何使用OpenCV库,结合SIFT(尺度不变特征变换)、KD树(K-Dimensional Tree)和RANSAC(随机样本一致)算法来实现图像拼接。 **SIFT(尺度不变特征变换)** SIFT是David Lowe在1999...

    sift+kd-tree

    在计算机视觉领域,SIFT(尺度不变特征转换)是一种强大的...总之,SIFT特征和KD-Tree匹配是计算机视觉中的关键技术,它们结合使用能有效地处理图像匹配问题。在Windows环境中,利用OpenCV库可以方便地实现这些功能。

    基于SIFT特征点及RANSAC筛选的图像拼接

    在图像处理领域,图像拼接是一项重要的技术,它主要用于将多张视角相近或者覆盖部分重叠的图片合并成一张全景图。...对于开发者而言,理解和掌握SIFT特征与RANSAC算法的使用,对于提升图像处理能力大有裨益。

    图像局部特征匹配算法发展综述.docx

    例如,在 SIFT 算法中,利用测试图像中的特征点建立一棵 KD-Tree,之后对于参考图像中的每一个特征点使用 BBF 算法在测试图像形成的 KD-Tree 中寻找相邻的点。 最后,生成几何变换即为求这些几何变换的参数的过程,...

    摄影测量中基于特征的匹配

    5. **几何验证**:通过计算匹配点对的几何关系(如Epipolar Geometry),可以进一步验证匹配的正确性,并确定相机间的相对姿态。 6. **三维重建**:通过匹配的特征点和它们在不同视图中的对应关系,可以运用三角...

    基于SIFT特征向量的图像拼接技术研究.docx

    2. **快速匹配策略**:利用启发式方法或近似算法减少特征匹配时间,如使用KD-Tree或FLANN(Fast Library for Approximate Nearest Neighbors)。 3. **鲁棒性改进**:采用RANSAC(随机样本一致)或其他迭代剔除算法...

    sift_python.zip

    SIFT(尺度不变特征变换)是一种强大的图像处理技术,用于识别和匹配图像中的关键点,不论图像的大小、旋转、光照变化如何。本项目“sift_python.zip”提供了一个使用Python实现的SIFT特征提取解决方案,并利用kd树...

    demo_ASIFT_src.tar.gz_DEMO_asift_sift 匹配

    在匹配过程中,计算两幅图像的关键点特征向量之间的欧式距离是常用的方法。欧式距离是两个向量之间直观的直线距离,它衡量了它们在多大程度上不重合。如果两个关键点的特征向量的欧式距离足够小,那么可以认为这两个...

    对图像预处理和特征提取及匹配.rar

    2. **KD-Tree搜索**:通过构建KD-Tree数据结构,快速找到近邻特征点,提高匹配效率。 3. **RANSAC(随机样本一致性)**:用于剔除异常值,提高匹配的稳定性。 4. ** Lowe's比率测试**:匹配时设定阈值,只有当两个...

    图像匹配程序

    6. **RANSAC(随机样本一致)**:在实际应用中,由于噪声和错误匹配的存在,采用RANSAC算法可以剔除异常值,提高匹配的准确性。 7. **OpenCV库**:在VC++环境下,OpenCV是一个广泛使用的图像处理库,很可能这个程序...

    Image Registration based on SIFT(perfect)

    2. **特征匹配**:使用匹配算法(如最近邻距离比测试,Brute-Force或KD-Tree)找出两组描述符之间的最佳匹配对。 3. **粗略配准**:基于匹配对,初步估计图像间的变换参数,如仿射变换、透视变换或刚体变换。常用的...

    ann.rar_ANN_RANSAC

    结合这两个算法,我们可以构建一个图像处理系统,比如在SIFT特征匹配中,先使用ANN快速找到可能匹配的特征对,然后用RANSAC去除错误匹配,得到更精确的对应关系。这种组合在计算机视觉中被广泛应用,尤其是在三维...

    图像匹配技术研究与实现

    可以使用Brute-force匹配(暴力匹配)或使用KD-Tree、FLANN(快速最近邻搜索)等数据结构来优化匹配速度。匹配过程中需要设置阈值,排除不匹配的候选点,例如利用 Lowe's 相对距离比率测试。 4. 稳定性检查:为了...

    关于图像匹配的高质量论文集

    1. **特征检测与描述**:图像匹配的第一步通常是检测和描述图像中的关键点,如SIFT(尺度不变特征变换)、SURF(加速稳健特征)和ORB(快速ORB特征)。这些特征应该具有鲁棒性,即在光照变化、旋转、缩放等条件下...

    图像匹配(可选精度+序贯相似(图像误差))

    另外,为了进一步提高匹配效率,可以使用特征匹配加速技术,如KD-Tree或FLANN(Fast Library for Approximate Nearest Neighbors),它们能够快速找到最近邻匹配。 在视频稳像中,图像匹配是关键步骤。通过对连续帧...

    figure matching update 5-28

    1. **特征检测**:包括SIFT(尺度不变特征变换)、SURF(加速稳健特征)、ORB(快速方向自旋不变鲁棒特征)等,这些算法能从图像中提取出稳定的特征点。 2. **特征描述**:对检测到的特征点进行描述,如描述符计算,...

    基于C++的双目视觉三维重构设计与实现

    8. **数据结构与算法**:在实现过程中,需要理解并运用如KD-Tree、哈希表等数据结构,以及动态规划、图优化等算法。 9. **误差处理与优化**:在实际应用中,由于噪声和不精确的匹配,可能会引入误差。可以通过...

    A invitation to 3D Vision

    1. **特征检测与匹配**:这是3D视觉的基础,包括SIFT、SURF、ORB等特征点检测算法,以及如何在不同视角下匹配这些特征点。 2. **立体视觉**:利用双目或多摄像头系统,通过三角测量原理计算物体的深度信息,实现3D...

Global site tag (gtag.js) - Google Analytics