`
javababy1
  • 浏览: 1161994 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

经典算法研究系列:九、图像特征提取与匹配之SIFT算法

阅读更多

经典算法研究系列:九、SIFT算法研究

作者:July、二零一一年二月十五日。

推荐阅读:
David G. Lowe, "Distinctive image features from scale-invariant keypoints,"
International Journal of Computer Vision, 60, 2 (2004), pp. 91-110
---------------------------------------------

尺度不变特征转换(Scale-invariant feature transform SIFT)是一种电脑视觉的算法用来侦测与描述影像中的局部性特征,它在空间尺度中寻找极值点,并提取出其位置、尺度、旋转不变量,此算法由 David Lowe 在1999年所发表,2004年完善总结。

Sift算法就是用不同尺度(标准差)的高斯函数对图像进行平滑,然后比较平滑后图像的差别,
差别大的像素就是特征明显的点。

一、Sift算法的步骤
Sift(Scale Invariant Feature Transform)是一个很好的图像匹配算法,
同时能处理亮度、平移、旋转、尺度的变化,利用特征点来提取特征描述符,最后在特征描述符之间寻找

匹配。
该算法主要包括5个步骤进行匹配:
1、构建尺度空间,检测极值点,获得尺度不变性;

2、特征点过滤并进行精确定位,剔除不稳定的特征点;

3、在特征点处提取特征描述符,为特征点分配方向值;

4、生成特征描述子,利用特征描述符寻找匹配点;
以特征点为中心取16*16的邻域作为采样窗口,
将采样点与特征点的相对方向通过高斯加权后归入包含8个bin的方向直方图,
最后获得4*4*8的128维特征描述子。
示意图如下:

5、计算变换参数。
当两幅图像的Sift特征向量生成以后,下一步就可以采用关键点特征向量的欧式距离来作为两幅图像中

关键点的相似性判定度量。
取图1的某个关键点,通过遍历找到图像2中的距离最近的两个关键点。
在这两个关键点中,如果次近距离除以最近距离小于某个阙值,则判定为一对匹配点。

最后,看下Sift 算法效果图:
下图左边部分Sift算法匹配结果,右边部分是其它算法匹配结果:

二、Sift算法的描述
在上述的Sift算法步骤一中,提到了尺度空间,那么什么是尺度和尺度空间呢?
尺度就是受delta这个参数控制的表示。
而不同的L(x,y,delta)就构成了尺度空间,实际上,具体计算的时候,即使连续的高斯函数,都要被离

散为(一般为奇数大小)(2*k+1) *(2*k+1)矩阵,来和数字图像进行卷积运算。

David Lowe关于Sfit算法,2004年发表在Int. Journal of Computer Vision的经典论文中,
对尺度空间(scal space)是这样定义的 :
It has been shown by Koenderink (1984) and Lindeberg (1994) that under a variety of
reasonable assumptions the only possible scale-space kernel is the Gaussian function.

Therefore,the scale space of an image is defined as a function, L(x; y; delta) that is

produced from the convolution of a variable-scale Gaussian, G(x; y; delta), with an input

image, I(x; y):

因此 ,一个图像的尺度空间,L(x,y,delta) ,
定义为原始图像I (x,y)与一个可变尺度的2维高斯函数G(x,y,delta) 卷积运算。

即,原始影像I(x,y)在不同的尺度e下,与高斯滤波器G(x,y,e)进行卷积,得到L(x,y,e),如下:
L(x,y,e) = G(x,y,e)*I(x,y)

其中G(x,y,e)是尺度可变高斯函数,
G(x,y,e) = [1/2*pi*e2] * exp[ -(x2 + y2)/2e2]
(x,y)是空间坐标, e是尺度坐标。


为了更有效的在尺度空间检测到稳定的关键点,提出了高斯差分尺度空间(DOG scale-space)。
利用不同尺度的高斯差分核与原始图像I(x,y) ,卷积生成。

D(x,y,e) = ((G(x,y,ke) - G(x,y,e)) * I(x,y)
= L(x,y,ke) - L(x,y,e)
DOG算子计算简单,是尺度归一化的LoG算子的近似。

Gaussian卷积是有尺寸大小的,使用同一尺寸的滤波器对两幅包含有不同尺寸的同一物体的图像求局部最值将有可能出现一方求得最值而另一方却没有的情况,但是容易知道假如物体的尺寸都一致的话它们的局部最值将会相同。

SIFT的精妙之处在于采用图像金字塔的方法解决这一问题,我们可以把两幅图像想象成是连续的,分别以它们作为底面作四棱锥,就像金字塔,那么每一个 截面与原图像相似,那么两个金字塔中必然会有包含大小一致的物体的无穷个截面,但应用只能是离散的,所以我们只能构造有限层,层数越多当然越好,但处理时 间会相应增加,层数太少不行,因为向下采样的截面中可能找不到尺寸大小一致的两个物体的图像。

有了图像金字塔就可以对每一层求出局部最值,但是这样的稳定 点数目将会十分可观,所以需要使用某种方法抑制去除一部分点,但又使得同一尺度下的稳定点得以保存
图像金字塔的构建:图像金字塔共O组,每组有S层,下一组的图像由上一组图像降采样得到。
如下图:

三、Sift算法的实现
作为一种匹配能力较强的局部描述算子,SIFT算法的实现相当复杂,
不过David Lowe到底也还是用c++实现了它,下面,阐述下其中的俩个关键函数。

关键函数一:
int sift_features( IplImage* img, struct feature** feat )
这个函数就是用来提取图像中的特征向量。
参数img为一个指向IplImage数据类型的指针,用来表示需要进行特征提取的图像。
IplImage是opencv库定义的图像基本类型(关于opencv是一个著名的图像处理类库,详细的介绍可以参见

http://www.opencv.org.cn
)。
参数feat 是一个数组指针,用来存储图像的特征向量。
函数调用成功将返回特征向量的数目,否则返回-1.

函数,完整表述如下:
int sift_features( IplImage* img, struct feature** feat )
{
return _sift_features( img, feat, SIFT_INTVLS, SIFT_SIGMA, SIFT_CONTR_THR,
SIFT_CURV_THR, SIFT_IMG_DBL, SIFT_DESCR_WIDTH,
SIFT_DESCR_HIST_BINS );
}


关键函数二:
int _sift_features( IplImage* img, struct feature** feat, int intvls,double sigma, double

contr_thr, int curv_thr, int img_dbl, int descr_width, int descr_hist_bins )

稍微介绍下此函数的几个参数:
intvls: 每个尺度空间的采样间隔数,默认值为3.
sigma: 高斯平滑的数量,默认值1.6.
contr_thr:判定特征点是否稳定,取值(0,1),默认为0.04,这个值越大,被剔除的特征点就越多。
curv_thr:判定特征点是否边缘点,默认为6.
img_dbl:在建立尺度空间前如果图像被放大了1倍则取值为1,否则为0.
descr_width:计算特征描述符时邻域子块的宽度,默认为4.
descr_hist_bins:计算特征描述符时将特征点邻域进行投影的方向数,默认为8,分别是0,45,90,135

,180,215,270,315共8个方向。

以下是此函数的完整表述:
int _sift_features( IplImage* img, struct feature** feat, int intvls,
double sigma, double contr_thr, int curv_thr,
int img_dbl, int descr_width, int descr_hist_bins )
{
IplImage* init_img;
IplImage*** gauss_pyr, *** dog_pyr;
CvMemStorage* storage;
CvSeq* features;
int octvs, i, n = 0;

/* check arguments */
if( ! img )
fatal_error( "NULL pointer error, %s, line %d", __FILE__, __LINE__ );

if( ! feat )
fatal_error( "NULL pointer error, %s, line %d", __FILE__, __LINE__ );

/* build scale space pyramid; smallest dimension of top level is ~4 pixels */
init_img = create_init_img( img, img_dbl, sigma );
octvs = log( MIN( init_img->width, init_img->height ) ) / log(2) - 2;
gauss_pyr = build_gauss_pyr( init_img, octvs, intvls, sigma );
dog_pyr = build_dog_pyr( gauss_pyr, octvs, intvls );

storage = cvCreateMemStorage( 0 );
features = scale_space_extrema( dog_pyr, octvs, intvls, contr_thr,
curv_thr, storage );
calc_feature_scales( features, sigma, intvls );
if( img_dbl )
adjust_for_img_dbl( features );
calc_feature_oris( features, gauss_pyr );
compute_descriptors( features, gauss_pyr, descr_width, descr_hist_bins );

/* sort features by decreasing scale and move from CvSeq to array */
cvSeqSort( features, (CvCmpFunc)feature_cmp, NULL );
n = features->total;
*feat = calloc( n, sizeof(struct feature) );
*feat = cvCvtSeqToArray( features, *feat, CV_WHOLE_SEQ );
for( i = 0; i < n; i++ )
{
free( (*feat)[i].feature_data );
(*feat)[i].feature_data = NULL;
}

cvReleaseMemStorage( &storage );
cvReleaseImage( &init_img );
release_pyr( &gauss_pyr, octvs, intvls + 3 );
release_pyr( &dog_pyr, octvs, intvls + 2 );
return n;
}

这个函数是上述函数一的重载,作用是一样的,实际上函数一只不过是使用默认参数调用了函数二,
核心的代码都是在函数二中实现的。


sift创始人David Lowe的完整代码,包括他的论文,请到此处下载:
http://www.cs.ubc.ca/~lowe/keypoints
日后,本BLOG内,会具体剖析下上述David Lowe的Sift算法代码。

Rob Hess维护的sift 库:
http://blogs.oregonstate.edu/hess/code/sift/
还可,参考这里:
sift图像特征提取与匹配算法代码(友人,onezeros博客):
http://blog.csdn.net/onezeros/archive/2011/01/05/6117704.aspx

完。

本人July对本博客所有任何文章、内容和资料享有版权。
转载务必注明作者本人及出处,并通知本人。July、二零一一年二月十五日。

分享到:
评论

相关推荐

    sift特征源代码 人脸识别 图像检索 图像匹配 图像拼接

    本代码是sift特征提取代码,sift特征可以用于人脸识别,图像检索 图像匹配 图像拼接,sift特征具有旋转不变形,尺度不变形,光照不变形等,此算法已广泛应用于人脸识别 图像检索 图像匹配 图像拼接的研究。...

    用于图像拼接的特征提取算法研究

    用于图像拼接的特征提取算法研究 摘要:图像拼接是计算机视觉领域的一个重要分支,也是现在的研究热点。研究了用于图像拼接的特征提取算法,该算法 提取的特征能对旋转、尺度缩放、仿射变换、视角变化、光照变化、...

    论文研究-基于分块和仿射不变性的SIFT图像匹配算法.pdf

    首先利用传统SIFT算法提取图像中的特征点;然后采用基于距离相对性的分块匹配算法进行特征匹配得到初始匹配对;由于初始匹配对中存在误匹配,运用基于仿射不变性的误匹配对剔除算法来剔除误匹配对;最后,在不同图像...

    Sift图像局部特征提取方法及应用研究

    首先对特征点提取的原理进行了详细研究,针对SIFT算法原理分模块进行了研究;然后本文对SIFT特征点在图像匹配和图像拼接领域的应用进行了讨论;最后,为了验证本文算法的有效性和优越性,本文进行了仿真实验实验。...

    论文研究-基于改进SIFT特征和图转换匹配的图像匹配算法.pdf

    针对SIFT特征在纹理丰富的图像中提取较多的伪点和不稳定的点而影响图像匹配的问题, 提出了一种基于Harris阈值准则的局部不变特征图像匹配算法。该算法在提取SIFT不变特征的基础上, 利用Harris阈值准则对所提取到的...

    基于SIFT算法的图像特征点提取与匹配.rar_RANSAC_random_sift+ransac_图像拼接_梯度提升树

    文章深入研究了 SIFT 特征点提取的原理及过程,以基于 K-D 树结构的近邻算 法对呈线性变换的两幅图像在不同视角和噪声干扰情况下进行了特征点的粗匹 配,并通过随机抽样一致性算法(Random Sample Consensus)进行特征...

    研究论文-基于SIFT的新特征提取匹配算法.pdf

    针对传统的图像匹配算法特征点不稳定和匹配时间慢的问题,提出了一种改进的尺度不变特征变换...实验结果表明:相比于传统的SIFT算法和SURF算法,研究所提出的方法能够有效地提高特征点匹配精度,减少图像匹配时间。

    sift特征匹配算法

    图像特征匹配已成为计算机视觉和数字图像处理等领域的研究热点,其首要 任务是从待匹配的图像中提取含有图像特征的特征点并进行描述,通过建立原图 像和待匹配图像的特征点集之间的点点对应关系,计算对应点之间的...

    论文研究-基于改进SIFT特征的双目图像匹配算法.pdf

    针对SIFT(尺度不变特征变换)算法无法准确定位物体形状特征的问题,提出了一种结合了Harris角点和SIFT...在降低SIFT算法的时间复杂度的同时提高了算法提取特征点的形状意义,在双目图像匹配实验中取得了较好的结果。

    基于角点的图像特征提取与匹配算法研究

    这篇论文主要是对FAST和BRISK做了改进 最后还对KAZE算法与sift等进行比较和评估

    论文研究-基于SIFT特征的图像匹配算法 .pdf

    基于SIFT特征的图像匹配算法,葛梦瑶,别红霞,尺度不变特征变换(Scale Invariant Feature Transform, SIFT)是图像匹配领域的研究热点,该算法在尺度空间寻找极值点,提取位置、尺度、旋转

    基于压缩感知和小波变换的快速SIFT图像拼接算法研究(中文翻译版)

    结合SIFT 算法提取图像特征点。最后,将自适应阈值的序列相似性检测算法 (SSDA)用于图像匹配进行快速搜索,找出最优的拼接线和全景图像。实验结果 表明,该方法实现了图像的快速匹配,有效地克服了图像特征提取的...

    特征算法研究(图像拼接)

    用于图像拼接的特征算法研究 :图像拼接是计算机视觉领域的一个重要分支,也是现在的研究热点。研究了用于图像拼接的特征提取算法,该算法 提取的特征能对旋转、尺度缩放、仿射变换、视角变化、光照变化、噪声等图像...

    论文研究-基于SIFT特征点匹配的水印图像几何校正算法.pdf

    为了有效实现水印图像的水印检测与水印嵌入之间的同步,提出一种应用SIFT(scale invariant feature transform)特征点匹配估计水印图像几何变换参数的校正算法。用两个稳定而又相距最远的图像SIFT特征点的变化估计...

    基于压缩感知和小波变换的快速SIFT 图像拼接算法研究

    结合SIFT 算法提取图像特征点。最后,将自适应阈值的序列相似性检测算法 (SSDA)用于图像匹配进行快速搜索,找出最优的拼接线和全景图像。实验结果 表明,该方法实现了图像的快速匹配,有效地克服了图像特征提取的...

    论文研究-POKD-tree:一种有效的SIFT图像特征点匹配方法.pdf

    首先,利用SIFT算法提取图像的特征点,以图像特征点集在X和Y方向中跨度最大的方向为分区直线的方向,计算图像特征点集的质心,用通过质心的分区直线来进行图像分区;采用欧式距离对图像进行特征点匹配,首先进行对应...

    十五个经典算法研究与总结、目录+索引(定稿版)

    九、图像特征提取与匹配之SIFT算法 (SIFT算法系列五篇文章) 九(续)、sift算法的编译与实现 九(再续)、教你一步一步用c语言实现sift算法、上 九(再续)、教你一步一步用c语言实现sift算法、下 九(三续):...

    基于相对定向的SIFT误匹配点剔除的算法研究

    基于相对定向的SIFT误匹配点剔除的算法研究,张宪柱,孙庆华,近几年来,基于SIFT算法的图像匹配成为国内研究的热点。SIFT算法在影像特征点提取方面具有独特的优势,但在匹配方面还存在一定得缺�

    研究论文-基于改进的FREAK算法的图像特征点匹配.pdf

    针对采集图像时存在尺度、光线强度以及图像...改进算法经实验与传统SIFT、SURF、以及FREAK算法比较分析后得知,在图像特征点匹配准确度上有一定的提高,并且对图像的尺度差异、光照差异以及旋转差异具有良好的鲁棒性。

Global site tag (gtag.js) - Google Analytics