一种面向异构文档的启发式适配方法

摘要

一种面向异构文档的启发式适配方法，对异构文档进行二值化处理。从用户点击位置作为种子点，开始以连通分量为基本对象，基于对连通分量类型的判断，对拟阅读区域进行局部化布局分析。同质区域扩展：从初始种子连通分量开始，依据横向同质性度量沿横向初始化扩展，依据纵向同质性度量纵向扩展，寻找新行，根据新行判断之前的行是否要继续横向扩展，继续纵向扩展直到左/右，上/下都达到边界，得到初步的同质区域。同质区域优化：对同质区域根据情况进行区域分割或合并，使优化后的区域宽高比适应屏幕比例。将最终拟适配区域对应的原图适配到屏幕，供阅读，用户可点击阅读前/后一个适配区域或退出适配阅读状态重新选择阅读区域。

权利要求

1.一种面向异构文档的启发式适配方法，其特征在于包括以下步骤：

1)对异构文档进行二值化处理；

2)从用户点击位置作为种子点，开始以连通分量为基本对象，基于对连通分量类型的判断，对拟阅读区域进行局部化布局分析；所述对连通分量类型的判断的方法如下：不同的连通分量决定需要采取的不同策略：判定为噪音的连通分量忽略即可；判定为图像的区域则直接适配；判定为文本的连通分量则必须进行布局分析得到整个同质区域再适配；对于每个连通分量CCk，通过6个特征进行描述，分别是：(1)B(CCk)，CCk的包围盒； 为包围盒的左上角坐标， 为右下角坐标；

(2)Ak为CCk包含的像素个数；

(3) 为CCk的包围盒B(CCk)的面积，其中，Wk为B(CCk)的长度，Hk为B(CCk)的宽度；

(4) 为CCk的密度；

(5)ξk为包含在B(CCk)内部的其他连通分量的数目；

(6)σk＝min(Wk,Hk)/max(Wk,Hk)，为CCk的宽高比，并且当CCk满足如下条件时，认为它是一个非文本连通分量：(a)Ak＜At，At为给定的阈值，即连通分量的面积小于给定阈值At，At＝

6；(b)ξk＞ξt，ξt为给定阈值，即B(CCk)内部包含多于ξt的其他连通分量，ξt＝3；(c)ρk＜ρt，ρt为给定的阈值，即密度小于给定阈值，ρt＝0.06％；(d)(σk＜σt)&(Hk＜Wk)，σt为给定的阈值，即宽高比小于给定阈值且连通分量包围盒的高小于宽，σt＝0.06；

3)同质区域扩展，具体方法如下：

首先从初始种子连通分量开始，依据横向同质性度量沿横向初始化扩展，接着依据纵向同质性度量纵向扩展，寻找新行，然后根据新行判断之前的行是否要继续横向扩展，最后继续纵向扩展直到左/右，上/下都达到了边界，从而得到初步的同质区域；

所述同质区域扩展是指一种迭代的循环改进的区域增长方法，利用每一行文本之间的这种潜在的相互约束关系指导区域增长的过程：(1)初始化：从初始种子连通分量开始，依据横向同质性度量沿横向扩展，直到遇到可能/确定的边界停止，将该扩展行的信息放入行队列，对于每一行Rk，存储的信息主要包括行的左右端位置 和 左右边界标记 和 Fk,初始值为0，若是确定边界，则Fk＝2，若是可能边界，则Fk＝1；

(2)纵向扩展：从种子连通分量开始，依据纵向同质性度量纵向扩展，寻找新行的种子连通分量；

(3)横向扩展：从当前行RC的种子连通分量开始，依据横向同质性度量沿横向扩展，直到遇到可能/确定的边界停止，设置相应的边界标记Fk；若行队列非空，则将当前扩展行RC与队列中每一行Rk进行比较：若 则继续对RC向左扩展，其中 为当前扩展行RC的最左边X轴坐标值，x为最初种子点的X轴坐标值， 为每一行Rk的最左边X轴坐标值；反之，若 则对Rk向左扩展，右端情况类似处理；

(4)循环：回到步骤3)第(2)部分；

(5)终止条件：当纵向扩展在上下两个方向都遇到边界时，则停止；对于横向扩展，当所有行的左/右边界为确定边界或相互对齐时，停止扩展；当纵向和横向扩展都停止时，则整个迭代过程停止；

4)同质区域优化，具体方法如下：

