sift研究.docx

sift研究.docx

《sift研究.docx》由会员分享，可在线阅读，更多相关《sift研究.docx（17页珍藏版）》请在冰点文库上搜索。

sift研究

sift研究（转）

1.介绍：

特征提取过程：

1，尺度空间极值检测。

2，特征点定位。

（包括去除不稳定的点）。

3，特征点的方向赋值。

4，特征点描述子生成。

2.极值点检测：

尺度空间由输入图像和高斯函数卷积产生。

尺度空间的极值点由高斯差分函数与图像卷积二乘的DOG求的。

第二组第一层的图像是第一组第二层图像重采样1/2得到的。

极值点的检测是在DOG空间中进行，在三层中选择特征点领域的极值。

每组DOG中采样3层时，正确率最高，即要6层的高斯层。

尺度空间的间隔为1.6.

3.特征点的准确定位：

亚像素精度的计算，求取泰勒级数，计算出对比度低的点淘汰。

边缘不稳定的点通过Hessian矩阵判断。

4.方向赋值通过给每个像素点赋予方向值，可以使特征点的特征向量拥有旋转不变性。

缺点：

限制了描述子使用或抛弃一些图像的信息，特别是在旋转一致性上不需要所有测量值时。

方向直方图是由特征点领域内的采样点的梯度方向形成的。

分36格，每格10度。

每个采样点加入直方图是由其梯度幅值和高斯圆窗（1.5当前尺度）加权产生。

方向直方图峰值是局部梯度的主要方向。

80%最大值以后的峰值方向也可作为特征点的第二方向。

大概只有15%的点有多个主方向。

用抛物线来拟合三个与每个峰值最近的直方图的值，峰值位置差值方法可提高精度。

5，局部图像描述符每个特征点都具有三个基本属性：

位置，尺度，方向。

一个比较明显的方法是采样特征点局部区域的光强，通过规范化的相关性测量方法匹配。

缺点：

对仿射变换还有3D视点的改变，非刚体的变形都很敏感。

Edelman,Intratorandpoggio（1997）.证明了一个更好的办法，由生物视觉知道在原始视觉表层，复杂的神经元细胞对梯度的一个特定方向和空间频率有相应。

而梯度的位置在视网膜上允许移动一些神经元，而不是精确定位。

文章的受上面的启发，采用了梯度方向描述符。

但是通过另一个方式实现了位置移动。

6.描述符表达通过取与特征点主方向的差值来实现描述符的方向不变性。

用高斯窗加权每一个点的梯度是为了避免描述符的突变当窗口的位置发生改变时，同时减小边远像素梯度的影响。

为每个方向直方图分配了8个方向。

箭头的长度和直方图条目的尺度有关。

采用4*4方格采样，可使局部区域内的像素点偏移4个点而不影响描述符。

避免边缘影响的方法是三线插值。

光照不变性，是通过归一化特征向量实现的。

通过设阀值降低大梯度在单位特征向量里的影响。

最大不能超过0.2。

影响描绘子的结构复杂性因素：

方向数和直方图的组数（即采用多大的局部区域）。

4*4*8=128维。

4*4是16个直方图（每个直方图由4*4个点组成），8是方向数。

7.对象识别的应用对象识别的步骤：

1.首先单独的为每个特征点匹配数据库中的特征点（样本图像）。

2.初始匹配由于模糊的特征和背景的遮挡等出错，所以每个类别在第一次识别时，至少有三个特征是符合对象和它的位姿的。

这些类别有很高的匹配正确率相对于单个的特征匹配。

3.这些类别将被通过一个具体的几何约束去匹配模型。

结果可用来判断接收或拒绝假设。

关键点的匹配准则是通过求特征向量的欧氏距离来寻找最近邻，同时这个距离必须满足是次近邻点的0.8倍以上。

在高维空间中，有效的数据组织方法是K-Dtree。

我们使用一个近似搜索方法best-bin-first（BBF）算法。

作者在搜寻了200个最近邻候选点后停止，（5%）正确匹配率损失。

霍夫分类：

当有3个特征点正确匹配时，对象可以可靠的识别。

RANSAC匹配法可适用。

通过投票方式实现特征的聚类（和特征一致的对象位姿）。

每个特征点有四个参数：

2D图像位置，尺度，方向，和匹配点的数据库记录。

