近年来，局部图像描述符凭借其优越的特性和广泛的应用领域，成为计算机视觉和图像处理领域的一个研究热点^[1]。相对于图像的全局描述方法，局部图像描述符在抗遮挡、抗大的几何和光度畸变等方面具有更优越的性能，其已成功于机器人视觉导航^[2]、图像搜索^[3]、图像分类^[4]、视频时空分析^[5]、从运动恢复结构^[6]等应用场合。

最早成功应用于计算机视觉和图像理解的局部图像描述符就是Dowe提出的SIFT(scale invariant feature transform)描述符^[7]。其把局部图像块分为4×4个小块，提取每个小块中每个像素的8个方向梯度特征并统计每个小块中各个方向梯度特征的分布，得到128维的梯度特征空间分布直方图。针对SIFT描述符，后人提出了很多改进和优化。Ke和Sukthankar^[8]利用PCA(principal components analysis)方法对SIFT描述符进行了维度约简得到PCA-SIFT。Bay等人^[9]提出了SURF(speeded-up robust features)描述符，其利用哈尔滤波和积分图像提高了梯度特征的计算速度。Tola等人^[10]提出的DAISY描述符采用了不同于SIFT的区域分块方法，其首先把兴趣区域分割为多个相互重叠的圆环，再把每个圆环分割为多个相互重叠的圆。为了获得最佳的空间分割，Simonyan等人^[11]提出了采用凸优化学习方法的空间分割汇聚策略。为了获得更精简的描述符，Trzcinski等人^[12]提出了基于Boost的二进制描述符学习方法。SIFT及其变体只利用了一阶梯度特征，Huang等人^[13]提出了基于二阶梯度特征的HSOG(histograms of the second-order gradient)描述符。

梯度特征受非线性光照影响很大，所以研究者提出了其他鲁棒特征。Ojala等人^[14]最早提出了局部二进制模式(LBP)并用于纹理分类。由于LBP模式维度很高，直接用于局部图像描述符构建会导致描述符维数太高。所以，LBP最早主要用于纹理分类、目标检测和人脸识别等领域。为了使LBP能用于局部描述符，Heikkila等人^[15]提出了一种LBP变体：局部对称二进制模式(CS-LBP)，其维度大大降低，并利用SIFT的图像块分割方法进行空间汇聚得到CS-LBP描述符。为了提高LBP的辨别性和鲁棒性，Tan等人^[16]把LBP扩展为局部三进制模式(LTP)。随后，Gupta等人^[17]提出了和CS-LBP类似的CS-LTP，并和相对强度直方图(HRI)级联得到HRI-CSLTP描述符。

上面提及的局部描述符都是利用像素的图像坐标位置把局部图像块分为多个子图像块，再对每个子图像块中的局部特征进行空间汇聚得到局部特征的空间统计直方图。这种空间汇聚方法需要计算图像块的主方向以保持局部描述符的旋转不变性，而主方向的计算是不精确的。像素的强度序^[18]对图像旋转保持内在的不变性，Fan等人^[19]利用像素的强度序进行空间分割，并提出了利用局部旋转不变坐标系计算CS-LBP特征和在多个支撑区域中计算局部描述符，从而得到MRRID(multisupport region rotation and intensity monotonic invariant descriptor)描述符。CS-LBP特征仅编码中心像素和所有周围像素间强度差值的符号，从而使得CS-LBP特征对非线性光照影响较小，所以相对于SIFT描述符的梯度特征其非线性光照鲁棒性更高。但在计算CS-LBP特征时任何一个差值符号的改变都会使CS-LBP模式发生变化，而图像噪声和几何畸变会使原图像区域和畸变图像区域对应位置像素强度发生较大的变化从而引起强度差值符号的改变，所以导致CS-LBP模式对噪声和几何畸变鲁棒性低。

本文提出了一种新的局部特征：最大边缘方向模式(MEOP)。与CS-LBP一样，其计算中心像素和周围像素强度间的差值。但MEOP仅编码最大强度差值，所以只要最大强度差值的位置和符号不出现改变，MEOP模式就不会发生改变。最大强度差值表示图像局部领域的最强边缘处，其稳定性一般较高，因此MEOP模式的鲁棒性较高。和MRRID描述符相似，利用局部旋转不变坐标系计算MEOP模式，并利用强度序空间分割方法和多支撑域方法得到新的局部图像描述符：最大边缘方向模式直方图(MEOPH)。相对于利用CS-LBP局部特征的MRRID描述符相比，MEOPH描述符不仅在鲁棒性方面有超越的性能，在辨别性方面也表现更好。

