胡海青，譚建龍，朱亞濤，龔國成，劉金剛

(1.首都師范大學(xué)計算機科學(xué)聯(lián)合研究院，北京 100037；2.中國科學(xué)院計算技術(shù)研究所，北京 100190；3.河北農(nóng)業(yè)大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北 保定 071000)

1 概述

圖像匹配是計算機視覺和模式識別領(lǐng)域的一個重要分支，也是目前研究的熱點。隨著智能手機的普及，在手機上裝卸載程序成為手機用戶不可或缺的需求。對于手機生產(chǎn)商而言，檢測手機能否成功安裝相應(yīng)程序，是手機檢測的重要部分，而原有的人工檢測方式需消耗大量的人力，因此，開發(fā)自動檢測手機程序運行狀態(tài)的項目勢在必行。該項目的核心部分是圖像匹配模塊，即已知原圖像A和模板圖像B，經(jīng)匹配程序計算處理，得到模板圖像B在原圖像 A中的坐標(biāo)位置，根據(jù)該位置判斷程序運行是否正常，或根據(jù)得到的坐標(biāo)位置進(jìn)行下一步操作。

文獻(xiàn)[1]提出了尺度不變特征變換(Scale Invariant Feature Transform, SIFT)局部特征描述算法，該算法具有旋轉(zhuǎn)不變性、縮放不變性、仿射不變性等特點，被廣泛應(yīng)用于圖像配準(zhǔn)、圖像匹配等領(lǐng)域。通過對SIFT算法的研究，標(biāo)準(zhǔn)的SIFT算法具有很強的通用性，在模板圖像尺度偏小、模板圖像和原圖像存在較大灰度差異時，匹配效果極不理想。此外，不同的文字圖像旋轉(zhuǎn)后產(chǎn)生相似的形狀，導(dǎo)致它們的特征向量相似度極高，也會影響匹配的效果。

針對上述問題，本文采用二值化圖像代替灰度圖像、增加特征點數(shù)目和取消 SIFT的旋轉(zhuǎn)不變性3種方法，提出一種改進(jìn)的SIFT算法。

2 標(biāo)準(zhǔn)SIFT算法

2.1 SIFT算法特性

SIFT算法由Lowe D G提出[1]，文獻(xiàn)[2]對其進(jìn)行了總結(jié)和完善。文獻(xiàn)[3-5]描述了 SIFT算法的各種特性，它是目前比較流行的局部特征描述算法，由于它的優(yōu)良特性，被成功利用于圖像匹配領(lǐng)域，在相同類型的特征描述子中，它往往能得到最好的效果[6-7]，文獻(xiàn)[8-9]對幾種具有代表性的局部特征算法通過各種實驗進(jìn)行了性能評估，結(jié)論表明 SIFT算法的綜合性能最為理想。

2.2 SIFT算法原理

SIFT算法的本質(zhì)是基于圖像特征尺度選擇的思想[10]，該算法主要分為 4個步驟：(1)在尺度空間尋找關(guān)鍵點；(2)確定關(guān)鍵點；(3)確定特征點的主方向；(4)生成SIFT特征點描述子。

2.2.1 尺度空間中的極值點檢測

一幅圖像的高斯尺度空間 L( x, y,σ) 由圖像I( x, y)與高斯核 G( x, y,σ)的卷積來實現(xiàn)，即：

其中，*表示卷積；σ為高斯濾波器方差，它決定對圖像的平滑程度。

Lowe D G采用高斯差分(Difference of Gaussian,DoG)算子，即一種歸一化的 LoG(Laplacian of Gaussian)算子的近似，對圖像進(jìn)行極值點檢測。通過將高斯尺度空間中相鄰尺度的2幅圖像相減來建立高斯差分尺度空間DoG，在DoG空間尋找極值時，如圖1所示，標(biāo)記為叉號的像素為待檢測點，需要跟同一尺度的周圍鄰域8個像素和上下相鄰尺度對應(yīng)位置的 9×2個像素共 26像素(如圖中的灰點所示)進(jìn)行比較，以保證在尺度空間和二維圖像空間都為極值，這樣的一個極值點即標(biāo)記為一個候選的特征點。

圖1 極值點檢測

2.2.2 關(guān)鍵點的確定

