改进SIFT算法在文字图像匹配中的应用

胡海青，谭建龙，朱亚涛，龚国成，刘金刚

(1.首都师范大学计算机科学联合研究院，北京 100037；2.中国科学院计算技术研究所，北京 100190；3.河北农业大学信息科学与技术学院，河北 保定 071000)

1 概述

图像匹配是计算机视觉和模式识别领域的一个重要分支，也是目前研究的热点。随着智能手机的普及，在手机上装卸载程序成为手机用户不可或缺的需求。对于手机生产商而言，检测手机能否成功安装相应程序，是手机检测的重要部分，而原有的人工检测方式需消耗大量的人力，因此，开发自动检测手机程序运行状态的项目势在必行。该项目的核心部分是图像匹配模块，即已知原图像A和模板图像B，经匹配程序计算处理，得到模板图像B在原图像 A中的坐标位置，根据该位置判断程序运行是否正常，或根据得到的坐标位置进行下一步操作。

文献[1]提出了尺度不变特征变换(Scale Invariant Feature Transform, SIFT)局部特征描述算法，该算法具有旋转不变性、缩放不变性、仿射不变性等特点，被广泛应用于图像配准、图像匹配等领域。通过对SIFT算法的研究，标准的SIFT算法具有很强的通用性，在模板图像尺度偏小、模板图像和原图像存在较大灰度差异时，匹配效果极不理想。此外，不同的文字图像旋转后产生相似的形状，导致它们的特征向量相似度极高，也会影响匹配的效果。

针对上述问题，本文采用二值化图像代替灰度图像、增加特征点数目和取消 SIFT的旋转不变性3种方法，提出一种改进的SIFT算法。

2 标准SIFT算法

2.1 SIFT算法特性

SIFT算法由Lowe D G提出[1]，文献[2]对其进行了总结和完善。文献[3-5]描述了 SIFT算法的各种特性，它是目前比较流行的局部特征描述算法，由于它的优良特性，被成功利用于图像匹配领域，在相同类型的特征描述子中，它往往能得到最好的效果[6-7]，文献[8-9]对几种具有代表性的局部特征算法通过各种实验进行了性能评估，结论表明 SIFT算法的综合性能最为理想。

2.2 SIFT算法原理

SIFT算法的本质是基于图像特征尺度选择的思想[10]，该算法主要分为 4个步骤：(1)在尺度空间寻找关键点；(2)确定关键点；(3)确定特征点的主方向；(4)生成SIFT特征点描述子。

2.2.1 尺度空间中的极值点检测

一幅图像的高斯尺度空间 L( x, y,σ) 由图像I( x, y)与高斯核 G( x, y,σ)的卷积来实现，即：

其中，*表示卷积；σ为高斯滤波器方差，它决定对图像的平滑程度。

Lowe D G采用高斯差分(Difference of Gaussian,DoG)算子，即一种归一化的 LoG(Laplacian of Gaussian)算子的近似，对图像进行极值点检测。通过将高斯尺度空间中相邻尺度的2幅图像相减来建立高斯差分尺度空间DoG，在DoG空间寻找极值时，如图1所示，标记为叉号的像素为待检测点，需要跟同一尺度的周围邻域8个像素和上下相邻尺度对应位置的 9×2个像素共 26像素(如图中的灰点所示)进行比较，以保证在尺度空间和二维图像空间都为极值，这样的一个极值点即标记为一个候选的特征点。

图1 极值点检测

2.2.2 关键点的确定

在得到候选的特征点时，要对这些候选点进行稳定性检测，检测通过的特征点描述为 SIFT特征点，这样可以增强特征点匹配的稳定性，提高抗噪声的能力。算法中通过3个步骤对一个特征点的稳定性进行测试，即对特征点进行精确定位、检测特征点的对比度和边缘响应。

2.2.3 特征点主方向的确定

为实现算法对图像的旋转保持不变性，需要将检测到的特征点的局部图像结构求得一个方向基准。一个特征点的主方向的选取，需在以特征点为中心的邻域窗口内采样，用直方图统计邻域像素的梯度方向。Lowe D G将其中每个像素点的梯度方向分到 36份中，从 0°～360°，每 10°为 1份。梯度方向直方图的峰值则代表了该特征点处邻域梯度的主方向，即作为该特征点的主方向。

2.2.4 SIFT特征点描述子的生成

