图像特征点匹配算法_bf模式匹配算法
摘要：现阶段，基于特征点匹配的算法，如SIFT,SURF等著名匹配算法，都是基于一个尺度空间来进行描述的，那么了解尺度空间是什么将是全面了解特征点匹配的关键性基础知识。网上基于尺度空间的基础知识有很少的介绍，所以本章将主要介绍尺度空间，我们将从最底层了解怎么提取特征点，为啥用这种特征点具有较强的鲁棒性。
网上基于尺度空间的基础知识有很少的介绍，所以本文将主要介绍尺度空间，使读者在运用基于SIFT等特征匹配算法时，能从最基本的理论上思考问题和解决问题。本文涉及很多理论数学公式，本来想着要不要就这种很数学的理论进行讲解，但是本公众号本着“知其所以然”的精神还是决定将这种“难啃的骨头”解释一遍，使大家能更加透彻。
01 背景及概念
同一个物体在成像时，由于远近不同，会导致在图像中的大小、细节性（模糊）等方面产生差异，但是该物体又是同一个物体，所以我们不知道到底哪个是真实的，该如何去衡量。于是在1994年由Lindeberg[1]提出来的尺度空间来衡量物体在图像中和现实中的一个关联。这其实就是地图上的距离尺标一样，用来表示不同大小成像物体和真实大小的一种关系。 [外链图片转存失败(img-qslwUMs2-1562988897683)(https://raw.githubusercontent.com/FutureIsM/blog_img/master/尺度空间/不同尺度空间的效果.JPG)] 以原图作为基准，最后一幅图就像是在距离很远的距离看的一大幅图中的部分截图。所以可以用一个尺度空间来表示距离和大小的相互关系。
02 尺度空间
Koenderink[2]等人用精准的数学形式通过不同的途径都证明了高斯核实实现尺度变换的唯一变换核。
尺度空间的最原始的形式是由热传导方程演变而来，热传导方程式是一个用来描述热量随着时间变化在空间的分布过程，具有下面的形式：
$$ \frac{\partial μ}{\partial t}= k \left( \frac{\partial ^2 μ}{\partial t^2} + \frac{\partial ^2 μ}{\partial t^2} +\frac{\partial ^2 μ}{\partial t^2} \right )= k \nabla^2 μ $$
其中μ描述的是热量在空间的分布，k是一个长寿。在信号处理领域中，如果把信号函数 f : R → R f: \mathbb R \to R f:R→R视成“温度”在空间中的初始分布，那么，尺度空间出生成过程则可以看作是尺度t的函数，是信号随着t变化的热扩散空间分布。这样信号的尺度空间L，有类似热扩散的方程表达式：
$${\partial _t}L = \frac{1}{2}{\nabla ^T}\nabla L = \frac{1}{2}\sum\limits_{i = 1}^N {
{\partial _{x_i^2}}L} $$
微分方程的初始条件为 L ( ⋅ ; 0 ) = f ( ⋅ ) L\left( { \cdot ;0} \right) = f\left( \cdot \right) L(⋅;0)=f(⋅)，t∈R(+)是尺度参数。该偏微分方程可以解析得到尺度空间表达L:R(N)xR(+)->R:
$$L\left( {x;t} \right) = g\left( {x;t} \right) * f\left( x \right) = \int_{\xi \in {R^N}} {f\left( {x – \xi } \right)g\left( \xi \right)} d\xi $$
式中，g是R(N)xR(+){0}->R高斯函数。上式定义了一个关于(x,t)的曲面函数，包含一个具有尺度变量t的高斯核，我们称为高斯尺度空间。其中高斯核表达式为：
$$g\left( {x,t} \right) = \frac{1}{
{
{
{\left( {2\pi t} \right)}^{N/2}}}}{e^{ – {x^T}x/\left( {2t} \right)}}\left( {x \in {R^N}} \right)$$
式中N表示维度，例如N=1为一维基本高斯函数。 在尺度空间的任一尺度上，都可以应用局部微分算子：
$${L_{
{x^\alpha }}}\left( { \cdot ;t} \right) = {\partial _{
{x^\alpha }}}L\left( { \cdot ;t} \right) = {\partial _{x_1^{
{\alpha _1}}}} \cdots {\partial _{x_D^{
{\alpha _D}}}}L\left( { \cdot ;t} \right)$$
式中，x=(x1,…,xD);α=α1+…+αD。由于微分算子和高斯平滑算子可以互换，即
$${L_{
{x^m}{y^n}}}\left( {x,y;t} \right) = {\partial _{
{x^m}{y^n}}}\left( {
{g_t} * f} \right) = \left( {
{\partial _{
{x^m}{y^n}}}{g_t}} \right) * f$$
所以，尺度空间微分算子可以等效为原始图像与高斯微分算子的卷积。因此，尺度空间微分算子有时候也被称为高斯微分算子。
03 高斯尺度空间特性
高斯核作为唯一具有线性尺度不变的变换核，由于我们在很多的图像处理中应用高斯核，例如高斯模糊核等，所以高斯核具有相关主要特性将在下面介绍。
- 加权平均性 由于高斯函数的特性，高斯尺度空间有平滑作用，也就是会抑制一些精细结构。
- 层叠平滑性
$$g\left( { \cdot ;t} \right) * g\left( { \cdot ;s} \right) = g\left( { \cdot ;t + s} \right)$$
- 局部极值递减性 （1）如果在某个尺度t0上，函数L(x,t0)在点x0上取得局部极大值，则该点拉普拉斯运算Δ L(x0,t0)是负值，也就意味着∂L(x0,t0)<0； （2）如果在某个尺度t0上，函数L(x,t0)在点x0上取得局部极小值，则该点拉普拉斯运算Δ L(x0,t0)是正值，也就意味着∂L(x0,t0)>0； 以上可以看出，函数L的各阶导数极值点数量不会增加，同样，意味着零点数量也不增加。 我们以某特定频率w0正弦信号为例，对这个性质作进一步探讨。为例简单介绍，仅考虑一维情况，f(x)=sin(w0x)。其尺度空间的解析解为：
$$L\left( {x;t} \right) = \int {\sin \left( {
{w_0}\left( {x – \xi } \right)} \right)\frac{1}{
{\sqrt {2\pi t} }}} {e^{ – \frac{
{
{\xi ^2}}}{
{2t}}}}d\xi = {e^{ – w_0^2t/2}}\sin {w_0}x$$
所以上式尺度t上的振幅表达式为：
$${L_{\max }}\left( t \right) = {e^{ – w_0^2t/2}}$$
m阶导数的振幅表达式为：
$${L_{
{x^m},\max }}\left( t \right) = {w_0}^m{e^{ – w_0^2t/2}}$$
这两个表达式都表明振幅会随着尺度的增加而指数级减少。
- 尺度伸缩不变性 假设有两个信号有一定的伸缩变换关系如下式：
则它们各自的尺度空间表达式为：
$$L\left( { \cdot ;t} \right) = g\left( { \cdot ;t} \right) * f$$
$${L^{‘}}\left( { \cdot ;{t^{‘}}} \right) = g\left( { \cdot ;{t^{‘}}} \right) * {f^{‘}}$$
其中，x’=sx;t’=s2t,空间变量 x 和尺度变量 t 有如下转换：
$${L^{‘}}\left( {
{x^{‘}};{t^{‘}}} \right) = {g^{‘}}\left( {
{x^{‘}};{t^{‘}}} \right) * {f^{‘}}\left( {
{x^{‘}}} \right) = g’\left( {sx;{s^2}t} \right) * {f^{‘}}\left( {sx} \right) = \frac{1}{s}g\left( {x,t} \right) * f\left( x \right) = \frac{1}{s}L\left( {x;t} \right)$$
这是本文推导的式子，和常见的推导结果有所不同，值得探讨。根据对应关系，我们可以知道对应的伸缩尺度上会有个相同的极值，只是幅度上会有一定的伸缩。除非g为广义高斯，没有前置系数。 假设如下公式成立
$${L^{‘}}\left( {
{x^{‘}};{t^{‘}}} \right) = L\left( {x;t} \right)$$
则有
$$\frac{
{\partial {L^{‘}}\left( {
{x^{‘}};{t^{‘}}} \right)}}{
{\partial {x^{‘}}}} = \frac{
{\partial L\left( {x;t} \right)}}{
{\partial x}}\frac{
{\partial x}}{
{\partial {x^{‘}}}}$$
$${\partial _{
{x^m}}}L\left( {x;t} \right) = {s^m}{\partial _{
{x^{‘m}}}}{L^{‘}}\left( {
{x^{‘}};{t^{‘}}} \right)$$
为了去除尺度参数对特征响应的影响，我们引入一个γ——坐标规范化的概念。那么，规范化后的变量为
$$\xi = \frac{x}{
{
{\sigma ^r}}} = \frac{x}{
{
{
{\left( {\sqrt t } \right)}^r}}}$$
则有
$$\frac{
{\partial L\left( {x;t} \right)}}{
{\partial \xi }} = \frac{
{\partial L\left( {x;t} \right)}}{
{\partial x}}\frac{
{\partial x}}{
{\partial \xi }}$$
$${\partial _{
{\xi ^m},\gamma – norm}}L\left( { \cdot ;t} \right) = {t^{\gamma m/2}}{\partial _{
{x^m}}}L\left( { \cdot ;t} \right)$$
$${\partial _{
{\xi ^{‘m}},\gamma – norm}}{L^{‘}}\left( { \cdot ;{t^{‘}}} \right) = {t^{‘\gamma m/2}}{\partial _{
{x^{‘m}}}}{L^{‘}}\left( { \cdot ;{t^{‘}}} \right)$$
引入规范化后有
$${\partial _{\xi ,\gamma – norm}}L\left( { \cdot ;t} \right) = {s^{m\left( {1 – \gamma } \right)}}{\partial _{
{\xi ^{‘}},\gamma – norm}}{L^{‘}}\left( { \cdot ;{t^{‘}}} \right)$$
所以为了去除这种因为尺度带来的指数性衰减，我们一般都是用一个规范化的γ=1来达到尺度不变性。由于s(m)是尺度变化本身带来的，我们只需要设定一个t(rm/2)的系数去抵消尺度。 下面在斑点检测中进行实验说明，我们设定一个斑点的宽度为4，则它的图像形式则为 [外链图片转存失败(img-yp7jPWMq-1562988897684)(https://raw.githubusercontent.com/FutureIsM/blog_img/master/尺度空间/光斑信号.JPG)] 假如不用规范化的二阶高斯核去卷积，卷积的结果为
上图左边为未规范前不同方差大小的二阶高斯核，右边为二阶高斯核和斑点信号卷积后的响应结果。为了去除方差导致的衰减现象，应用高斯函数的导数时，对其进行规范化处理，其中γ=1：
$$\frac{d}{
{dx}}\bar g = \sigma \frac{d}{
{dx}}g = \sqrt t \frac{d}{
{dx}}g,\frac{
{
{d^2}}}{
{d{x^2}}}\bar g = {\sigma ^2}\frac{
{
{d^2}}}{
{d{x^2}}}g = t\frac{
{
{d^2}}}{
{d{x^2}}}g$$ 响应结果为： [外链图片转存失败(img-hBgK0HU4-1562988897685)(https://raw.githubusercontent.com/FutureIsM/blog_img/master/尺度空间/规范后响应.JPG)] 上图实验结果可以看到，规范化后，能够在正确的尺度下找到峰值。
03 图像特征检测
最后再来看看图像特征提取中的应用，最经典的就是sift，它就是构建了一个尺度空间来寻找最合适的峰值。 [外链图片转存失败(img-mW7UNGz8-1562988897685)(https://raw.githubusercontent.com/FutureIsM/blog_img/master/尺度空间/尺度空间特征.JPG)] 由上图可以看到，同样一个物体，由于远近导致在同一个图片中的尺度不一样，而我们通过拉普拉斯求得某个点在尺度空间遍历的峰值，我们就认为这个尺度就是该物体的尺度。如左边的路灯是远景，尺寸比较小，所以拉普拉斯的峰值相对于右边近景横轴尺度t要小。 那么需要判断什么是特征点呢？前人总结了很多角点和斑点的特征，他们会在尺度上有一个峰值，这个峰值存在而且具有超过阈值的响应，我们就认为这个点鲁棒性很强，又具有尺度不变性，加上设计的方向描述子，这就是一个完整的尺度不变性，旋转不变性，鲁棒性强的特征点，这就是基本的sift设计思维。
小结：简单的原理下面是复杂的数学推理和公式计算，而通透这些理论公式是非常枯燥乏味的过程，但同时也是最基础最能给予人最深刻体会的过程。通过了解尺度空间，我们可以知道尺度不变性是什么样的概念，那么特征点匹配算法等是怎么利用这种特性来建立鲁棒性强的特征提取算法的，感谢阅读，如有任何疑问请向我们留言，我们下章见！
[1] Lindeberg T. Scale-space theory incomputer vision[M]. Springer Science & Business Media, 2013. [2] Koenderink J J. The structure of images[J]. Biologicalcybernetics, 1984, 50(5): 363-370.
闲在写了个公众号《算故为法》，本公众号其实主打夯实基础，也许后期后做些视野型的文章写些关注发展前言，本公众号将分享和梳理基础理论知识，也许有错误的地方，也请同行多指点。最后，欢迎大家关注，你的关注是我不断更新的动力！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/182202.html原文链接：https://javaforall.cn
腾讯云开发者
