一种答卷的扫描方向判断方法

摘要

本发明公开了一种答卷的扫描方向判断方法，其特征在于，包括如下步骤：(1)扫描答卷，获得答卷图像；(2)计算答卷图像的最佳分割阈值；(3)检测水平直线特征点；(4)检测垂直直线特征点；(5)水平直线特征点和垂直直线特征点进行匹配；(6)生成模板数据；(7)判断扫描方向。本发明设计了一种直线特征点之间的相似度指标计算方法，该方法考虑了匹配率和匹配精度两种因素，具有准确率高、算法时间复杂度低且易于实现的优点；在扫描方向判断算法的设计上，使用水平直线检测或者垂直直线检测的多个直线模式与模板数据做匹配算法，因此算法具有非常高的稳定性。该方法广泛应用于答卷图像的扫描、分析、识别等领域。

说明书

技术领域

本发明涉及电子化阅卷领域，具体地讲，涉及一种答卷的扫描方向判断方法。

背景技术

答卷在教育领域中仍然发挥着非常重要的作用，答卷经高速采集设备扫描得 到答卷图像，这些图像一般存储于计算机，提供给数字化网上阅卷系统使用。

常用的答卷扫描方向判断方法使用特殊标记点的识别方法，例如缺角识别方 法和方块标记点识别方法，这些方法具有识别速度快、准确性高的特点，非常适 合于标准化考试领域。对于普通中学领域，缺乏足够的信息卡设计专业人员，因 此基于特殊标记点识别的扫描方向判断受到很大的限制。为此本发明研究了基于 答卷直线结构的扫描方向判断方法，该方法不受标记点识别方法的限制条件，具 有更广泛的应用性。

常用的直线检测包括Hough变换检测方法和有向单连通链检测方法,Hough变 换检测方法具有几何解析性简单、鲁棒性好、易于实现的特点，但也有很多缺点， 比如时间复杂性高、存储空间要求较高、不能判断线段的端点和长度等。基于有 向单连通链的方法虽然可以定位线段的端点和长度，但是通常需要估计连通链的 最小长度、连通链的合并和伪连通链的消除等方法，时间复杂度较高，不适合实 时图像处理的应用场合。

本发明提出了一种快速的水平直线和垂直直线特征点检测方法，使用直线特 征之间的匹配方法定量分析直线特征之间的相似性，给出相似性评价指标。

2.扫描答卷图像的特点

答卷图像是一种特殊的文档图像，具有一定的版面结构特征。一般答卷图像 都含有直线信息，并且包含部分文字内容，考生作答后，字符在尺寸、颜色等方 面差别加大，使得答卷图像的分析工作变得相对复杂。

常用的答卷图像方向判别使用标记点识别方法，一般是一些容易识别的标记 块。

如图1所示，是典型的带标记点的答卷图像(图像左下方的黑色矩形)，仅通 过识别这些黑色矩形就可以确定答卷的扫描方向，这种方法具有识别快速、准确 性高的特点。

但是随着数字化网上阅卷技术的普及，大量的普通中学开始自行组织数字化 网上阅卷项目，答卷的制作、学生考试、答卷扫描、网上阅卷不在依赖专业的技 术公司人员，同时给答卷图像的分析工作提出了更高的要求，其中出现了大量的 不规范的答卷，标记点的尺寸也缺乏统一的标准，因此研究基于直线特征的扫描 方向判别显得尤其重要。

如图2所示，图像中不存在用于判断扫描方向的标记点，一般通过图像的直线 特征分析图像的扫描方向。该答卷图像较复杂，直线特征比较明显，并且直线对 应的线段在颜色深浅、粗细、长短方面变化比较大，而且字符包含了中文、英文 字符，字符的排列方向上有横排、竖排，字符尺寸变化较大，这些因素增加了直 线分析的难度。

发明内容

本发明要解决的技术问题是提供一种答卷的扫描方向判断方法，具有较高的 准确性和稳定性，时间复杂度低易于实现。

本发明采用如下技术手段实现发明目的：