为实现算法的旋转不变性，需将坐标轴旋转为特征点的主方向，以特征点为中心取8×8的邻域窗口，如图2(a)所示，每个小格代表对应位置的像素，箭头方向表示该像素的梯度方向，箭头长度表示该像素的梯度幅值，圈内表示二维高斯加权的范围。计算出梯度方向和幅值后取每4×4的图像小块计算8个方向的梯度直方图，产生一个种子点。如图2(b)所示，一共产生 2×2=4个种子点，每个种子点有8个方向信息，则能产生 2×2×8=32个数据，形成32维的向量，即SIFT特征点描述子。

图2 SIFT特征描述子的生成

Lowe D G提出SIFT 描述子时，为增强匹配的稳健性，建议对每个特征点使用4×4 共16个种子点来描述，一个种子点有8个方向向量，即一个特征点就可以产生128个数据，最终形成128维的SIFT特征向量。

3 改进的SIFT算法

在手机模板匹配应用中，模板图像往往比较小，且内容不确定，有各种图形内容的模板，也有纯文字内容的模板。使用标准的SIFT算法，对于尺寸偏小的纯文字模板图像只能检测到极少的特征点甚至无法检测到，并且由于文字图像的特殊性，SIFT算法中的旋转不变性也严重影响了文字图像模板匹配的准确性。基于上述 2点，本文提出一种改进的 SIFT算法。

3.1 图像二值化

在标准的 SIFT算法中，使用原图像的灰度图像来构建高斯差分金字塔。系统在实际的使用中，原图像和模板图像往往存在很大的灰度差异，加之文字模板极容易受噪音干扰，如果使用标准SIFT算法生成特征描述子，同一位置生成的描述子也会存在极大差异，影响匹配的准确率。研究发现，将灰度差异较大的原图像和模板图像分别进行自适应二值化后，得到的二值化图像在对应位置上的形状基本保持一致，从而有效消除了灰度差异带来的干扰。

如图 3所示的模板图像(图 3(a)为 97×40像素；图 3(b)为 96×35像素)，在一组大小不同、亮度不同的类似图4所示的原图像中进行位置匹配，分别使用灰度图像和二值化图像构建的高斯差分金字塔下进行匹配，匹配的正确率结果如表1所示，从表中的数据可以得出，使用二值化图像作为算法的输入图像能有效提高匹配的准确率。

图3 文字图像模板1

图4 原图像示例

表1 匹配准确率 (%)

3.2 特征点数目的增加

前面已经介绍了高斯差分 DoG算子，该算子实际上是对高斯拉普拉斯算子 LoG的一个近似，并存在如式(3)所示的近似关系：

其中，σ2▽2G表示拉普拉斯算子，方程式左边表示DoG算子。式中常数k–1不会影响极值点的位置，因此，2种方法得到的特征点位置会保持一致。即如果点(x, y,σ)在LoG方法中是极值点，则在DoG方法的对应位置上的点(x, y,σ)也是极值点。

在 LoG算法中，对于图 5(a)中的二值化圆形斑点，不同的尺度σ对应不同的 LoG响应值，其变化关系如图5(b)所示。当尺度σ= r /时，高斯拉普拉斯响应值达到最大。同理如果图5(a)中的二值化圆形斑点如果黑白相反，则它的拉普拉斯响应值就在σ= r /时达到最小[11]。

图5 图像中的圆形斑点与拉普拉斯响应值

根据LoG和DoG的关系式(3)和上文的论证，对于图 5(a)中的二值化斑点，在使用 DoG算法时，同样当σ= r /时，DoG算子有最大响应值。

在对图 6所示的 2个文字模板图像进行标准SIFT算法提取特征点时(图 6(a)为 85×35 像素；图 6(b)为 80×32 像素)，图中 6(a)对应的文字模板“是”没有找到符合条件的特征点，图6(b)对应的的文字模板“否”只找到2个特征点。

图6 文字图像模板2

经过对文字图像的分析，发现文字图像较普通图形图像有其特殊的地方，文字图像的形状是由类似线条的细笔迹组成，而普通的图形图像一般不具有这个特点。标准的SIFT算法中，建议高斯核σ的初始值为1.6，因此只有半径大于r=σ×= 2.26的斑点才有稳定的极大值响应，而对于半径小于 2.26的斑点没有极大值响应。研究发现，图6中的文字图像的实际笔迹宽度只有 1或 2个像素，因此，对于标准的SIFT算法，没有能满足极大值响应条件的斑点，导致了找不到特征点或特征点极少。

