局部特征描述子中的数学原理

孙卓婷 王福龙

摘  要：近十年来，传统的图像检测与匹配算法进入瓶颈期，以深度学习为首的图像特征检测与匹配正展露尖角，将传统算法和深度学习相互融合已是大势所趋。文章简要叙述了几种经典检测算法中特征描述子的生成流程，从数学角度严谨地阐述了局部描述子对图像存在噪声、光照和旋转变化等干扰因素具有良好鲁棒性的原理，并分析讨论了其性能及优缺点。

关键词：局部特征;特征描述子;光照不变性;旋转不变性;PCA

中图分类号：TP391.4      文献标识码：A文章编号：2096-4706（2021）14-00103-06

Abstract： In recent ten years， traditional image detection and matching algorithms have entered a bottleneck period. Image feature detection and matching led by deep learning are showing sharp corners. It is a general trend to integrate traditional algorithms and deep learning. This paper briefly describes the generation process of feature descriptors in several classic detection algorithms， rigorously expounds the principle that local descriptors have good robustness to image interference factors such as noise， illumination， and rotation changes from a mathematical point of view， and analyzes and discusses its performance， advantages and disadvantages.

Keywords： local feature; feature descriptor; illumination invariance; rotation invariance; PCA

0  引  言

近十年来，由于计算机性能不断攀升、海量数据不断涌现，以深度学习为首的学习算法推进了图像配准算法的革新。新的研究表明：图像配准算法正从手工选择特征向从数据中学习特征过渡，将学习算法和具有实时性和一定数学理论支撑的传统图像配准算法融合，有助于该领域的改革和创新。因此用数学原理详细解释近些年经典特征检测算法中的特征描述子的各个特性以及优缺点，可以为更好地解决复杂环境下获取图像特征的问题提供坚实的理论基础。

图像的局部特征相较于全局特征更能获取受各种干扰因素影响的真实图像特征，所以往往使用图像局部特征进行匹配。这个局部特征作为匹配过程的基础，应与其他区域具有强区分度。特征点作为图像稳定的稀疏特征，含有该特征点在图像中的位置、朝向、大小等结构信息，在基于点特征匹配算法中起着不可替代的作用。从特征点周围取一个图像块，将其转换成更小的数据集，这个新的数据集称为图像块的“局部描述子”，反映着特征点周围像素的信息，通常用特征向量来表示，用于比对。一个优秀的局部描述子还应可以鲁棒地处理各种图像变换的情况，因此构建局部描述子时，不变性成了其核心问题，在实际匹配中，需要考虑特征描述子的尺度不变性、视角变化不变性、旋转不变性以及光照不变性等。基于梯度直方图及基于局部二进制特征的描述是局部特征描述子主要方法。

1  基于梯度直方图的局部描述子

基于梯度直方图的局部描述子，顾名思义，是利用梯度幅值对特征点邻域内的梯度方向加权统计，从而生成梯度方向直方图来构造特征描述子的一种方法。该方法所构造的特征将整幅图像进行分块处理，对图像局部区域的位置和空间进行量化，使得图像局部像素点直接的差异信息明确，并且在对直方图进行归一化后，一定程度上可以消除光照影响，使得图像数据维度降低。但因其核心是获取梯度，因此计算量大。

1.1  SIFT

尺度不變特征变换（Scale-invariant feature transform， SIFT）[1]，是Lowe等在2004年提出的用于图像处理领域的一种描述子。该算法生成特征描述子流程如下：首先为特征点邻域像素的梯度幅值和方向确定一个主方向，这是为了让描述子具有旋转不变性。然后将坐标轴旋转到对应的主方向，并在主方向上取特征点周围的22个邻域，每个邻域内含44个像素，再把360度的幅角范围进行8等分，计算每个邻域上8个方向的梯度方向直方图，生成一个分块区域，如图1所示。为了增强描述子的鲁棒性，Lowe建议用44共16个分块区域，因此每个特征点生成一个128维的SIFT特征，且该特征向量具有尺度和旋转不变性。

最后，为了获得光照不变性，特征描述子由分量平方之和的平方根归一化（即L2范数），其数学原理为：

由此可见，对于数字图像经线性变换前后，其梯度方向不变，对应的梯度幅值增大为原来的a倍。而SIFT描述子是由特征点邻域内的像素点的梯度方向和梯度幅值以加权累加方式组成，即在变换前后的两个特征向量只差一个常数倍，即这两个特征向量共线，用L2范数归一化后结果相同，从而消除了光照对该描述子的影响。

1.2  PCA-SIFT