与现有技术相比，本发明的优点和积极效果是：本发明的直线特征点检测算 法计算稳定、高效，并且具有一定的自适应能力，检测行步长或者列步长具有自 适应能力；直线的特征点检测算法可处理图像偏斜、直线断裂等复杂情况；直线 特征点之间的匹配算法计算稳定、可靠，扫描方向判定方法计算简单、高效，实 际计算结果表明该算法可以非常稳定地确定答卷图像的扫描方向；该直线特征点 检测、匹配方法可用于其他图像处理领域，例如基于直线检测的文档图像倾斜角 估计、表格分析、表格识别等领域。

附图说明

图1为典型的标记点识别方法判断答卷扫描方向示意图。

图2为典型的无标记点的答卷图像。

图3为像素灰度增强邻域选择标识图。

图4为水平直线左边、右边连续像素标识图。

图5为水平直线特征点检测流程图。

图6为水平直线上面、下面连续像素标识图。

图7为垂直直线特征点检测流程图。

图8(a)为水平直线长度较短的特征点检测效果图；图8(b)为水平直线 长度较长的特征点检测效果图。

图9(a)为扫描效果较差的原始表格图像；图9(b)为垂直直线特征点检 测标记结果图。

图10(a)为水平直线倾斜的原始扫描图像；图10(b)倾斜图像的水平特 征点检测标记结果图。

图11为图10(a)的水平直线模板数据计算结果。

图12为图10(a)的垂直直线模板数据计算结果。

图13(a)为普通答卷模板图像；图13(b)为扫描方向为0时的扫描图像； 图13(c)为扫描方向为1时的扫描图像；图13(d)为扫描方向为3时的扫描 图像。

具体实施方式

下面结合附图和优选实施例对本发明作更进一步的详细描述。

1.快速直线特征点检测算法

1.1答卷图像的最佳分割阈值计算方法

本发明研究的扫描答卷图像采用100dpi扫描，扫描灰度位深为8，本发明使用 k均值聚类方法实现答卷图像的二值化，(k＝2：前景为直线文字等、背景为空白 区域，分割阈值初值设置为128)，使用迭代方法得到最优分割阈值。这种全局聚 类方法在一致的图像区域保证全局最优，是一种非常有效的最佳分割阈值计算方 法，该算法的核心思想是找出k个聚类中心，使得每一个样本数据点与其最近的 聚类中心的平方距离和最小化，计算步骤：

(1)计算图像的直方图H，满足$\underset{i=0}{\overset{255}{\Sigma }}{H}_i=1;---\left(1\right)$

(2)根据灰度分割阈值T0(初值为128)，计算两个聚类中心(前景聚类中心C0、 背景聚类中心C1)，满足：

$C0=\frac{\underset{i=0}{\overset{T0}{\Sigma }}i*H_i}{\underset{i=0}{\overset{T0}{\Sigma }}{H}_i}---\left(2\right)$

$C1=\frac{\underset{i=T0+1}{\overset{255}{\Sigma }}i*H_i}{\underset{i=T0+1}{\overset{255}{\Sigma }}{H}_i}---\left(3\right)$

(3)根据前景、背景的聚类中心，得到分割阈值T1，满足条件：

(4)若T0＝＝T1，迭代停止，转步骤(5)，否则令T0＝T1，重复执行步骤(2)； (5)输出最佳灰度分割阈值T1。

1.2水平直线特征点检测算法

为了能够快速地检测到直线对应的特征点，记水平直线检测的列位置总数为 N_h，一般取N_h＝32，假设图像的宽度表示为W，则列位置的间隔(步长)S_h表示 为：

S_h＝W/N_h                      (5)

因此所有的列位置的集合可以表示为：

P_h＝{p_i|i*S_h},i＝0,1,2,...(N_h-1)           (6)

依次判断每个列位置上的行位置处像素灰度是否满足水平直线的特征点，水 平直线的特征点满足两个基本条件：

