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

摘要

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

权利要求

1.基于能量最小化框架的文档图像倾斜度检测与纠正方法，其特征在于，该方法包括三个过程：(1)计算前景像素状态信息

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

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

接下来利用文档图像中最外围的前景像素的状态信息来估算初始倾斜度，一个边界框有四个边：上、下、左和右，对每一边都能得到其最外围的前景像素状态信息子集，用以下方式得到上边最外围前景像素状态信息子集，记为将TS中每个元素的xp做为x坐标，yp作为y坐标画图，图中的点拟合成一条直线，边界框剩下的三边都经过该处理，将使用直线拟合的技术来估算文档图像的初始倾斜度，在直线拟合之前先对TS进行采样，用如下方式将TS划分为N个互不重叠的部分STSi：N＝32，接下来用如下方式构建一个子集FTS，即计算每个部分STSi中yi最小的那个前景像素状态信息：进行采样操作完之后，需要通过以下方式进一步消除没用的状态信息得到有效的用来进行直线拟合的状态信息VTS：然后采用穷举搜索的方式在VTS中做直线拟合直到找到两个状态信息使得有最多的其他状态信息到由这两个状态信息确定的直线之间的距离小于指定的阈值D；

对边界框的四边都进行直线拟合之后得到四条直线，接下来就是找到拟合最好的那条直线，同时该直线对应的倾斜角就是文档图像的初始倾斜角；用{lt，lb，ll，lr}记作拟合的四条直线，{LSt，LSb，LSl，LSr}记作靠近相应直线的状态信息，要是某条直线对应的状态信息的个数小于M，在下面的操作中将不再考虑该直线，对每条直线li∈{lt，lb，ll，lr}，计算其对应的所有状态信息LSi和直线li之间的距离之和SDi，然后用如下方式计算比值Ri：其中f(·)计算一个集合中元素的个数，{Rt，Rb，Rl，Rr}中的最小值对应的直线就是最佳拟合的直线，最终最佳拟合的直线对应的倾斜角就是文档图像的初始倾斜角，其中D＝5，M＝5；

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

得到初始倾斜角之后，然后用能量最小化过程计算最终倾斜角，如下式所示：该过程包括能量函数构建和能量最小化两个步骤，如下式所示：E(S)＝ωEB(S)+(1-ω)EF(S)   (7)ω＝0.98，其中EB(S)考虑了全局背景信息，如下式所示：设置 和φ(·)为：

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

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

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

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

其中 MY＝max{f(Yi)|Yi∈Y}，MX＝max{f(Xi)|Xi)∈X}，且f(·)计算一个集合中元素的个数；

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

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

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

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

说明书

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

技术领域

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

背景技术

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

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

发明内容

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

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

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

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

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

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

[0010]

[0011] yi∈si∩yi＝min{yp|yp∈sp∩xp∈sp∩xp＝i}.

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

[0013]

[0014]

[0015]

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

[0017]

[0018] yi∈si∩yi＝min{yp|yp∈sp∩sp∈STSi}

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

[0020]

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

[0022] 对边界框的四边都进行直线拟合之后得到四条直线，接下来就是找到拟合最好的那条直线，同时该直线对应的倾斜角就是文档图像的初始倾斜角；用{lt，lb，li，lr}记作拟合的四条直线，{LSt，LSb，LSi，LSr}记作靠近相应直线的状态信息，要是某条直线对应的状态信息的个数小于M，在下面的操作中将不再考虑该直线，对每条直线li，计算所有直线状态信息Lsi和直线li之间的距离之和，然后用如下方式计算比值Ri：

[0023]

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

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

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

[0027]

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

[0029] E(S)＝ωEB(S)+(1-ω)EF(S)     (7)

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

[0031]

[0032] 设置 和φ(·)为：

[0033]

[0034] Yi＝{sp|sp∈S∩yp∈sp∩yp＝i}     (9)

[0035] Xj＝{sp|sp∈S∩xp∈sp∩xp＝j}

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

[0037]

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

[0039] EF(S)＝δ(S)+λ(S)     (11)

[0040] 设置δ(·)和λ(·)为：

[0041]

[0042]       (12)

[0043]

[0044]

[0045] 其中 MY＝max{f(Yi)|Yi∈Y}，MX＝max{f(Xi)|Xi∈X}，且f(·)计算一个集合中元素的个数；

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

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

[0048] S′＝rotate(S，θ)     (13)

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

[0050]

[0051]

[0052] wp′＝W-xp′，hp′＝H-yp′

[0053] 本发明的优点：

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

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

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

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

附图说明

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

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

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

[0061] 图3为能量最小化过程图，

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

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

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

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

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

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

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

具体实施方式

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

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

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

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

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

[0074]

[0075] yi∈si∩yi＝min{yp|yp∈sp∩xp∈sp∩xp＝i}

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

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

[0078]

[0079]

[0080]

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

[0082]

[0083] yi∈si∩yi＝min{yp|yp∈sp∩sp∈STSi}

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

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

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

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

[0088]

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

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

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

[0092]

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

[0094] E(S)＝ωEB(S)+(1-ω)EF(S)     (21)

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

[0096]

[0097] 我们设置 和φ(·)为：

[0098]

[0099] Yi＝{sp|sp∈S∩yp∈sp∩yp＝i}     (23)

[0100] Xj＝{sp|sp∈S∩xp∈sp∩xp＝j}

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

[0102]

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

[0104] EF(S)＝δ(S)+λ(S)     (25)

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

[0106]

[0107]      (26)

[0108]

[0109]

[0110] 其中 MY＝max{f(Yi|Yi∈Y}，MX＝max{f(Xi)|Xi∈X}，且f(·)计算一个集合中元素的个数。

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

[0112] S′＝rotate(S，θ)    (27)

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

[0114]

[0115]

[0116] wp′＝W-xp′，hp′＝H-yp′

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

[0118]

[0119]

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