改進的SURF算法在書法筆畫匹配識別中的應用

王 民，龐爽爽，周軍妮

(西安建筑科技大學信息與控制工程學院,陜西 西安 710055)

1 引言

中國書法作為一門抽象的漢字書寫藝術，因其價格昂貴、收藏價值高，在藝術市場上出現了很多偽作。目前常用的書法真偽鑒別方法主要是專家經驗性鑒別、物理化學鑒別和機器鑒別三種[1]。前兩種方法的缺點是存在較多的主觀因素，缺少客觀的、可量化的判別依據。因此，利用計算機進行書法真偽鑒別就成為了行之有效的方法。

計算機輔助的書法真偽鑒別系統中[2]的主要步驟是書法特征提取和匹配。文獻[3,4]將SIFT(Scale Invariant Feature Transform)[5]算法應用到漢字匹配與識別中。針對SIFT算法的維度高、計算速度慢、匹配時間長等問題，文獻[7]在Herbert Bay等人基礎上提出了一種改進的SURF(Speed Up Robust Features)算法，并將此應用到漢字識別中，取得了不錯的效果。鑒于局部特征檢測算法SURF在漢字識別中的諸多優勢，本文將其與Contourlet變換[8]進行結合，并應用到書法筆畫的特征提取及匹配中，實驗驗證了該方法的可行性和有效性。

2 SURF特征檢測與Contourlet變換

2.1 SURF算法特征點定位與描述

SURF算法能夠在光照因素的影響和復雜的背景環境下較好地提取特征點，且時間復雜度相對于SIFT算法較低，SURF算法主要包含兩部分：特征點檢測與定位，以及特征點描述算子[9 - 12]的生成。

設(x，y)為圖像I(X)中某一像素點的坐標，對應尺度空間中的尺度為δ，則Hessian矩陣的定義如下所示：

(1)

其中，Lxx、Lxy、Lyy是圖像上的點分別與高斯濾波二階偏卷積的結果。計算H(x,δ)行列式，得到某一像素點的特征值。

為了提高算法運算速度，將高斯模板簡化為矩形區域盒子濾波器后，采用箱式濾波模板與原始輸入圖像的卷積Dxx、Dxy、Dyy來分別替代Lxx、Lxy、Lyy。如圖1所示，黑色部分為1，白色部分為-1，權值簡單，其他區域不進行權值運算。

Figure 1 Box filter instead of Gauss filter圖1 盒子濾波器代替高斯濾波器

Hessian矩陣行列式利用近似高斯可表示為：

Δ(Happrax)=DxxDxy-(0.9Dxy)2

(2)

設定一個閾值，當H(x,δ)大于閾值時，進行下一步的判定。在對關鍵點進行下一步判定時，以該關鍵點為中心，對上下對應的3*3*3的3維尺度空間進行非極大值抑制，尋找極值點，當該點比其他26個響應值都大時才能選為特征點。對尺度空間進行插值得到特征點的位置和尺度值。

以檢測到的特征點為中心，對特征點鄰域20S*20S范圍內的區域進行4*4的劃分，得到16個子區域，每個子區域的像素值為5S*5S。算出X方向和Y方向各個像素點的Harr小波響應值dx和dy，求出X方向和Y方向像素點的Harr小波響應值的和∑dx和∑dy，Harr小波在X方向和Y方向響應值變化情況用∑|dx|和∑|dy|來描述。對于每個區域，建立一個四維的特征向量,如式(3)所示：

v=(∑dx,∑dy,∑|dx|,∑|dy|)

(3)

將16個子區域的向量分別加入到特征向量中，就形成了一個64(4*16)維的特征向量。將特征描述子進行歸一化處理后，使其具有亮度和尺度不變特性。

2.2 Contourlet變換

Contourlet變換[13,14]是一種將方向分析和多尺度分析分開進行的圖像二維表示方法。圖2顯示了用Contourlet濾波器組對圖像進行多尺度及方向分解的流程，它由兩個主要部分組成：子帶分解LP(Laplacian Pyramind)和方向性濾波DFB(Direction Filter Bank)。每一級結構相同，可快速實現。

