基于能量最小化框架的文档图像倾斜度检测与纠正方法

摘要

本发明提出了一种基于能量最小化框架的文档图像倾斜度检测和纠正方法，该方法的研究对象为机打文档图像，文档图像中的内容可以是文字、表格、图片等。本发明首先需要使用扫描仪将文档扫描成电子文档图像，然后估算前景像素状态信息，然后利用前景像素状态信息构建能量函数，然后利用图像处理技术和直线拟合技术计算初始的倾斜度，最后进行能量最小化过程得到最终的倾斜度并将文档图像进行纠正。本发明能适用于多种不同类型的文档，使得倾斜度检测更加精确，在保证精度的同时也提高了倾斜度检测的速度。

说明书

技术领域

本发明涉及文档分析与应用领域，具体涉及一种基于能量最小化框架的文档 图像倾斜度检测与纠正方法。

背景技术

随着数字化技术的不断发展，电子文档的出现在人们日常生活中变得越来越 流行，比如使用相机或扫描仪来记录管理日志，存储历史文件等。相对纸质文档， 电子文档具有方便性，永久性等优势。在获取或采集电子文档图像时，发生一定 的倾斜是不可避免。然而，大部分文档系统(例如光学字符识别，文档页面布局 分析等)对文档图像的倾斜度是敏感的。因此，倾斜度检测和纠正在文档图像分 析与应用领域中变成一个重要的问题。为了纠正倾斜度，在数字化过程中，文档 对齐预处理操作是必要的。

文档图像可以分为两种：手写文档图像和机打文档图像。当在一个不受约束 的条件下书写文本时，从手写文档图像中检测倾斜度是一个相对困难的任务。相 对手写文档图像，机打文档图像通常是规则排列的而且内容具有多样性(文字， 表格，图像等等)。尽管目前已有大量科研人员在研究机打文档图像的倾斜度检 测和纠正方法，但是它仍然是一个具有挑战性的问题。

发明内容

基于以上不足之处，本发明提出了一种基于能量最小化框架的文档图像倾斜 度检测和纠正方法，该方法的研究对象为机打文档图像，文档图像中的内容可以 是文字、表格、图片等。本发明首先需要使用扫描仪将文档扫描成电子文档图像， 然后估算前景像素状态信息，然后利用前景像素状态信息构建能量函数，然后利 用图像处理技术和直线拟合技术计算初始的倾斜度，最后进行能量最小化过程得 到最终的倾斜度并将文档图像进行纠正。

该方法包括三个过程，具体如下：

(1)计算前景像素状态信息

在计算前景像素状态信息之前，首先对扫描得到的文档图像进行二值化，用 黑色表示前景，白色表示背景像素，给定一个前二值文档图像I之后，前景像素 的状态计算过程如下：一个边界框定义为一个文档图像的边界，用P记作整个前 景像素的集合，(W，H)记作文档图像I的大小，那么对每一个前景像素p∈P，它 的状态信息为s_p＝(x_p，y_p，w_p，h_p)，其中x_p，y_p，w_p，h_p分别为p到图像最左、最上、 最右和最下边的距离；

(2)利用直线拟合技术估算初始倾斜度

接下来利用文档图像中最外围的前景像素的状态信息来估算初始倾斜度，一 个边界框有四个边：上、下、左和右，对每一边都能得到其最外围的前景像素状 态信息子集，用以下方式得到上边最外围前景像素状态信息子集，记为

$\mathrm{TS}=\underset{i=1}{\overset{W}{\cup }}{s}_i---\left(1\right)$

y_i∈s_i∩y_i＝min{y_p|y_p∈s_p∩x_p∈s_p∩x_p＝i}.

将TS中每个元素的x_p做为x坐标，y_p作为y坐标画图，图中下面的点拟合成一条 直线，边界框剩下的三边都经过该处理，将使用直线拟合的技术来估算文档图像 的初始倾斜度，在直线拟合之前先对TP进行采样，用如下方式将TP划分为N 个互不重叠的部分STS_i：

