SURF算法解析 一、积分图像 那么,当我们想要计算图片一个区域的积分,就只需计算这个区域的四个顶点在积分图像里的值,便可以通过2步加法和2步减法计算得出,其数学公式如下: 二、Hession矩阵探测器 高斯拉普拉斯Log探测器的响应值就是在衡量图像的相似性,如下图是一个图像的高斯拉普拉斯变换的三维图和灰度图显示,在图像中的斑点尺寸与高斯拉普拉斯函数 Hession矩阵就是利用二阶微分来进行斑点检测,其矩阵如下: 2、Hession矩阵与盒子滤波器 在图像中的Hession矩阵如下: 他们的三维图和灰度图如下所示: 由此,我们把模板(图像中的区域)与图像的卷积运算转化为盒子滤波器的运算,如下图所示: 3、hession矩阵行列式的简化 当我们用sigma = 1.2.的高斯二阶微分滤波,模板尺寸为9X9最为最小的尺度空间值对图像进行滤波和斑点检测,Hession矩阵的行列式可做如下简化: 常数C不影响极值点的比较,所以最终简化式如下,这也是SURF论文里面Hession响应值计算公式的来源: 另外,响应值还要根据滤波器大小进行归一化处理,以保证任意大小滤波器的F范数是统一的。0.9^2是滤波器响应的相关权重w是为了平衡Hessian行列式的表示式。这是为了保持高斯核与近似高斯核的一致性。理论上来说对于不同的σ的值和对应尺寸的模板尺寸,w值是不同的,但为了简化起见,可以认为它是同一个常数。 使用近似的Hessian矩阵行列式来表示图像中某一点x处的斑点响应值,遍历图像中所有的像元点,便形成了在某一尺度下琉璃点检测的响应图像。使用不同的模板尺寸, 便形成了多尺度斑点响应的金字塔图像,利用这一金字塔图像,就可以进行斑点响应极值点的搜索。 三、3D非极大值抑制 1、尺度金字塔构造 在SURF中,采用不断增大盒子滤波器模板尺寸与积分图像求取Hession矩阵响应,然后在响应图像上采用3D非极大值抑制,求取各种不同尺度 的斑点,以下是两种不同的金字塔,SURF的金字塔属于第二种: SURF中采用9X9尺寸的滤波器作为起始滤波器,之后的滤波器尺寸可由以下公式计算得出: octave、interval在公式中都是从1开始,也就是当第0组第0层时,在公式中octave = 1, interval = 1。 采用这种方式来定义滤波器尺寸的理由如下; 滤波器响应长度、滤波器尺寸、组索引O、层索引S 尺度sigma之间的关系如下: 采用类似的方法来处理其他几组的模板序列。其方法是将滤波器尺寸增加量翻倍(6,12,24,38)。这样,可以得到第二组的滤波器尺寸,它们分别为15,27,39,51。第三组的滤波器尺寸为27,51,75,99。如果原始图像的尺寸仍然大于对应的滤波器尺寸,尺度空间的分析还可以进行第四组,其对应的模板尺寸分别为51,99,147,195。下图显示了第一组至第三组的滤波器尺寸变化: 在通常尺度分析情况下,随着尺度的增大,被检测到的斑点数量迅速衰减。所以一般进行3-4组就可以了,与此同时,为了减少运算量,提高计算的速度,可以考虑在滤波时,将采样间隔设为2。 3、局部极大值精确定位 采用3维线性插值法得到亚像素级的特征点,同时也去掉那些值小于一定阈值的点。 四、特征点描述符 1、特征点方向分配 以特征点为中心,计算半径为6s(S为特征点所在的尺度值)的邻域内的点在x、y方向的Haar小波(Haar小波边长取4s)响应,Harr小波 模板如图所示: 计算出图像在哈尔小波的x和y方向上的响应值之后,对两个值进行因子为2S的高斯加权,加权后的值分别表示在水平和垂直方向上的方向分量。 Harr特征值反应了图像灰度变化的情况,那么这个主方向就是描述那些灰度变化特别剧烈的区域方向。 接着,以特征点为中心,张角为π/3的扇形滑动,计算窗口内的Harr小波响应值dx、dy的累加: 扇形窗口的滑动如图所示: 在OpenSURF的C++代码实现如下: for(int i = -6; i <= 6;="" ++i)="" {="" for(int="" j="-6;" j="">=><= 6;="" ++j)="" {="" if(i*i="" +="" j*j="">=>< 36)="" {="" gauss=""> 通过i,j来控制以特征点为中心的6X6的范围,(i*i + j*j <> 滤波。并计算出每个点的角度。 最后将最大值那个扇形的方向作为该特征点的主方向。在OpenSURF寻找扇形中具有最大值得方向代码如下: for(ang1 = 0; ang1 < 2*pi;="" ang1+="0.15f)" {="" ang2="(" ang1+pi/3.0f=""> 2*pi ? ang1-5.0f*pi/3.0f : ang1+pi/3.0f); sumX = sumY = 0.f; for(unsigned int k = 0; k < ang.size();="" ++k)="" {="" get="" angle="" from="" the="" x-axis="" of="" the="" sample="" point="" const="" float="" &="" ang="Ang[k];" determine="" whether="" the="" point="" is="" within="" the="" window="" if="" (ang1="">< ang2="" &&="" ang1="">< ang="" &&="" ang="">< ang2)="" {="" sumx+="resX[k];" sumy+="resY[k];" }="" else="" if="" (ang2="">< ang1="" &&="" ((ang=""> 0 && ang < ang2)="" ||="" (ang=""> ang1 && ang < 2*pi)="" ))="" {="" sumx+="resX[k];" sumy+="resY[k];" }="" }="" if="" the="" vector="" produced="" from="" this="" window="" is="" longer="" than="" all="" previous="" vectors="" then="" this="" forms="" the="" new="" dominant="" direction="" if="" (sumx*sumx="" +="" sumy*sumy=""> max) { // store largest orientation max = sumX*sumX + sumY*sumY; orientation = getAngle(sumX, sumY); } } 2、特征点特征矢量的生成 以特征点为中心,沿主方向将20SX20S的图像划分为4X4个子块,每个子块用尺寸2S的Harr模板进行响应值计算,并统计每个子块中 这样就有4X4X4=64维的特征数据。如下图所示: 在计算这个矩形区域时并不是先把它旋转到主方向,而是先计算出每一个点的Harr响应值dx、dy并高斯加权处理后,把dx、dy进行旋转变换,计算 公式如下: 在OpenSURF的实现源码中采用的是另外一种方式,通过点旋转公式,把点旋转到主方向上并进行最近邻插值的对应点,公式如下: 五、匹配 为了加速匹配过程,SURF借助Laplacian(在之前计算Hessian是可以顺便得出,不占用太多的时间)的符号使匹配过程索引加快。这样可以将下面的情况区分开,然后在进行描述符匹配: 参考资料: http://www.cnblogs.com/ronny/p/4045979.html http://doc./ronny/archive/107771.html http://www./articles/2i6fqq3 http://wenku.baidu.com/view/cf0c164f2e3f5727a5e96238.html |
|