条件(1)：该位置处的像素灰度小于最佳灰度分割阈值T1，如果该位置处的像素 灰度大于等于T1，则增强该位置处的像素灰度，增强后的像素灰度如果小于固定 灰度阈值T_D＝128，则仍认为该位置处的原始像素灰度小于最佳分割阈值T1，选 择在该位置处增强灰度，将大大提高直线检测的稳定性，同时又保证了水平直线 特征点检测的速度(大大减少了需要灰度增强的像素位置)。

如图3所示，“*”标识当前需要灰度增强的像素位置，水平和垂直方向上的 邻域选择为{-2,-1,0,1,2}，首先计算该邻域内所有像素的平均灰度M，当前像 素的灰度为g，增强因子记为σ，则增强后的灰度g'计算为：

g'＝g+σ*(g-M)                (7)

增强相关的邻域尺寸与检测直线的宽度(粗细)有关，经大量样本反复实验， 一般设置为待检测直线的宽度(图3所示邻域尺寸为2)，增强因子一般设置为 6.0，该值越大，越能够从极低质量的图像中检测出特征点，但是会增加伪特征 点被检测出来的概率。

条件(2)：该位置处左边至少有连续L_h(根据水平直线的特点和检测要求，一般 取32即可满足要求)个像素位置满足条件(1)，或者该位置处右边至少有连续L_h个像素位置满足条件(1)，或者该位置处左边与右边总共至少有连续L_h个像素位 置满足条件(1)。

如图4所示，“*”表示当前需要判断的像素位置，左边连续像素判断位置为 0,1,2表示的位置，右边连续像素判断位置为3,4,5表示的位置，“X”表示不需 要判断的位置。

假设水平直线的最大宽度(粗细)为w_h，如果找到了一个水平特征点位置(i,j) 后，下一个特征点检测位置为(i+w_h,j)，这样实际上检测了直线的下边缘位置， 这样将大大提高直线检测的效率。

一般来说，水平的直线的长度不会覆盖图像整个宽度空间，因此每个列上至 少检测到一个直线特征点的列的总数D_h一般会小于N_h，如果D_h太小，会影响直 线检测精度和后期的匹配算法，因此规定一个初值R_h，如果(D_h/N_h)<R_h(一般取 R_h＝0.90)成立，则重新调整S_h为S_h'如下：

S_h'＝S_h*(D_h/N_h)                    (8)

经过列的步长调整后，重新检测特征点，输出所有列位置上的水平直线特征 点，列位置的总数N_h'

N_h'＝W/S_h'                (9)

水平直线特征点检测流程图如图5所示.水平直线特征点需满足上述水平 直线特征点条件(1)和条件(2)，所有列的检测总数D_h一般是需要调整的(调 整列的步长)，发生在以下两种情况之一：

条件(1)：水平直线的长度不足以覆盖待检测图像的宽度；

条件(2)：尽管水平直线的长度接近(例如覆盖90％的图像宽度)待检测图像的 宽度，但是水平直线的质量较差，以至于部分水平直线特征点没有检测出来。

1.3垂直直线特征点检测算法

垂直直线特征点的检测算法与水平直线特征点的检测算法在思路上是一致 的，记垂直直线检测的行位置总数为N_v，一般取N_v＝32，假设图像的高度表示为 H，则行位置的间隔(步长)S_v表示为：

S_v＝H/N_v                         (10)

因此所有的行位置的集合可以表示为：

P_v＝{p_i|i*S_v},i＝0,1,2,...(N_v-1)               (11)

依次判断每个行位置上的列位置处像素灰度是否满足垂直直线的特征点， 垂直直线的特征点满足两个基本条件：

条件(1)：该位置处的像素灰度小于最佳灰度分割阈值T1，如果该位置处的像素 灰度大于等于T1，则增强该位置处的像素灰度，增强后的像素灰度如果小于固定 灰度阈值T_D＝128，则仍认为该位置处的原始像素灰度小于最佳分割阈值T1，选 择在该位置处增强灰度(增强算法按照公式(7)计算)，将大大提高直线检测的 稳定性，同时又保证了垂直直线特征点检测的速度(大大减少了需要灰度增强的 像素位置)。

