題庫查找問題的一類簡單局部采樣算法

楊 旻 于憲榮

(煙臺大學數學與信息科學學院 山東 煙臺 264005)

題庫查找問題的一類簡單局部采樣算法

楊 旻 于憲榮

(煙臺大學數學與信息科學學院 山東 煙臺 264005)

近年來，諸如在線查題這樣的圖像匹配問題，由于廣泛的用戶需求和良好的應用前景，日益得到重視。對于這類題庫匹配查找問題構建了一類新型的局部采樣算法，該算法適用于輕微變形且文字較為稀疏的題庫問題，如數學題庫。對于經過預處理后的圖像，采用不同的空間步長，僅僅針對每幅圖像的中間部分進行間隔的降采樣，并對采樣結果進行簡單的行(列)求和構建相應的低維特征向量，利用所得低維特征向量進行自適應查找匹配。最后，實驗結合傾斜與變形圖像、邊緣模糊圖像這兩類情形進行算法測試，獲得了令人滿意的查找結果。

題庫查找 局部采樣 自適應

0 引 言

近年來，諸如在線查題這樣的圖像匹配問題，由于廣泛的用戶需求和良好的應用前景，日益得到重視。這類應用一般由用戶拍照上傳待查找題目的圖像，計算機經過與數據庫圖像比對后，返回查找結果并提供具體的解題過程。這一問題實現的一個關鍵在于題庫圖像特征向量的構建。

圖像特征向量構建的常用手段有灰度方法和特征方法。基于灰度方法的匹配是用一定大小的圖像灰度矩陣與參考圖像的灰度矩陣按某種相似性度量方法進行搜索比較的匹配算法。序貫相似性檢測法(SSDA)算法[1]是基于灰度的匹配算法，該算法能夠很快丟棄不匹配點，減少花在不匹配點上的計算量，從而提高匹配速度。算法比較簡單，易于實現，但算法沒有抗干擾性能，對噪聲比較敏感。歸一化灰度組合相關(NIC)算法[2]是基于灰度組合矩陣的一種灰度相關法，主要利用相似圖像間像素灰度組合最少的原理進行圖像匹配，該算法解決了相關法對噪聲和灰度變化敏感的問題。平均絕對差(MAD)算法也是一種常用的基于灰度的圖像匹配算法[3]，其優點是方法簡單、抗干擾性能好、易于硬件實現，缺點是計算量大。

基于特征的匹配模式是首先提取反映圖像重要信息的特征如點、線、距，然后建立圖像之間特征的對應關系，從而進行圖像查找與匹配，其匹配優劣在很大程度上取決于特征提取的質量。常見的特征提取方法有Harris特征[4]、SUSAN特征[5]、M估計法[6]、隨機抽樣最大似然估計MLESAC(Maximum likelihood estimation by sample and consensus)[7]、SURF算法[8]等。其中，SURF算法由于對光照、旋轉、尺度變換有良好的魯棒性，在圖像匹配領域得到廣泛應用。但SURF算法比較復雜，主要包括特征點檢測、主方向選取、特征描述符生成、特征點匹配等步驟，并且在利用SIFT算子進行匹配時，需要計算兩幅圖像的所有維度SIFT描述算子間的歐氏距離，這需要耗費大量時間。為提高匹配速度，近年來，很多改進算法被相繼提出[9-12]。

考慮到大部分試題庫的圖像，其相應的二值化矩陣具有較好的稀疏性，針對此類特殊的圖像匹配問題，本文提出了一種新型的特征提取方法——局部采樣算法。該算法僅對圖像的中間部分進行縱向或橫向間隔采樣，采樣后對像素點求和，形成相應圖像的低維特征向量，并借助這些特征向量進行圖像的查找匹配，根據匹配結果自動確定比對次數。就題庫圖像匹配問題而言，與經典的圖像匹配算法，如SURF算法相比，本文所構建的局部采樣算法具有原理簡單、計算量小而又不失精度的優點。

1 自適應局部采樣匹配算法

我們首先對題庫中的所有圖像進行特征提取，并預存相應的特征向量。這一過程主要包括以下兩個步驟：

圖1 分辨率調整示意圖

圖2 αi=2，D=5時的特征提取示意圖