假设匹配是指开始的距离粗匹配。

通过匹配点对的四个方程计算3个参数，包括对象的平移，旋转，缩放等三个。

（不是全仿射，即没有切边变换在内平行四边形）。

通过哈希表来表达投票的箱格。

8.仿射参数求解用最小二乘法求解广义逆求解。

一个通常的方法是使用基础矩阵（hartley,zisserman,2000）.但是基础矩阵方法需要七个匹配点对，相对与仿射变换方法只需3个匹配点对，且要求匹配点对有较高的稳定性。

验证模型是通过判断最后类别中的匹配点对个数，对于小的区域物体3个，大的物体或纹理丰富的10个。

9.应用场合：

单幅图像的多对象识别，位置识别，机器人的自主定位等。

10.结论：

阐述了SIFT特征点的特点及产生过程。

用SIFT特征完成目标识别，包括最近邻搜索，对象位姿的霍夫聚类，最小二乘位姿计算，最后验证。

其他应用还有3D重建，运动跟踪，分割，机器人定位，摄像机标定等。

未来的研究包括建立光照不变的色彩描述符（目前是单色的）。

局部纹理的测量已经在人类是绝中扮演了越来越重要的角色，可以整合到特征描述符中。

可以多特征结合进行对象识别。

另一个方向是特定对象类别的识别。

后记：

 这是我在5月份看SIFT的文献写下的总结。

局部特征描述子有很多，最早的Harris角点，后来的SITF、Harris-Laplac、SURF等等，网上可以找到相关的文献，具体的可以参照K.mikolajczyk：

aperformanceevaluationoflocaldescriptors.SIFT算法后来也有两个变种：

PCA-SIFT和GLOH。

SIFT是目前应用最广的局部描述符，具有较高的稳定性和区分度，但是在计算时间上消耗较大，现在也有通过显卡（OPENGL和CUDA）加速的。

SURF和SIFT很相近，但是速度上有很大的提高，源于它使用了积分图像和Haar小波的技术，但是在匹配的性能上貌似稍逊色点。

尺度空间的概念经常出现在各类的图像处理技术中，所以理解它非常重要，可以参考Lindeberg（1994）的关于尺度空间理论的文献。

在后来看关于直线段的描述符时发现它和特征点描述符，在研究思路和实现上时很相似的。

基本就是1.选取一个判定准则找出特征点或线，一般都是选取局部极值（能量最大值）；2，判断稳定性，加一些约束条件，删除掉不稳定的特征；3，产生描述符，通过核的方式加权区域信息，使得描述符的鲁棒性更强，然后对描述符做一些处理，归一化等。

这些技术基本都是建立在了利用图像梯度和梯度方向的信息上、再加个Laplace（二阶导数），特征描述子就反复倒腾琢磨这几个信息如何更有效的利用。

在这个方向上，感觉做的比较成熟了，很难有新的突破，现在很多文献的工作都是基于上述描述子的基础根据相应的应用做适当的修改，没有从原理上突破。

以上是个人愚见，仅供参考，如果大家有好的想法和意见一定要告知^_^。

SIFT特征点匹配与消除错配：

BBF，RANSAC

Step1:

BBF算法，在KD-tree上找KNN。

第一步做匹配咯~

1.      什么是KD-tree（fromwiki）

K-Dimensiontree，实际上是一棵平衡二叉树。

一般的KD-tree构造过程：

functionkdtree（listofpointspointList,intdepth）

{

ifpointListisempty

returnnil;

else{

//Selectaxisbasedondepthsothataxiscyclesthroughallvalidvalues

varintaxis:

=depthmodk;

//Sortpointlistandchoosemedianaspivotelement

selectmedianbyaxisfrompointList;

//Createnodeandconstructsubtrees

vartree_nodenode;

node.location:

=median;

node.leftChild:

=kdtree（pointsinpointListbeforemedian,depth+1）;

node.rightChild:

=kdtree（pointsinpointListaftermedian,depth+1）;

returnnode;

}

}

【例】pointList=[（2,3）,（5,4）,（9,6）,（4,7）,（8,1）,（7,2）]tree=kdtree（pointList）

2.      BBF算法，在KD-tree上找KNN（K-nearestneighbor）

BBF（BestBinFirst）算法，借助优先队列（这里用最小堆）实现。