LP分解將每層的低頻分量分解成一個低頻分量和一個高頻分量，繼續分解低頻分量得到圖像的多尺度多方向性特征。和小波變換相比，Contourlet變換能更好地捕獲邊緣的奇異點，將相近位置的奇異點匯集成輪廓段，得到分解圖像的輪廓信息[15-17]。

Figure 2 Schematic diagram of Contourlet transformation圖2 Contourlet變換示意圖

3 基于Contourlet的改進SURF算法

基于文獻[6]，SURF算法在漢字識別和匹配中取得了不錯的效果，但是相較于SIFT算法，雖然在計算速度和魯棒性上有所提高，但是檢測到的特征點數目減少且錯誤匹配點數增多。因此，在進行SURF筆畫特征提取和匹配之前進行Contourlet變換，將預處理后的筆畫信息分解為低頻細節分量al(x,y)和高頻細節分量ah(x,y)，然后進行SURF特征點提取與匹配，這樣不僅提高了檢測的特征點數，同時降低了誤匹配率。

Figure 3 Block diagram of the improved SURF algorithm圖3 改進的SURF算法框圖

具體算法流程如下：

Step1對書法作品進行去噪、二值化、平滑、頁面切分等預處理，得到書法筆畫信息I(X)。

Step2對經過預處理后的書法筆畫信息I(X)進行Contourlet變換，得到筆畫信息的低頻細節分量al(x,y)和高頻細節分量ah(x,y)。

Step3用SURF算法從低頻細節分量al(x,y)中提取特征點，每個特征點會生成一個64維的SURF特征向量v′，利用特征向量的最小歐氏距離準則MEDC(Minimum Euclidean Distance Criterion)對真跡與測試圖像的特征向量進行相似性判定。

Step4對分解得到的高頻細節分量ah(x,y)進行去噪，經過2個尺度的Contourlet變換后分解出2i(i=2)個方向子帶，則由2i個方向子帶合成的梯度矢量可表示為：

|D(x,y)|=(|D14(x,y)|2+|D23(x,y)|2+

2·|D14(x,y)||D23(x,y)|cosθ)1/2

(4)

S(t,f)=

(5)

Step6匹配中產生的錯誤點用隨機抽樣一致RANSAC(RANdom SAmple Consensus)算法進行剔除，得到正確匹配結果。

圖3為改進的SURF算法框圖，通過以上步驟提取的SURF特征點，在一定范圍內是隨機表現出來的。計算特征點的均值μ和方差δ2，特征值服從正態分布的書法字特征點a(x,y)的均值μa的概率P(a)計算方法如下所示：

(6)

針對文獻[6]，提取到的特征點數量較少，計算SURF特征值的概率時，對應的特征值概率增大，相應地該特征對于區分該作品的貢獻越小，相似性越低，匹配率下降。而通過Contourlet變換對書法的筆畫信息進行Contourlet變換得到低頻細節分量al(x,y)和高頻細節分量ah(x,y)。al(x,y)大體上保持了原書法字的整體特征；ah(x,y)含有很多筆畫細節的同時存在大量的噪聲，在下一步的特征點描述與提取前對高頻細節分量進行去噪，獲取了更多筆畫信息特征點，其特征點對于區分該作品的貢獻越大，相似性越高，在進行SURF特征點匹配時匹配率越高。對作品楷書單字“春”和草書單字“識”進行去噪、二值化、頁面切分、平滑等預處理后得到書法筆畫信息。同一個人在正常情況下書寫時，其筆畫細節特征和形狀會很相似，在匹配時使用RANSAC算法剔除誤匹配點，匹配率顯著提高。圖4表示兩種算法的特征點提取數，圖5表示正確匹配結果比較。

Figure 4 Number of feature points extracted by of the 2 algorithms圖4 兩種算法特征點提取數