接下來考慮待查詢題目在題庫中的匹配問題。為保證匹配的準確性，這里要求待查詢題目由用戶完整拍攝并上傳，為保證搜題的準確性，每幅圖像應只含有一道題目。首先，由于拍攝角度的差異，需要對待查詢圖像進行傾斜校正，可采用的算法很多，例如投影法、Hough變換和近鄰法[14]；其次，如果圖像中有大量留白，需對圖像進行去空白邊緣處理，使整幅圖像均為黑色帶字部分。類似題庫圖像的預處理手段，對待查詢圖像進行二值化處理，得到相應的0-1矩陣B，其列的階數和題庫中圖像的列階數一致，等于m。

(1)

若題庫中某幅圖像相似度小于指定閾值T，則該幅圖像備選。第一輪比對結束后，若備選集圖像數目過多(大于M)，則調整步長為α2，對備選圖像進行新一輪的比對，當備選集圖像數目小于或等于M時，備選圖像集便可作為相似圖像輸出。這里根據備選集圖像數目自適應地確定比對輪數，從而在很大程度上減小了計算量，根據每幅圖像提取出的特征向量數目， 至多進行S輪比對。

算法：給定閾值T，最大相似圖像數M，初始化i=1，備選圖像集W為整個題庫。

(2)

則更新W，即淘汰k。

步驟3若W中圖像數目等于0，則輸出“未找到匹配圖像”，結束算法。若W中圖像數目大于0小于M，則輸出W作為相似圖像，結束算法；否則i++，返回步驟1。

步驟4若i=s，則直接輸出W中圖像，若W中圖像數目大于M，則輸出前M幅圖像，結束算法。

注意上述算法的空間復雜度至多為O(NS)。

2 實驗結果及分析

本節考慮兩類情形，第一類情形是用戶提供的圖像有一定的傾斜且部分字體有輕度變形；第二類情形是用戶提供的圖像邊緣模糊或部分缺失。

實驗的運行環境為: Intel ( R) Core ( TM) i5 CPU @3.07 GHz，6.00 GB RAM，Windows 7( 64 位) 旗艦版操作系統；程序運行環境為：MATLAB R2014a。

測試題庫中包括近1 000張涉及高等數學，概率統計，常微分方程的題目圖片，圖片為.jpg格式，分辨率不一。這里我們將水平分辨率統一調整為350 dpi，并采用OTSU算法進行二值化處理。

(1) 測試一：考慮如圖3所示的待查詢題目，該圖像有一定的傾斜且部分字體有輕度變形。

圖3 待查詢題目一

首先，對查詢圖像采用Hough變換法進行傾斜校正，去空白邊緣處理，處理后的圖像如圖4所示。

圖4 處理后的圖像

其次，對處理后圖像采用OTSU算法進行二值化處理，得到的二值化圖像如圖5所示。

圖5 二值化圖像

按上述算法提取特征向量并進行查找匹配，當匹配次數i=3時，輸出圖像數目為4，查詢結果如圖6-圖9所示。

圖6 輸出圖像1

圖7 輸出圖像2

圖8 輸出圖像3

圖9 輸出圖像4

其中，輸出圖像1為要查詢的題目，輸出圖像2屬于相似圖像。

(2) 測試二：考慮如圖10所示的待查詢題目圖像，該圖像兩側邊緣模糊。

圖10 待查詢題目二

對圖像采用OTSU算法進行二值化處理，得到的二值化圖像如圖11所示。

圖11 處理后的圖像

按上述算法提取特征向量并進行查找匹配，當匹配次數i=3時，輸出圖像數目為2，查詢結果如圖12、圖13所示。

圖13 輸出圖像6

其中，圖13為要查詢的題目。由于本文構建的特征提取算法僅在圖像中間進行局部采樣，所以當圖像邊緣部分模糊時，算法能夠找到匹配圖像。而對于一般的題庫圖像查找匹配問題來說，用戶上傳的圖像多為邊緣模糊圖像，當然，如果圖像中間部分模糊，且模糊程度較高時，算法可能無法匹配出相似圖像了。

3 結 語