对得到的同质区域，根据情况进行区域分割或合并，使得优化后的区域宽高比适应屏幕比例；

所述同质区域优化是对同质区域进行分割或合并以匹配屏幕，首先根据适配后文本的大小来决定该区域适合横屏显示还是纵屏显示，记屏幕的长宽比为σs，同质区域的长宽比为σr，若σs＞1.3*σr则对区域执行分割，若σs＜0.8*σr则进行区域合并；

5)将得到的最终拟适配区域对应的原图适配到屏幕，供用户阅读，用户点击阅读前/后一个适配区域，或者退出适配阅读状态重新选择阅读区域。

说明书

一种面向异构文档的启发式适配方法

技术领域

[0001] 本发明涉及移动终端设备数字内容阅读体验，尤其是涉及一种面向异构文档的启发式适配方法。

背景技术

[0002] 随着各种移动终端设备(如智能手机、平板电脑、电子阅读器)等的迅速普及和功能日益强大，人们越来越多依赖这些设备阅读各种数字内容。然而，这些设备在屏幕分辨率、大小、长宽比等方面的多样性很大程度上影响着人们的阅读体验，从而对数字内容的处理提出了新的挑战。图像适配(见文献：riel Shamir,Alexander Hornung,&Olga Sorkine.(2012).Modern Approaches to Media Retargeting.In SIGGRAPH Asia Course Notes.)即是一个典型的例子。在源图像分辨率和目标屏幕尺寸比例不匹配时，简单地对图像进行均匀缩放会导致整体比例失真，引起重要物体严重扭曲。许多学者因此提出了各种内容敏感的适配方法，其基本思想在于利用图像的重要性尺度来控制适配过程，使得图片的重要区域比次要区域在适配过程中受到的改变更小。已有的方法大致可以分为离散(裁剪和缝雕刻)和连续(变形)两大类。裁剪方法(如Bongwon Suh,Haibin Ling,Benjamin B.Bederso,&David W.Jacobs.(2003).Automatic Thumbnail Cropping and its Effectiveness.In Proceedings of the ACM Symposium on User Interface Software and Technology(pp.95–104).)试图计算一个覆盖图像大部分重要区域的最优矩形区域，舍弃不在该区域的图像内容。缝雕刻算法(如Shai Avidan,&Ariel Shamir.(2007).Seam carving for content-aware image resizing.ACM Transactions on Graphics,26(3),Article No.10.)在图像上查找重要性最小的横向或纵向的缝进行删除或复制以改变图像的长宽比。非均匀变形方法(如Guo-Xin Zhang,Ming-Ming Cheng,Shi-Min Hu,&Ralph R.Martin.(2009).A Shape-Preserving Approach to Image Resizing.Computer Graphics Forum,28(7),1897–1906.)将适配问题定义为一个能量优化问题，通过对定义在图像矩形区域上三角网格进行变形使之满足期望的长宽比，通过插值的方式得到调整后的图像。

[0003] 经常会遇到一些篇幅很大(分辨率也相应的比较高)、包含各种内容(图像、表格、文字等)的异构文档(如报纸)。由于移动终端设备的屏幕尺寸一般比较小，使得在移动设备上全文显示时内容会变得太小而难以阅读。为此，用户需要不停进行局部放大、缩小、平移等操作的切换以阅读文档的不同部分。这无疑是一种糟糕的阅读体验，更重要的是，阅读的效率也很低。若在用户大致点击拟阅读区域后，系统能自动分析得到由若干个逻辑区块构成的适配屏幕(文字大小适中、长宽比匹配)的矩形连续阅读区域呈现给用户，则无疑能极大的改善用户的阅读体验，用户将不再需要频繁的进行缩放、移动等操作的切换。然而在这些文档未完全电子化的情况下，这并不是一个容易解决的问题。我们需要对点击区域的文档布局进行分析得到同质区域，并根据屏幕参数对这些同质区域进行适当合并和分割生成最终的矩形连续阅读区域。已有的文档布局分析方法的效率仍然无法满足交互应用的需要，且分析的结果很多时候也不如人意。类似于图像适配，我们也要在文档上确定一个包含拟显示内容的最优矩形。然而我们所要寻求的是用户所要阅读的一个或若干个同质区块构成的连续阅读区域，而非显著性或重要度最高的区域。这个过程叫做文档布局分析。