从根开始，在KD-tree上找路子的时候，错过的点先塞到优先队列里，自己先一个劲儿扫到leaf；然后再从队列里取出目前key值最小的（这里是是ki维上的距离最小者），重复上述过程，一个劲儿扫到leaf；直到队列找空了，或者已经重复了200遍了停止。

Step1:

将img2的features建KD-tree; kd_root=kdtree_build（feat2,n2）;。

在这里，ki是选取均方差最大的那个维度，kv是各特征点在那个维度上的median值，features是你率领的整个儿子孙子特征大军，n是你儿子孙子个数。

/**anodeinak-dtree*/

structkd_node{

intki;                     /**

doublekv;                  /**

intleaf;                   /**<1ifnodeisaleaf,0otherwise*/

structfeature*features;   /**

intn;                      /**

structkd_node*kd_left;    /**

structkd_node*kd_right;   /**

};

Step2:

将img1的每个feat到KD-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

{

expl=（structkd_node*）minpq_extract_min（min_pq）;//取出最小的，front&pop

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

for（i=0;in;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++;

}

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

structkd_node*explore_to_leaf（structkd_node*kd_node,structfeature*feat,

structmin_pq*min_pq）//expl,feat,min_pq

{

structkd_node*unexpl,*expl=kd_node;

doublekv;

intki;

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维上的差值

}

returnexpl;

}

Step3:

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

d0=descr_dist_sq（feat,nbrs[0]）;//计算两特征间squaredEuclidiandistance

d1=descr_dist_sq（feat,nbrs[1]）;

if（d0

{

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（RandomSampleConsensus,随机抽样一致） （fromwiki）

该算法做什么呢？

呵呵，用一堆数据去搞定一个待定模型，这里所谓的搞定就是一反复测试、迭代的过程，找出一个error最小的模型及其对应的同盟军（consensusset）。

用在我们的SIFT特征匹配里，就是说找一个变换矩阵出来，使得尽量多的特征点间都符合这个变换关系。

算法思想：

input:

data–asetofobservations

model–amodelthatcanbefittedtodata

n–theminimumnumberofdatarequiredtofitthemodel

k–themaximumnumberofiterationsallowedinthealgorithm

t–athresholdvaluefordeterminingwhenadatumfitsamodel

d–thenumberofclosedatavaluesrequiredtoassertthatamodelfitswelltodata

output:

best_model–modelparameterswhichbestfitthedata（ornilifnogoodmodelisfound）

best_consensus_set–datapointfromwhichthismodelhasbeenestimated

best_error–theerrorofthismodelrelativetothedata

iterations:

=0

best_model:

=nil

best_consensus_set:

=nil

best_error:

=infinity

whileiterations

maybe_inliers:

=nrandomlyselectedvaluesfromdata

maybe_model:

=modelparametersfittedtomaybe_inliers

consensus_set:

=maybe_inliers

foreverypointindatanotinmaybe_inliers

ifpointfitsmaybe_modelwithanerrorsmallerthant//错误小于阈值t

addpointtoconsensus_set  //成为同盟，加入consensusset

ifthenumberofelementsinconsensus_setis>d//同盟军已经大于d个人，够了

（thisimpliesthatwemayhavefoundagoodmodel,

nowtesthowgooditis）

better_model:

=modelparametersfittedtoallpointsinconsensus_set

this_error:

=ameasureofhowwellbetter_modelfitsthesepoints

ifthis_error

（wehavefoundamodelwhichisbetterthananyofthepreviousones,

keepituntilabetteroneisfound）

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）;

/*initializerandomnumbergenerator*/

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）

gotoiteration_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）;

}

/*calculatefinaltransformbasedonbestconsensusset*/

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里（matchingfeaturefromforward

imge）。

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

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

3.      一旦大于当前的in_max，那么该模型就升级为目前最牛的模型。

（最最原始的RANSAC是按错误率最小走的，我们这会儿已经保证了错误率在err_tol范围内，按符合要求的对应数最大走，尽量多的特征能匹配地上）

4.      重复以上3步，直到（1-wm）k<=p_badxform（即0.01），模型就算找定~

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

浅谈对象侦测与对象切割技术…

在视讯中进行对象侦测是一个重要的课题，如人与车的侦测等，此一技术可运用在许多视讯安全监控系统，如智能型空间（Smart