1.1 特征点检测方法

特征点是图像最基本的特征，又称兴趣点、关键点，它指的是图像灰度值发生剧烈变化的点或者在图像边缘上曲率较大的点（即两个边缘的交点）。特征点是图像特征的局部表达，对遮挡有一定的鲁棒性，且具有较好的辨识性，不同物体上的点容易区分。通常图像中可以检测到成百上千的特征点。通过特征点的匹配能够完成图像的匹配，识别出图像中的目标物体。

1.1.1 常见的特征点检测方法

1.Harris与Hessian检测算子

Moraves^[3]第一个给出了特征点的检测算法，该算法是基于图像灰度自相关函数的，它使用一个邻域窗口在图像平面的四个方向 （水平的正负方向和竖直的正负方向）上平移，计算原始窗口与平移窗口之间的灰度变化量。如果四个方向上的最小变化量大于某个设置的阈值，则将原始窗口中心的图像点作为特征点输出。Harris检测算子^[5]在Moraves的基础上进行了数学简化，它使用图像的一阶差分来刻画图像灰度的自相关性，并利用一阶差分的自相关矩阵来避免平移操作。Harris的自相关矩阵定义如下：

式中， G_i是高斯加权函数，即，它表示距窗口中心越远的点对特征点的贡献越小；Δ_x（x_i,y_i）和Δ_y（x_i,y_i）分别表示水平和竖直方向的差分：

Harris指出，式（1-1）所定义的矩阵可以描述图像在窗口内的结构，如果矩阵的两个特征值较大且比较接近，则窗口中心点对应于一个角点；如果矩阵的两个特征值相差较大或者都比较小，则窗口中心点对应于一个边缘点或均匀区域（指具有相近灰度值的区域）内的点。为了计算方便，Harris使用下述函数来检测特征点：

式中，det和tr分别表示方阵的行列式和迹；k是常数，一般取0.04≤k≤0.06。

当C是较大的正值时，窗口中心点是特征点；当C是较小的正值时，窗口中心点是边缘点；当C是负值时，窗口中心点是均匀区域点。Harris检测算法就是根据上述原理来实现角点检测的，虽然Harris检测算法是为检测角点而设计的，但在实际应用中也能检测出在各个方向灰度变化都很剧烈的点，因此Harris检测算法所检测的角点通常也称为Harris特征点。

Hessian矩阵具有同Harris矩阵相似的形式和特征点检测性质：

式中，I_xx（x,y）、I_yy（x,y）、I_xy（x,y）分别表示图像进行对应的二阶高斯滤波后点（x,y）处的值。相对于Harris矩阵，Hessian矩阵检测出的特征点具有更高的定位精度，但同时二阶差分使得它对噪声的影响更加敏感。

2.CSS检测算子

Mokhtarian同时利用Canny边缘检测技术和曲率空间技术^［6］，通过在边缘上寻找曲率较大的极值点来检测角点的初始位置，然后通过多尺度跟踪定位角点的准确位置，提出了著名的CSS角点检测算法（已被MPEG-7采用）。

将边缘近似看作一条曲线，设曲线的参数方程为Γ（u,σ）=（x（u,σ）,y（u,σ）），则曲线Γ上任意一点处的曲线曲率定义为：

其中，

x_u（u，σ）=x（u）⊗g_u（u，σ）， x_uu（u，σ）=x（u）⊗g_uu（u，σ）

y_u（u，σ）=y（u）⊗g_u（u，σ）， y_uu（u，σ）=y（u）⊗g_uu（u，σ）

在曲线上，变化平缓的普通边缘点处的曲率k（u,σ）的值一般比较小，而在角点位置处，曲率k（u,σ）有着较大的值并能达到局部极大值。因此，通过在边缘上计算并寻找曲率达到局部极大值的点能够达到检测角点的目的。CSS角点检测算子的具体步骤如下：

1）利用Canny边缘检测算子进行边缘检测。

2）重新连接所得边缘中的间断部分，识别并标记其中的T形角点。

3）利用曲线曲率极大值在边缘图像上进行角点检测。

4）进行从粗到细的多尺度跟踪来重新精确定位角点。

5）比较合并步骤2）、3）获得的位置足够接近的角点。

3.LoG与DoG检测算子

高斯拉普拉斯 （Laplacian of Gaussian, LoG）算子是二阶微分算子，实际上它等价于首先利用高斯函数对图像进行平滑，然后对图像进行二阶差分运算，其连续函数的数学表达式为：

通过对上式进行离散采样，即可获得LoG模板。LoG算子在中心附近的值为正数，而模板边缘处的值为负值，直观上可以看作一个区域内环和外环的差异响应，LoG的这种性质与图像中局部块状（Blob）点的结构相一致，因此，LoG 能够有效地检测出图像中的Blob结构。