[0004] 文档布局分析试图将文档图像分解成许多不同的区域如文本、图像、分隔符以及表格。已有的方法可以分为四类：自底向上、自顶向下、混合以及多尺度方法。自底向上的方法(如O’Gorman,L.(1993).The Document Spectrum for Page Layout Analysis.IEEE Transactions on Pattern Analysis and Machine Intelligence,15(11),1162–1173.)从诸如词语等局部信息开始，逐渐合并成文本块或段落。这些方法适用于各种各样的布局，但是时间和空间复杂度都比较高，至少为O(n^2)。自顶向下方法(如Simon,A.,Pret,J.-C.,&Johnson,A.P.(1997).A fast algorithm for bottom-up document layout analysis.IEEE Transaction on Pattern Analysis and Machine Intelligence,19(3),273–277.)首先在整个页面上寻找全局信息，将之进一步分割成块直至词语。这些方法一般为线性复杂度，效率比较高，但一般只适用于曼哈顿布局。混合方法(如Smith,R.(2009).Hybrid page layout analysis via tab-stop detection.In Proceedings.of 10th International Conference on Document Analysis and Recognition(pp.241–245).)着重分析图像上的连通区域及其周围的空白。然而，这些方法得到的结果都不太尽人意，尤其在涉及到非文本区域的归类时。多尺度方法(如Lee,S.-W.,&Ryu,D.-S.(2001).Parameter-free geometric document layout analysis.IEEE Transactions on Pattern Analysis and Machine Intelligence,23(11),1240–1256.)一般比较通用，结果也比较好，但比较耗时。

发明内容

[0005] 本发明的目的在于解决异构文档在小尺寸的移动终端上阅读无法看清内容，不得不频繁进行缩放、平移，使得阅读效率不高的问题，提供使用户可以避免繁琐的缩放、平移操作，极大提高阅读效率的一种面向异构文档的启发式适配方法。

[0006] 本发明包括以下步骤：

[0007] 1)对异构文档进行二值化处理。

[0008] 2)从用户点击位置作为种子点，开始以连通分量为基本对象，基于对连通分量类型的判断，对拟阅读区域进行局部化布局分析。

[0009] 3)同质区域扩展，具体方法如下：

[0010] 首先从初始种子连通分量开始，依据横向同质性度量沿横向初始化扩展，接着依据纵向同质性度量纵向扩展，寻找新行，然后根据新行判断之前的行是否要继续横向扩展，最后继续纵向扩展直到左/右，上/下都达到了边界，从而得到初步的同质区域。

[0011] 4)同质区域优化，具体方法如下：

[0012] 对得到的同质区域，根据情况进行区域分割或合并，使得优化后的区域宽高比适应屏幕比例。

[0013] 5)将得到的最终拟适配区域对应的原图适配到屏幕，供用户阅读，用户可以点击阅读前/后一个适配区域，或者退出适配阅读状态重新选择阅读区域。

[0014] 在步骤2)中，所述对连通分量类型判断的方法可为：不同的连通分量决定需要采取的不同策略：判定为噪音的连通分量忽略即可；判定为图像的区域则可直接适配；判定为文本的连通分量则必须进行布局分析得到整个同质区域再适配；对于每个连通分量CCk，通过6个特征进行描述，分别是：

[0015] (1)B(CCk)，CCk的包围盒； 为包围盒的左上角坐标， 为右下角坐标；

[0016] (2)Ak为CCk包含的像素个数；

[0017] (3) 为CCk的包围盒B(CCk)的面积，其中，Wk为B(CCk)的长度，Hk为B(CCk)的宽度；

[0018] (4) 为CCk的密度；

[0019] (5)ξk为包含在B(CCk)内部的其他连通分量的数目；

[0020] (6)σk＝min(Wk,Hk)/max(Wk,Hk)，为CCk的宽高比。并且当CCk满足如下条件时，认为它是一个非文本连通分量：(a)Ak＜At，At为给定的阈值，即连通分量的面积小于给定阈值At，在我们的实现中At＝6；(b)ξk＞ξt，ξt为给定阈值，即B(CCk)内部包含多于ξt的其他连通分量，在我们的实现中ξt＝3；(c)ρk＜ρt，ρt为给定的阈值，即密度小于给定阈值，在我们的实现中ρt＝0.06％；(d)(σk＜σt)&(Hk＜Wk)，σt为给定的阈值，即宽高比小于给定阈值且连通分量包围盒的高小于宽，在我们的实现中σt＝0.06。