条件(2)：该位置处上面至少有连续L_v(根据垂直直线的特点和检测要求，一般 取32即可满足要求)个像素位置满足条件(1)，或者该位置处下面至少有连续L_v个像素位置满足条件(1)，或者该位置处上面与下面总共至少有连续L_v个像素位 置满足条件(1)。

如图6所示，“*”表示当前需要判断的像素位置，上面连续像素判断位置为 0,1,2表示的位置，下面边连续像素判断位置为3,4,5表示的位置，“X”表示不 需要判断的位置。

假设垂直直线的最大宽度(粗细)为w_v，如果找到了一个垂直特征点位置(i,j) 后，下一个特征点检测位置为(i,j+w_v)，这样实际上检测了直线的左边缘位置， 这样将大大提高直线检测的效率。

一般来说，垂直直线的长度不会覆盖图像整个高度空间，因此每个行上至少 检测到一个直线特征点的行的总数D_v一般会小于N_v，如果D_v太小，会影响直线 检测精度和后期的匹配算法，因此规定一个初值R_v，如果(D_v/N_v)<R_v(一般取 R_v＝0.90)成立，则重新调整S_v为S_v'如下：

S_v'＝S_v*(D_v/N_v)                      (12)

经过行的步长调整后，重新检测特征点，输出所有行位置上的垂直直线特征 点，行位置的总数N_v'

N_v'＝H/S_v'                   (13)

垂直直线特征点检测流程图：如图7所示，垂直直线特征点需满足上述垂直 直线特征点条件(1)和条件(2)，所有行的检测总数D_v一般是需要调整的(调 整行的步长)，发生在以下两种情况之一：

条件(1)：垂直直线的长度不足以覆盖待检测图像的高度；

条件(2)：尽管垂直直线的长度接近(例如覆盖90％的图像高度)待检测图像的 高度，但是垂直直线的质量较差，以至于部分垂直直线特征点没有检测出来。

2.直线特征点之间的匹配算法

水平或者垂直直线特征点检测完成后，输出直线对应的特征点的坐标，这些 坐标构成了图像中的水平直线或者垂直直线的模式。为了讨论的方便性，使用两 个集合表示某两个行或者某两个列检测到的直线特征点的位置(直线特征点的位 置构成直线模式)。

L_i＝{p₀,p₁,...p_m-1}

L_j＝{q₀,q₁,...q_n-1}                   (14)

i≠j

公式(14)表示在第i个位置检测到了m个直线特征点的坐标，在第j个位置 检测到了n个直线特征点的坐标，因为直线检测是按照坐标从小到大顺序检测的， 因此满足下列不等式：

p₀<p₁<p₂<,...<p_m-1                      (15)

q₀<q₁<q₂<,...<q_n-1

这样直线特征点之间的匹配问题等价于两个位置集合之间的最佳匹配问题， 并且两个集合中的坐标满足公式(15)的要求，所有可能的匹配模式总数C＝m*n， 假定集合L_i中的第α个位置和集合L_j中的第β个位置是匹配的，定义该匹配模式 的相似度S_α,β为：

S_α,β＝R_M*E_M

R_M∈[0,1]                       (16)

E_M∈[0,1]

其中R_M表示匹配率，E_M表示匹配精度，匹配率和匹配精度越大越好，集合L_i中的第α个位置和集合L_j中的第β个位置匹配时，按下列方式判断是否匹配：

$f(p_{\alpha },q_{\beta })=\left(\begin{array}{c}1,|p_{\alpha }-q_{\beta }|\le T\\ 0,\mathrm{else}\end{array}\right)---\left(17\right)$

其中T表示系统容许的最大匹配误差参数，一般设置为6，越大表示越容易匹 配，越小表示系统要求的匹配精度越高，f(p_α,q_β)＝1表示两个点是匹配的，否则 两个点不匹配(不匹配时匹配误差记为0)，匹配的两个点按如下方式计算两个 点位置的匹配误差：

e(p_α,q_β)＝|p_α-q_β|/T                   (18)