在尺度空间中，为达到尺度不变性，Lindeberg提出了尺度正则化的LoG算子：，Mikolajczyk指出在众多的特征点检测方法中，能够提供最为稳定的特征点^［8］。由于高斯函数关于尺度σ的偏导数：

是LoG算子的σ倍，它们仅相差一个常数因子，因此它们具有完全相同的特征点检测性能。又有：

即

因此，在尺度空间中能够利用高斯的差分来近似，Lowe将这种高斯差分算子称为DoG （Difference of Gaussian）算子，相对于LoG算子，DoG算子具有更高的计算效率。

4.SUSAN检测算子

与常见算子有着完全不同的工作原理，Smith和Brady^［9］提出了最小核值相似区（Smallest Univalue Segment Assimilating Nucleus, SUSAN）。其基本工作原理是：对于图像中的任意一点（x₀,y₀），选定在以它为中心的一个圆形邻域窗口，该邻域窗口内亮度与中心点相同或者相近的像素组成的区域称为USAN区域，USAN区域的大小用以下两式进行计算：

式中，I（x,y）表示点（x,y）处的灰度值；t为设定的阈值。将USAN区域大小与一个给定阈值g（一般取窗口面积的一半）进行比较，可得到一个响应函数：

对应于图像中平滑区域位置处的点，其利用式（1-11）和式（1-12）计算所得的USAN值一般接近其窗口内像素点的个数，于是利用式（1-13）得到的响应值一般为0；对应于图像中边缘两侧的点，其USAN值一般接近其窗口面积的1/2，其最终得到的响应值很小；而位于角点附近的点由于USAN值通常小于窗口面积的一半，因此最终将获得较大的响应。实际应用中，利用式（1-11）比较两个点的灰度值是否相似对参数t的选择比较敏感，为克服这种问题，一般使用如下函数代替式（1-11）来计算两个像素点之间的灰度相似度:

5.其他特征点检测方法

基于自适应阈值和动态支持区域策略，He和Yung^［10］提出了一种改进型的CSS算法。Zhang等^［11］在深入研究角点在尺度空间的极值性质后，指出利用多个尺度曲率乘积能够有效地进行自适应尺度选择，从而避免了CSS算法的多尺度跟踪。Zhong^［12］从理论上分析了CSS算法直接用于检测平面曲线角点时的性能，指出将尺度空间图像变换到树状图的方法能够提高算法的鲁棒性。

Arrebola^［13］等提出的算法同时利用了曲线多分辨率像素连接技术和轮廓链表编码技术，能够有效检测曲线轮廓上的角点，但该算法不能直接用于灰度图像的角点提取。基于小波变换的角点检测算法^［14］易于进行多尺度分析并具有较高的鲁棒性，但频域变换需要大量计算导致算法效率不高。此外，协方差传播理论和支持向量机技术也被引入角点检测领域。文献中还提出了许多其他的角点检测方法^［15,16］。

为比较各种角点检测算法的性能，Mokhtarian提出了衡量角点检测算法性能的五条准则：①真实角点检测能力；②虚假角点抑制能力；③角点定位精度；④噪声鲁棒性；⑤计算效率。通过对常见的角点检测算子分析比较，Harris算子、SUSAN算子和CSS算子具有最好的角点检测性能。但实际上，由于诸多因素（噪声、滤波平滑效果、角点附近的其他边缘等）的影响，常见检测算子检测出角点的位置与其真实位置之间经常存在偏差。

1.1.2 尺度不变特征点检测

Lindeberg^［7］对特征检测的尺度选择问题进行了深入研究，提出了一种基于尺度归一化高斯拉普拉斯LoG算子的特征检测方法。通过使用不同尺度的高斯核函数对高分辨率图像连续地进行平滑处理，可以建立起一个三维尺度空间，然后通过在该尺度空间中检测LoG算子的极大值来进行特征点检测。由于LoG算子是圆形对称的，用它检测出来的特征主要是类似于局部块状（Blob）的结构，即灰度均匀的、可近似为椭圆的区域的中心。

利用DoG算子近似LoG算子 （式1-9），Lowe提出了具有更高计算效率的尺度空间金字塔建立方法，具体步骤如下：在尺度空间中，利用 LoG算子检测出的特征点具有最好的稳定性。由于 LoG可以用 DoG来近似（式1-9），为提高算法的运算效率，Lowe采用了DoG算子来建立尺度空间金字塔图像结构，如图1-1 所示，首先利用高斯核函数对原始图像进行平滑处理，并将其尺寸放大一倍；然后将图像通过高斯核函数进行连续平滑与下采样获得一系列平滑图像；最后对同一层上 （图像尺寸相同）相邻的两个平滑图像相减得到DoG多尺度空间表示。建立高斯金字塔后，通过将 DoG金字塔尺度空间中每个点与其相邻尺度和相邻位置的点逐个进行搜索比较来进行特征点检测：如图1-2所示，如果该点处的值大于或者小于其26个邻域位置的值，则该点将被检测为关键特征点。