在得到候選的特征點時，要對這些候選點進(jìn)行穩(wěn)定性檢測，檢測通過的特征點描述為 SIFT特征點，這樣可以增強特征點匹配的穩(wěn)定性，提高抗噪聲的能力。算法中通過3個步驟對一個特征點的穩(wěn)定性進(jìn)行測試，即對特征點進(jìn)行精確定位、檢測特征點的對比度和邊緣響應(yīng)。

2.2.3 特征點主方向的確定

為實現(xiàn)算法對圖像的旋轉(zhuǎn)保持不變性，需要將檢測到的特征點的局部圖像結(jié)構(gòu)求得一個方向基準(zhǔn)。一個特征點的主方向的選取，需在以特征點為中心的鄰域窗口內(nèi)采樣，用直方圖統(tǒng)計鄰域像素的梯度方向。Lowe D G將其中每個像素點的梯度方向分到 36份中，從 0°～360°，每 10°為 1份。梯度方向直方圖的峰值則代表了該特征點處鄰域梯度的主方向，即作為該特征點的主方向。

2.2.4 SIFT特征點描述子的生成

為實現(xiàn)算法的旋轉(zhuǎn)不變性，需將坐標(biāo)軸旋轉(zhuǎn)為特征點的主方向，以特征點為中心取8×8的鄰域窗口，如圖2(a)所示，每個小格代表對應(yīng)位置的像素，箭頭方向表示該像素的梯度方向，箭頭長度表示該像素的梯度幅值，圈內(nèi)表示二維高斯加權(quán)的范圍。計算出梯度方向和幅值后取每4×4的圖像小塊計算8個方向的梯度直方圖，產(chǎn)生一個種子點。如圖2(b)所示，一共產(chǎn)生 2×2=4個種子點，每個種子點有8個方向信息，則能產(chǎn)生 2×2×8=32個數(shù)據(jù)，形成32維的向量，即SIFT特征點描述子。

圖2 SIFT特征描述子的生成

Lowe D G提出SIFT 描述子時，為增強匹配的穩(wěn)健性，建議對每個特征點使用4×4 共16個種子點來描述，一個種子點有8個方向向量，即一個特征點就可以產(chǎn)生128個數(shù)據(jù)，最終形成128維的SIFT特征向量。

3 改進(jìn)的SIFT算法

在手機模板匹配應(yīng)用中，模板圖像往往比較小，且內(nèi)容不確定，有各種圖形內(nèi)容的模板，也有純文字內(nèi)容的模板。使用標(biāo)準(zhǔn)的SIFT算法，對于尺寸偏小的純文字模板圖像只能檢測到極少的特征點甚至無法檢測到，并且由于文字圖像的特殊性，SIFT算法中的旋轉(zhuǎn)不變性也嚴(yán)重影響了文字圖像模板匹配的準(zhǔn)確性?；谏鲜?2點，本文提出一種改進(jìn)的 SIFT算法。

3.1 圖像二值化

在標(biāo)準(zhǔn)的 SIFT算法中，使用原圖像的灰度圖像來構(gòu)建高斯差分金字塔。系統(tǒng)在實際的使用中，原圖像和模板圖像往往存在很大的灰度差異，加之文字模板極容易受噪音干擾，如果使用標(biāo)準(zhǔn)SIFT算法生成特征描述子，同一位置生成的描述子也會存在極大差異，影響匹配的準(zhǔn)確率。研究發(fā)現(xiàn)，將灰度差異較大的原圖像和模板圖像分別進(jìn)行自適應(yīng)二值化后，得到的二值化圖像在對應(yīng)位置上的形狀基本保持一致，從而有效消除了灰度差異帶來的干擾。

如圖 3所示的模板圖像(圖 3(a)為 97×40像素；圖 3(b)為 96×35像素)，在一組大小不同、亮度不同的類似圖4所示的原圖像中進(jìn)行位置匹配，分別使用灰度圖像和二值化圖像構(gòu)建的高斯差分金字塔下進(jìn)行匹配，匹配的正確率結(jié)果如表1所示，從表中的數(shù)據(jù)可以得出，使用二值化圖像作為算法的輸入圖像能有效提高匹配的準(zhǔn)確率。