$\mathrm{TS}=\underset{i=1}{\overset{N}{\cup }}{\mathrm{STS}}_i$

${\mathrm{STS}}_i=\left\{s_p\right|x_p\in s_p\cap \frac{(i-1)\times W}{N}+1\le x_p\le \frac{i\times W}{N}\}$

N＝32，接下来用如下方式构建一个子集FTS，即计算每个部分STS_i中y_i最小 的那个前景像素状态信息：

$\mathrm{FTS}=\underset{i=1}{\overset{N}{\cup }}(s_i\cap s_i\in {\mathrm{STS}}_i)---\left(3\right)$

y_i∈s_i∩y_i＝min{y_p|y_p∈s_p∩s_p∈STS_i}

进行采样操作完之后，需要通过以下方式进一步消除没用的状态信息得到有 效的用来进行直线拟合的状态信息VTS

$\mathrm{VTS}=\left\{s_p\right|s_p\in \mathrm{FTS}\cap y_p\in s_p\cap y_p<\frac{H}{3}\}---\left(4\right)$

然后采用穷举搜索的方式在VTS中做直线拟合直到找到两个状态信息使得有最 多的其他状态信息到由这两个状态信息确定的直线之间的距离小于指定的阈值 D；

对边界框的四边都进行直线拟合之后得到四条直线，接下来就是找到拟合最 好的那条直线，同时该直线对应的倾斜角就是文档图像的初始倾斜角；用 {l_t，l_b，l_i，l_r}记作拟合的四条直线，{LS_t，LS_b，LS_i，LS_r}记作靠近相应直线的状态信 息，要是某条直线对应的状态信息的个数小于M，在下面的操作中将不再考虑该 直线，对每条直线l_i，计算所有直线状态信息Ls_i和直线l_i之间的距离之和，然后 用如下方式计算比值R_i：

$R_i=\frac{{\mathrm{SD}}_i}{{\left(f\left({\mathrm{LS}}_i\right)\right)}^2}---\left(5\right)$

其中f(·)计算一个集合中元素的个数，{R_t，R_b，R_t，R_r}中的最小值对应的直线就是 最佳拟合的直线，最终最佳拟合的直线对应的倾斜角就是文档图像的初始倾斜 角，其中D＝5，M＝5；

(3)使用能量最小化过程计算最终倾斜度

得到初始倾斜角之后，然后用能量最小化过程计算最终倾斜角，如下式所示：

$\hat{S}=\underset{S}{\arg \min }E\left(S\right)---\left(6\right)$

该过程包括能量函数构建和能量最小化两个步骤，如下式所示：

E(S)＝ωE_B(S)+(1-ω)E_F(S)     (7)

ω＝0.98，其中E_B(S)考虑了全局背景信息，如下式所示：

设置和φ(·)为：

Y_i＝{s_p|s_p∈S∩y_p∈s_p∩y_p＝i}     (9)

X_j＝{s_p|s_p∈S∩x_p∈s_p∩x_p＝j}

其中Sgn(·)是一个符号函数，定义为：

E_F(S)反应了全局的前景信息，如下式所示：

E_F(S)＝δ(S)+λ(S)     (11)

设置δ(·)和λ(·)为：

$\delta \left(S\right)=\frac{1}{M_Y}\sqrt{\frac{1}{f\left(Y\right)}\underset{k=1}{\overset{f\left(Y\right)}{\Sigma }}{(f\left(Y_k\right)-\bar{Y})}^2}$

$\bar{Y}=\frac{1}{f\left(Y\right)}\underset{k=1}{\overset{f\left(Y\right)}{\Sigma }}f\left(Y_k\right)$      (12)

$\lambda \left(S\right)=\frac{1}{M_X}\sqrt{\frac{1}{f\left(X\right)}\underset{k=1}{\overset{f\left(X\right)}{\Sigma }}{(f\left(X_k\right)-\bar{X})}^2}$