Mikolajczyk和Schmid^［17］将Harris特征检测算法扩展为尺度不变的Harris-Laplace算子。原始的Harris特征只具有旋转不变性，为了适应图像分辨率的变化，在自相关矩阵中加入尺度参数。尺度自适应的Harris自相关矩阵定义如下：

式中，σ_I,σ_D分别是积分尺度和微分尺度。矩阵中的局部导数采用尺度大小为σ_D的高斯内核计算，然后采用尺度大小为σ_I的高斯加权计算邻域窗口内所有导数的平均。积分尺度和微分尺度之间一般可取为倍数关系，并可将积分尺度作为特征点的特征尺度。

Mikolajczyk和Schmid将多尺度下的Harris特征检测与Lindeberg的自动尺度选择方法相结合，通过计算LoG算子的极值来选择特征点的最稳定尺度，提出了一种迭代方法在三维尺度空间中由粗到精地搜索特征点的精确位置和尺度，这种算法被称为Harris-Laplace检测算子。同样的思想也可以用于基于Hessian矩阵的特征检测算法: 特征点的位置通过Hessian矩阵行列式的局部极大值确定，尺度则通过LoG算子的局部极大值来确定，这种算法被称为Hessian-Laplace检测算子。相对于Harris-Laplace算子，Hessian-Laplace算子在尺度空间中的定位精度更高，但对图像噪声更加敏感。此外，Kadir和Brady^［18］采用信息熵作为显著性度量，通过计算描述子的熵的局部极值来选择显著尺度，这种算法检测出来的区域称为显著区域。

1.1.3 仿射不变特征点检测

在特征检测方面，近年来对仿射不变特征区域的研究取得了很大的进展。1997年Alvarez和Morales^［19］提出了一种仿射不变算法来检测角点特征。他们采用了仿射形态学多尺度分析的方法，对提取的每个特征点，将对应于同一局部图像结构在不同尺度下检测出来的点连成一链，然后用这个点链形成的平分线（Bisector）来计算角点的位置和方向。实际上，由于图像中的纹理会严重影响局部最大值的定位精度，因此不同尺度下检测出来的点并不是完全沿着一条直的平分线。这类方法对那些由直线或者近似直线形成的角点效果较好，但并不能全面地解决仿射不变性区域检测的问题。

Lindeberg和Garding^[20]提出了一种迭代算法来检测局部块状结构的仿射不变特征，该工作为仿射不变特征检测提供了很好的理论基础。式 （1-15 ）的二阶矩矩阵描述了图像局部结构的各向异性的形状，因此通过归一化的方法可以将仿射形变转换为旋转。如图1-3所示，X_L和X_R分别为左图和右图中的点，它们之间满足仿射变换X_R=AX_L。其中M_L和M_R分别代表左图中的点M_L和右图中的点M_R点邻域的二阶矩矩阵，则仿射变换A可以定义为：，其中R为一旋转矩阵。因此，通过图中的坐标变换可将仿射形变归一化为仅仅相差一个旋转因子。Lindeberg和Garding首先在各向同性的尺度空间中提取局部极值作为特征点，然后利用二阶矩矩阵的性质通过迭代计算来调整特征点的尺度和形状。但是该方法在进行特征点初始位置检测时没有考虑仿射不变性，而且在迭代过程中也没有进行调整，因此在仿射形变剧烈的情况下检测获得的特征的定位误差较大。

Baumberg^［21］将这种归一化仿射形状的思路用于匹配和识别中，首先在多个尺度下检测Harris特征点，然后采用Lindeberg提出的迭代算法调整特征点邻域的形状以适应图像的局部结构。在该方法中，特征点的尺度和位置在迭代中都是固定的，因此在大的仿射形变下不能保持不变性。Schaffalitzky和Zisserman^［22］将Harris-Laplace检测算法进行扩展使其具有仿射不变性，他采用尺度不变的Harris-Laplace算法来检测特征的位置和尺度，然后采用Baumberg的方法消除仿射形变，因此也带来了和文献［21］中同样的问题。

Mikolajczyk和Schmid^［17］在Harris-Laplace的基础上提出了一种仿射不变的Harris-Affine算法。这种方法也是基于Lindeberg的二阶矩矩阵变换的思路，首先采用多尺度的Harris检测算法提取角点特征，然后在迭代过程中不断调整特征点的尺度、位置和形状。积分尺度的选择采用了LoG算子，计算微分尺度时则引入了一个各向同性度量值，选择能够达到最大度量值（即二阶矩矩阵的两个特征值相等）的微分尺度。通过这种处理，Harris-Affine特征能够在大仿射形变下依然保持较好的不变性，这也是对前面提到的几种类似算法的改进。当然，这个算法也可以用于基于Hessian矩阵的方法，即Hessian-Affine特征检测算法。