- 浏览: 282716 次
- 性别:
- 来自: 济南
文章分类
最新评论
《SIFT原理与源码分析》系列文章索引:http://blog.csdn.net/xiaowei_cqu/article/details/8069548
由前一步《DoG尺度空间构造》,我们得到了DoG高斯差分金字塔:
如上图的金字塔,高斯尺度空间金字塔中每组有五层不同尺度图像,相邻两层相减得到四层DoG结果。关键点搜索就在这四层DoG图像上寻找局部极值点。
DoG局部极值点
寻找DoG极值点时,每一个像素点和它所有的相邻点比较,当其大于(或小于)它的图像域和尺度域的所有相邻点时,即为极值点。如下图所示,比较的范围是个3×3的立方体:中间的检测点和它同尺度的8个相邻点,以及和上下相邻尺度对应的9×2个点——共26个点比较,以确保在尺度空间和二维图像空间都检测到极值点。
在一组中,搜索从每组的第二层开始,以第二层为当前层,第一层和第三层分别作为立方体的的上下层;搜索完成后再以第三层为当前层做同样的搜索。所以每层的点搜索两次。通常我们将组Octaves索引以-1开始,则在比较时牺牲了-1组的第0层和第N组的最高层
高斯金字塔,DoG图像及极值计算的相互关系如上图所示。
关键点精确定位
以上极值点的搜索是在离散空间进行搜索的,由下图可以看到,在离散空间找到的极值点不一定是真正意义上的极值点。可以通过对尺度空间DoG函数进行曲线拟合寻找极值点来减小这种误差。
利用DoG函数在尺度空间的Taylor展开式:
则极值点为:
程序中还除去了极值小于0.04的点。如下所示:
// Detects features at extrema in DoG scale space. Bad features are discarded // based on contrast and ratio of principal curvatures. // 在DoG尺度空间寻特征点(极值点) void SIFT::findScaleSpaceExtrema( const vector<Mat>& gauss_pyr, const vector<Mat>& dog_pyr, vector<KeyPoint>& keypoints ) const { int nOctaves = (int)gauss_pyr.size()/(nOctaveLayers + 3); // The contrast threshold used to filter out weak features in semi-uniform // (low-contrast) regions. The larger the threshold, the less features are produced by the detector. // 过滤掉弱特征的阈值 contrastThreshold默认为0.04 int threshold = cvFloor(0.5 * contrastThreshold / nOctaveLayers * 255 * SIFT_FIXPT_SCALE); const int n = SIFT_ORI_HIST_BINS; //36 float hist[n]; KeyPoint kpt; keypoints.clear(); for( int o = 0; o < nOctaves; o++ ) for( int i = 1; i <= nOctaveLayers; i++ ) { int idx = o*(nOctaveLayers+2)+i; const Mat& img = dog_pyr[idx]; const Mat& prev = dog_pyr[idx-1]; const Mat& next = dog_pyr[idx+1]; int step = (int)img.step1(); int rows = img.rows, cols = img.cols; for( int r = SIFT_IMG_BORDER; r < rows-SIFT_IMG_BORDER; r++) { const short* currptr = img.ptr<short>(r); const short* prevptr = prev.ptr<short>(r); const short* nextptr = next.ptr<short>(r); for( int c = SIFT_IMG_BORDER; c < cols-SIFT_IMG_BORDER; c++) { int val = currptr[c]; // find local extrema with pixel accuracy // 寻找局部极值点,DoG中每个点与其所在的立方体周围的26个点比较 // if (val比所有都大 或者 val比所有都小) if( std::abs(val) > threshold && ((val > 0 && val >= currptr[c-1] && val >= currptr[c+1] && val >= currptr[c-step-1] && val >= currptr[c-step] && val >= currptr[c-step+1] && val >= currptr[c+step-1] && val >= currptr[c+step] && val >= currptr[c+step+1] && val >= nextptr[c] && val >= nextptr[c-1] && val >= nextptr[c+1] && val >= nextptr[c-step-1] && val >= nextptr[c-step] && val >= nextptr[c-step+1] && val >= nextptr[c+step-1] && val >= nextptr[c+step] && val >= nextptr[c+step+1] && val >= prevptr[c] && val >= prevptr[c-1] && val >= prevptr[c+1] && val >= prevptr[c-step-1] && val >= prevptr[c-step] && val >= prevptr[c-step+1] && val >= prevptr[c+step-1] && val >= prevptr[c+step] && val >= prevptr[c+step+1]) || (val < 0 && val <= currptr[c-1] && val <= currptr[c+1] && val <= currptr[c-step-1] && val <= currptr[c-step] && val <= currptr[c-step+1] && val <= currptr[c+step-1] && val <= currptr[c+step] && val <= currptr[c+step+1] && val <= nextptr[c] && val <= nextptr[c-1] && val <= nextptr[c+1] && val <= nextptr[c-step-1] && val <= nextptr[c-step] && val <= nextptr[c-step+1] && val <= nextptr[c+step-1] && val <= nextptr[c+step] && val <= nextptr[c+step+1] && val <= prevptr[c] && val <= prevptr[c-1] && val <= prevptr[c+1] && val <= prevptr[c-step-1] && val <= prevptr[c-step] && val <= prevptr[c-step+1] && val <= prevptr[c+step-1] && val <= prevptr[c+step] && val <= prevptr[c+step+1]))) { int r1 = r, c1 = c, layer = i; // 关键点精确定位 if( !adjustLocalExtrema(dog_pyr, kpt, o, layer, r1, c1, nOctaveLayers, (float)contrastThreshold, (float)edgeThreshold, (float)sigma) ) continue; float scl_octv = kpt.size*0.5f/(1 << o); // 计算梯度直方图 float omax = calcOrientationHist( gauss_pyr[o*(nOctaveLayers+3) + layer], Point(c1, r1), cvRound(SIFT_ORI_RADIUS * scl_octv), SIFT_ORI_SIG_FCTR * scl_octv, hist, n); float mag_thr = (float)(omax * SIFT_ORI_PEAK_RATIO); for( int j = 0; j < n; j++ ) { int l = j > 0 ? j - 1 : n - 1; int r2 = j < n-1 ? j + 1 : 0; if( hist[j] > hist[l] && hist[j] > hist[r2] && hist[j] >= mag_thr ) { float bin = j + 0.5f * (hist[l]-hist[r2]) / (hist[l] - 2*hist[j] + hist[r2]); bin = bin < 0 ? n + bin : bin >= n ? bin - n : bin; kpt.angle = (float)((360.f/n) * bin); keypoints.push_back(kpt); } } } } } } }
删除边缘效应
除了DoG响应较低的点,还有一些响应较强的点也不是稳定的特征点。DoG对图像中的边缘有较强的响应值,所以落在图像边缘的点也不是稳定的特征点。
一个平坦的DoG响应峰值在横跨边缘的地方有较大的主曲率,而在垂直边缘的地方有较小的主曲率。主曲率可以通过2×2的Hessian矩阵H求出:
D值可以通过求临近点差分得到。H的特征值与D的主曲率成正比,具体可参见Harris角点检测算法。
为了避免求具体的值,我们可以通过H将特征值的比例表示出来。令为最大特征值,为最小特征值,那么:
Tr(H)表示矩阵H的迹,Det(H)表示H的行列式。
令表示最大特征值与最小特征值的比值,则有:
上式与两个特征值的比例有关。随着主曲率比值的增加,也会增加。我们只需要去掉比率大于一定值的特征点。Lowe论文中去掉r=10的点。
// Interpolates a scale-space extremum's location and scale to subpixel // accuracy to form an image feature. Rejects features with low contrast. // Based on Section 4 of Lowe's paper. // 特征点精确定位 static bool adjustLocalExtrema( const vector<Mat>& dog_pyr, KeyPoint& kpt, int octv, int& layer, int& r, int& c, int nOctaveLayers, float contrastThreshold, float edgeThreshold, float sigma ) { const float img_scale = 1.f/(255*SIFT_FIXPT_SCALE); const float deriv_scale = img_scale*0.5f; const float second_deriv_scale = img_scale; const float cross_deriv_scale = img_scale*0.25f; float xi=0, xr=0, xc=0, contr; int i = 0; //三维子像元插值 for( ; i < SIFT_MAX_INTERP_STEPS; i++ ) { int idx = octv*(nOctaveLayers+2) + layer; const Mat& img = dog_pyr[idx]; const Mat& prev = dog_pyr[idx-1]; const Mat& next = dog_pyr[idx+1]; Vec3f dD((img.at<short>(r, c+1) - img.at<short>(r, c-1))*deriv_scale, (img.at<short>(r+1, c) - img.at<short>(r-1, c))*deriv_scale, (next.at<short>(r, c) - prev.at<short>(r, c))*deriv_scale); float v2 = (float)img.at<short>(r, c)*2; float dxx = (img.at<short>(r, c+1) + img.at<short>(r, c-1) - v2)*second_deriv_scale; float dyy = (img.at<short>(r+1, c) + img.at<short>(r-1, c) - v2)*second_deriv_scale; float dss = (next.at<short>(r, c) + prev.at<short>(r, c) - v2)*second_deriv_scale; float dxy = (img.at<short>(r+1, c+1) - img.at<short>(r+1, c-1) - img.at<short>(r-1, c+1) + img.at<short>(r-1, c-1))*cross_deriv_scale; float dxs = (next.at<short>(r, c+1) - next.at<short>(r, c-1) - prev.at<short>(r, c+1) + prev.at<short>(r, c-1))*cross_deriv_scale; float dys = (next.at<short>(r+1, c) - next.at<short>(r-1, c) - prev.at<short>(r+1, c) + prev.at<short>(r-1, c))*cross_deriv_scale; Matx33f H(dxx, dxy, dxs, dxy, dyy, dys, dxs, dys, dss); Vec3f X = H.solve(dD, DECOMP_LU); xi = -X[2]; xr = -X[1]; xc = -X[0]; if( std::abs( xi ) < 0.5f && std::abs( xr ) < 0.5f && std::abs( xc ) < 0.5f ) break; //将找到的极值点对应成像素(整数) c += cvRound( xc ); r += cvRound( xr ); layer += cvRound( xi ); if( layer < 1 || layer > nOctaveLayers || c < SIFT_IMG_BORDER || c >= img.cols - SIFT_IMG_BORDER || r < SIFT_IMG_BORDER || r >= img.rows - SIFT_IMG_BORDER ) return false; } /* ensure convergence of interpolation */ // SIFT_MAX_INTERP_STEPS:插值最大步数,避免插值不收敛,程序中默认为5 if( i >= SIFT_MAX_INTERP_STEPS ) return false; { int idx = octv*(nOctaveLayers+2) + layer; const Mat& img = dog_pyr[idx]; const Mat& prev = dog_pyr[idx-1]; const Mat& next = dog_pyr[idx+1]; Matx31f dD((img.at<short>(r, c+1) - img.at<short>(r, c-1))*deriv_scale, (img.at<short>(r+1, c) - img.at<short>(r-1, c))*deriv_scale, (next.at<short>(r, c) - prev.at<short>(r, c))*deriv_scale); float t = dD.dot(Matx31f(xc, xr, xi)); contr = img.at<short>(r, c)*img_scale + t * 0.5f; if( std::abs( contr ) * nOctaveLayers < contrastThreshold ) return false; /* principal curvatures are computed using the trace and det of Hessian */ //利用Hessian矩阵的迹和行列式计算主曲率的比值 float v2 = img.at<short>(r, c)*2.f; float dxx = (img.at<short>(r, c+1) + img.at<short>(r, c-1) - v2)*second_deriv_scale; float dyy = (img.at<short>(r+1, c) + img.at<short>(r-1, c) - v2)*second_deriv_scale; float dxy = (img.at<short>(r+1, c+1) - img.at<short>(r+1, c-1) - img.at<short>(r-1, c+1) + img.at<short>(r-1, c-1)) * cross_deriv_scale; float tr = dxx + dyy; float det = dxx * dyy - dxy * dxy; //这里edgeThreshold可以在调用SIFT()时输入; //其实代码中定义了 static const float SIFT_CURV_THR = 10.f 可以直接使用 if( det <= 0 || tr*tr*edgeThreshold >= (edgeThreshold + 1)*(edgeThreshold + 1)*det ) return false; } kpt.pt.x = (c + xc) * (1 << octv); kpt.pt.y = (r + xr) * (1 << octv); kpt.octave = octv + (layer << 8) + (cvRound((xi + 0.5)*255) << 16); kpt.size = sigma*powf(2.f, (layer + xi) / nOctaveLayers)*(1 << octv)*2; return true; }
至此,SIFT第二步就完成了。参见《SIFT原理与源码分析》
(转载请注明作者和出处:http://blog.csdn.net/xiaowei_cqu未经允许请勿用于商业用途)
发表评论
-
unity基础开发----物体位移和旋转实用代码
2013-11-21 22:46 1271using UnityEngine; using Syst ... -
Android中View绘制优化之一---- 优化布局层次
2012-09-04 23:00 1083... -
Android中View绘制优化二一---- 使用<include />标签复用布局文件
2012-09-08 13:54 1067... -
Android中View绘制优化之三---- 优化View
2012-09-13 21:00 1090... -
兰林任务管理应用程序雏形版以及概要说明
2012-09-15 21:54 887... -
Android中measure过程、WRAP_CONTENT详解以及xml布局文件解析流程浅析(上)
2012-10-10 18:14 1180... -
Android中measure过程、WRAP_CONTENT详解以及xml布局文件解析流程浅析(下)
2012-10-17 20:05 877... -
Android中文件选择器的实现
2012-11-30 08:59 1183... -
【编译原理】使用Lex将C/C++文件输出为HTML文件
2012-07-20 09:37 108508年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大 ... -
【编译原理】正则表达式
2012-07-21 21:49 232508年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大 ... -
【OpenCV】访问Mat图像中每个像素的值
2012-07-22 07:10 1183今天百度搜资料还搜到了自己的。。。《访问图像中每个像素的值 ... -
【编译原理】用Yacc做语法分析
2012-07-23 05:47 180308年9月入学,12年7月毕 ... -
【UML】UML几种图的绘制
2012-07-24 09:49 99408年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大 ... -
【OpenCV】邻域滤波:方框、高斯、中值、双边滤波
2012-07-26 10:52 1467邻域滤波(卷积) 邻域算子值利用给定像素 ... -
【数据结构】排序算法:希尔、归并、快速、堆排序
2012-07-28 06:15 103508年9月入学,12年7月毕 ... -
【OpenCV】角点检测:Harris角点及Shi-Tomasi角点检测
2012-07-31 13:25 1552角点 特征检测与匹配 ... -
【UML】案例分析:机场运作系统
2012-08-01 17:22 314908年9月入学,12年7月毕 ... -
【OpenCV】边缘检测:Sobel、拉普拉斯算子
2012-08-04 13:41 1559边缘 边缘(edge)是指图像局部强度变化最显著的部分。主要 ... -
【OpenCV】Canny 边缘检测
2012-08-08 10:17 2002Canny 边缘检测算法 1986 ... -
【UML】案例分析:新型超市购物自助系统
2012-08-19 01:13 130008年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大 ...
相关推荐
这个名为"openCV-2.2_collection.rar"的压缩包包含了一个针对OpenCV 2.2版本的源码分析,特别关注了SIFT(尺度不变特征变换)算法的实现。SIFT是一种经典且广泛使用的特征检测和描述方法,它在图像识别、匹配和3D...
在这个压缩包中,"93_SIFT配合暴力匹配进行关键点描述和提取"可能是一个示例程序,展示了如何使用OpenCV库实现上述步骤,包括SIFT特征的提取和基于这些特征的图像匹配。通过分析和运行这个代码,可以加深对SIFT算法...
3. **方向分配**:为每个关键点分配一个或多个主方向,这是通过分析关键点周围的梯度方向来实现的,有助于提高匹配时的稳定性。 4. **关键点描述符生成**:在每个关键点周围选取一个小窗口,计算窗口内像素的梯度...
在OpenCV-Python中实现SIFT,你需要导入`cv2`库,调用`cv2.xfeatures2d.SIFT_create()`函数创建SIFT对象,然后分别调用`detect`和`compute`方法检测关键点并计算描述符。最后,可以使用`BFMatcher`或其他匹配器进行...
1. **SIFT算法**:SIFT算法由David Lowe在1999年提出,包括四个主要步骤:尺度空间极值检测、关键点定位、关键点方向分配和关键点描述符计算。这个算法的关键在于它能够生成尺度不变和方向不变的特征,对于图像识别...
这个压缩包中的“sift算法的C源码”提供了一个不依赖于OpenCV等第三方库的原创实现,意味着你可以更深入地理解SIFT的工作原理,而不受其他库的实现细节干扰。 首先,SIFT算法的核心步骤包括: 1. **尺度空间极值...
2. **关键点定位**:对初步检测到的候选关键点进行精确定位,消除边缘响应并确定关键点位置。 3. **关键点主方向计算**:根据邻域像素梯度的方向分布确定每个关键点的主方向,用于后续描述符的定向。 4. **关键点...
2. **关键点定位**:对初步找到的极值点进行精确定位,确保它们是稳定的特征点,排除边缘响应和噪声引起的假阳性。 3. **方向分配**:为每个关键点分配一个主方向,这使得特征点在图像旋转时仍能保持一致。 4. **...
2. **关键点定位**:在找到可能的关键点后,进一步精确定位它们的位置,确保它们是稳定的局部极值。 3. **关键点定向**:为每个关键点分配一个主方向,这使得关键点具有旋转不变性。通常使用关键点周围的梯度方向...
2. **关键点定位**:找到极值点后,通过二次微分判别法确定关键点的位置,确保它们在尺度空间中是稳定的。 3. **方向分配**:为每个关键点分配一个主方向,这有助于提高匹配的稳健性,因为旋转变化不会影响特征的...
对于想要使用OpenCVSharp进行计算机视觉应用开发的开发者来说,以下是一些关键知识点: 1. 图像处理:OpenCVSharp提供了丰富的图像处理函数,如灰度化、直方图均衡化、色彩空间转换(BGR to HSV等)、滤波(高斯...
3. **关键点的精确定位**:对初步定位的关键点进行二次微分测试,消除边缘响应,并通过迭代优化精确确定关键点的位置。 4. **关键点方向赋值**:计算关键点周围的梯度方向直方图,分配一个主方向和一个方向稳定性值...
SIFT通过多尺度空间分析找出关键点,然后计算关键点的尺度、方向和位置。其核心步骤包括:尺度空间极值检测、关键点定位、方向分配和关键点描述符的生成。`siftDemoV4.zip`和`sift-latest_win.zip`可能是SIFT算法的...
在《高清opencv2.4.9源码分析—SIFT.pdf》中,你可以找到关于如何在C++环境中使用OpenCV库实现SIFT算法的详细步骤和源代码解析: 1. **初始化SIFT对象**:通过`cv::SIFT`类创建一个SIFT检测器实例,可以设置参数如...
在OpenCV contrib中,你可以找到如下的关键知识点: 1. **xfeatures2d**:这个模块提供了各种特征检测和描述算子,例如SIFT(尺度不变特征变换)、SURF(加速稳健特征)、ORB(快速ORB)、BRISK(二进制稳健兴趣点...
2. 特征检测:如SIFT、SURF、ORB等,用于识别和匹配图像中的关键点。 3. 目标检测:Haar级联分类器、HOG等方法,用于人脸或其他特定目标的检测。 4. 图像分割:基于区域、阈值、边缘的图像分割技术。 5. 机器学习与...
SIFT(尺度不变特征变换)是一种强大的图像处理技术,用于检测和描述图像中的关键点,即使在不同的尺度、旋转和光照变化下也能保持稳定。它由David G. Lowe在1999年提出,被广泛应用于图像识别、物体检测、图像配准...
在OpenCV 2.4.9版本中,对SURF算法的实现进行了源码级别的分析,这有助于开发者更好地理解算法的内部工作原理。OpenCV是开源的计算机视觉和机器学习软件库,提供众多视觉处理和图像处理的功能。在OpenCV中,使用SURF...
在本文中,我们将深入探讨OpenCV 3源码包中的关键知识点,包括其设计思想、主要功能模块、架构以及如何进行编译与应用。 首先,OpenCV 3的开发目标是提供高效且灵活的工具,帮助研究人员和工程师实现计算机视觉任务...