改進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.