圖3 文字圖像模板1

圖4 原圖像示例

表1 匹配準(zhǔn)確率 (%)

3.2 特征點數(shù)目的增加

前面已經(jīng)介紹了高斯差分 DoG算子，該算子實際上是對高斯拉普拉斯算子 LoG的一個近似，并存在如式(3)所示的近似關(guān)系：

其中，σ2▽2G表示拉普拉斯算子，方程式左邊表示DoG算子。式中常數(shù)k–1不會影響極值點的位置，因此，2種方法得到的特征點位置會保持一致。即如果點(x, y,σ)在LoG方法中是極值點，則在DoG方法的對應(yīng)位置上的點(x, y,σ)也是極值點。

在 LoG算法中，對于圖 5(a)中的二值化圓形斑點，不同的尺度σ對應(yīng)不同的 LoG響應(yīng)值，其變化關(guān)系如圖5(b)所示。當(dāng)尺度σ= r /時，高斯拉普拉斯響應(yīng)值達(dá)到最大。同理如果圖5(a)中的二值化圓形斑點如果黑白相反，則它的拉普拉斯響應(yīng)值就在σ= r /時達(dá)到最小[11]。

圖5 圖像中的圓形斑點與拉普拉斯響應(yīng)值

根據(jù)LoG和DoG的關(guān)系式(3)和上文的論證，對于圖 5(a)中的二值化斑點，在使用 DoG算法時，同樣當(dāng)σ= r /時，DoG算子有最大響應(yīng)值。

在對圖 6所示的 2個文字模板圖像進(jìn)行標(biāo)準(zhǔn)SIFT算法提取特征點時(圖 6(a)為 85×35 像素；圖 6(b)為 80×32 像素)，圖中 6(a)對應(yīng)的文字模板“是”沒有找到符合條件的特征點，圖6(b)對應(yīng)的的文字模板“否”只找到2個特征點。

圖6 文字圖像模板2

經(jīng)過對文字圖像的分析，發(fā)現(xiàn)文字圖像較普通圖形圖像有其特殊的地方，文字圖像的形狀是由類似線條的細(xì)筆跡組成，而普通的圖形圖像一般不具有這個特點。標(biāo)準(zhǔn)的SIFT算法中，建議高斯核σ的初始值為1.6，因此只有半徑大于r=σ×= 2.26的斑點才有穩(wěn)定的極大值響應(yīng)，而對于半徑小于 2.26的斑點沒有極大值響應(yīng)。研究發(fā)現(xiàn)，圖6中的文字圖像的實際筆跡寬度只有 1或 2個像素，因此，對于標(biāo)準(zhǔn)的SIFT算法，沒有能滿足極大值響應(yīng)條件的斑點，導(dǎo)致了找不到特征點或特征點極少。

根據(jù)上文分析，為增加特征點的數(shù)目，即增加DoG算子的極大值響應(yīng)數(shù)目，應(yīng)盡量使文字的筆跡寬度與極大值響應(yīng)斑點半徑相接近。本文結(jié)合文字圖像的特點和 DoG算子極大值響應(yīng)的條件，提出了 2種增加特征點數(shù)目的方法。

(1)放大圖像

標(biāo)準(zhǔn)的 SIFT高斯核σ=1.6，對于半徑大于r=σ×= 2.26的斑點才有極值響應(yīng)。為了增加特征點數(shù)目，但又保持高斯核初始值σ=1.6不變，則只能通過增加文字筆跡的寬度來實現(xiàn)。增加文字的筆跡寬度可通過將待處理的圖像先進(jìn)行放大，可以采用雙線性插值算法，以保證圖像邊緣的平滑性。放大的倍數(shù)根據(jù)實際情況而定，需要考慮放大后特征提取的效果和系統(tǒng)對圖像放大后性能的容忍度。圖6中的文字圖像經(jīng)過不同放大倍數(shù)后提取的特征點數(shù)目如表 2所示，顯然，隨著放大倍數(shù)n的增加，特征點的數(shù)目也成倍增加。

表2 輸入圖像放大不同倍數(shù)時的特征點數(shù)目

(2)計算最佳高斯核σ