[0021] 在步骤3)中，所述同质区域扩展是指一种迭代的循环改进的区域增长方法，利用每一行文本之间的这种潜在的相互约束关系指导区域增长的过程：

[0022] (1)初始化：从初始种子连通分量开始，依据横向同质性度量沿横向扩展，直到遇到可能/确定的边界停止，将该扩展行的信息放入行队列，对于每一行Rk，存储的信息主要包括行的左右端位置 和 左右边界标记 和 (Fk,初始值为0，若是确定边界，则Fk＝2，若是可能边界，则Fk＝1)；

[0023] (2)纵向扩展：从种子连通分量开始，依据纵向同质性度量纵向扩展，寻找新行的种子连通分量；

[0024] (3)横向扩展：从当前行RC的种子连通分量开始，依据横向同质性度量沿横向扩展，直到遇到可能/确定的边界停止，设置相应的边界标记Fk；若行队列非空，则将当前扩展行RC与队列中每一行Rk进行比较：若 则继续对RC向左扩展，其中 为当前扩展行RC的最左边X轴坐标值，x为最初种子点的X轴坐标值， 为每一行Rk的最左边X轴坐标值；反之，若 则对Rk向左扩展，右端情况可类似处
理；

[0025] (4)循环：回到步骤(2)；

[0026] (5)终止条件：当纵向扩展在上下两个方向都遇到边界时，则停止；对于横向扩展，当所有行的左/右边界要么为确定边界，要么相互对齐时，停止扩展；当纵向和横向扩展都停止时，则整个迭代过程停止；

[0027] 在步骤4)中，所述同质区域优化是对同质区域进行分割或合并以更好的匹配屏幕，首先根据适配后文本的大小来决定该区域适合横屏显示还是纵屏显示，记屏幕的长宽比为σs，同质区域的长宽比为σr，若σs＞1.3*σr则对区域执行分割，若σs＜0.8*σr则进行区域合并。

[0028] 本发明针对移动终端设备在屏幕分辨率、长宽比等参数上都存在较大的差异，并且屏幕大小有限，而对以图像形式存在的、包含不同元素的异构文档而言，它们的分辨率一般比较高，在小尺寸的移动设备上只能部分显示以保证可读性。为此，用户不得不频繁的进行缩放、平移以阅读整个文档，极大地影响了阅读效率的问题，一种针对异构文档的适配方法，通过对异构文档布局的局部分析进行启发式适配的方法。本发明具有算法明确、界面友好、结果鲁棒等特点，在产业化后可以极大地提高阅读的效率，促进市场发展。

附图说明

[0029] 图1为本发明的技术方案流程图。

[0030] 图2为图1中同质区域扩展过程图。

[0031] 图3为图1中同质区域优化过程图。

具体实施方式

[0032] 以下实施例将结合附图对本发明作进一步的说明。

[0033] 一种面向异构文档的启发式适配方法：系统首先对异构文档进行二值化处理，然后在二值化后的图上，从用户点击位置开始寻找种子连通分量，以连通分量为基本对象依据横向同质性度量沿横向初始化扩展，接着依据纵向同质性度量纵向扩展，寻找新行，然后根据新行判断之前的行是否要继续横向扩展，最后继续纵向扩展直到左/右，上/下都达到了边界，从而得到初步的同质区域。对得到的同质区域，根据情况进行区域分割或合并，使得优化后的区域宽高比适应屏幕比例。将得到的最终拟适配区域对应的原图适配到屏幕，供用户阅读。具体流程参见图1～3。

[0034] 本发明实施的关键有三点：连通分量分类、同质区域扩展、同质区域优化。下面具体介绍关键的实现细节：

[0035] 1.连通分量分类

[0036] 启发式适配方法是从用户点击位置开始进行布局的文档布局分析的，以连通分量为基本的分析对象。不同的连通分量决定了需要采取的不同策略：判定为噪音的连通分量忽略即可；判定为图像的区域则可直接适配；判定为文本的连通分量则必须进行布局分析得到整个同质区域再适配。这里，对于每个连通分量CCk，考察如下的特征：

[0037] 1)B(CCk)，CCk的包围盒。 为包围盒的左上角坐标， 为右下角坐标。

[0038] 2)Ak为CCk包含的像素个数。