PCA-SIFT[4]，Ke等于2004年提出通过主成分分析（Principal Component Analysis， PCA），将SIFT的128维特征描述向量做去相关处理，从而达到降维目的。该算法流程为：首先按特征点主方向，在特征点周围选取一个41×41矩形邻域，计算其水平和垂直两个方向的偏导数，得到39×39×2=3 042维的向量（最外层像素不计算偏导数），并对其归一化处理。此时，所有特征描述子向量构成一个k×3 042大小的描述子矩阵（其中k为特征点数目）。接着，计算该矩阵的协方差矩阵及矩阵对应的特征值和特征向量。在这个步骤里，需要对特征值的大小进行降序排列，选取前n个特征值对应的特征向量，组成一个n×3 042大小的投影矩阵。最后，对投影矩阵与描述子矩阵作乘法，即可实现降维，且降维后的矩阵大小为k×n。该算法巧妙地将SIFT特征和PCA方法相结合，不仅弥补了SIFT特征维数过大的缺陷，还滤除了描述子向量中大量干扰信息。

PCA是通过“去冗余”和“降噪”来达到降维目的。“去冗余”是指使保留下来的维度中方差尽可能大，“降噪”是指使保留下来的维度间的相关性尽可能小。协方差矩阵恰恰是度量维度间关系的工具，其主对角线上的元素是各个维度的方差，非对角线元素是两两维度间的协方差。换句话说，PCA降维问题可转换为使协方差矩阵中非对角线元素都基本为零的问题。这就需要找到一个转换矩阵，使得新的协方差矩阵能够尽量地对角化。而对于一个n阶对称矩阵，必定存在正交矩阵P，使得：

P-1AP =PTAP =Λ                            （7）

其中，Λ是以A的n个特征值为对角元的对角矩阵[5]。P是特征值对应的特征向量矩阵并正交化所得。协方差矩阵A恰恰是一个对称矩阵，这便是PCA降维过程中，选择协方差矩阵的原因。

特征向量矩阵P就是PCA-SIFT中提及的“投影矩阵”，它是正交矩阵，基向量两两正交，说明两个向量相关性很小，数据在这两个维度上的相关性很小，这样的特性也更加印证了投影矩阵选择的正確性。

对角矩阵Λ对角线上的元素还是各个维度上的新方差，并且有tr（Λ）>tr（A），这是因为通过对角化后，各个维度间的相关性已经减到最弱，噪声和冗余的数据被删减，每个维度本身拥有的方差自然比之前大。而对角线上较小的新方差则是冗余的维度，这就是PCA-SIFT描述子构造投影矩阵时选择前若干个最大特征值所对应的特征向量的原因。新的协方差矩阵Λ1是以前若干个最大特征值为对角元的对角矩阵。

1.3  GLOH

梯度位置方向直方图（Gradient Location-Orientation Histogram， GLOH）[6]，是K. Mikolajczyk于2005年提出的SIFT描述子的变体，通过圆形划分取代SIFT的方形并用PCA降维来提高其独立性和稳健性。具体体现在：GLOH计算SIFT描述子中4×4的网格邻域改成对数极坐标下半径分别为6、11、15的同心圆。每层同心圆按角度方向分为8等分，共生成17个子块（第一层没有按角度划分），如图3所示。在每个子块中计算梯度方向直方图，梯度方向分为16个区间，因此生成一个17×16=272维的特征向量。受PCA-SIFT启发，通过投影矩阵对每个特征点作PCA降维处理，最终得到一个128维的特征向量。

图像f（x，y）到g（ρ，θ）的对数极坐标变换定义[7]为：

其中，ρ表示对数极坐标的极径，θ表示角度，（xc，yc）是笛卡尔坐标系的变换中心，在SIFT特征中该变换中心相当于特征点，（x，y）表示笛卡尔坐标系的像素点，在SIFT特征中指特征点邻域内的像素点。

对数极坐标是对人眼的仿生模拟。人眼的中心凸起有聚焦的作用，即视焦点区域清晰，外围逐渐模糊。对数极坐标下的像素都分布在原点（在GLOH特征中指特征点）附近，随着极径的增大，越远离中心点的区域分辨率越低，从而简化了图像。可以将该变换看作对图像作了如图4的滤波，也就是说，GLOH相当于通过对数极坐标变换对离特征点较近的像素点做了一次加权处理，因此其计算复杂度会增大。

由式（9）可见，图像在笛卡尔坐标系下的旋转和尺度变换，在对数极坐标下，相应的转化为沿θ轴和ρ轴上的位移。即对数极坐标具有旋转不变性和尺度不变性。由此可见，在对数极坐标系下的人眼仿生模拟特性以及旋转不变性使得GLOH特征描述子在生成过程中，计算复杂度增加，但可以不需要特征点的主方向。