本文針對目前被人們廣泛關注的在線查題這樣的圖像匹配問題，構建了一類新型題庫圖像匹配算法。該算法不依靠邊緣特征，僅從圖像中間進行局部采樣，并通過簡單累積求和獲取圖像特征，自適應地確定搜索匹配次數，相比于經典的圖像匹配算法，避免了特征點檢測、主方向選取、特征描述符生成、特征點匹配等步驟，具有原理簡單、計算量小而又不失精度的優點。實驗表明對于旋轉或輕微變形、且二值化矩陣具有較高稀疏性的理工類題目圖像，算法具有很好的匹配結果。

算法有待改進的地方包括：1) 僅考慮了完整圖像及邊緣部分模糊圖像的匹配問題，對于待查詢圖像為中間缺損圖像的匹配需要進一步研究。2) 對于文科類的文本密集題庫，如何提高匹配精度也需要進一步考慮。

[1] 吳培景,陳光夢.一種改進的SSDA圖像匹配算法[J].計算機工程與應用,2005,41(33):76-78.

[2] 陳寧江,李介谷.用歸一化灰度組合法進行圖像匹配[J].紅外與激光工程,2000,29(5):5-9.

[3] 王魯平,馬峰,韓建濤.基于距離加權平均絕對差的模板漂移抑制算法[J].中南大學學報(自然科學版),2012,43(10):3894-3899.

[4] Harris C,Stephens M.A combined corner and edge detector[C]//Proc. of Fourth Alvey Vision Conference,1988.

[5] Smith S M,Brady J M.SUSAN-a new approach to low level image processing[J].Internation Journal of Computer Vision,1997,23(1):43-78.

[6] Chen J H,Chen C S.Fast algorithm for robust template matching with M-estimators[J].IEEE Transactions on Single Processing,2003,51(1):230-243.

[7] Torr P H S,Zisserman A.MLESAC:a new robust estimator with application to estimating image geometry[J].Computer Vision and Image Understanding,2000,78(1):138-156.

[8] Bay H,Ess A,Tuytelaars T,et al.Speeded-up robust features (SURF)[J].Computer vision and image understanding,2008,110(3):346-359.

[9] 劉利鋒,馬燕,張相芬,等.采用二值SIFT特征描述的圖像匹配方法[J].計算機應用與軟件,2016,33(12):152-155,210.

[10] 楊松,邵龍潭,宋維波,等.一種基于SIFT特征的快速圖像匹配算法[J].計算機應用與軟件,2016,33(7):186-189,256.

[11] 伏雪,馬燕,林濤.一種新的基于圖論的圖像匹配算法[J].計算機應用與軟件,2016,33(12):156-159.

[12] 李麗,郭雙雙,梅樹立,等.基于特征點提取匹配的蝗蟲切片圖像的拼接和修復方法[J].農業工程學報,2015,31(7):157-165.

[13] Otsu N.A threshold selection method from gray-level histograms[J].IEEE Transsactions on Systems,Man and Cybernetics,1979,9(1):62-66.

[14] 呂亞軍,陳繼榮,鹿曉亮.基于內容的文檔圖像傾斜校正[J].計算機仿真,2006,23(12):192-196.

ASIMPLELOCAL-SAMPLINGALGORITHMFORSEARCHINGINQUESTIONBANKS

Yang Min Yu Xianrong

(SchoolofMathematicsandInformationScience,YantaiUniversity,Yantai264005,Shandong,China)

In recent years, due to a wide range of user needs and good application prospects, the image matching problems such as searching in question banks receive much more attention. In this paper, a new type of local sampling algorithm was proposed for the matching problem of this kind of question bank. The algorithm was suitable for the problem of minor problem and the sparse question such as the question bank of mathematics. For the pre-processed images, different spatial steps were used to sample the middle part of each image, and the corresponding low-dimensional eigenvectors were constructed by simply summing the sampling results. The adaptive matching of the low-dimensional eigenvector was used. Finally, the slight deformation and vague edge situations were tested in the experiments and the satisfying search results were obtained.

Question bank searching Local-sampling Adaptive matching

2016-12-26。山東省自然科學基金項目(ZR2014AM003)。楊旻，教授，主研領域：科學工程計算，機器學習。于憲榮，本科生。

TP391.41

A

10.3969/j.issn.1000-386x.2017.12.041