题库查找问题的一类简单局部采样算法

杨 旻 于宪荣

(烟台大学数学与信息科学学院 山东 烟台 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