最大边缘方向模式寻找周围像素和中心像素间最大强度差值，对其位置和符号进行编码。在局部领域中与中心像素呈现最大强度差值的像素代表最强边缘处。最大强度差值的所在像素位置描述了径向方向，差值的符号描述了径向方向的朝向(中心向外或指向中心)。为了使最大边缘模式具有旋转不变性，采用文献[19]的局部旋转不变坐标系统。图 1给出了用于计算最大边缘方向模式的局部旋转不变系统。$P$为局部不变特征检测子提取的兴趣点，$x_c$为支撑域中一个的采样点。$\mathit{\boldsymbol{P}}{\mathit{\boldsymbol{x}}_\mathit{\boldsymbol{c}}}$为$P$指向$x_c$的向量，把其设定为正$y$轴，再把$\mathit{\boldsymbol{P}}{\mathit{\boldsymbol{x}}_\mathit{\boldsymbol{c}}}$沿顺时针方向旋转90°得到正$x$轴。以$x_c$为中心的半径为$R$的圆上采样$N$个点，起始点$x_1$位于正$x$轴上。$N$的大小表示径向角度划分的分辨率。$R$表示最大边缘方向模式中圆形周围像素和中心像素之间的距离，其取不同的值表示不同的尺度。

局部旋转不变坐标系和原始图像坐标系之间的夹角计算为

${\theta _c} = {\rm{ta}}{{\rm{n}}^{ - 1}}(x_c^y/x_c^x)$

(1)

$x_c^x$和$x_c^y$分别表示像素点$x_c$在原始图像坐标系上的$x$坐标和$y$坐标。则${x_c}{x_i}$与原始图像坐标系$x$轴的夹角为

${\theta _k} = {\theta _c} + 2{\rm{ \mathsf{ π} }}\left( {k - 1} \right)/N$

(2)

则像素点$x_k$在原始图像坐标系下的坐标计算为

$x_k^x = x_c^x + R \cdot {\rm{cos}}({\theta _k})$

(3)

$x_k^y = x_c^y + R \cdot {\rm{sin}}({\theta _k})$

(4)

则采样像素点和周围像素之间最大强度差值的位置标号和符号为

$p({x_c}) = \mathop {{\rm{max}}}\limits_k \{ {\rm{abs}}(I({x_k}) - I({x_c})),k = 1, \cdots ,N\} $

(5)

$s({x_c}) = sign(I({x_k}) - I({x_c}))$

(6)