$\bar{X}=\frac{1}{f\left(X\right)}\underset{k=1}{\overset{f\left(X\right)}{\Sigma }}f\left(X_k\right)$

其中M_Y＝max{f(Y_i)|Y_i∈Y}， M_X＝max{f(X_i)|X_i∈X}，且f(·)计算一个集合中元素的个数；

构造完能量函数以后，根据直线拟合得到的初始倾斜角和所有前景像素的状 态信息，通过反复地计算能量函数和旋转前景像素的状态信息，找到使得能量函 数值最小时所旋转的角度，这个角度就是最终的倾斜角；

状态信息的旋转过程如下：

S′＝rotate(S，θ)     (13)

其中rotate(·)计算每个前景像素的状态信息s_p∈S旋转后的结果s_p′，计算过程如 下：

${x_p}^{\prime }=(x_p-\frac{W}{2})\cos \theta -(y_p-\frac{H}{2})\sin \theta +\frac{W}{2}$

${y_p}^{\prime }=(x_p-\frac{W}{2})\sin \theta +(y_p-\frac{H}{2})\cos \theta +\frac{H}{2}---\left(14\right)$

w_p′＝W-x_p′，h_p′＝H-y_p′

本发明的优点：

1.本发明中的文档图像倾斜度检测和纠正方法，它不考虑文档图像中的具体内 容，考虑的是文档图像的全局结构。这样使得本发明能适用于多种不同类型 的文档。

2.本发明中的方法是基于能量最小化框架，且提出了一个新的能量代价函数， 该函数综合考虑了文档图像中的全局背景信息和前景信息，从而使得倾斜度 检测更加精确。

3.本发明在检测文档图像倾斜度时，是一个由粗到细的过程。先通过直线拟合 技术得到初始倾斜度，再通过能量最小化得到最终倾斜度，这样在保证精度 的同时也提高了倾斜度检测的速度。

4.本发明中直线拟合技术和能量最小化技术是两个独立的过程，因此可以设计 出其他的方法替换它们，同时也可根据具体应用的需要可以选择其中一个技 术或两个技术来完成倾斜度检测。这样提高了本发明的使用灵敏性。

附图说明

图1为基于能量最小化的倾斜度检测方法的框图

图2为初始倾斜度计算过程图，

其中，(a)：前景像素状态信息计算过程图，(b)：最外围状态信息(x，y)坐标图， (c)：直线拟合过程图；

图3为能量最小化过程图，

其中，(a)：初始倾斜度，(b)：能量最小化过程，(c)：倾斜度纠正后图像；

图4为漫画文档图像倾斜度检测和纠正实例图，

其中，(a)：原始图像，(b)：能量最小化过程，(c)：倾斜度纠正后图像；

图5为图表文档图像倾斜度检测和纠正实例图，

其中，(a)：原始图像，(b)：能量最小化过程，(c)：倾斜度纠正后图像；

图6为建筑结构图文档图像倾斜度检测和纠正实例图，

其中，(a)：原始图像，(b)：能量最小化过程，(c)：倾斜度纠正后图像。

具体实施方式

本发明提出了一种基于能量最小化框架的文档图像倾斜度检测和纠正方法， 图1给出了该方法的框图。如图所示，该方法主要包括三个过程：计算前景像素 状态、使用直线拟合技术得到初始倾斜度和进行能量最小化过程得到最终倾斜 度。下面分别详细地描述这三个步骤。

1.计算前景像素状态信息

在计算前景像素状态信息之前，首先对扫描得到的文档图像进行二值化，用 黑色表示前景，白色表示背景像素。给定一个前二值文档图像I之后，如图2(a) 所示，前景像素的状态计算过程如下：一个边界框定义为一个文档图像的边界， 如图2(a)中的最外侧矩形框。用P记作整个前景像素的集合，(W，H)记作文档图 像I的大小。那么对每一个前景像素p∈P，它的状态信息为s_p＝(x_p，y_p，w_p，h_p)， 其中x_p，y_p，w_p，h_p分别为p到图像最左、最上、最右和最下边的距离，若将原点 设置在图像的左上角，则(x_p，y_p)为像素p在图像I中的位置的坐标， w_p＝W-x_p，h_p＝H-y_p。用S＝{(x_p，y_p，w_p，h_p)}_p∈P记为图像中所有前景像 素点P的状态信息。