根据上文分析，为增加特征点的数目，即增加DoG算子的极大值响应数目，应尽量使文字的笔迹宽度与极大值响应斑点半径相接近。本文结合文字图像的特点和 DoG算子极大值响应的条件，提出了 2种增加特征点数目的方法。

(1)放大图像

标准的 SIFT高斯核σ=1.6，对于半径大于r=σ×= 2.26的斑点才有极值响应。为了增加特征点数目，但又保持高斯核初始值σ=1.6不变，则只能通过增加文字笔迹的宽度来实现。增加文字的笔迹宽度可通过将待处理的图像先进行放大，可以采用双线性插值算法，以保证图像边缘的平滑性。放大的倍数根据实际情况而定，需要考虑放大后特征提取的效果和系统对图像放大后性能的容忍度。图6中的文字图像经过不同放大倍数后提取的特征点数目如表 2所示，显然，随着放大倍数n的增加，特征点的数目也成倍增加。

表2 输入图像放大不同倍数时的特征点数目

(2)计算最佳高斯核σ

图像的放大会影响系统的性能，因此单纯依靠图像放大来增加特征点数目是不理想的。在图像大小保持不变的前提下，可以通过计算最佳的σ初始值，使半径小的斑点也能满足极值响应，来增加特征点数目。要计算出最佳的σ= r /初始值，则根据文字模板的实际情况而定，即跟文字笔迹的宽细程度相关。σ下调过少，则起不到增加特征数目的作用。σ下调过多，则会产生过多的特征点，会增加系统的开销，同时使特征点失去代表性，而影响匹配的准确性。

实际使用中，一般结合图像放大和下调σ相结合的方法来增加特征点数目。对于图6的文字模板，在放大2倍的基础上，经实验测试，得出的测试结果数据如表3所示。

表3 取不同高斯核σ时的特征点数目

3.3 SIFT旋转不变性的取消

标准的 SIFT算法加入了特征点的主方向信息，目的是实现特征点描述子的旋转不变性。如在图7中，未提取特征前，右边图像是经过左边图像旋转 180°所得。然后分别对它们进行特征点提取，得到的特征点信息如图 7所示(箭头方向表示特征点方向，箭头长度表示特征点大小)。可以发现，2幅图像的特征数目、相应特征点的方向和大小几乎保持一致，即产生的特征描述子距离极小，证明了 SIFT的旋转不变性具有很强的稳定性。

图7 SIFT算法的旋转不变性

在文字模板图像的特征提取时，由于文字结构的特殊性，很多文字都与其他文字旋转一定角度后的形状相似，例如数字6和9；或者文字中的某些部分与其他文字旋转一定角度后的形状相似，例如士和刊；还有某些文字中的部分笔画经旋转后结构相似，例如仁和川。根据前面叙述的SIFT稳定的旋转不变性，当对这些经过旋转而相似的结构提取 SIFT特征时，对应位置的特征点的大小，方向基本保持一致，即产生的特征描述子距离极小。如图8所示，分别对数字6和9进行特征提取，它们产生的特征点信息基本保持一致。

图8 “6”和“9”的特征点信息

根据上面实验验证，这些经过旋转而结构相似的文字结构，在使用标准 SIFT算法时，会产生大量的相似度极高的特征描述子，与系统实际需求相矛盾。根据系统的实际情况，在大量的手机图像测试数据中，模板图像和原图像的方向都是完全一致的，不存在任何的旋转情况，即保持 SIFT算法的旋转不变性不能提高本系统的准确率，而且还对文字模板的匹配产生了严重的干扰，因此，取消标准 SIFT算法中的旋转不变性对系统更有利。

4 实验与结果分析

为比较改进后的SIFT算法和标准SIFT算法在手机模板匹配准确率的情况，详细列出了实验的测试平台和匹配。

实验用的计算机匹配如下：主频2.53 GHz，内存 2.00 GB；操作系统Win7，程序运行平台VS 2010；OpenCV开发包。

4.1 评价方法

采用标准的SIFT算法和改进后的SIFT算法分别对2组文字图像数据进行匹配测试，匹配度采用余弦距离描述。分别统计2种方法对2组数据匹配过程中产生的特征点数目及最后匹配的正确性，统计不同方法下匹配的准确率。

