sift算法
特征点检测学习_1(sift算法)
与ORB相比，比较费时的是（非原文）：
1、角点的获取，一为改进版fast角点，一为通过不同尺度下DOG（difference of Gaussian）中最亮或最暗，然后在曲线拟合获取附近极大值极小值作为角点
2 特征点方向 ORB直接使用质心与几何中心之间夹角，而SIFT利用关键点邻域像素的梯度方向分布特性（直方图中的峰值是主方向，其他的达到最大值80%的方向作为辅助方向）
3 描述子 ORB是二进制描述子（邻域亮为1，暗为0），而sift描述子是其按特征方向进行旋转后再进行计算的梯度方向。
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.****.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( "<img src=../sift_detect/src.jpg>" );
}
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( "<img src=../sift_detect/dst.jpg>" );
}
}
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
里面讲得比较详细，且举了例子，很容易理解，这里就没有必要重复了。