1.4  SURF

加速稳健特征（Speeded Up Robust Features， SURF）[8]，是Herbert Bay于2006年提出的SIFT算法加速版。具体体现在：在特征点检测上，采用了积分图像和快速hessian矩阵检测技术提高计算速度。在生成特征描述子过程中，surf特征仿照SIFT特征的思想，通过对每个特征点建立一个主方向以保证其选择不变性，只是选取主方向的方式不同：surf特征首先利用积分图像加权计算特征点周围半径为6σ（σ为尺度）的圆域内像素的水平和垂直方向的Haar小波响应（边长为4σ）。再以特征点为中心，将张角为60°的扇形区域内的响应累加得到一个矢量，按此过程遍历整个圆，如图5（a）所示，取最长矢量为主方向。然后，将坐标轴旋转到主方向，在特征点附近取一定大小的矩形区域，分成4×4个分块区域，每个分块区域以σ为步长取5×5个采样点，根据距离中心点的远近加权计算两个方向的haar小波响应，如图5（b）所示。最后统计响应值∑dx，∑dy，∑|dx|，∑|dy|形成特征向量，得到4×4×4=64维的SURF特征描述子。SURF特征具有和SIFT特征相近的性能，如尺度、旋转和光照不变性，但维数却大大减少，在对匹配精度要求不是非常高的实际应用中，SURF更能做到实时性。

1.5  DAISY描述子

DAISY特征描述子是由Tola[9]等人于2008年提出的面向稠密特征提取的可快速计算的特征描述子。不同于SIFT和GLOH特征分块统计梯度方向直方图，DAISY特征采用高斯卷积进行梯度方向直方图加权，即在特定方向上与多个高斯滤波器进行卷积，利用高斯滤波函数性质中的可分离性，可以大大提高计算效率。DAISY描述子用类似“雏菊”的结构来替换SIFT描述子中的矩形邻域，如图6所示，围绕着特征点，每8个蓝色采样点以45°为间隔建立一层同心圆，各个采样点分布在同心圆环上，不同高斯尺度建立不同大小的同心圆环，越外层，高斯尺度值越大。每个圆圈代表一个直方图区域，各向同性的高斯核和圆形网格相结合，使得图像发生旋转时，特征点附近的像素不会变化，在直方图上表现为直方图柱子顺序的改变，因此不需要像SIFT特征一样计算特征点的主方向来保持描述子的旋转不变性，可以直接用其结构中第二层梯度直方图来判断方向[10]。

根据这个表达式可知，图像与高斯核做卷积运算时，可以先和水平方向上的一维高斯核计算，再和垂直方向上一维高斯核进行计算，最终输出图像。

由此可见，DAISY特征通过改进SIFT的分块策略，利用高斯卷积的可分离性进行梯度方向直方图的分块汇聚，对每个特征点的计算量由平方阶降为线性阶，大大提高了计算效率，从而快速稠密地提取特征描述子。

2  基于局部二进制的描述子

基于梯度直方图的局部描述子对图像各种变换（旋转、缩放、遮挡）具有完全或部分的鲁棒性，但为获取梯度而进行的大量计算以及其丰富的浮点型描述子信息所需的大量存储空间，使得它不能在实时应用场景中使用。随着移动设备运行需要的不断增长，二进制局部描述子应运而生，该描述子生成简单，所需存储空间小，在进行特征匹配时，匹配速度远超浮点型描述符。

2.1  BRIEF

BRIEF（BinaryRobust Independent Elementary Features）[12]描述子由Michael Calonder等人于2010年提出，该算法是使用二进制针对已经检测到的特征点进行编码的描述子，摈弃了传统的梯度直方图描述特征点方法，把局部描述子的简化做到了极致。它以特征点为中心选取一块方形区域，先对该区域做平滑处理，过滤掉冗余信息，再在该区域内以某种特定的方式选择若干个像素点对（点对两个像素间的顺序以及点对顺序不再更改），然后比较像素点对的灰度值，最后将所有点对的比较结果按特定的顺序排列，形成一串二值编码，该编码即该特征描述子唯一匹配码。但由于仅采用单像素点的灰度值进行判断，因此不具备旋转不变性和尺度不变性。

2.2  ORB

ORB（Oriented FAST and Rotated BRIEF）[13]是由Ethan Rublee等人于2011年中提出的将FAST特征检测与BRIEF特征描述相结合的一种新的特征提取和描述的算法。主要针对BRIEF不具备旋转不变性进行改进，即计算特征点以一定半径范围内的质心，特征点坐标到质心形成一个向量作为该特征点的方向，从而解决旋转不变性的问题。除此之外，它还使用数据学习的方法来替代手工选择像素点对。而事实上，传统特征算法自2010年后与学习算法之间的界限变得模糊，而学习算法依赖数据的特性，使得混合使用手工标注的描述子和学习算法成为趋势。