圖像的放大會影響系統(tǒng)的性能，因此單純依靠圖像放大來增加特征點數(shù)目是不理想的。在圖像大小保持不變的前提下，可以通過計算最佳的σ初始值，使半徑小的斑點也能滿足極值響應(yīng)，來增加特征點數(shù)目。要計算出最佳的σ= r /初始值，則根據(jù)文字模板的實際情況而定，即跟文字筆跡的寬細(xì)程度相關(guān)。σ下調(diào)過少，則起不到增加特征數(shù)目的作用。σ下調(diào)過多，則會產(chǎn)生過多的特征點，會增加系統(tǒng)的開銷，同時使特征點失去代表性，而影響匹配的準(zhǔn)確性。

實際使用中，一般結(jié)合圖像放大和下調(diào)σ相結(jié)合的方法來增加特征點數(shù)目。對于圖6的文字模板，在放大2倍的基礎(chǔ)上，經(jīng)實驗測試，得出的測試結(jié)果數(shù)據(jù)如表3所示。

表3 取不同高斯核σ時的特征點數(shù)目

3.3 SIFT旋轉(zhuǎn)不變性的取消

標(biāo)準(zhǔn)的 SIFT算法加入了特征點的主方向信息，目的是實現(xiàn)特征點描述子的旋轉(zhuǎn)不變性。如在圖7中，未提取特征前，右邊圖像是經(jīng)過左邊圖像旋轉(zhuǎn) 180°所得。然后分別對它們進(jìn)行特征點提取，得到的特征點信息如圖 7所示(箭頭方向表示特征點方向，箭頭長度表示特征點大小)?？梢园l(fā)現(xiàn)，2幅圖像的特征數(shù)目、相應(yīng)特征點的方向和大小幾乎保持一致，即產(chǎn)生的特征描述子距離極小，證明了 SIFT的旋轉(zhuǎn)不變性具有很強的穩(wěn)定性。

圖7 SIFT算法的旋轉(zhuǎn)不變性

在文字模板圖像的特征提取時，由于文字結(jié)構(gòu)的特殊性，很多文字都與其他文字旋轉(zhuǎn)一定角度后的形狀相似，例如數(shù)字6和9；或者文字中的某些部分與其他文字旋轉(zhuǎn)一定角度后的形狀相似，例如士和刊；還有某些文字中的部分筆畫經(jīng)旋轉(zhuǎn)后結(jié)構(gòu)相似，例如仁和川。根據(jù)前面敘述的SIFT穩(wěn)定的旋轉(zhuǎn)不變性，當(dāng)對這些經(jīng)過旋轉(zhuǎn)而相似的結(jié)構(gòu)提取 SIFT特征時，對應(yīng)位置的特征點的大小，方向基本保持一致，即產(chǎn)生的特征描述子距離極小。如圖8所示，分別對數(shù)字6和9進(jìn)行特征提取，它們產(chǎn)生的特征點信息基本保持一致。

圖8 “6”和“9”的特征點信息

根據(jù)上面實驗驗證，這些經(jīng)過旋轉(zhuǎn)而結(jié)構(gòu)相似的文字結(jié)構(gòu)，在使用標(biāo)準(zhǔn) SIFT算法時，會產(chǎn)生大量的相似度極高的特征描述子，與系統(tǒng)實際需求相矛盾。根據(jù)系統(tǒng)的實際情況，在大量的手機圖像測試數(shù)據(jù)中，模板圖像和原圖像的方向都是完全一致的，不存在任何的旋轉(zhuǎn)情況，即保持 SIFT算法的旋轉(zhuǎn)不變性不能提高本系統(tǒng)的準(zhǔn)確率，而且還對文字模板的匹配產(chǎn)生了嚴(yán)重的干擾，因此，取消標(biāo)準(zhǔn) SIFT算法中的旋轉(zhuǎn)不變性對系統(tǒng)更有利。

4 實驗與結(jié)果分析

為比較改進(jìn)后的SIFT算法和標(biāo)準(zhǔn)SIFT算法在手機模板匹配準(zhǔn)確率的情況，詳細(xì)列出了實驗的測試平臺和匹配。

實驗用的計算機匹配如下：主頻2.53 GHz，內(nèi)存 2.00 GB；操作系統(tǒng)Win7，程序運行平臺VS 2010；OpenCV開發(fā)包。