计算S_α,β时，先按如下方式调整集合L_i和L_j：

L_i＝{p₀-p_α,p₁-p_α,...p_m-1-p_α}＝{p'₀,p₁',...p'_m-1}

L_j＝{q₀-q_β,q₁-q_β,...q_n-1-q_β}＝{q'₀,q₁',...q'_m-1}   (19)

i≠j

按公式(19)调整后，集合L_i中第α个位置处的坐标为0，同理集合L_j中第β个 位置处的坐标为0。下面计算集合L_i中第k个点的坐标在集合L_j中的匹配点对应 的下标k'，该下标满足条件：

min(|p'_k-q_kk'|),kk＝0,1,2...m-1                (20)

根据公式(20)可以计算出集合L_i中每个点的下标u_i在集合L_j中匹配的下标v_i， 记匹配对应关系为：

M＝{(u_i,v_i)|i＝0,1,2,...(m-1)}                   (21)

根据匹配对应关系，计算匹配率和匹配精度如下：

$R_M=\frac{1}{m}\underset{i=0}{\overset{m-1}{\Sigma }}f(p_{u_i},q_{v_i})$

$E_M=1.0-\frac{1}{\underset{i=0}{\overset{m-1}{\Sigma }}f(p_{u_i},q_{v_i})}\underset{i=0}{\overset{m-1}{\Sigma }}e(p_{u_i},q_{v_i})---\left(22\right)$

将公式(22)带入公式(16)即可得到S_α,β，因此直线特征点之间的匹配问题 等价于如下最大值问题：

maxS_α,β

α＝0,1,2,...(m-1)                      (23)

β＝0,1,2,...(n-1)

3.模板数据生成方法

在扫描方向判断时，首先选取一张质量较好的扫描图像(用于生成模板数据， 用于生成模板数据的图像称为模板图像)，执行水平直线特征点检测或者垂直直 线特征点检测步骤，为了叙述的方便性，假设该扫描图像只含有水平直线，经水 平直线检测步骤，最终得到D_h个列检测位置，每个列检测位置对应一个水平直线 模式，按如下方式选择最佳直线模式：

(1)每个水平直线模式都记录了水平直线的位置，计算每个水平直线模式中水 平直线位置的个数，如果D_h个水平直线模式中水平直线位置的个数的最大值 只有一个，那么直接给出直线模式对应的特征点数据作为模板数据，同时可 信度标记为0，这时需要人工确认模板数据正确性以免发生错误；否则转步 骤(2)。

(2)如果D_h个水平直线模式中水平直线位置的个数的最大值大于1个，那么根 据直线特征点之间的匹配算法两两计算它们之间的匹配相似度，把匹配相似 度最大的两个直线模式之一作为模板数据输出，可信度即为这两个直线模式 之间的匹配相似度，相似度小于给定的阈值(例如0.95)，则需要人工确认 模板数据的正确性。

4.扫描方向判断方法

一般来说，扫描图像的宽度和高度是不相等的，而且差别比较大，因此扫描 方向判断时，可以根据宽度和高度的大小关系确定答卷是横向扫描的还是纵向扫 描的，为了叙述的方便性，假设只用图1所示的水平直线特征点判定扫描方向， 并且规定扫描图像正常(如图1所示)用方向0表示，扫描图像(图1所示)顺 时针旋转90度、180度、270度时，依次用方向1、方向2、方向3表示，则某 个待确定图像的扫描方向按如下步骤确定：

(1)对模板图像执行水平直线特征点检测并生成模板数据η0(如图1所示，扫 描方向为方向0)，记录图像的宽度W0和高度H0之间的大小关系Ω0，根据模板 数据η0(模板数据中有m个水平直线特征点坐标)生成数据η2：

η0＝{p_i|i＝0,1,2,...(m-1)}                         (24)

η2＝{H0-p_i|i＝0,1,2,...(m-1)}

(2)输入待确定扫描方向的图像I；

(3)图像I的宽度W1和高度H1之间的大小关系Ω1如果与Ω一致，则图像I的扫 描方向为方向0或者方向2，转步骤(4)，否则图像I的扫描方向为方向1或者 方向3，转步骤(7)；

(4)检测图像I的水平直线特征点，输出所有列位置上的水平直线特征点，假设 最终输出了N个水平直线模式Ψ＝{ψ₀,ψ₁,ψ₂...ψ_N-1}，根据直线特征点之间的匹配算 法计算模板数据η0与N个水平直线模式Ψ之间的相似度，得到N个相似度S_η0,Ψ， 同理计算模板数据η2与N个水平直线模式Ψ之间的相似度，得到N个相似度 S_η2,Ψ：

S_η0,Ψ＝{s_η0,i|i＝0,1,2...(N-1)}                 (25)

S_η2,Ψ＝{s_η2,i|i＝0,1,2...(N-1)}

(5)计算S_η0,Ψ中最大的相似度，记为s_η,0，计算S_η2,Ψ中最大的相似度，记为s_η,2； (6)如果s_η,0>(s_η,2+δ)，则图像I的扫描方向为方向0，其中δ为可靠性控制参数， 一般取值为0.1(当s_η,0与s_η,2很接近时需要人工确认扫描方向)，如果(s_η,0+δ)<s_η,2， 图像I的扫描方向为方向2，否则图像I的扫描方向不能确定，给出提示信息，人 工确认扫描方向。

(7)检测图像I的垂直直线特征点，输出所有行位置上的垂直直线特征点，假设 最终输出了K个垂直直线模式根据直线特征点之间的匹配算法 计算模板数据η0与K个垂直直线模式之间的相似度，得到K个相似度同 理计算模板数据η2与K个垂直直线模式之间的相似度，得到K个相似度

(8)计算中最大的相似度，记为s_η,1，计算中最大的相似度，记为s_η,3；

(9)如果s_η,1>(s_η,3+δ)，则图像I的扫描方向为方向1，如果(s_η,1+δ)<s_η,3，图像I的 扫描方向为方向3，否则图像I的扫描方向不能确定，给出提示信息，人工确认 扫描方向。

如图8(a)、图8(b)所示，初值N_h＝32，图像中的“□”表示检测到的 水平直线特征点的位置，水平直线的长度较短时，列的检测步长也较小(图8(a))， 水平直线的长度较大(图8(b))，列的检测步长较大，算法具有一定的自适应 能力，从而保证检测到的水平直线的特征点在数量上保持一致，图8(a)检测 到了29个水平直线特征点，图8(b)检测到了31个水平直线特征点，均与N_h接 近。

4.2垂直直线特征点检测效果

垂直直线特征点的检测算法具有一定的自适应能力，为了观察垂直直线特征 点检测的稳定性，使用结构比较复杂的表格图像做测试。

如图9(a)、图9(b)所示，初值N_v＝32，图像中的“□”表示检测到的垂 直直线特征点的位置，可有效检测图像中的倾斜直线。

4.3倾斜图像直线特征点检测效果

如图10所示，初值N_h＝32，图像中的“□”表示检测到的水平直线特征点的 位置，直线特征点检测算法对倾斜角度不敏感，可正确定位水平直线特征点的位 置。

4.4模板数据生成效果

如图11所示，N_h＝32，图像中的“□”表示检测到的水平直线特征点的位置， 对应的模板数据可信度为0.9722，总共有39个水平直线特征点，他们代表39 条水平直线。

如图11所示，N_v＝32，图像中的“□”表示检测到的垂直直线特征点的位置， 对应的模板数据可信度为1.0，总共有5个垂直直线特征点，他们代表5条垂直 直线。

4.5扫描方向判断实验效果

如图13所示，普通答卷扫描图像，其中(a)作为模板图像，使用水平直线 特征点判断扫描方向，计算结果如下：

表1扫描方向判断计算结果

如表1所示，根据计算结果，可以判定图13(b)的扫描方向为方向0，图 13(c)的扫描方向为方向1，图13(d)的扫描方向为方向3。