介绍
该[1]文中是由M Grabner, H Grabner在ACCV2006上提出对SIFT作了彻头彻尾的近似处理,在略降低精度的情况下,大幅度提高运行速度。该算法的主体框架与SIFT一致,但在每一步都做了近似处理,变卷积运算为求平均、减少旋转变换运算,大量使用动归预计算,减少对特征点的精确修正,在SIFT中耗时的瓶颈作了很大突破。值得注意的是算法虽然用了大量近似处理,但依然取得不错的效果。
算法描述
首先,用DoM金字塔取代DoG金字塔
- 构造DoG金字塔耗时长得根本原因是卷积时间长,即对于每一像素点的邻域计算Σ[I(x,y)*Gauss(x,y)]。而DoM金字塔对于每一像素点的邻域计算ΣI(x,y)/N(其中N为邻域内像素总数),即计算邻域像素亮度的平均数,而不考虑高斯核函数的权重;其余方面与DoG的构造步骤一致。这就带来了极大的速度提升。我们可以通过动态规划预计算以(1,1)、(x,y)为顶点构成的矩形的所有像素的和S(x,y)(S(x,y)=S(x-1,y-1)+I(1:x-1,y)+I(x,1:y-1)+I(x,y)),从而计算以(p,q)和(x,y)为顶点的任意矩形的所有像素的亮度和的时间复杂度为O(1),即卷积的时间复杂度O(n2)降为现在的O(1)。
- 特征点的提取同DoG金字塔相同。根据实验表明,小尺度特征点在匹配时通常不稳定,故该算法省略了第0组图像的构建(即不再将原始图像放大一倍作为金字塔的底层图像)。
- 另外,为确保时效,该算法提取的特征点的坐标不再作亚像素修正,即使用整数坐标。这对于图像拼接来说会失去一些精度。
- 首先,每个特征点主方向的确定方法与传统SIFT算法一致。
- 传统SIFT算法在构建描述子时,将整个圆形区域旋转一个角度(主方向的角度);而该算法仅将4X4子区域的中心点旋转一个角度(减少了计算量),再根据每个旋转后的中心点矩形邻域计算梯度直方图。
- 为了提高时效,矩形区域的长宽与X,Y轴对齐,且计算直方图时不考虑高斯函数的权重,这样每个子区域的直方图可以在O(1)时间内出解(前提是经过预计算)。
实验结果比较
在尺度变换,投影变换的情形下,该算法与传统SIFT的效果基本相近;在旋转变换的情形下,逊于传统SIFT。在运行时间方面,速度基本上是传统SIFT的12~16倍。总体来说,该算法十分适用与图像快速检索,但对于融合需要在精度方面做进一步提升。
参考资料
[1] Michael Grabner, Helmut Grabner, and Horst Bischof,"Fast approximated SIFT"ACCV 2006,NCS 3851, pp. 918–927, 2006.
关于Image
Engineering& Computer Vision更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.