4.1 評價方法

采用標(biāo)準(zhǔn)的SIFT算法和改進(jìn)后的SIFT算法分別對2組文字圖像數(shù)據(jù)進(jìn)行匹配測試，匹配度采用余弦距離描述。分別統(tǒng)計2種方法對2組數(shù)據(jù)匹配過程中產(chǎn)生的特征點數(shù)目及最后匹配的正確性，統(tǒng)計不同方法下匹配的準(zhǔn)確率。

4.2 實驗結(jié)果

實驗測試時，標(biāo)準(zhǔn)的SIFT算法中，將256色真彩色圖像灰度化，然后放大2倍作為輸入圖像，取高斯核σ=1.6為初始值；改進(jìn)后的SIFT算法中，在灰度圖的基礎(chǔ)上將圖像作二值化處理，同樣放大2倍后作為輸入圖像，取高斯核σ=1.0為初始化值，并取消SIFT的旋轉(zhuǎn)不變特性。以這 2種方法分別對圖 3和圖 6中的模板圖像在對應(yīng)的大原圖像中進(jìn)行搜索匹配，匹配的結(jié)果如表4所示。

表4 實驗匹配結(jié)果

4.3 結(jié)果分析

根據(jù)表4可以觀察出，系統(tǒng)匹配的成功率與特征點的數(shù)目有著密切的關(guān)系。經(jīng)研究發(fā)現(xiàn)，圖3中的模板圖像，產(chǎn)生的特征點數(shù)目偏少，匹配的過程中又受到其他文字特征點的干擾，而且模板圖像與原圖像有較大的灰度差異，是導(dǎo)致匹配率低的原因。圖6(a)只有一個特征點，并且這個僅有的特征點并不是由文字“是”產(chǎn)生的，而是圖像邊緣上的灰度差異產(chǎn)生的，所以導(dǎo)致匹配正確率為0；圖6(b)中產(chǎn)生了2個特征點，而且2個特征點是由“否”字產(chǎn)生，并且測試的數(shù)據(jù)中模板圖像與大原圖像不存在灰度值的差異，原圖像中也沒有可能引起干擾的其他文字，因此，匹配率十分理想；改進(jìn)后的SIFT算法中，對圖3中匹配失敗的例子進(jìn)行研究發(fā)現(xiàn)，原圖像與圖3的兩模板圖像的灰度值差異極大，分別二值化后得到的圖像是形狀一致但黑白相反，導(dǎo)致不能正確匹配。

從實驗數(shù)據(jù)可以看出，對于標(biāo)準(zhǔn) SIFT算法匹配率偏低的數(shù)據(jù)，改進(jìn)后的 SIFT算法能大大提高匹配的準(zhǔn)確率。對于準(zhǔn)確率本來就高的測試數(shù)據(jù)，改進(jìn)后的 SIFT算法也能保持原來的準(zhǔn)確率。因此，改進(jìn)后的SIFT算法更適合在文字圖像匹配領(lǐng)域中使用。

5 結(jié)束語

針對尺寸偏小的文字圖像模板在大圖像中的匹配率偏低的問題，本文提出了一種改進(jìn)的SIFT算法，解決了灰度差異較大帶來的干擾問題、文字筆跡偏細(xì)找不到特征點的問題和非匹配文字之間的干擾問題，大幅提高了匹配的準(zhǔn)確率；對使用標(biāo)準(zhǔn) SIFT算法匹配率就很高的數(shù)據(jù)集，改進(jìn) SIFT算法能保持原有準(zhǔn)確率，因此，改進(jìn)SIFT算法能廣泛地應(yīng)用在模式匹配鄰域。但改進(jìn)后的算法不能完全處理形狀相似灰度值相反的數(shù)據(jù)集，且文字之間不旋轉(zhuǎn)就會產(chǎn)生的嚴(yán)重干擾。因此，如何解決上述問題是下一步的研究方向。

[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]王 蕾.圖像配準(zhǔn)技術(shù)及應(yīng)用研究[D].西安: 西安電子科技大學(xué), 2007.

[7]趙 輝.基于點特征的圖像配準(zhǔn)算法研究[D].濟南:山東大學(xué), 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].北京: 國防工業(yè)出版社, 2010.