一种基于MSER的仿射不变二进制特征提取算法

胡汉莉 席志磊

（武汉数字工程研究所 武汉 430205）

1 引言

景象匹配作为一种自主、无源的导航定位手段，在现在军事武器中发挥重要的作用。景象匹配的实质是实现实时图与基准图之间的图像匹配问题，以特征相似性为度量的图像匹配作为景象匹配中的核心内容，得到了广泛的关注与研究。由于受成像设备安装角度、成像姿态、传感器误差等因素影响，图像之间会存在复杂的线性或非线性变形，景象匹配算法需要对实测图与基准图存在的形变有较强的稳定性，能够有效地克服图像之间存在的几何与辐射变形。

最大稳定极值区域检测子（MSER）［1］算法通过对图像进行连续的阈值分割，寻找在一定阈值范围内保持边界不变的区域，然后在该区域内提取稳定的多边形仿射不变特征；基于熵函数的显著区域（Salient Region）检测子［2］其理论基础为局部区域上的亮度概率密度函数，且利用尺度空间思路来实现尺度不变性，特征的尺度由描述子的熵极值来定义，使得显著区域能有效抵抗仿射及尺度变形。但由于目前对于景象匹配算法的时间和存储效率的要求不断提高，有必要对现有的MSER算法进行优化改进。

2MSER特征检测算法

存在大视角差异的图像间的相关性不能通过比较矩形或圆形等固定的形状来建立，因为此类形状在仿射变化下不能够保持，如图1，同一场景中相同的物体内容，在大视角拍摄条件下，发生明显的几何形变，相同形状的窗口不能代表同样的场景内容。而解决该问题的关键在于提取仿射协变区域来构建特征描述。若某区域能通过仿射变换变成规范形，则该区域即为潜在的仿射协变区域［3］。

图1 不同视角下场景的几何形变

几何特性优的椭圆区域是目前在各种局部仿射不变特征中使用最为广泛的仿射协变区域。最大稳定极值区域［4］（Maximally Stable Extremal Regions，MSER）是宽基线立体匹配中常用的仿射不变的局部区域检测算法。该算法由Matas于2002年提出，MSER提取具有任意形状的仿射不变区域，不需预先对图像进行平滑处理，可以在多种尺度下检测MSER，可以检测不同精细程度的区域。算法提取的特征稳定性强、精度高；而且MSER特征区域提取算法具有近似线性的计算速度。据有关学者研究试验证明，MSER算子在众多仿射不变特征提取算法中，多数情况下具有最佳性能［5］，其在宽基线、大视角图像匹配中具有广泛的应用［6～8］。

2.1 最大稳定极值区域的定义

最大稳定极值区域由区域内或者区域边界上的灰度函数的极值属性来定义。假设灰度图像I(x ，y) ，其灰度值属于区间［0，255］。设置不同的灰度阈值t∈(0 ，1，…，255) ，对应的阈值图像分别为 I0，I1，…，I255。

设图像I(x ，y)中像素值小于某阈值的点为黑点（其像素值为0），而不小于阈值的点为白点（像素值为255）。若将得到的阈值图像It按照阈值t逐渐增大的顺序连续展开，即可得到一系列由白到黑的二进制图像。如图2所示，当阈值t=0时，灰度图像I(x ，y)上所有的像素值均高于该阈值，所以得到一幅白色图像；随着阈值t的增大，一些黑色区域在图像上出现，这些黑色区域由灰度值小于阈值t的像素组成，称其为局部灰度最小值区域。随着阈值的增大，这些黑色区域会逐渐增长、融合，最终将变成一幅完全黑色的图像。这一系列阈值图像中，每个白色的连通区域都是最大值区域，而那些在多个阈值图像中面积变化率小于一定阈值的极大值区域就是最大稳定极大极值区域（MSER）。

图2 阈值图像