2.利用直线拟合技术估算初始倾斜度

接下来利用文档图像中最外围的前景像素的状态信息来估算初始倾斜度。如 图2(a)所示，一个边界框有四个边：上、下、左和右。对每一边都能得到其最外 围的前景像素状态信息子集。下面以上边为例，我们用以下方式得到上边最外围 前景像素状态信息子集，记为

$\mathrm{TS}=\underset{i=1}{\overset{W}{\cup }}{s}_i---\left(15\right)$

y_i∈s_i∩y_i＝min{y_p|y_p∈s_p∩x_p∈s_p∩x_p＝i}

将TS中每个元素的x_p做为x坐标，y_p作为y坐标画图，如图2(b)左上角的子图所 示。由图可知，图中下面的点可以拟合成一条直线。同理边界框剩下的三边都可 以经过以上处理。这样在拟合得到的四条直线中，至少有一条直线的倾斜角与文 档图像本身的倾斜角很接近。因此本发明将使用直线拟合的技术来估算文档图像 的初始倾斜度。下面以TP为例，详细描述本发明中的直线拟合方法。

为了加快整个直线拟合的过程并估计得到更精确的初始倾斜度，本发明在直 线拟合之前先对TP进行采样。即用如下方式将TP划分为N个互不重叠的部分 STS_i：

$\mathrm{TS}=\underset{i=1}{\overset{N}{\cup }}{\mathrm{STS}}_i$

${\mathrm{STS}}_i=\left\{s_p\right|x_p\in s_p\cap \frac{(i-1)\times W}{N}+1\le x_p\le \frac{i\times W}{N}\}$

在本发明中，N被设置为N＝32。接下来用如下方式构建一个子集FTS，即计算 每个部分STS_i中y_i最小的那个前景像素状态信息：

$\mathrm{FTS}=\underset{i=1}{\overset{N}{\cup }}(s_i\cap s_i\in {\mathrm{STS}}_i)---\left(17\right)$

y_i∈s_i∩y_i＝min{y_p|y_p∈s_p∩s_p∈STS_i}

图2(c)给出了对应图2(b)采样后的结果。

进行采样操作完之后，尽管大部分远离理想拟合的直线的状态信息被移除 了，但是我还需要通过以下方式进一步消除没用的状态信息得到有效的用来进行 直线拟合的状态信息VTS(如图2(c)中虚线以下的状态信息)：

$\mathrm{VTS}=\left\{s_p\right|s_p\in \mathrm{FTS}\cap y_p\in s_p\cap y_p<\frac{H}{3}\}---\left(18\right)$ 然后我们采用穷举搜索的方式在VTS中做直线拟合直到找到两个状态信息使得 有最多的其他状态信息到由这两个状态信息确定的直线之间的距离小于指定的 阈值D。

对边界框的四边都进行直线拟合之后得到四条直线，接下来就是找到拟合最 好的那条直线，同时该直线对应的倾斜角就是文档图像的初始倾斜角。用 {L_t，l_b，l_i，l_r}记作拟合的四条直线，{LS_t，LS_b，LS_i，LS_r}记作靠近相应直线的状态信 息(如图2(c)中的十字点)。要是某条直线对应的状态信息的个数小于M，在下 面的操作中将不再考虑该直线。对每条直线l_i，计算所有直线状态信息LS_i和直线l_i之间的距离之和，然后用如下方式计算比值R_i：

$R_i=\frac{{\mathrm{SD}}_i}{{\left(f\left({\mathrm{LS}}_i\right)\right)}^2}---\left(19\right)$