2.3  BRISK

BRISK（Binary Robust in Variant Scalable Keypoints）[14]是2011年由Leutenegger等人提出的根据像素值间的比较结果生成的二进制字符串，其采样模板受DAISY特征启发，采用与不同于DAISY特征的采用方式，即以特征点为中心，对特征点周围若干个点进行均匀采样形成同心圆环，再分别进行不同的高斯平滑，以取代DAIYSY特征的8点采样，如图7所示，蓝点为采样位置，红圈大小反映高斯平滑程度。

这些二进制描述子中每对像素点进行灰度比较后仅生成一个二进制位，可以表示每对像素点的差异，但差异指向并不明确，因为灰度值相差较高和较低的两对像素点的比较结果是相同的，从而可能导致丢失感兴趣区域中的纹理信息。因此二进制描述子对噪声十分敏感。

3  結  论

图像获取技术的迅猛发展使得采集的图像信息越来越复杂丰富，传统手工选择的特征检测与匹配算法总是基于各种前提假设对庞大的数字图像信息进行简化，因此不具备很好的泛化能力。近十年来，传统的图像检测与匹配算法进入瓶颈期。以深度学习为首的图像特征检测与匹配正展露尖角。但因为深度学习所需的普适性的数据集难以获取，且其计算量十分庞大。因此将传统算法和深度学习相互融合成为趋势，使得该技术同时具有实时、泛化能力。而这一切的前提需要完备的数学理论做支撑，因此，本文选取了具有代表性几种特征描述子，简要叙述了其生成流程，并对里面提及的性能进行详细数学原理的分析，意在期望更多研究者透彻了解传统特征描述子，以此推动这一课题的发展。

参考文献：

[1] LOWE D G. Distinctive Image Features from Scale-Invariant Keypoints [J].International Journal of Computer Vision，2004，60（2）：91-110.

[2] LAX P D.泛函分析 [M].侯成军，王利广，译.北京：人民邮电出版社，2010.

[3] MAITRE H，等著.数字图像处理 [M].孙洪，译.北京：电子工业出版社，2009.

[4] KE Y，SUKTHANKAR R. PCA-SIFT：a more distinctive representation for local image descriptors [C]//Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington：IEEE，2014：506-513.

[5] 刘仲奎，杨永保，程辉，等.高等代数 [M].北京：高等教育出版社，2003.

[6] MIKOLAJCZYK K，SCHMID C. A performance evaluation of local descriptors [C]//2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2003.Proceedings.Madison：IEEE，2005：1615-1630.

[7] 冉洪成.基于对数极坐标的图像匹配综述 [J].现代计算机，2020，4（4）：65-69.

[8] BAY H，ESS A，TUYTELAARS T，et al. SURF：Speeded up robust features [J].Computer Vision and Image Understanding，2008，110（3）：346-359.

[9] TOLA E，LEPETIT V，FUA P. DAISY：An Efficient Dense Descriptor Applied to Wide-Baseline Stereo [J].IEEE Trans on Pattern Analysis and Machine Intelligence，2010，32（5）：815-830.

[10] FISCHER J，RUPPEL A，WEISSHARDT F，et al. A rotation invariant feature descriptor O-DAISY and its FPGA implementation [C]//https：//ieeexplore.ieee.org/xpl/conhome/6034548/proceeding.San Francisco：IEEE，2011：2365-2370.

[11] LINDEBERG T. Scale-space theory： a basic tool for analyzing structures at different scales [J].Journal of Applied Statistics，1994，21（1-2）：225-270.

[12] CALONDER M，LEPETIT V，STRECHA C，et al. BRIEF：Binary Robust Independent Elementary Features [C]//Computer Vision–ECCV.Springer-Verlag，2010：778-792.

[13] RUBLEE E，RABAUD V，KONOLIGE K，et al. ORB：An efficient alternative to SIFT or SURF [C]//2011 International Conference on Computer Vision. Barcelona：IEEE，2011，58（11）：2564-2571.

[14] LEUTENEGGER S，CHLI M，SIEGWART R Y. BRISK：binary robust in variant scalable keypoints [C]//2011 International Conference on Computer Vision.Barcelona：IEEE，2011：2548-2555.

作者簡介：孙卓婷（1996—），女，汉族，广东惠州人，硕士在读，研究方向：图像处理、模式识别;王福龙（1968—），男，汉族，广东广州人，教授，博士，研究方向：图像处理、模式识别和智能控制及应用。