与其它极大值区域不同的是，MSER区域中阈值t从i-Δt变化到i+Δt，对应的极值区域面积变化率最小。因此，MSER区域就是在2Δt邻域的阈值图像中，区域面积近似不变的极值区域。以g代表像素点的灰度值，x代表像素点的位置，g（x）代表像素分布曲线，而R、Rg+Δ、Rg-Δ代表极值区域，采用二维图来代表像素点位置与灰度值的关系（如图3），则依据三个区域的大小与稳定条件能清楚地判断出R是否为极值区域。

2.2 MSER区域特征检测算法流程

MSER算法通过并查算法构造成分树，利用稳定性度量分析成分树来提取MSER区域，主要步骤包括：

1）像素点排序

对图像中所有的像素根据其灰度值按照升序或降序排序。

图3 极值区域二维关系图

2）提取极值区域

利用并查算法提取极值区域，并确定区域面积。然后构造成分树并对嵌套区域进行有效的管理。

3）由成分树判断MSER区域

当某个极值区域沿成分树的某条路径上下移动，以一定的条件判定该区域是否属于MSER区域，判断的依据为阈值变化小于2Δ。

4）区域清理

经过上述步骤可以得到非常多的MSER区域，但部分区域稳定性并不够，因此需要清理掉面积过小或过大以及区域面积变化率过大或过小的区域。

5）不规则区域椭圆化

由上述过程提取出来的不规则MSER区域很难进行特征描述，需利用组成不规则MSER区域的像素灰度值构建二阶中心距，通过二阶中心距将不规则的MSER区域调整为规则的椭圆形区域，下图描述了不规则区域椭圆化调整方法。

图4 不规则区域椭圆化调整

通过以上五个步骤，即可提取出稳定、有效的MSER特征区域。该区域特征具有良好的仿射不变特性，且对于光照变化和噪声干扰也具有较强的鲁棒性。图5中椭圆形的区域即为提取MSER区域。

图5 不规则区域椭圆化调整

3 基于MSER的仿射不变二进制特征提取

MSER仿射不变特征区域提取出来后，需要对区域进行特征描述才能匹配。目前用来表达MSER区域最常用的描述符为SIFT或SURF结构描述符［7，9～10］，以 ORB为代表的二进制特征描述子在时间效率与存储效率方面比SIFT或SURF具有非常大的优势。因此本文讨论基于ORB描述子的MSER特征匹配。本文将基于MSER的仿射不变二进制特征提取算法简称为MSER-ORB算法。

3.1 基于MSER的仿射不变二进制特征提取流程

在上文中获得基于椭圆描述的MSER区域特征后，使用二进制描述子ORB做特征的描述。由于特征描述子为二进制，则可以使用海明距离作为相似性度量来进行特征的匹配，基于MSER的仿射不变二进制特征提取流程描述如图6。

图6 基于MSER的仿射不变二进制特征提取流程图

在以上流程图中描述的过程中，如何对MSER区域特征进行二进制描述是关键，下节将具体介绍。

3.2 基于ORB描述子的最大稳定极值区域描述

MSER特征匹配算法的抗仿射性能是由每一个独立的MSER区域来体现的，每一个MSER区域就是一个独立的仿射不变单元。理想的特征描述子必须能完整地表达整个区域的信息，且该表达不能具有二义性。然而，这样理想的描述子是不存在的，为了使MSER区域的仿射不变性尽可能地得到保持，特征描述子应当最大限度地反映整个区域的真实属性。

由2.2节可知，提取出的不规则的MSER区域通过椭圆调整变成了规则的椭圆形状，对每个椭圆形的MSER区域做如下定义：(Ex，Ey)代表椭圆的中心，a1、a2分别为椭圆长短轴方向的幅值，θ代表长轴的方向，如图7所示。

图7 MSER区域的椭圆表达

而ORB描述子的几个决定性因素包括：特征点的位置eCenter、尺度eScale、主方向eAngle。将MSER椭圆区域转换为ORB描述子，过程如下：

2）获取特征点中心坐标：eCenter=(Ex，Ey)；

3）获取特征点主方向：eAngle=θ。

由此，MSER仿射不变椭圆区域就转换为了ORB可进行描述的特征点。

4 实验与分析