Figure 5 Correct matching result comparison圖5 正確匹配結果比較

4 實驗結果與分析

在Windows 7操作系統上，Matlab R2013a環境下通過對真跡作品和待檢測作品進行匹配識別實驗來驗證文獻[6]算法與本文算法的匹配性能與抗噪性能，實驗表明本文算法在書法筆畫匹配識別中具有明顯的效果。

4.1 匹配識別結果分析

實驗樣品來源于中國藝術標準化研究中心，從樣品庫中選取王獻之50幅真跡作品，同時選取50幅待檢測作品(其中臨摹作品3幅，真跡作品47幅)。對100幅作品進行預處理，從每幅作品中各選取100個單字(共10 000字)進行特征點的提取與匹配實驗，比較分析實驗結果。將正確匹配率TMR(Ture Matching Rate)作為算法匹配性能的衡量指標，則：

(7)

其中,M表示匹配點數；Mf表示誤匹配點數；TMR表示正確匹配率，TMR越大，匹配性能越好。

表1是選取的其中10組匹配結果，分析每組數據發現，正確匹配率與匹配點數密切相關。由于本文算法在進行SURF特征點提取前對書法字的筆畫信息進行了分解，得到了詳細的筆畫特征，在進行匹配前利用RANSAC算法剔除誤匹配點，誤匹配點數減少，特征點數和匹配率與文獻[6]相比明顯提高。

Table 1 Feature points extraction and matching results

表2是統計100幅作品的5 000個真跡單字和5 000個待檢測單字的匹配識別結果，其中能正確匹配識別的單字數為4 655個，正確識別率達到了93.1%，而文獻[6]正確匹配識別字數僅為4 498個，本文算法相比文獻[6]算法提高了3%。

Table 2 Handwriting recognition results

4.2 抗噪性能比較

為了驗證算法的抗噪性能，分別對真跡作品和檢測作品加入方差VAR(Variance)為0.02、0.04、0.06的高斯白噪聲，進行匹配實驗，并比較其正確識別率。

表3是加入不同方差的高斯白噪聲后，文獻[6]算法與本文算法匹配率比較。由表3可知，兩種算法雖然匹配率都逐漸降低，但本文算法匹配點數目變化不大，匹配率降低幅度較小。因為本文算法在對高頻分量分解前進行去噪，提高了圖像正確匹配率。

Table 3 Comparison of anti noise performance

由圖6可知，在不同方差下，改進的SURF算法相比文獻[6]算法整體上來看，識別率都有提高，并且隨著方差的增大，本文算法抗噪性能更好。由實驗可知，改進的SURF特征提取及匹配算法在書法字特征提取與識別中具有較好的效果。

Figure 6 Comparison of recognition rates under different variances圖6 不同方差下識別率比較

5 結束語

針對SURF算法相較于SIFT算法提取特征點數目較少的問題，本文提出了一種基于Contourlet與SURF結合的算法，利用Contourlet變換對書法字的筆畫信息進行高低頻分解，得到高頻細節分量和低頻細節分量后進行特征點提取和匹配。實驗結果表明，改進的SURF算法能有效地提取出書法筆畫特征點并進行正確匹配識別，且識別率有一定提升，同時大大提高了抗噪性能。下一步工作主要是對算法計算量進行優化，提高算法的運行速度。

[1] Liu Yang. Identification of the authenticity of calligraphy works by computer aided [D].Nanchang:Nanchang University,2013.(in Chinese)

[2] Yu Kai.Research on some key technologies of computer calligraphy [D].Hangzhou:Zhejiang University,2010.(in Chinese)

[3] Jin Zhen,Qi Kai-yue,Chen Kai.For complex image features Chinese characters [J].Information and Communication Security,2010 (2): 62-64.(in Chinese)

[4] Hu Hai-qing, Tan Jian-long,Zhu Ya-tao,et al.Application of improved SIFT algorithm in text image matching [J].Computer Engineering,2013,39(1): 239-243.(in Chinese)