[0039] 3) 为CCk的包围盒B(CCk)的面积。其中Wk为B(CCk)的长度，Hk为B(CCk)的宽度。

[0040] 4) 为CCk的密度。

[0041] 5)ξk为包含在B(CCk)内部的其他连通分量的数目。

[0042] 6)σk＝min(Wk,Hk)/max(Wk,Hk)，为CCk的宽高比。

[0043] 当CCk满足如下条件时，可以认为它是一个非文本连通分量：

[0044] 1)Ak＜At，At为给定的阈值，即连通分量的面积小于给定阈值At，在我们的实现中At＝6。

[0045] 2)ξk＞ξt，ξt为给定阈值，即B(CCk)内部包含多于ξt的其他连通分量，在我们的实现中ξt＝3。

[0046] 3)ρk＜ρt，ρt为给定的阈值，即密度小于给定阈值，在我们的实现中ρt＝0.06％。

[0047] 4)(σk＜σt)&(Hk＜Wk)，σt为给定的阈值，即宽高比小于给定阈值且连通分量包围盒的高小于宽，在我们的实现中σt＝0.06。

[0048] 2.同质区域扩展

[0049] 注意到除了围绕在图形区域的文本块以外，同一区域的每一行文本的首末两端大部分都是对齐的，即遵循曼哈顿布局。为此，设计一种迭代的循环改进的区域增长方法，利用每一行文本之间的这种潜在的相互约束关系指导区域增长的过程：

[0050] 1)初始化。从初始种子连通分量开始，依据横向同质性度量沿横向扩展，直到遇到可能/确定的边界停止，将该扩展行的信息放入行队列，对于每一行Rk，存储的信息主要包括行的左右端位置 和 左右边界标记 和 (Fk,初始值为0，若是确定边界，则Fk＝2，若是可能边界，则Fk＝1)。

[0051] 2)纵向扩展。从种子连通分量开始，依据纵向同质性度量纵向扩展，寻找新行的种子连通分量。

[0052] 3)横向扩展。从当前行RC的种子连通分量开始，依据横向同质性度量沿横向扩展，直到遇到可能/确定的边界停止，设置相应的边界标记Fk；若行队列非空，则将当前扩展行RC与队列中每一行Rk进行比较：若 则继续对RC向左扩展其中 为当前扩展行RC的最左边X轴坐标值，x为最初种子点的X轴坐标值， 为每一行Rk的最左边X轴坐标值；反之，若 则对Rk向左扩展。右端情况可类似处理。

[0053] 4)循环。回到步骤2)。

[0054] 5)终止条件。当纵向扩展在上下两个方向都遇到边界时，则停止；对于横向扩展，当所有行的左/右边界要么为确定边界，要么相互对齐时，停止扩展。当纵向和横向扩展都停止时，则整个迭代过程停止。

[0055] 该方法的成功实施依赖于两个关键因素：行/列同质性度量和扩展边界的确定。

[0056] (1)同质性度量

[0057] 同质性度量同时考虑了连通分量和空白间隔的属性。

[0058] 拟加入当前扩展行的连通分量，其包围盒面积 必须满足：

[0059]

[0060] 且该连通分量的包围盒与当前位于扩展行的相邻连通分量包围盒的间隔 满足：

[0061]

[0062] 公式(1)中 为当前扩展行所包含连通分量的平均面积， 为连通分量的同质性阈值。公式(2)中 为当前扩展行所包含连通分量间隔的平均值， 为间隔的同质性阀值。列同质向量的定义类似。

[0063] 在扩展过程中，若不满足同质性度量，则将边界标记设置为Fi＝1，暂停扩展，其中i为左l或右r。

[0064] (2)扩展边界判定

[0065] 类似的，扩展边界的判定也综合考虑连通分量及它们之间的空白区域的情况。

[0066] 若扩展行Ri右/左端拟加入的连通分量CCk满足：

[0067]

[0068] 则判定为确定边界，并设置相应的标记Fi＝2。

[0069] 3.同质区域优化

[0070] 上述得到包含当前点击位置的同质区域在长宽比上可能跟屏幕的长宽比差异比较大。为此，需要对这些区域进行分割或合并以更好的匹配屏幕。

[0071] 首先根据适配后文本的大小来决定该区域适合横屏显示还是纵屏显示。记屏幕的长宽比为σs，同质区域的长宽比为σr，若σs＞1.3*σr则对区域执行分割，若σs＜0.8*σr则进行区域合并。