2011-12-13各种特征点

图像的特征点研究 特征点需要具备的两个基本的要求： 1 稳定性好，旋转，缩放，平移，光照的不变性； 2 提取精度高（亚像素级） 。 其他一些重要的评价指标 1 提取算法的复杂度（快速性要求） 2 用于跟踪，立体匹配等是否容易实现。 3 特征点有明显的几何或者物理意义 常用的特征点主要包括:harris 角点 sift 角点 suft 角点 1 Harris 角点 1.1 数学原理 Harris 角点最初由 Harris 在 A combined corner and edge detector 一文中提出，该文实际 上是对 Moravec 在 Rover visual obstacle avoidance 提出的相关思想的改进。Harris 角点最直 观的解释是，在两个相互垂直的方向，都有较大变化的点。这一直观认识的数学描述如下。 下面是理论解释 首先，定义自相关函数： 2,(,)uvxyvuExywII 其中 指给定的窗口，原文对它的解释为 is unity within a specified rectangular region, ,uvw and zero elsewhere。 为灰度值，这样 实际上刻画的是图像偏移造成的窗口内像素I(,)xy 的平均变化。显然，窗口固定之后 为 的函数。而角点，则是当 取两组相E(,)xy 互垂直的值时， 都有较大值的点。(,)Exy 若令 ，则有 可以在原点 Taylor 展开。可以得到以,xuyvDII(,)Dxy(0,) 下公式 2(,)(0,)(,)0,)dxxyyx 显然有 ，忽略高阶无穷小 ，可以得到,(0,)xyuvDI2(,) (,)dDxyy 有因为 22, ,(,) ()uvxyvuuvExywIIwx 从而有 2,(,)()uvdDyx22,()()uv dDwxydy 2AxBCx 其中 ， ， 2,uvdDAwx,uvDdy,uvdwxy 进而可以将 记为(,)Ey(,)xyxyHCB 由于 ，故 可以理解为 变化时，窗口内图像一阶, ,xuyvxuyvuvdIdIDAx 差分的平方和。同理， 可以理解为 方向一阶差分的平方和， 理解为 方向一阶差分B 与 方向一阶差分的乘积。y 一阶差分可以由 sobel 算子求得，也即是 和 。(1,0)I(1,0)TI 由此可以求得 矩阵。这个 矩阵，实际上对 的 Hessian 矩阵的近似。这需HExy 要我们到频率里研究，令 。则有以下关系12(,)(,)FIxyI1212(,)(,)ExyII 进而 1212(,)(,)(,)xyjII21212, (,)(,)(),IxyIFjjFx 所以， 。同样可以得到 ，以及 2,(,)(,)EyIxIyA2(,)ExyB ，从而得到 是 Hessian 矩阵的另一种表达，但是由于求导等运算并不严 2(,)xCyH 格，所以只能认为这是一种近似。 前面已经说过角点是当 取两组相互垂直的值时， 都有较大值的点。所以，(,)xy(,)Exy 我们考虑先找出是 取最大值的 ，如果该方向 有较大的取值，再考虑其,E, 垂直方向。 求 最大值方向本质上为以下最优化问题(,)xy(,)maxEy1T 这一问题在博士期间用的教材应用数理统计教材的 P251 页求解过，方法其实也很 简单，可以直接用拉格朗日数乘法，或者展开为对角性的方法。他的解为 的最大特征值H 的特征向量 。并且有此时 。由矩阵论知识， 的垂直方向为11(,)xy11(,)Exy1(,)xy 的令一个特征值 对应的特征向量。相应的有H222(,)xy 要判断一个点是否为特征点，本质上是要求该点的 矩阵，以及 矩阵的两个特征 值。特征值有三种情况，如图所示 ， 都很小，对应于图像中的平滑区域；12 ， 都很大，对应于图像中的角点； ， 一个很大，一个很小，对应于图像中的边缘；12 至此，Harris 角点的求取的全部数学问题都已解决。 1.2 角点性质与描述 Harris 角点的直观描述为两个方向都变化较为剧烈的点，它的描述只有一个值强度， 没有方向。Harris 角点匹配更多的是对 Harris 角点附近的灰度区域进行匹配。相关内容可 以参见国产大牛张正友的文章 A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry 另外 Harris 角点对尺度的缩放非常敏感，为了解决这一问题，David Lowe 在 1990 年 ICCV 发表了论文 Object recognition from local scale-invariant features，并且在此基础上，David Lowe 提出了性质更好 SIFT 角点。 2 SIFT SIFT 最初由加拿大英属哥伦比亚大学的 David Lowe 提出，给一张老先生的照片在下面， 哈哈。 SIFT 的全称是 Scale Invariant Feature Transform 即尺度不变特征变换。 先生的主页链接为 http:/www.cs.ubc.ca/lowe/ David Lowe 04 年发表在 IJCV 上的论文 Distinctive Image Features from Scale-Invariant Keypoints 全面的阐述了 SIFT 的相关思想。 原文对 SIFT 特征点的定位为 The features are invariant to image scale and rotation, and are shown to provide robust matching across a substantial range of affine distortion, change in 3D viewpoint, addition of noise, and change in illumination. The features are highly distinctive, in the sense that a single feature can be correctly matched with high probability against a large database of features from many images。 也即是具有缩放、旋转、亮度变换具有不变性，从某种意义上，对仿射、噪音、和视 角（透视）变换也有良好的稳定性。此外，SIFT 具有良好的区分度，非常适合用于匹配算 法。此外原文总结它还有以下性质。 1， 上述不变性； 2， 信息量丰富，可以用于匹配； 3， 数量多，小的图片也可以产生很多的 SIFT 特征点； 4， 高速度性，SIFT 特征点提取有较高的实时性； 5， 可以生成描述子，方便的与其他特征融合。 2.2 数学原理 首先引入一个概念，尺度空间(scale space)。它是通过不同 的高斯卷积来实现的，用 来模拟图像由远到近，由模糊到清晰的过程。Koenderink 在 The structure of images 一文中 证明了高斯卷积核为尺度变换的唯一核，而 Lindeberg 在 Scale-space theory: A basic tool for analysing structures at different scales 一文中则证明了高斯核是唯一的线性核。将高斯卷积 的优异性质总结如下。 1， 二维的高斯卷积可以分成两个一维的卷积来加快速度，而按视觉测量P50 的描述，一位的卷积还可以设计为递归的。这可以很大程度上提高高斯卷积的 速度； 2， 对一个图像的多次高斯模糊等效与一次更大的模糊； 3， 高斯模糊具有圆对称性。 基于高斯卷积，我们可以定义高斯金字塔。高斯金字塔的构建包括两步。 1， 对图像做高斯平滑； 2， 对图像做降采样； 如下图所示： 数学上可以定义尺度空间 。及不同 的函数与原图像(,)(,)(,LxyGxyI 的卷积。其中 22()/1(,)Gxye 则 描述的空间即为尺度域。当然，我们不可能实现 连续变化的尺度域，,L 因此尺度域往往按一下方法构造。 0()2sSkk(1)0() 其中 为尺度空间坐标。 为每组(octave) 图片的初始尺度。 为每组的总层数0k (interval)， 为组内的第几层， 对应第 组的第 层。相邻两组的同一层，除了满足s()sks 上述关系之外，还做以此隔点降采样。 在实际实现时，只需要明确第 0 层的初始尺度 以及每组的层数 ，便可以生成上0S 述金字塔。工程中常常取 3 到 5。由于相机拍摄已经相当于对图像进行了以此初始模糊，S 所以 常取：0 0intitpre 这其中 为设计的第 0 组的初始尺度，而 为摄像机的初始模糊，例如，在intr Lowe 的论文中，有 这样得到第 层，第 层的 值为ks0(,)skSs 事实上，高斯平滑会造成会造成高频信息丢失，这样产生的高斯金字塔，即使是第 0 层，也已经丢失了高频信息。因此，Lowe 在原文中建议，对原始图像长宽扩展一倍，来产 生-1 层，这一层的尺度定义如下 102intitprere 到此为止，解决了金字塔生成的全部数学问题。 在得到高斯金字塔之后，首先要解决的问题，是在尺度域大致找到特征点的分布区域， 这是通过计算高斯差分（DOG，difference-of-Gaussian）来解决的，高斯差分记为 。其表达式如下。(,)Dxy 。 1(,)(,2)(,)SDxyLxyxy 这既是著名的 DOG 算子。差分的计算是在组内相领两层进行的。如下图所示。得到的 结果称为 DOG 金字塔。与高斯金字塔相对应。 选择这一函数一方面是因为 的极值点（包括极大值和极小值）从某种意义(,)Dxy 上刻画了特征较强的点，这些点相对稳定(由远到近一直不变的区域，以及由远到近变化最 剧烈的点) 。另一方面，它只是简单的做尺度域的差分，计算量小； 在得到 之后，需要求取极值，请注意极值实在三维的尺度域求取的，而不(,)Dxy 是二维的图像上。David Lowe 所用的方法是在尺度域的 26 领域里计算。26 领域的第一和 二维上的 8 领域类似，如下图所示。如果一个点的 值比它 26 个领域的 值都小或者都DD 大，则这个点被标记为极值点。 显然，在每一组的内部，最顶层和最底层的图像是无法计算极值的，这样会造成 DOG 金字塔在尺度域不等距分布。为了让 在不同的组之间连续过渡，Lowe 建议在每一组增 加 3 层。下面的图很好的说明了这一思想。这张图来至北理工宋丹老师的 PPT，在此谢过。 O c t a v e 1 3k 4 56 7k 8 3 4 56 7 k 89 10k 6 7 2 L e v e l S i z e ： 2 M 2 N G a u s s i a n S p a c e D o G S p a c e O c t a v e 3 L e v e l S i z e ： M N G a u s s i a n S p a c e D o G S p a c e L e v e l S i z e ： M / 2 N / 2 G a u s s i a n S p a c e D o G S p a c e k 2 3 4 5k O c t a v e 2 O c t a v e N 这样，我们只牺牲了第-1 组的第 0 层，和第 N 组的最高层。 这样我们就可以在尽可能多的层里讨论极值点的求取问题了。求得的极值点可以作为 关键点的初始估计，这些点是像素级别的，而且受到噪音的影响。 下面介绍关键点精确定位的方法。这一方法本质上分为三个部分。 1， 求取亚像素级精度。所用的方法为非常常用的 Talyor 展开法； 2， 剔除平滑区域的点，因为这些点不稳定；判断准则为 的值()DX 3， 剔除边缘区域的点，因为这些点不稳定；判断边缘的方法与 Harris 角点一节中给 出的方法一样，即 矩阵两个特征值的模，一个大一个小的点为边缘点H 设上面求得的极值点坐标为 则设亚像素的精确极值点坐标为00,TXxy ，两者之间的偏差 。将 DOG 函数在 处的值表示为在 处,TXxydX0X 的 Taylor 展开。有以下式。 20 00000() ()1()()2TTDXDD 由于极值点处的一阶导数为零。固有 2000()()() )XX 解得 12000()()DdX 当然，如果 在任何一个维度大于 0.5，意味着极值点离另外一个像素更近，我们应 该转而到该像素点进行上述泰勒展开，如此迭代，直到收敛或者达到迭代设置的上限。在 得到将 回带，可以得到 120000()()()1()2TDXDXDX 也即是 。这样可以求得 ， 值越小，00() T() 说明极值点附近区域越平滑，为了得到稳定的关键点，平滑区域的关键点被去除。原文中 设置的阈值条件为 。().3DX 去除边缘上的点的方法和 Harris 所用方法相同，都是通过指定尺度的图片的 Hessian 矩阵 的特征值来判断。边缘上的点一个特征值的绝对值大，而另一个较小。做如下推导HxyDH 将 较大的特征值记为 ，较小的特征值记为 ，且有 。有以下关系。2det()2(1)trH 进而有 ，由于 ，故该比值有随着 增大而增大的趋势。 22()1)detr 又因为 ， 。()xyHD2det()xyxD 所以取阈值 ，得到判断一个点不在边界上的条件0220()(1)xyxD Lowe 建议 取 10。0 这样得到的关键点，有三个坐标 也就具备了位置和尺度的不变形。为了使其(,)xy 具备旋转不变性质，还需要生成方向直方图。 对于每一个关键点，我们还需要为关键点生成一个方向向量。下面的计算都是在特征 点最接近的一个尺度进行。这样也是的计算的方向向量具备尺度不变形。 为了对方向进行描述，首先计算图像的梯度。使用下面的公式 2 2(,)(1,)(,)(,1)(,)mxyLxyxyLxyxy1,tan(,)(,) 实际上是 sobel 算子近似计算的梯度的幅度， 为 sobel 算子近似计算的(,)xy xy 梯度的方向。为了生成关键点的特征描述，做一下处理。 1， 统计关键点附近一定区域内（Lowe 建议，以关键点为圆心，以 为半径的区1.5 域）内的梯度的方向直方图，直方图以 10 度为一个柱，一共 36 个柱。直方图的 值为区域内，梯度方向在指定方向范围的所有点的梯度值的高斯加权的和。 2， 统计直方图的最大的峰值被检测出来，作为方向直方图的主方向； 3， 如果有其他的峰值，并且该峰值在最大峰值的 85%以内，则被检测出来作为统计 直方图的副方向。Lowe 表示约有 15%的直方图有副方向，而且这些副方向对于描 述得稳定性有非常重要的作用。 4， 对所用峰值附近的三个点进行抛物线拟合，以求取极值点的准确位置。 完整的步骤如下所示。 1， 确定计算关键点直方图的高斯函数权重函数参数 ； 2， 生成含有 36 柱的方向直方图，梯度直方图范围 0360 度，其中每 10 度一个柱。 由半径为图像区域生成； 3， 对方向直方图进行两次平滑，模板采用0.25，0.5，0.25； 4， 求取关键点方向（可能是多个方向） ； 5， 对方向直方图的 Taylor 展开式进行二次曲线拟合，精确关键点方向； 至此，解决了 SIFT 关键点的全部求解问题。每一个关键点都已经包含坐标，尺度，主 方向（以及副方向） 。 但是为了将 SIFT 特征点用于匹配等应用，还需要对特征点生成更为详细的描述。这一 描述由下图所示。 描述子的具体生成步骤如下： 1， 确定生成描述子所需要的区域，这一区域是以关键点为圆心的一个圆，圆的半 径可以参考一下选取 321octdradius 其中 为组内的尺度，oct4 2， 将区域坐标旋转到主方向，以使生成的描述子具有旋转不变性。如下图所示 x y x y 3， 将特征点附近区域分割，按高斯加权生成描述子，Lowe 建议描述子为 也即是特征值附近分割为 的子区域，并在子区域按 8 个方向统484 计直方图。 4， 对描述子做适当的后处理，例如归一化，或者门限化，用于匹配。 所有 SIFT 特征点和描述子的数学问题都已解决。 3 SUFT Herbert Bay, Tinne Tuytelaars, and Luc Van Gool 三人 2006 年在 ECCV 上发表了名为 SURF: Speeded Up Robust Features 的文章，提出了一种高速、稳定