楊 旻 于憲榮

(煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院 山東 煙臺(tái) 264005)

題庫(kù)查找問(wèn)題的一類(lèi)簡(jiǎn)單局部采樣算法

楊 旻 于憲榮

(煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院 山東 煙臺(tái) 264005)

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

題庫(kù)查找 局部采樣 自適應(yīng)

0 引 言

近年來(lái)，諸如在線(xiàn)查題這樣的圖像匹配問(wèn)題，由于廣泛的用戶(hù)需求和良好的應(yīng)用前景，日益得到重視。這類(lèi)應(yīng)用一般由用戶(hù)拍照上傳待查找題目的圖像，計(jì)算機(jī)經(jīng)過(guò)與數(shù)據(jù)庫(kù)圖像比對(duì)后，返回查找結(jié)果并提供具體的解題過(guò)程。這一問(wèn)題實(shí)現(xiàn)的一個(gè)關(guān)鍵在于題庫(kù)圖像特征向量的構(gòu)建。

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

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

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

1 自適應(yīng)局部采樣匹配算法

我們首先對(duì)題庫(kù)中的所有圖像進(jìn)行特征提取，并預(yù)存相應(yīng)的特征向量。這一過(guò)程主要包括以下兩個(gè)步驟：

圖1 分辨率調(diào)整示意圖

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

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

(1)

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

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

(2)

則更新W，即淘汰k。

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

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

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

2 實(shí)驗(yàn)結(jié)果及分析

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

實(shí)驗(yàn)的運(yùn)行環(huán)境為: Intel ( R) Core ( TM) i5 CPU @3.07 GHz，6.00 GB RAM，Windows 7( 64 位) 旗艦版操作系統(tǒng)；程序運(yùn)行環(huán)境為：MATLAB R2014a。

測(cè)試題庫(kù)中包括近1 000張涉及高等數(shù)學(xué)，概率統(tǒng)計(jì)，常微分方程的題目圖片，圖片為.jpg格式，分辨率不一。這里我們將水平分辨率統(tǒng)一調(diào)整為350 dpi，并采用OTSU算法進(jìn)行二值化處理。

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

圖3 待查詢(xún)題目一

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

圖4 處理后的圖像

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

圖5 二值化圖像

按上述算法提取特征向量并進(jìn)行查找匹配，當(dāng)匹配次數(shù)i=3時(shí)，輸出圖像數(shù)目為4，查詢(xún)結(jié)果如圖6-圖9所示。

圖6 輸出圖像1

圖7 輸出圖像2

圖8 輸出圖像3

圖9 輸出圖像4

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

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

圖10 待查詢(xún)題目二

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

圖11 處理后的圖像

按上述算法提取特征向量并進(jìn)行查找匹配，當(dāng)匹配次數(shù)i=3時(shí)，輸出圖像數(shù)目為2，查詢(xún)結(jié)果如圖12、圖13所示。

圖13 輸出圖像6

其中，圖13為要查詢(xún)的題目。由于本文構(gòu)建的特征提取算法僅在圖像中間進(jìn)行局部采樣，所以當(dāng)圖像邊緣部分模糊時(shí)，算法能夠找到匹配圖像。而對(duì)于一般的題庫(kù)圖像查找匹配問(wèn)題來(lái)說(shuō)，用戶(hù)上傳的圖像多為邊緣模糊圖像，當(dāng)然，如果圖像中間部分模糊，且模糊程度較高時(shí)，算法可能無(wú)法匹配出相似圖像了。

3 結(jié) 語(yǔ)

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

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

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

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

[3] 王魯平,馬峰,韓建濤.基于距離加權(quán)平均絕對(duì)差的模板漂移抑制算法[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),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].計(jì)算機(jī)應(yīng)用與軟件,2016,33(12):152-155,210.

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

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

[12] 李麗,郭雙雙,梅樹(shù)立,等.基于特征點(diǎn)提取匹配的蝗蟲(chóng)切片圖像的拼接和修復(fù)方法[J].農(nóng)業(yè)工程學(xué)報(bào),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] 呂亞軍,陳繼榮,鹿曉亮.基于內(nèi)容的文檔圖像傾斜校正[J].計(jì)算機(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。山東省自然科學(xué)基金項(xiàng)目(ZR2014AM003)。楊旻，教授，主研領(lǐng)域：科學(xué)工程計(jì)算，機(jī)器學(xué)習(xí)。于憲榮，本科生。

TP391.41

A

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