本章通过MSER-ORB与MSER-SURF以及ORB特征的比较实验，验证分析MSER-ORB的相关性能。其中，MSER-SURF是以MSER作为特征检测算子，SURF作为特征描述子，ORB特征是以oFAST作为特征检测子，ORB作为特征描述。主要讨论这三种特征在时空效率、仿射不变性方面的性能。

本研究对图像仿射变形的实验使用的是由牛津大学机器人研究实验室提供的图像特征匹配标准测试数据集［11］中的graf图像组，该组图像由6张不同视角差异的彩色图像组成，图像分辨率为800×600。与第一张图像相比，后续5张图像的拍摄视角与之差异越来越大，图像如图8。

图8 graf仿射不变测试图像序列

实验所有的测试软件均由C++语言在Visual Studio2010平台下编写，计算机为32位Win7系统，处理器为4核Intel i7，4G内存。

4.1 时空效率对比分析

对graf图像序列中的img1与img2做多次匹配，统计MSER-SURF、ORB、MSER-ORB三种特征匹配算法的时间性能，如表1。

表1 三种特征匹配算法耗时统计表（单位：ms）

由上表可以看出，MSER-ORB在特征描述与匹配方面的耗时比MSER-SURF降低19%。然而，由于MSER特征检测比oFAST慢比较多，导致基于MSER特征检测的MSER-ORB与MSER-SURF算法耗时均为ORB的两倍左右。

考虑三种算法的内存消耗，存储一个ORB特征与SURF特征分别需要内存为32与256字节，即MSER-ORB对内存的占用少于MSER-SURF的八分之一。

4.2 匹配效果对比分析

用graf图像序列中的img1分别与img2-6匹配，随着图像视角差异的变大，图像间的仿射变形越大，匹配难度也逐渐增大。MSER-SURF、ORB、MSER-ORB三种算法精匹配点对数统计如表2。

表2 三种算法精匹配点对数统计表

其匹配率描述如下表3。

表3 三种算法匹配率统计表

其匹配正确率描述如表4。

表4 三种算法匹配正确率统计表

由以上表格统计结果可以看出，随着图像视角差异的增大，具有仿射不变性的MSER-SURF及MSER-ORB匹配性能与ORB算法相比的优势原来越明显，其中对于img1-img5及img1-img6图像对，ORB算法匹配失败，而MSER-SURF及MSER-ORB都能得到13对以上的精确的同名匹配点对，由此证明了将ORB算法的oFAST特征检测子替换为具有仿射不变性的MSER特征，有效地提高了其对大视角差异图像匹配的性能，提高了匹配算法的稳健性。

同时，考虑基于MSER仿射不变特征检测的MSER-SURF与MSER-ORB算法，由于SURF描述子考虑了尺度不变性，使基于SURF描述子的特征匹配算法比基于ORB描述子的算法在尺度差异较大的时候有更好的适应性，而图像视角差异过大同时也意味着部分区域的尺度差异较大，如img1-img5与img1-img6，在这两组的匹配实验中，MSER-SURF效果优于MSER-ORB，而在视角差异小的前三组实验中，MSER-ORB的匹配结果优于MSER-SURF。基于MSER-SURF与MSER-ORB的 img1-img5匹配结果展示如下（ORB算法在img1-img5匹配失败）。

图9 img1-img5匹配结果

另外，由于MSER算子检测的特征比oFAST少很多，使得到的精匹配点对数量不多，这在一定程度上制约了后续基于匹配特征的空间模型解算精度。但以MSER为检测子的MSER-SURF与MSER-ORB算法的特征匹配率与匹配正确率绝大多数都由于基于oFAST检测子的ORB算法。

5 结语

本文提出了一种结合MSER特征检测与ORB特征描述的仿射不变二进制特征提取方法。实验表明基于MSER的仿射不变二进制特征提取能有效结合MSER的抗仿射性能与ORB描述子的快速低存储优势，能在满足抗仿射变形的同时获得较高的匹配效率。然而，MSER-ORB景象匹配算法的缺陷是提取的特征较少，当图像在噪声、尺度、旋转等方面的变形太大时，MSER-ORB景象匹配算法适应性较差。