sift算法在cv领域的重要性不言而喻,该作者的文章引用率在cv界是number1.本篇博客只是本人把sift算法知识点整理了下,以免忘记。本文比较早的一篇博文opencv源码解析之(3):特征点检查前言1 中有使用opencv自带的sift做了个简单的实验,而这次主要是利用Rob Hess的sift源码来做实验,其实现在的opencv版本中带的sift算法也是Rob Hess的,只是稍微包装了下。
首先网上有不少文章介绍了sift算法,写得都不错,比如:
http://www.cnblogs.com/cfantaisie/archive/2011/06/14/2080917.html
该博客对sift算法理论做了介绍,且有示意图辅助理解,从该文中可以了解sift算法的大概流程.
http://www.cnblogs.com/linyunzju/archive/2011/06/14/2080950.html
这篇文章对sift算法做了通俗易懂的解释.
http://blog.csdn.net/v_july_v/article/category/795430
这篇博客有教你怎样用c语言一步一步写sift算法。
http://underthehood.blog.51cto.com/2531780/658350
该文也对sift做了详细的介绍,博客的作者还对sift匹配做了讲解。
下面还是简单看下sift算法的理论,具体的内容可以参考上面的几篇文章。
一、Sift描述子形成的步骤
1、 构造高斯差分空间图像。
Sift特征点的检测时在DOG图像上进行的,DOG图像是将相邻尺度空间图像相减得到的。且金字塔的每一层都要构造一个DOG空间图像。默认参数是金字塔4层,即4个octave,每一个octave中有5张不同尺度的图片,不同octave的图片尺寸大小不同,所以每一层中就会得到4幅DOG图像。
高斯金字塔的第1层第1副原图像是将原图像放大2倍且sigma(sigma=1.6)模糊,第2幅图像是k*sigma(k等于根号2)模糊,第3幅是k*k*sigma模糊,后面类推…
高斯金字塔第2层第1幅图是选择金字塔上一层(这里是第1层)中尺度空间参数为k*k*sigma的那幅图(实际上是2倍的尺度空间)进行降采样(尺寸大小为原来的1/4倍)得到,如果k不等于根号2,那么取原图的2*sigma降采样得到。第2层第2幅图是在本层第一幅图尺度模糊系数增加k倍模糊后的图像,后面类似…
示意图如下所示:
尺度不变当然是与图片尺寸有关,即图片的尺寸大小变化,但是其检测结果不变。
2、寻找极大极小值点。
将每个像素点与其所在的那幅图像邻域的8个像素,它所在的向量尺度空间上下2幅图对应位置邻域各9个点,总共26个点进行像素值比较,如果该点是最大或者最小点,则改点就暂时列为特征点。
其邻图如下:
3、精确定位极值点
子像素级极值点:
由于上面找到的近似极值点落在像素点的位置上,实际上我们在像素点附近如果用空间曲面去拟合的话,很多情况下极值点都不是恰好在像素点上,而是在附近。所以sift算法提出的作者用泰勒展开找到了亚像素级的特征点。这种点更稳定,更具有代表性。
消除对比度低的特征点:
对求出亮度比较低的那些点直接过滤点,程序中的阈值为0.03.
消除边界上的点:
处理方法类似harrs角点,把平坦区域和直线边界上的点去掉,即对于是边界上的点但又不是直角上的点,sift算法是不把这些点作为特征点的。
4、选取特征点主方向
在特征点附近选取一个区域,该区域大小与图图像的尺度有关,尺度越大,区域越大。并对该区域统计36个bin的方向直方图,将直方图中最大bin的那个方向作为该点的主方向,另外大于最大bin80%的方向也可以同时作为主方向。这样的话,由于1个特征点有可能有多个主方向,所以一个特征点有可能有多个128维的描述子。如下图所示:
5、 构造特征点描述算子。
以特征点为中心,取领域内16*16大小的区域,并把这个区域分成4*4个大小为4*4的小区域,每个小区域内计算加权梯度直方图,该权值分为2部分,其一是该点的梯度大小,其二是改点离特征点的距离(二维高斯的关系),每个小区域直方图分为8个bin,所以一个特征点的维数=4*4*8=128维。示意图如下(该图取的领域为8*8个点,因此描述子向量的维数为32维):
6、实验部分
下面来做下试验,试验sift代码采用Rob Hess的代码,opencv目前版本中的sift源码也是采用Rob Hess的。代码可以在他的主页上下载:http://blogs.oregonstate.edu/hess/code/sift/
这里我下载的是windows版本的,并采用Qt做了个简单的界面。
环境:WindowsXP+Opencv2.4.2+Qt4.8.2+QtCreator2.5.1,QtCreator内部采用的是vc的编译器。
运行软件,单击Open Image后选择一张需要进行特征点检测的图片,我这里显示的结果如下:
单击Sift Detect按钮后,检测到的效果如下:
主要代码部分如下(附录有工程code下载链接):
SiftDetect.h:
-
#ifndef SIFTDETECT_H
-
#define SIFTDETECT_H
-
-
#include <QDialog>
-
#include <opencv2/core/core.hpp>
-
#include <opencv2/highgui/highgui.hpp>
-
#include <opencv2/imgproc/imgproc.hpp>
-
//#include <opencv/cxcore.h>
-
//#include <opencv/highgui.h>
-
//#include <opencv/imgproc.h>
-
#include <stdio.h>
-
#include <stdio.h>
-
#include "sift.h"
-
#include "imgfeatures.h"
-
#include "utils.h"
-
-
-
using namespace cv;
-
-
namespace Ui {
-
class SiftDetect;
-
}
-
-
class SiftDetect : public QDialog
-
{
-
Q_OBJECT
-
-
public:
-
explicit SiftDetect(QWidget *parent = 0);
-
~SiftDetect();
-
-
private slots:
-
-
-
void on_openButton_clicked();
-
-
void on_detectButton_clicked();
-
-
void on_closeButton_clicked();
-
-
private:
-
Ui::SiftDetect *ui;
-
-
Mat src, dst;
-
IplImage* img;
-
struct feature* features;
-
int n;
-
int display;
-
int intvls;
-
double sigma;
-
double contr_thr;
-
int curv_thr;
-
int img_dbl;
-
int descr_width;
-
int descr_hist_bins;
-
};
-
-
#endif // SIFTDETECT_H
SiftDetect.cpp:
-
#include "siftdetect.h"
-
#include "ui_siftdetect.h"
-
#include <QtGui>
-
#include <QtCore>
-
#include "sift.h"
-
#include "imgfeatures.h"
-
#include "utils.h"
-
//#include <sift.c>
-
-
SiftDetect::SiftDetect(QWidget *parent) :
-
QDialog(parent),
-
ui(new Ui::SiftDetect)
-
{
-
ui->setupUi(this);
-
-
n = 0;
-
display = 1;
-
intvls = SIFT_INTVLS;
-
sigma = SIFT_SIGMA;
-
contr_thr = SIFT_CONTR_THR;
-
curv_thr = SIFT_CURV_THR;
-
img_dbl = SIFT_IMG_DBL;
-
descr_width = SIFT_DESCR_WIDTH;
-
descr_hist_bins = SIFT_DESCR_HIST_BINS;
-
}
-
-
SiftDetect::~SiftDetect()
-
{
-
// cvReleaseImage( &img );//释放内存退出程序后竟然报错
-
delete ui;
-
}
-
-
-
-
void SiftDetect::on_openButton_clicked()
-
{
-
QString img_name = QFileDialog::getOpenFileName(this, "Open Image", "../sift_detect",
-
tr("Image Files(*.png *.jpeg *.jpg *.bmp)"));
-
// img = cvLoadImage( img_name.toAscii().data() );
-
src = imread( img_name.toAscii().data() );
-
imwrite( "../sift_detect/src.jpg", src );
-
ui->textBrowser->clear();
-
ui->textBrowser->setFixedSize( src.cols, src.rows );
-
ui->textBrowser->append( "
" );
-
-
}
-
-
void SiftDetect::on_detectButton_clicked()
-
{
-
//将Mat型的src转换成IplImage*型的img,因为这里是opencv新老版本混合编程的方法。
-
img = &src.operator IplImage();
-
n = _sift_features( img, &features, intvls, sigma, contr_thr, curv_thr, img_dbl, descr_width, descr_hist_bins );
-
if( display )
-
{
-
draw_features( img, features, n );
-
ui->textBrowser->clear();
-
//将IplImage*型的img转换成Mat型的dst,这也是opencv新老版本混合编程的一种方法。
-
dst = Mat( img );
-
imwrite( "../sift_detect/dst.jpg", dst );
-
//cvSaveImage( "../sift_detect/dst.jpg", img );
-
ui->textBrowser->append( "
" );
-
}
-
}
-
-
void SiftDetect::on_closeButton_clicked()
-
{
-
close();
-
}
二、Sift特征点匹配过程
由步骤一我们已经获得了图片的特征点向量集合。现在来看看特征点匹配,特征点匹配的一个应用就是物体的识别,比如说我有2张图片A和B,图片的内容相同,只是图片的大小尺寸不同。假设A图片尺寸比较大,且我们已经采用sift算法对图片A和B都进行了检测,获得了它们的特征点集合,现在我们的问题是需要把A和B中相应的特征点给对应连线起来。
既然是匹配,当然每个特征点向量要相似才能匹配到一起,这里采用的是欧式距离来衡量其相似度。
对B中的特征点x,去寻找A中最相似的点y,最简单的方法就是拿x与A中所有点进行相似度比较,距离最小的那个为匹配点。但是如果图片中特征点数目很多的话,这样效率会很低。所以我们需要把A中特征点向量集合用一种数据结构来描述,这种描述要有利于x在A中的搜索,即减少时间复杂度。在sift匹配中,这种数据结构采用的是kd-tree。
关于kd-tree的讲解,可以参考博文http://underthehood.blog.51cto.com/2531780/687160
里面讲得比较详细,且举了例子,很容易理解,这里就没有必要重复了。
同样,采用Rob Hess的代码做了个sift匹配的实验,开发环境与上面的一样。
打开软件后,单击Open Image按钮,依次打开需要匹配的2张图片,如下图所示:
单击Sift Detect按钮,则程序会单独对这2幅图片进行sift特征点检测,结果如下图所示:
单击Sift Match按钮,则会对这2幅图的特征点结果进行匹配,本次实验的匹配图如下所示:
实验主要部分代码(附录有工程code链接下载):
SiftMatch.h:
-
#ifndef SIFTMATCH_H
-
#define SIFTMATCH_H
-
-
#include <QDialog>
-
#include <opencv2/core/core.hpp>
-
#include <opencv2/highgui/highgui.hpp>
-
#include <opencv2/imgproc/imgproc.hpp>
-
-
using namespace cv;
-
-
namespace Ui {
-
class SiftMatch;
-
}
-
-
class SiftMatch : public QDialog
-
{
-
Q_OBJECT
-
-
public:
-
explicit SiftMatch(QWidget *parent = 0);
-
~SiftMatch();
-
-
private slots:
-
void on_openButton_clicked();
-
-
void on_detectButton_clicked();
-
-
void on_matchButton_clicked();
-
-
void on_closeButton_clicked();
-
-
private:
-
Ui::SiftMatch *ui;
-
Mat src1, src2, src1_c, src2_c, dst;
-
IplImage *img1, *img2, *img3, *stacked;
-
Point pt1, pt2;
-
double d0, d1;
-
struct feature *feat1, *feat2, *feat;
-
struct feature **nbrs;
-
struct kd_node *kd_root;
-
int open_image_number;
-
int n1, n2, k, i, m;
-
};
-
-
#endif // SIFTMATCH_H
SiftMatch.cpp:
-
#include "siftmatch.h"
-
#include "ui_siftmatch.h"
-
-
#include <QtCore>
-
#include <QtGui>
-
#include "imgfeatures.h"
-
#include "kdtree.h"
-
#include "minpq.h"
-
#include "sift.h"
-
#include "utils.h"
-
#include "xform.h"
-
-
/* the maximum number of keypoint NN candidates to check during BBF search */
-
#define KDTREE_BBF_MAX_NN_CHKS 200
-
-
/* threshold on squared ratio of distances between NN and 2nd NN */
-
#define NN_SQ_DIST_RATIO_THR 0.49
-
-
SiftMatch::SiftMatch(QWidget *parent) :
-
QDialog(parent),
-
ui(new Ui::SiftMatch)
-
{
-
open_image_number = 0;
-
m = 0;
-
-
ui->setupUi(this);
-
}
-
-
SiftMatch::~SiftMatch()
-
{
-
delete ui;
-
}
-
-
void SiftMatch::on_openButton_clicked()
-
{
-
QString img_name = QFileDialog::getOpenFileName(this, "Open Image", "../sift_detect",
-
tr("Image Files(*.png *.jpeg *.jpg *.bmp)"));
-
open_image_number++;
-
//打开第1张图片
-
if( 1 == open_image_number )
-
{
-
src1 = imread( img_name.toAscii().data() );
-
img1 = cvLoadImage( img_name.toAscii().data() );
-
//转换成IplImage*类型,但是这样转换过的后面使用起来感觉还是不特别顺利,说明并不是完全100%兼容了。
-
// img1 = &src1.operator IplImage();
-
imwrite( "../sift_match/src1.jpg", src1 );
-
ui->textBrowser->setFixedSize( src1.cols, src1.rows );
-
ui->textBrowser->append( "
" );
-
}
-
//打开第2张图片
-
else if( 2 == open_image_number )
-
{
-
src2 = imread( img_name.toAscii().data() );
-
img2 = cvLoadImage( img_name.toAscii().data() );
-
// img2 = &src2.operator IplImage();
-
imwrite( "../sift_match/src2.jpg", src2 );
-
ui->textBrowser->setFixedSize( src2.cols+src1.cols, src2.rows+src1.rows );
-
ui->textBrowser->append( "
" );
-
}
-
else
-
open_image_number = 0;
-
-
}
-
-
void SiftMatch::on_detectButton_clicked()
-
{
-
//将2幅图片合成1幅图片
-
//img1 = cvLoadImage();
-
stacked = stack_imgs( img1, img2 );
-
ui->textBrowser->clear();
-
-
//显示第1幅图片上的特征点
-
n1 = sift_features( img1, &feat1 );
-
draw_features( img1, feat1, n1 );
-
src1_c = Mat(img1);
-
imwrite("../sift_match/src1_c.jpg", src1_c);
-
ui->textBrowser->append("
");
-
-
//显示第2幅图片上的特征点
-
n2 = sift_features( img2, &feat2 );
-
draw_features( img2, feat2, n2 );
-
src2_c = Mat(img2);
-
imwrite("../sift_match/src2_c.jpg", src2_c);
-
ui->textBrowser->append("
");
-
}
-
-
void SiftMatch::on_matchButton_clicked()
-
{
-
kd_root = kdtree_build( feat2, n2 );
-
for( i = 0; i < n1; i++ )
-
{
-
feat = feat1+i;
-
k = kdtree_bbf_knn( kd_root, feat, 2, &nbrs, KDTREE_BBF_MAX_NN_CHKS );
-
if( k == 2 )
-
{
-
d0 = descr_dist_sq( feat, nbrs[0] );
-
d1 = descr_dist_sq( feat, nbrs[1] );
-
if( d0 < d1 * NN_SQ_DIST_RATIO_THR )
-
{
-
pt1 = Point( cvRound( feat->x ), cvRound( feat->y ) );
-
pt2 = Point( 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++;
-
feat1[i].fwd_match = nbrs[0];
-
}
-
}
-
free( nbrs );
-
}
-
dst = Mat( stacked );
-
imwrite( "../sift_match/dst.jpg", dst );
-
ui->textBrowser->clear();
-
ui->textBrowser->setFixedSize( dst.cols, dst.rows );
-
ui->textBrowser->append("
");
-
-
}
-
-
void SiftMatch::on_closeButton_clicked()
-
{
-
close();
-
}
总结:
通过整理下sift算法知识点,对sift算法有了更全面的认识,另外感谢Rob Hess开源了sift算法的代码,感觉写好这个算法确实不同意的。(另外,本文博客中引用了上面提到的博客中的图片,在此声明一下。)
附录一:
Rob Hess sift的c代码在c++中的使用。
由于Rob Hess的代码是基于c的,如果在其它关于界面开发的c++程序中,比如Qt,MFC等。我这里是Qt,连接时会报如下错误:
siftdetect.obj:-1: error: LNK2019: 无法解析的外部符号 "int __cdecl _sift_features(struct _IplImage *,struct feature * *,int,double,double,int,int,int,int)" (?_sift_features@@YAHPAU_IplImage@@PAPAUfeature@@HNNHHHH@Z),该符号在函数 "private: void __thiscall SiftDetect::on_detectButton_clicked(void)" (?on_detectButton_clicked@SiftDetect@@AAEXXZ) 中被引用
网上也有不少网友碰到过类似的情况,比如和 但是他们都没有给出解决办法。
因此我们要找本质的原因,原因就是c语法和c++语法毕竟不同,所以难免有些兼容性问题。看错误提示我们知道是在函数_sift_features时报的错,该函数在Rob Hess的头文件中是被定义的extern类型。而在c的编译器中,extern的函数文件名编译后会自动在前面加一杆,”_”;而c++语法中会有函数重载的现象,因此它不是像c那样直接在前面加”_”,否则会冲突,因此c++编译器会在其函数名后面加入一些像乱码的东西(反正链接时是机器去寻找,只要能区分即可)。
具体的内容可以参考博客:http://blog.csdn.net/wujian53/article/details/706975 这里面讲得比较明白,谢谢这位博主。
本次实验的解决方法是在Rob Hess的sift.h等几个头文件文件开始处加入语句:
#ifdef __cplusplus extern "C" { #endif
该文件的结处加入语句:
#ifdef __cplusplus
} #endif
这样的话编译器在编译该文件时会知道这是C语法,所以其中间文件命名规则会相应改变,问题也就相应的解决了。
另外,如果出现错误提示:
utils.obj:-1: error: LNK2019: 无法解析的外部符号 _va_end,该符号在函数 _fatal_error 中被引用。
则在utils.c代码中找到va_start( ap, format );和va_end( ap );并将其注释起来即可。
附录二:
。