二特征点提取算法
1 基于 SIFT (Scale Invariant Feature Transform )方法的图像特征匹配
参看 David G. Lowe 的“ Distinctive Image Features from Scale-Invariant Keypoints ” 基于SIFT方法的图像特征匹配可分为特征提取和特征匹配两个部分， ① 尺度空间极值检测(Scale-space extrema detection)； ② 精确关键点定位(Keypoint localization ) ③ 关键点主方向分配(Orientation assignment)
④ 关键点描述子生成( Keypoint descriptor generation ) ⑤ 比较描述子间欧氏距离进行匹配(
可细化分为五个部分：
Compari ng the Euclidean dista nee of the descriptors for
match ing)
1.1尺度空间极值检测
特征关键点的性质之一就是对于尺度的变化保持不变性 必须具备的性质之一，
就是在不同尺度下都能被检测出来。
。因此我们所要寻找的特征点 要达到这个目的，我们可以在尺
度空间内寻找某种稳定不变的特性。
Koenderink和Lindeberg已经证明，变换到尺度空间唯一的核函数是高斯函数。因此一
个图像的尺度空间定义为:
L(x, y,；「)，是由可变尺度的高斯函数 G(x, y,；「)与输入图像
I(x, y)卷积得到，即:
L（x, y,；「）=G（x, y,；「）T（x, y）
其中:
（1.1）
G(x, y,二)二
e_（x2 y2）/^
：2
在实际应用中，为了能计算的相对高效，所真正使用的是 差分高斯尺度空间
（differenee of Gaussian） D（x, y,二）。其定义如下:
D（x,y,二）=（G（x,y,k；「）-G（x,y,；「））T（x, y）
（1.2）
= L（x, y,k；「）-L（x, y, ；「）
如上式，D即是由两个相邻的尺度的差(两个相邻的尺度在尺度上相差一个相乘系数
k)。
士£；^^龙老戸
Difference of
Gaussian (DOG)
Gaussian
图1.1
图1.1所展示的是建立 DOG的一种实用的方法。初始图像与不同 到一垛模糊后的图像，然后将这一垛模糊图像临近两两相减即得所对应的
后的图像以k为系数在尺度空间里被分隔开，并且该垛内最高的尺度应是最低尺度的 为了能开展后续工作（与尺度空间极值检测相关，
将在后续文章中作出解释）并满足上述要
b值的高斯函数卷积，得
DOG。这些模糊
2倍。
求，每垛需要通过卷积得到 s+3个模糊后的图像，并且 s和k需要具有关系k = 21/s。
在一垛图像建立完毕后，还需要降采样得到下一垛图像的
DOG。在实际操作中首先用
2个像素抽出
2倍于第一垛图像的b值建立出模糊图像，然后再将此垛图像降二采样，即每
一个像素，就可以得到下一垛图像的
DOG。
DOG上的某个像素要和本
在上述工作完成后，所要完成的就是尺度空间的极值检测。
尺度的8个相邻像素以及上下相邻尺度各 9个相邻像素比较。这样做的目的是为了确保图像 在尺度空间和二维图像空间均检测到极值点。 如果该像素点在这所有参与比较的点中有最大 值或者最小值，则认为该像素点是尺度空间的极值点之一。
图1.2表示这种极值检测的原理。
图1.2
另外需要注意的是，上述的尺度空间极值点检测在每一个垛中都要进行。最后获得的 极值点总和是所有垛中所检测到的极值点的集合。那么如果这个极值点处在降采样后的垛 中，则需要在找出他后将其坐标变换到原始大小的原图上。容易写出这个变换公式为：
灭=°心0 Omh
2
-], Xo [0,... No
（「3）
1
- [0,...皿
1]
0-
1]
其中Xo是原始大小图像即原始图像上的坐标，经采样变换后变为 X ； 0是处于垛的阶数（即
处于第几个垛中）；Omin=0或者-1，当第一垛图像为原图经过尺寸加倍后的图像生成时值为
1,不经过加倍则为 0。
另外在建立尺度空间的过程中有两个较为重要的参数要确定。 抽样频率和空间域抽样频率。
尺度空间抽样频率表现为每个
可以将之描述为尺度空间
DOG垛所含有的DOG数目。由于每个DOG垛中最大尺
度已经确定是最小尺度的 2倍，则在这个范围内的 DOG数目越多，抽样频率就越高。这个
1 &D80SC4020 ID6PUJI 」亠3d -匕呂瓷一 qffiIEQ Luodx.aJM300025002000 」9quunN 會11 b Tota numbe r orf ksyp onts f ri dgtg base 4 jescriptc 500
1
3
4
5
6
7
NilTibtir of scales sampled per octave
Number :f sea ss samp w： per octave
图1.3
实验表明在每个垛中有 3个抽样时特征点提取效果是最好的（从图 1.3左图可以看出, 无论是变化过的图像中能取到与原图中相同的特征点的比例，
还是所取到的特征点与数据库
内特征点匹配上的比例都是最高）。而之所以更高的抽样频率不能带来更好的匹配效果，是 因为抽样频率越高， 虽然提取的特征点越多，
但这样的特征点大多是不稳定的，
因此无法提
高匹配的成功率，这从图 1.3右图可以看出。
另外一个参数是空间域抽样频率。表现为
d的数值。由于图像与高斯函数的卷积可以
看作是空间滤波，则 d与滤波的截止频率有很大的关系。 d越大，截止频率就越小，能够看
到的抽样值频率也越小。
100
80
(零工=qCQIBaday O O 20
12 1.4 16 1.6 2
Prior smoothing for each octave (sigma)
图1.4
Lowe教授在文章中也对 d的取值做了相关实验，实验结果表明当
d取1.6时所得到的
匹配效果最好，这从图 1.4中可以看出（同样的，在变化过的图像中能取到与原图中相同的
8
特征点的比例，还是所取到的特征点与数据库内特征点匹配上的比例都是最高） 证明，在建立尺度空间的第一垛图像时， 征点
的数目达到原来的 4倍。 1.2精确关键点定位
极值点确定之后，必须进行有效的后续工作对这些点进行筛选；
先将原始图像的尺寸加倍，则可以使稳定的特
。另外他还
因为此时往往会有可观
数量的极值点具有很低的对比度或者处于不理想的边缘。我们把这些极值点成为备选关键 点，而后续工作的目的就是去掉那些对比度低的以及处于不理想边缘处的备选关键点 （keypoi nt can didate），以得到最终参与匹配的特征关键点（ 1.2.1更精确的关键点位置描述
早期的关键点定位方法比较粗糙。目前所采用较多的方法是由
keypoi nt ）。
Brown教授所提出的三
维二次曲线（3D quadratic function ）展开。该方法将 DOG在所关注的像素点处用三维泰勒 级数展开（展开到 2次方项），然后再精确定位极值的位置至亚像素级。展开式如下：
D(x)二
.X 2
卫 x 1\"2D
(1.4)
飞Di
f
◎2D
,瞅
2 -
C2D
a 2
FD C2D〕
dx
T FD
ex cyx
cxy cx<^
〜2
创2
其中：x«ww
)T
cD
矽
◎2D S2D d2D
dyw 52D
2
IcD
—
（
◎D
2
1
-旳1
旳X
cD c^y
（D行-D行）-D^D行），（k指当前k层，k-1指k的下层，k+1指上一层）
4
-2
x 1,y x J,y
x 1,y
x4,y
旳2
D _ （Dk卅 —Dk卅）—（Dy —Dk』）... fx匚 4
c
可以看到，所有的偏导数值都由像素值的差分来近似；后面会涉及到的 关计算也是由像素值的差分来近似的。按照泰勒级数的定义，其中
Hessian算子中的相 D和D的偏导数都是在
展开点所计算的值，而 x是估计点到展开点的偏移量，即：
x = （x-x°, y-y°F - 二。）
其中被减值是估计点的坐标，减数为展开点的坐标。
那么要求得D的极值，则自然想到对这样展开后的
D对x求导，然后使导数为
0,即
求得了局部的极值。在这种理念下，则极值点对于展开点的偏移量
?满足:
(1.5)
则容易由此得到极值点的坐标。容易想到，如果三维向量 那么这个极值点会更接近另外一个像素点，
?在任何一个维度的值大于
0.5，
而不是本身的这个展开点。那么此时就将展开点
换做更接近的那个点，然后再次展开计算偏移量 到关键点的最终位置。
x。最后偏移量的值被加到展开点上以得
所以这个关键点的位置是一
当然这个最终位置的坐标不一定是整数，
种修正过的，或说插值过（interpolated ）的估计值。需要注意的是， SIFT特征匹配最终也
不需要有一个整数的坐标值。在生成了关键点描述子之后，在匹配时与具体的坐标就不相关 了。 1.2.2去除对比度低的不稳定关键点
在精确定位了特征关键点之后，该特征关键点的
DOG函数可以由其临近的像素点的 DOG函数值D（：?）可以用来去除那
DOG展开获得，即式（1.1）。研究表明，特征关键点的
些因为对比度偏低而不稳定的关键点。其值越低，则越不稳定越应该忽略。在实际操作中， 用来求D的函数并不是（1.1），而是在此基础上继续忽略
（x）
2阶项后所得：
D&)
在Lowe教授的研究中，这个阈值为
(1.6)
0.03，亦即所有 D（0 <0.03的点全部去除。
1.2.3去除由边缘响应所带来的不稳定关键点
为了增强特征点的稳定性，仅仅去除低对比的点是不够的。 响应，如果关键点被定位在边缘， 那么这个关键点很有可能是不稳定的， 的影响，即是是少量的噪声也会影响匹配的稳定性。
一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，
而在垂直边缘
DOG函数有着较强的边缘
尤其容易受到噪声
的方向有较小的主曲率。 那么我们只需要求出关键点主曲率便可以决定是否因其处于边缘而 舍去他。主曲率可以通过 2 x 2的Hessian矩阵H来计算，其中：
Dxx Dxy _Dxy Dyy
该点的两个主曲率是与
Hessian矩阵的两个特征值成比例的。而在实际应用中并不用计算出
H的特征值，因为我们可以只考虑他们中较大的特征值比较小的特征值的比例 r便可以确定 该点是不是处于
边缘 （因为在横跨边缘的地方有较大的主曲率， 对应一个大特征值； 而在垂 直边缘的方向有较小的主曲率， 对应一个较小特征值， 比例只要足够大， 就可以认为该点满 足处于边缘的性质）。设a为较大的特征值，3为较小的特征值，则:-=<■。由于
Tr(H ) = Dxx Dyy '
2
(1.7)
Det(H ) = DxxDyy - (Dxy)
我们构建
( 1.8)
ratio
则如果我们考虑
Tr(H)2 C )2 (r 1)2 Det( H) 厂 r
(1.9 )
r r0时则认为该点处于边缘，那在具体判定时，我们可以不用计算
2
出其具体特征值，而是只用等效判断是否有
ratio
的迹以及其行列式，要比计算其特征值的代价小得多， 一般情况下，阈值 0取为10。 1.3关键点主方向分配
给一个关键点分配主方向， 就具有了旋转不变性。
只用进行20次不到的浮点操作即可。
(r。1) ro
即可。计算一个二阶矩阵
r
并将主方向纳入关键点的描述子特性之中， 那么这个关键点
描述主方向需要用到像素点的梯度。梯度的模和方向如下以像素差分的方法定义和计 算:
m( x, y) = J(L(x+1,y) - L(x-1,y))2 +(L(x, y + 1)-L(x, y-1))2
珂x,y) =tan'(L(x,y 1) - L(x, y-1))/(L(x 1, y) - L(x-1,y)) 关键点的主方向是通过统计以关键点为中心的一个邻域之内所有点梯度方向来确定。
(
“。)
( 1.11 )
在实际计算中，这种统计通过梯度方向直方图来确定。梯度直方图将 360°分为36个柱, 每个柱为10 °。其中出现的梯度方向峰值就是这个关键点的主方向。在邻域内的点的方向 被纳入直方图时，还要经过一次高斯加权；这个加权的高斯函数是以关键点为中心，
1.5
（T
为标准差的，其中b就是这个关键点所在的尺度。
若当梯度直方图中存在的次高峰，其模值大于等于最高峰的
80%，那么就将该次高峰
对应的方向定为该点的辅方向。 如果一个特征点有辅方向， 那么就建立另外一个新的特征点，
这个特征点和原特征点有着同样的坐标， 但是方向不同。 也就是说这样会出现一些坐标相同 但是主方向不同
的特征点。实验表明，虽然只有 15%的特征点存在辅方向，但是给具有辅
方向的关键点生成新关键点，能极大的提高匹配的稳定性。
最后，如果还想进一步提高峰值位置的精度，可以用最接近峰值的 3 个直方图值做抛 物线拟合，将拟合出的抛物线最大值的位置作为精确的峰值位置，亦即精确的主方向角度。 1.4 关键点描述子生成
前面的工作我们已经指定了 特征关键点的位置、尺度和方向 ，这样特征点就已经对于 这些参数的变化保持了不变性。 下一步就是要生成一种能描述这样特征的描述子， 并尽可能 让这种描述子对于其他一些变化也有一定的不变性，如光照和三维视角变化。
在建立描述子时，要将描述子的主方向坐标旋转到关键点的主方向上来 ，这样才能保 证具有旋转不变性。之后选择以关键点为中心的
16X 16区域（图1.5）,计算出其中每一点
（高斯函
的梯度值； 然后将这个区域所有的梯度值用一个中心在该区域的高斯函数加权
数的标准差为1.5倍的区域宽度）。接下来将整个区域分为 16个4 X 4的小区域（图1.5中红 色区域），在这个小区域中统计梯度直方图，直方图分为 8 个方向；那么整个描述子所覆盖 的区域含有的信息就是 16X
8=128 个，则整个描述子可以看做是一个 128 维的向量，即特 征向量。生成描述子的过程可以由图 1.6表
示。
最后将特征向量归一化，则可以去掉光照变化产生的影响
。如果光照变化是对比度变
化，则相当于是对每个点的梯度乘上了一个常数， 那么标准化后这个常数就被消除了； 如果 光照变化是亮度的变化， 那么相对于对每个点的像素值加上了一个常数， 对梯度的变化没有 任何影响。 但是由于一些非线性的光照变化会使某些像素的梯度模值产生较大变化，
同时对
梯度方向没有影响， 因此我们在统计梯度直方图时将所有大于某个阈值的梯度模值都置为这 个阈值， 就可以降低光照变化的影响。 要注意的是， 向量归一化是在所有模值经过阈值的限 制之后进行的。 因为这样的操作相当于降低了大模值点的模值在匹配中的权重。 般选为 0.2。
这个阈值一
图1 .6
至此SIFT特征全部集中在 SIFT向量，亦即特征描述子之上。作为图像的局部特征一 种表征，他决定
了基于特征的各种后续处理方法的效果。 1.5比较描述子间欧氏距离进行匹配
在描述子生成完毕之后，特征提取阶段即告结束。完成图像匹配，接下来要做的是对 这些特征运用适当的比较方法来找到对应关系。由于特征点描述子可以看做为 量，则可以通过向量的相关概念来抽象出比较描述子的方法。 氏距离，我们可以容易的想出，两个相同的向量其欧式距离为
128维的向
最直观的便是两个向量间的欧
0，那么两个完全相同的特征
点描述子，其欧氏距离也为 0。不过很显然，由于噪声以及其他图像变换的存在，同一个点 对应在不同图像上的特征描述子不可能完全相同，那么如何确定两个描述子匹配呢？
首先应该想到，描述子距离越近，越应该认为其匹配。但是为了达到稳健的匹配，仅 仅有“最近” 是不够的。 因为对于 128 维这样高维的描述子， 误匹配并没有像独特的对应性， 因此误匹配的描述子容易具有比较接近的距离。因此， 如果两个特征点 A 和 B 真正的是 个对匹配点，那么他们的描述子之间所对应欧式距离首先要最小；其次，这个小还要小到 一定程度：需要他比描述子 A 到除 B 以外其他任何描述子的距离都显著的小，才能体现正 确匹配的唯一独特性。在造作中，我们可以以最近距离与次近距离的比例来衡量这种“显 著程度”，只有当最近距离与次近距离小于某个比例阈值时，我们才接受这一对匹配。
要比较所有描述子的距离，我们可以通过遍历搜索完成。虽然相对于模板匹配的整图 像遍历搜索， 这样的计算量并不算太大， 但也比较可观。 选择一种合适的数据结构存贮这些 描述子，并用合适的搜索策略这个数据结构， 是重要优化命题，但在本文中，不对这个问题 进行具体的讨论。
RANSAC 去误匹配的思路
RANSAC 方法本身是一种迭代的方法，用在去误匹配当中的思路如下
设 A 、 B 分别为基准图和目标图上所找出的匹配点集合 (1)
随机在 A、B 中选取 3 对匹配点对，并通过这三对点得到一个仿射变换矩阵。
(2) 用该矩阵变换 A中所有的点到B '此时比较B和B '中对应点的坐标误差 ei=||B'i-Bi|| , 设置一个误差阈值 sigma，如果误差e小于该值，判定该点对为内点。 (3)
( 1)、( 2)，找到内点最多的一次变换，并将该次变换得到的内点对作为新的
重复
A、
B ，进行一轮新的迭代。
(4)
代所找到的最大内点数目，与此次
(5) 最后得到的这一组 A B 就是去误配后的匹配点集。
迭代终止判定，就是该次迭
A、B 中的点数目一致。