$sign\left( x \right) = \left\{ {\begin{array}{*{20}{l}} 1&{x ＞ 0}\\ 0&{其他} \end{array}} \right.$

(7)

则采样像素点的最大边缘方向模式计算为

$f({x_c}) = N \cdot s({x_c}) + p({x_c})$

(8)

$f({x_c})$的取值范围为[1，2$N$]，所以$N$个周围采样点数的最大边缘方向模式共有$k$=2$N$种模式。最后，把$f({x_c})$映射为$k$维的向量，得到最大边缘方向模式特征为

$\mathit{\boldsymbol{MEOP}}({x_c}) = \left( {{F_1}({x_c}),{F_2}({x_c}), \cdots ,{F_k}({x_c})} \right)$

(9)

${F_j}({x_c}) = \left\{ {\begin{array}{*{20}{l}} 1&{f({x_c}) = j}\\ 0&{其他} \end{array}} \right.$

(10)

在CS-LBP特征中，任何一个差值的正负发生改变都会影响其模式的变化。所以，相对于CS-LBP，MEOP会更稳定，抗噪声能力更强。只要最大强度差值的位置和符号保持不变，MEOP的值就保持不变。图 2给出了局部领域强度值发生[-10, 10]范围内数值变化时，CS-LBP和MEOP模式的变化。图 2(a)中短虚线箭头的指向表示CS-LBP模式中像素强度差值的符号，如果图 2(b)的差值符号和图 2 (a)相同，则用短虚线表示，不同则用实线表示。从图 2可以看出：相对于图 2(a)，图 2(b)的1个箭头指向发生了改变。因此，相应的CS-LBP模式也发生了改变。图 2(c)中长虚线及箭头的指向表示MEOP模式中最大强度差值位置和符号，其他7个带箭头的短虚线表示其他7个周围像素和中心像素间强度差值符号。如果图 2(d)中周围像素和中心像素差值符号和图 2(c)相同，则用短虚线表示，不同则用实线表示，最大强度差值仍用长虚线表示。相对于图 2(c)，图 2(d)有4个箭头指向发生了改变。长虚线的位置和方向未发生改变，所以MEOP模式也未发生改变。所以即使有4个位置的强度差值的符号发生变化也没有影响MEOP模式。MEOP除了具有比CS-LBP更稳定的特性外，与CS-LBP还存在一定的互补特性。二者描述的模式不一样：CS-LBP描述中心对称的4个方向二进制强度差值模式；MEOP描述8个方向的最大强度差值模式。CS-LBP编码固定位置像素对之间的强度差符号，不编码最大差值，而MEOP仅编码最大差值。后面的实验也证实了该特性。

由于强度序具有旋转不变性和单调强度不变性，近年来被用于局部描述符的空间分割。相对于SIFT中采用的网格空间划分方法，强度序空间分割具有内在的旋转不变性，所以其不需要计算图像块的主方向以及使图像块绕主方向旋转。强度序空间分割流程为：对图像块中所有像素点的强度值进行排序，然后根据每个像素的强度序值，划定他们归属于那个强度序区间。设图像块共包含$n$个像素点，空间分割的区间数目为$d$，则划分的空间可表达为

$\begin{array}{l} \quad \quad \quad \quad \mathit{\boldsymbol{R}}{_i} = \{ {x_j} \in \mathit{\boldsymbol{R}}|\\ n \times \left( {i - 1} \right)/d \le O(I({x_j})) \le n \times i/d\} \end{array}$

(11)

式中，$\mathit{\boldsymbol{R}}$表示支撑区域，$O(I({x_j}))$表示像素点$x_j$的强度序。

为了使局部图像块保持尺度不变性或仿射不变性，需要对检测的兴趣区域进行归一化，得到标准的局部图像块(大小一般为41×41像素的圆形区域)。该归一化区域也称为支撑域。不同场景的局部图像区域可能会出现相似的外观特性，但多个尺寸不同的局部图像区域联合呈现相似外观的概率会更小，所以文献[19]提出了多个支撑域描述符MRRID，其辨别性大大高于单一支撑域的局部描述符。文献[19]的实验得出如下结论：具有内在旋转不变性的描述符在多支撑域条件下可大大提高性能，但通过计算主方向并对图像块进行旋转而获得旋转不变的描述符(如SIFT)在多支撑域条件下获得的性能提高非常有限。和MRRID一样，本文的MEOPH采用强度序空间汇聚策略，局部特征MEOP也在局部旋转不变坐标系下计算，也具有内在旋转不变性，所以采用多支撑域可大大提高描述符的性能。图 3 (a)由Hession仿射不变区域检测子检测到的4个大小不同的椭圆区域，图 3(b)—(e)分别为归一化后的4个支撑区域。

图 3给出了MEOPH的构建过程，首先在每个支撑域上分别计算MEOP特征和强度序空间分割。图 3 (f)为可视化的MEOP特征，$k$个值用不同的灰度级表示。图 3 (g)为利用强度序把整个支撑域分割为多个子区域。

由于受几何畸变影响，离兴趣点越近的最大边缘方向模式越稳定。所以，不同空间位置的最大边缘方向模式对描述符的贡献是不一样的。和SIFT描述符一样，采用高斯函数对MEOP特征进行加权。统计每个空间分割区域中加权MEOP特征数目为

$\mathit{\boldsymbol{D}}{_i} = \sum\limits_{{X_j} \in {\mathit{\boldsymbol{R}}_i}} {\mathit{\boldsymbol{MEOP}}\left( {{X_j}} \right) \cdot W\left( {{X_j}} \right)} $

(12)

$W\left( {{X_j}} \right) = {\rm{exp}}\left( { - \frac{{{r^2}\left( {{X_j}} \right)}}{{2{\delta ^2}}}} \right)$

(13)

式中，$r$函数表示采样点距离支撑域中心点的距离。$\delta $是高斯函数的标准差。在一个支撑域上对$d$个$D_i$向量进行级联，即

$\mathit{\boldsymbol{de}}{\mathit{\boldsymbol{s}}_j} = (\mathit{\boldsymbol{D}}{_1},{\mathit{\boldsymbol{D}}_2}, \cdots ,{\mathit{\boldsymbol{D}}_d})$

(14)

对上述向量进行归一化。设共有$m$个支撑域，把所有支撑域上计算得到的描述符向量进行级联，得到最后的描述符为

$\mathit{\boldsymbol{MEOPH}} = (\mathit{\boldsymbol{de}}{\mathit{\boldsymbol{s}}_1},\mathit{\boldsymbol{de}}{\mathit{\boldsymbol{s}}_2}, \cdots ,\mathit{\boldsymbol{de}}{\mathit{\boldsymbol{s}}_m})$

(15)

采用广泛应用于局部图像描述符评价的牛津大学标准图像匹配数据集^[20]对本文方法进行了测试。该数据集包含了视角变换、图像模糊、图像压缩、光照变化、旋转和尺度变换这6种变换下的图像序列。图 4给出了评价描述符图像匹配性能所采用的6组图像数据。每组数据有6幅图像，第1幅为基准图像，其余5幅为对上述变换后的图像，从第2幅到第6幅其图像变换强度逐步加大。第1组Leuven序列为光照变化，第2组Boat序列为旋转和尺度变化。第3组UBC序列为JPG图像压缩。第4组Bikes序列为结构图像的模糊变化。第5组Wall序列为纹理图像的视角变化。第6组Graffiti序列为结构图像的视角变化。

采用和文献[20]一样的性能评价方法，匹配结果用查全率-查错率曲线表示，其定义为

$recall = \frac{{{N_c}}}{N}$

(16)

$1 - precision = \frac{{{N_f}}}{{{N_M}}}$

(17)

式中，$N_c$表示正确匹配数，$N$表示图像对中所有的对应特征数目。$N_f$表示错误匹配数，$N_M$表示全部匹配数。为了公平地对局部图像描述符进行性能对比，采用广泛应用于局部图像描述符性能评价的区域检测子。和文献[20]一样，采用Hession仿射不变区域检测子^[21]来评价局部描述符的性能。

MEOPH描述符有3个参数：MEOP模式数目$k$，强度序分组数目$d$，多支撑域数目$m$。一般而言，MEOP模式数目、强度序分组数目和多支撑域数目越大，描述符的辨别性就越高。但辨别性太高会导致描述符的鲁棒性下降，而且会导致描述符的维数增加。所以，需要合理设置这3个参数。本文采用Graffiti序列研究这3个参数对描述符性能的影响。如表 1所示，对这3个参数取值的各种组合(参考主流描述符的维数，各种参数组合使得MEOPH的维数控制在96维至384维之间)进行了MEOPH的图像匹配实验。从图 5可以看出，$k$=12，$d$=4，$m$=2(96)；$k$=12，$d$=6，$m$=2(144)；$k$=16，$d$=4，$m$=2(128) 和$k$=16，$d$=6，$m$=2(192) 的匹配性能明显较差。$k$=12，$d$=4，$m$=4(192)；$k$=12，$d$=6，$m$=4(288)；$k$=16，$d$=4，$m$=4(256) 和$k$=16，$d$=6，$m$=4(384) 这4个性能相差很小，其中$k$=12，$d$=4，$m$=4(192) 稍差一些。所以综合匹配性能和维数，本文采用$k$=16，$d$=4，$m$=4(256) 的参数设置。

为了评价提出的MEOPH描述符的优越性能，选择了相关的主流描述符进行了图像匹配对比实验。这些相关的主流描述符包含SIFT、DAISY、CS-LBP、HRI-CSLTP和MRRID。其中，SIFT是目前最流行的、最广泛应用的局部描述符，其采用梯度特征。DAISY也采用梯度特征，但相对于SIFT，其采用了改进的空间分割方法。CS-LBP采用局部二进制模式。HRI-CSLTP采用局部三进制模式。MRRID也采用局部二进制模式，但在局部旋转不变坐标下计算。实验结果如图 6所示。从图 6可以看出，本文的MEOPH和MRRID获得了最好的性能，大大优于其他的局部描述符，在大多数情况下MEOPH的图像匹配效果要稍好一些。MEOPH在所有测试数据集上的匹配性能都优于SIFT、DAISY、CS-LBP和HRI-CSLTP。MRRID除在Boat 1-5上的匹配性能稍逊于DAISY和HRI-CSLTP外，其他情况下都优于SIFT、DAISY、CS-LBP和HRI-CSLTP。查全率-查错率曲线对描述符的辨别性和鲁棒性进行综合评价，一个优秀的描述符应同时具备一定的辨别性和鲁棒性。MEOPH在Boat 1-5、Wall 1-5和Ubc 1-5情况下的匹配性能都大大优于MRRID，而MRRID仅在Leuven 1-5情况下的匹配性能大大优于MEOPH，其他情况下二者匹配性能都相当。所以综合考虑，MEOPH的总体匹配性能要稍优于MRRID。

为了评价描述符的抗噪声性能，分别对牛津大学数据集的基准图像加不同级别的高斯噪声，得到基准图像—加噪图像对，如图 7所示。另外，对牛津大学数据集的变形图像再叠加高斯噪声，得到基准图像-变形加噪图像对。限于篇幅限制，图 8给出了Bikes和Wall图像序列的实验结果，其他图像序列得到相似的结果。从图 8(a)—(d)可以看出，在单独高斯噪声条件下，MEOPH的匹配性能大大优于MRRID，且噪声级别越大二者性能相差越大；从2.2节实验可以看出，在不加噪声情况下MEOPH和MRRID在Bikes 1-3和Wall 1-3图像对上匹配性能是相当的，但从图 8(e)(f)可以看出，在这些图像对上加入高斯噪声后MEOPH的匹配性能则大大优于MRRID。所以，在抗噪声性能方面MEOPH描述符要大大优于MRRID。

为了评价最大边缘方向模式在描述图像局部结构上和局部二进制模式具有互补的统计特性，本文把MRRID和MEOPH描述符向量进行简单的级联，得到LBP-MEOP描述符。由于MRRID和MEOPH描述符都是256维向量，所以LBP-MEOP描述符有512维。由于LBP-MEOP的维数太高，我们对仅采用2个支撑域的MRRID(2) 和MEOPH(2) 进行级联得到了256维的LBP-MEOP(2) 描述符。限于篇幅限制，图 9给出了部分图像对的匹配结果，牛津数据集中的其他图像对也得到相似的结果。由图 9可以看出，级联的LBP-MEOP(2) 描述符匹配性能大大优于单独的MRRID(2) 和MEOPH(2)。为了进一步突出LBP-MEOP(2) 的优越性能，图 9的匹配曲线中还包括了4个支撑域的MEOPH。从图 9中可以看出，LBP-MEOP(2) 的匹配性能超越了MEOPH。MRRID采用局部二进制模式作为其空间汇聚的局部特征，而MEOPH描述符采用最大边缘方向模式。由2.1节给出的2种模式分析可知，2种模式描述图像的局部结构特征是完全不一样的，所以2种模式在表达图像的局部结构方面具有较大的互补性。所以，互补性实验证明了本文提出的描述符具有独特性，和现有的描述符具有不同的统计特性。

最后，对MEOPH描述符的平均运行时间进行了评价，结果如表 2所示。所有描述符在主频为2.2 GHz的Intel Core 2 Duo T6600笔记本电脑上计算。从表 2可以看出，多支撑域描述符的计算时间远远大于其他的单支撑域描述符。2个多支撑域描述符MRRID和MEOPH的计算时间差不多。单支撑域描述符中HRI-CSLTP的计算时间最长，CS-LBP的计算时间最短。

本文提出了一种新的局部特征：最大边缘方向模式，利用该新特征得到了新的局部描述符MEOPH。实验结果证实了MEOPH的有效性和优越性能。在图像匹配评价实验中，MEOPH描述符的匹配性能大大高于SIFT、DAISY、CS-LBP和HRI-CSLTP，在大多数情况下MEOPH要优于MRRID，但在抗噪声性能方面MEOPH远远优于MRRID。另外，MEOPH和MRRID具有很大的互补性，在二者联合情况下性能大大增强。所以，MEOPH可以适应复杂环境下的局部描述符匹配场合。另外，其还可以配合MRRID一起使用提高其匹配性能。下一步的研究工作将把MEOPH拓展到3D描述符。