4.2 实验结果

实验测试时，标准的SIFT算法中，将256色真彩色图像灰度化，然后放大2倍作为输入图像，取高斯核σ=1.6为初始值；改进后的SIFT算法中，在灰度图的基础上将图像作二值化处理，同样放大2倍后作为输入图像，取高斯核σ=1.0为初始化值，并取消SIFT的旋转不变特性。以这 2种方法分别对图 3和图 6中的模板图像在对应的大原图像中进行搜索匹配，匹配的结果如表4所示。

表4 实验匹配结果

4.3 结果分析

根据表4可以观察出，系统匹配的成功率与特征点的数目有着密切的关系。经研究发现，图3中的模板图像，产生的特征点数目偏少，匹配的过程中又受到其他文字特征点的干扰，而且模板图像与原图像有较大的灰度差异，是导致匹配率低的原因。图6(a)只有一个特征点，并且这个仅有的特征点并不是由文字“是”产生的，而是图像边缘上的灰度差异产生的，所以导致匹配正确率为0；图6(b)中产生了2个特征点，而且2个特征点是由“否”字产生，并且测试的数据中模板图像与大原图像不存在灰度值的差异，原图像中也没有可能引起干扰的其他文字，因此，匹配率十分理想；改进后的SIFT算法中，对图3中匹配失败的例子进行研究发现，原图像与图3的两模板图像的灰度值差异极大，分别二值化后得到的图像是形状一致但黑白相反，导致不能正确匹配。

从实验数据可以看出，对于标准 SIFT算法匹配率偏低的数据，改进后的 SIFT算法能大大提高匹配的准确率。对于准确率本来就高的测试数据，改进后的 SIFT算法也能保持原来的准确率。因此，改进后的SIFT算法更适合在文字图像匹配领域中使用。

5 结束语

针对尺寸偏小的文字图像模板在大图像中的匹配率偏低的问题，本文提出了一种改进的SIFT算法，解决了灰度差异较大带来的干扰问题、文字笔迹偏细找不到特征点的问题和非匹配文字之间的干扰问题，大幅提高了匹配的准确率；对使用标准 SIFT算法匹配率就很高的数据集，改进 SIFT算法能保持原有准确率，因此，改进SIFT算法能广泛地应用在模式匹配邻域。但改进后的算法不能完全处理形状相似灰度值相反的数据集，且文字之间不旋转就会产生的严重干扰。因此，如何解决上述问题是下一步的研究方向。

[1]Lowe D G.Object Recognition from Local Scale-invariant Features[C]//Proceedings of International Conference on Computer Vision.Corfu, Greece: [s.n.], 1999: 1150-1157.

[2]Lowe D G.Distinctive Image Features from Scaleinvariant Keypoints[J].International Journal of Computer Vision, 2004, 60(2): 91-110.

[3]Ke Y, Sukthankar R.PCA-SIFT: A More Distinctive Representation for Local Image Descriptors[C]//Proceedings of Conference on Computer Vision and Pattern Recognition.Washington D.C., USA: [s.n.], 2004:511-517.

[4]Mikolajczyk K, Schmid C.A Performance Evaluation of Local Descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615-1630.

[5]Zhou Huiyu, Yuan Yuan, Shi Chunmei.Object Tracking Using SIFT Features and Mean Shift[J].Computer Vision and Image Understanding, 2009, 113(3): 345-352.

[6]王 蕾.图像配准技术及应用研究[D].西安: 西安电子科技大学, 2007.

[7]赵 辉.基于点特征的图像配准算法研究[D].济南:山东大学, 2006.

[8]Li Jing, Allinson N M.A Comprehensive Review of Current Local Features for Computer Vision[J].Neurocomputing, 2008, 71(10-12): 1771-1787.

[9]Mikolajczyk K, Tuytelaars T, Schmid C, et al.A Comparison of Affine Region Detectors[J].International Journal of Computer Vision, 2005, 65(1-2): 43-72.

[10]Lindeberg T.Scale Space Theory: A Basic Tool for Analyzing Structures at Different Scales[J].Journal of Applied Statistics, 1994, 21(2): 224-270.

[11]王永明, 王贵锦.图像局部不变性特征与描述[M].北京: 国防工业出版社, 2010.