其中f(·)计算一个集合中元素的个数。{R_t，R_b，R_i，R_r}中的最小值对应的直线就是 最佳拟合的直线(如图2(c)右上角和图3(a)拟合的直线)。最终最佳拟合的直线 对应的倾斜角就是文档图像的初始倾斜角。其中D和M本发明确定为 D＝5，M＝5。

3.使用能量最小化过程计算最终倾斜度

得到初始倾斜角之后，然后用能量最小化过程计算最终倾斜角，如下式所示：

$\hat{S}=\underset{S}{\arg \min }E\left(S\right)---\left(20\right)$

该过程包括能量函数构建和能量最小化两个步骤。本发明构建的能量函数既考虑 到了全局的前景信息又考虑到了全局的背景信息，如下式所示：

E(S)＝ωE_B(S)+(1-ω)E_F(S)     (21)

其中E_B(S)考虑了全局背景信息，即文本图像在水平和垂直方面上投影后，没有 前景像素出现的空白区域的长度，如下式所示：

我们设置和φ(·)为：

Y_i＝{s_p|s_p∈S∩y_p∈s_p∩y_p＝i}     (23)

X_j＝{s_p|s_p∈S∩x_p∈s_p∩x_p＝j}

其中Sgn(·)是一个符号函数，定义为：

E_F(S)反应了全局的前景信息，即文本图像在每行每列上前景像素个数的方差， 如下式所示：

E_F(S)＝δ(S)+λ(S)     (25)

我们设置δ(·)和λ(·)为：

$\delta \left(S\right)=\frac{1}{M_Y}\sqrt{\frac{1}{f\left(Y\right)}\underset{k=1}{\overset{f\left(Y\right)}{\Sigma }}{(f\left(Y_k\right)-\bar{Y})}^2}$

$\bar{Y}=\frac{1}{f\left(Y\right)}\underset{k=1}{\overset{f\left(Y\right)}{\Sigma }}f\left(Y_k\right)$     (26)

$\lambda \left(S\right)=\frac{1}{M_X}\sqrt{\frac{1}{f\left(X\right)}\underset{k=1}{\overset{f\left(X\right)}{\Sigma }}{(f\left(X_k\right)-\bar{X})}^2}$

$\bar{X}=\frac{1}{f\left(X\right)}\underset{k=1}{\overset{f\left(X\right)}{\Sigma }}f\left(X_k\right)$

其中M_Y＝max{f(Y_i|Y_i∈Y}， M_X＝max{f(X_i)|X_i∈X}，且f(·)计算一个集合中元素的个数。

构造完能量函数以后，根据直线拟合得到的初始倾斜角和所有前景像素的状 态信息，通过反复地计算能量函数和旋转前景像素的状态信息，找到使得能量函 数值最小时所旋转的角度，这个角度就是最终的倾斜角。状态信息的旋转过程如 下：

S′＝rotate(S，θ)    (27)

其中rotate(·)计算每个前景像素的状态信息s_p∈S旋转后的结果s_p′，计算过程如 下：

${x_p}^{\prime }=(x_p-\frac{W}{2})\cos \theta -(y_p-\frac{H}{2})\sin \theta +\frac{W}{2}$

${y_p}^{\prime }=(x_p-\frac{W}{2})\sin \theta +(y_p-\frac{H}{2})\cos \theta +\frac{H}{2}---\left(28\right)$

w_p′＝W-x_p′，h_p′＝H-y_p′

整个能量最小化过程概括为Algorithm1，如下所示：

本发明中ω＝0.98。图3(b)给出了能量最小化后的最终倾斜角，且图3(c)给 出了图2(a)经过倾斜度纠正之后的结果。图4-6给出了3个不同类型文档图像对 应的倾斜度检测和纠正实例。图4-6(a)给出的是原始图像，图4-6(b)给出的是对 应图像的能量最小化过程，图4-6(c)给出的是进行倾斜度纠正后的结果图。