[5] Lowe D G. Distinctive image features from scale-invariant keyPoints[J].International Joumal of Computer Vision,2004,60(2):91-110.

[6] Bay H，Tuvtellars T，van Gool L.SURF：Speeded up robust features[C]∥Proc of the European Conference on Intelligent and Autonomous Sytems，2007：2-12.

[7] Meng Wei,Zhong Na.Application of improved SURF algorithm in image recognition Chinese characters[J].Computer Engineering and Application,2015,51(12): 156-160.(in Chinese)

[8] Kato N,Suzuki M,Omachi S,et al.A handwritten character recognition system using directional element feature and asymmetric Mahalanobis distance [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1999,21(3): 258-262.

[9] Brown M，Lowe D G.Automatic panoramic image stitching using invariant features[J].International Journal of Computer Vision，2007(1)：2-5.

[10] Li Huan-huan, Huang Shan, Zhang Hong-bin.Automatic image mosaic based on Harris and SIFT algorithm[J].Computer Engineering & Science,2012,34 (11): 104-108.(in Chinese)

[11] Zou Cheng-ming,Hou Xiao-bi,Ma Jing.SIFT image mosaic algorithm based on geometric image registration[J].Journal of Huazhong University of Science and Technology (Natural Science Edition),2016,44 (4): 32-36.(in Chinese)

[12] Wang Jun-ben,Lu Xuan-min,He Zhao.An image matching algorithm based on fast and robust feature[J].Computer Engineering & Science,2011,33 (2): 112-117.(in Chinese)

[13] Yeh C Y,Su W P,Lee S J.Employing multiple-kernel support vector machines for counterfeit banknote recognition [J].Applied Soft Computing,2011,11(1): 1439-1447.

[14] Zhu Bei-bei, Shang Zhao-wei, Yuan Bo, et al.Offline Chinese handwriting-based writer identification with non-aliasing Contourlet transform[J].Computer Engineering and Applications,2011,47(24):150-153.(in Chinese)

[15] He Z, Tang Y Y,You X.A contourlet-based method for writer identification[C]∥Proc of 2005 IEEE International Conference on Systems,Man and Cybernetics,2005:364-368.

[16] Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10)：1615-1630.

[17] Chen Shu-rong, Li Bo,Dong Rong,et al.Contourlet-SIFT feature matching algorithm[J].Journal of Electronics and Information,2013(5):1215-1221.(in Chinese)

附中文參考文獻：

[1] 劉洋.計算機輔助書法作品真偽鑒別[D].南昌：南昌大學,2013.

[2] 俞凱.計算機書法若干關鍵技術研究[D].杭州：浙江大學,2010.

[3] 金貞，齊開悅，陳凱.一種適用于復雜圖像的漢字特征[J].信息安全與通信保密,2010(2):62-64.

[4] 胡海青,譚建龍,朱亞濤,等.改進SIFT算法在文字圖像匹配中的應用[J].計算機工程,2013,39(1)：239-243.

[7] 孟偉,鐘娜.改進SURF算法在圖像漢字識別中的應用[J].計算機工程與應用,2015,51(12):156-160.

[10] 李歡歡,黃山,張洪斌.基于Harris與SIFT算法的自動圖像拼接[J].計算機工程與科學,2012,34(11):104-108.

[11] 鄒承明,侯小碧,馬靜.基于幾何學圖像配準的SIFT圖像拼接算法[J].華中科技大學學報(自然科學版),2016,44(4):32-36.

[12] 王君本,盧選民,賀兆.一種基于快速魯棒特征的圖像匹配算法[J].計算機工程與科學,2011,33(2):112-117.

[14] 朱貝貝，尚趙偉，袁博，等.抗混疊輪廓波變換的脫線中文手寫體筆跡識別[J]. 計算機工程與應用，2011,47(24):150-153.

[17] 陳抒瑢,李勃,董蓉,等.Contourlet-SIFT特征匹配算法[J].電子與信息學報,2013(5):1215-1221.