（模式识别与智能系统专业论文）中文复杂版面分析方法.pdf

摘要： 文档图像理解( d o c u m e n ti m a g eu n d e r s t a n d i n g ) 是把纸介质上的信息转变成讨算机 能够理解和编辑的信息，以方便保存和使用。在o c r 技术已经相当完善的今天，版面分 析成为文档图像理解工作中一个十分关键的问题。中文版面分析研究历史比较短，再加 之中文在字符和排版方式上不同于英文使得中文版面分析有其自身的难点，所以对中文 版面分析方法的研究是很有价值的。 本文针对报纸等复杂版面提出了一个新的中文版面分析方法。该方法是自底向七和自 顶向下方法的结合，吸取两种方法的优点。本文的一个突出特点是把造成中文版面分析 困难的原因分为四类：1 字符的不连通性的影响；2 标题的影响；3 文字方向不确定 的影响；4 复杂区域结构的影响。本文针对以上四类困难分别提出了解决方案，并将这 些方案结合在一个完整的版面分析流程中。试验结果表明该版面分析方法有相当好的效 果。 关键字： 文档图像理解、版面分析、中文版面分析、自底向上与自项向下结合 a b s t r a c t ： d o c u m e n ti m a g eu n d e r s t a n d i n g ( d i u ) t r a n s f o r m st h ei n f o r m a t i v ec o n t e n to fad o c u m e n t f r o mp a p e ri n t oa ne l e c t r o n i cf o r m a tf o rt h ec o n v e n i e n c eo ft h es t o r a g ea n du s a g eo ft h e i n f o r m a t i o n n o wt h a tt h eo c rt e c h n i q u eh a sb e e np o w e r f u le n o u g ht om e e tt h ec o m m e r c i a l r e q u e s t ，t h el a y o u ta n a l y s i sb e c o m e s a k e yp r o b l e m i nd i u c o m p a r e dw i t he n g l i s hd o c u m e n t s c h i n e s ed o c u m e n t sh a v et h e i ro w nc h a r a c t e r i s t i ci nt h ea s p e c to ft h ec o n n e c t i v i t yo fc h a r a c t e r s a n dt h es t y l eo fl a y o u t i na d d i t i o n ，o n l ys e v e r a ly e a r sa g o ，r e s e a r c h e r ss e tt h e i rf e e to nt h ef i e l d o fl a y o u ta n a l y s i so fc h i n e s ed o c u m e n t s t h e r e f o r e ，t h e r ei sm u c hr o o mf o rt h er e s e a r c ho f l a y o u ta n a l y s i so f c h i n e s ed o c u m e n t t h i s p a p e rp r o p o s e d an e w l a y o u ta n a l y s i sm e t h o d ，a i m i n ga tt h er e l a t i v e l yc o m p l e xl a y o u t o fd o c u m e n t s ，s u c ha s n e w s p a p e r t h i sn e wm e t h o de m p l o y sb o t hb o t t o m u pa n dt o p d o w n a p p r o a c h e st ot a k ea d v a n t a g eo ft h e s et w oa p p r o a c h e s t h ep r o m i n e n tf e a t u r eo ft h i sp a p e ri s c l a s s i f y i n gt h ed i f f i c u l t i e s i nt h el a y o u ta n a l y s i so fc h i n e s ed o c u m e n t si n t o f o l l o w i n gf o u r c a t e g o r i e s ：1 d i f f i c u l t i e sc o m i n g f r o mt h ep o o r c o n n e c t i v i t yo f c h i n e s ec h a r a c t e r s ；2 d i f f i c u l t i e s c o m i n gf r o mt h ee f f e c to fh e a d l i n e s ；3 d i f f i c u l t i e sc o m i n gf r o mt h eu n c e r t a i nf l o wo ft h et e x t l i n e s ；4 d i f f i c u l t i e sc o m i n gf r o mt h ev e r s a t i l ei n n e rs t r u c t u r eo ft h et e x t r e g i o n s f o re a c h c a t e g o r yo fd i f f i c u l t i e s ，t h i sp a p e rg i v e st h ec o r r e s p o n d i n gr e s o l v e n ta n di m p l e m e n t si ti na n i n t e g r a t i v el a y o u ta n a l y s i ss y s t e m t h i sn e wl a y o u ta n a l y s i sm e t h o di sp r o v e nt ob ee f f i c i e n t a n d p r a c t i c a lb y t h ee x p e r i m e n t a lr e s u l t s t e r m s ： d o c u m e n t i m a g eu n d e r s t a n d i n g ，l a y o u ta n a l y s i s ，l a y o u ta n a l y s i so fc h i n e s ed o c u m e n t s b o t t o m u pa n dt o p d o w n 第一章弓l 言 第一章引言 1 。 。文档溪像璎髂豹意义 在辔兰滔酌各个方筒中，我 f j 都需要传邋接惑。蕊错惑豹传遴总燕鬻癸一定酾余震。院 颤，我们糖声音介蕨记录猩磁带上，我们整文字溪靖倚惑记袋在缀章杂悫上a 麓蓉人类 文明随不断进步，承载僖怠的介质也在不傍魂更鞭抉代。扶豢石，竹简等初级介灏发麟 到恕纸作为主攥的信息记录介质，蕊来又出现了磁带，唱片等柬承羧声裔信恿e 到计算 撬鹣出璇，为僚惑鹃传递，保存和检索掇珙了藤匏飞越。蕊今，瞧子媒体琶经娥为人们 获取镲惑酶羹袋渠邋，电子媛奉以旗方便、抉犍、铃廉、可震复馕臻、节省资源簿特 点，受裂了人嬲黪广滋欢遴。 键楚在入炎文麓妖淫串，蠢上千霉豹耩尊润娣蔗镬瓣纸奔矮寒黎载镶惑鹣，覆麓这憋承 载蔼息瀚羝夯臻静数爨还程戳缀麓的瀵度蹭长。绦存这鏊缎夯震释梭索其串色雷憨傣慧 已经变成了一谗十分囡滚的事情。箍翔纂能把这些纸介质上煞髂怠转燮为电子媒体傣 惑，会极大方便绉怠的保存和使爝。骚凳成遽任务，使髑人工输入的方法浸然是不磷 行的。所以我们簧寻求耪方法让计辫极能够固韵竞成纸介质锫塞戮憩予媒体锖惠骢转 化。 文档燃稼溅解( d o c u m e n ti m a g eu n d e r s t a n d i n g ) 技术黢遁麓生。文撼豳豫理解娩称 邃渤文攫处臻a u t o m a t i cd o c u m e n tp r o c e s s i n g ) ，窀熬整要点睬是撼纸会震土煞偿 患，辩缀绥，象惑， 誊藉，攘凌等，转黛戒诗冀藏熬够联鼹瓣编辑豁嵇惑，熬w o r d 文 襁，t x t 文档等，蔽者黻数瓣霹方蕊缀缀黻方畿检索。 交辎溺稼壤瓣妻簧筵建立在光学字符谈象( o c r ，o p t i c a lc h a r a c t e rr e c o g mt i o n 技术的蒸獭之上。孤零瞧缀六十年代起，人 、j 簸在o c r 方蕊做了太鬣骢研究，魏筒，o c r 技术已经糊当成熟，对予印剩体豹英文，识掰率般都能繇9 8 p a 上，究垒可以满足熨 际的鬻要* 健怒o c r 技零圭嚣是钵对文零瓣识剃，它只鼹娥壤投食文字愚文字规则撼蹶 的文档图像，箍程实际应餍申，这撵的缎竣鼹然跫不成立熬。髓饕穗版羧拳的不凝撬 蕊t 印剃菇瓣舨瑟继橡越来越复杂。鼗戬，大绞二卡零瓣，入镪瑟始了篷硝救嚣鲶遴 ( a u t o m a t i cl a y o u tp r o c e s s i n g ) 拣磷究。 第一章引言 1 1 2 自动版面处理 自动版面处理的主要作用有两个方面：首先，自动版面处理要把输入文档图像切割成 若干简单文本( 即只包含- - 个字或几个字的图像) 区域，以便于o c r 的识别工作。另 外，文档图像理解的目的并不仅仅是为了把纸介质上的字转化为计算机能理解的机器编 码，我们还希望从文档图像中得到更多的信息，比如标题和正文的区分、阅读顺序的确 定、那些文字区域属于同一篇文章等。在相当多的应用中，要求文档图像理解系统的结 果( 如w o r d 文件、p d f 文件等) 能保持和输入的文档图像有相同的版面结构。自动版面 处理的第二个作用就是抽取出文档图像的版面结构。 所有的文档有两种版面结构：物理结构和逻辑结构。物理结构( p h y s i c a l s t r u c t u r e ) ，也称为几何结构( g e o m e t r i cs t r u c t u r e ) ，是由图像中物理组件及其关 系决定的。物理组件包括：字符，文字行，文字区域，图像区域，或者表格区域等。物 理组件之间的关系包括：位置关系( 如：部件l 在部件2 的左边) 和包含关系( 如：字 符包含在文字行中、文字行包含在文字区域中) 。文档图像的逻辑结构在一定程度上是 由阅读者决定的，它包含了各个物理组件逻辑关系：部件在文档中角色( 如：标题、正 文或插图) ，哪些部件属于同一篇文章，以及阅读顺序等。 自动版面处理分析文档图像的版面结构，所以由文档图像的两种类型的版面结构就得 出了自动版面处理的两个阶段：版面分析( l a y o u ta n a l y s i s ) 和版面理解( l a y o u t u n d e r s t a n d i n g ) 。版面分析是抽取文档图像的物理结构，其目标是把文档图像划分成若 干个不相交的同质区域( h o m o g e n e o u sr e g i o n s ) ，并且标定各个区域的属性( 如：文 字、图像、表格等) 。版面理解完成从物理结构到逻辑结构的映射，其目标是标定各个 区域的逻辑属性，文章的层次关系和阅读顺序等。但是，在自动版面处理中，版面分析 和版面理解也不是完全隔离的两个阶段，在某些系统中，它们也是彼此有覆盖的。比 如，在本文中提到的方法里，在版面分析中会把文字区域区分为标题和正文，这就相当 于区别了文字区域在文档的逻辑结构中的不同地位，当然这样的区分也是建立在标题和 正文区域有不同的物理性质的基础上的。 1 1 3 版面分析的意义 在o c r 技术发展比较成熟的条件下，自动版面处理工作对文档图像理解技术的发展有 重要的意义。版面分析是自动版面处理前提，自动版面处理系统的性能如何在很大程度 上取决于版面分析的结果即能否正确的对文档图像进行区域拆分，以及对拆分的图像 能否j 下确的标明属性( 即是图还是文) 。而且，文档图像的逻辑结构并没有一个明确的 2 繁一拳辱l 塞 定义，不嗣躺阅读豢对嗣一个文档图象的逻辑结构麓理麟甚至可以怒不榉豹，版面瑗 解工作就有了一定的不确定性。由上面的讨论可以看出版两分析在簸麓文橙图像处理中 是必不可少的，肖极其重要的地位。 气。2 本文酌组织 本文圭戮分缨耪薪翡应蹋予中文笈杂叛嚣分辚方法+ 寿面的熹节瀚缀级熟下：第二 章分析现有版面分析算法，介绍了国外已有版面分析方法和它们的优缺点，中文版面分 褥魏发展憾况，幽予本文方法主要是针对报纸等复杂舨藤，繇以在第二肇孛怒麓单套绥 了报纸舨磷努轿的情况。第三露分桥了中文复杂敝疆分析存在的难点阕题，掇造成中文 舨嚣分辑困难豹骧嚣分为四类；1 字簿懿不连遥热豹影暖；2 标题豹影嚼：3 。文字方 向不确定的影响；4 复杂区域结构的影响；并概翳描述了解决方案和该版面分析的主要 流程：第朋章详细分析了中文版砸分掇难点闯题的解决方法，即版磁分析流獠中几个重 甏熬步骤。第五牵麓示7 该蔽蕊分辑方法应薅鹫不阏类蝥释张的结果，慧绥该方法嚣傻 缺点，并对将来进步的工作避行了展攫。 3 第二章现有版面分析方法介绍 第二章现有版面分析方法介绍 2 - l 国外皈面分析的方法和成果 2 1 1 综述 版面分析的目的是从文档图像中抽取物理结构，它把文档图像切分成若干个彼此分 离，互不相交的同质区域。所谓同质，就是指区域的内容是单一的，如：文字行，图片 等，而就文字区域来说，同一个区域内部的文字也应该有大致相同的物理性质，比如： 字号，行宽等。 在过去的二十年中提出了许多版面分析的方法，总的来说可以分为如下两个类别：层 次化的方法( h i e r a r c h i c a lm e t h o d ) 和非层次化的方法( n o n - h i e r a r c h i c a l m e t h o d ) 。这两类方法的主要区别是：前者在分析中利用了各个物理组件之间的几何关 系，而后者并不考虑这种几何关系“。下面的两个小节分别讨论了这两类方法。 2 1 2 层次化版面分析方法 在层次化版面分析的方法中，我们可以采取两个途经来达到区域划分的目的：自顶向 下的方法和自底向上的方法。 自项向下的方法，也称模型驱动的方法，它从整个文档图像着手，使用递归的切分的 方法，把整个文档一步步划分为越来越小的区域，如 1 3 。自底向上的方法，也称数据 驱动的方法，它从连通体着手，使用递归合并的方法，逐步把连通体合并为越来越大的 区域。 自顶向下的方法一般利用了某个已知的文档结构模板或各物理组件之间用于间隔的空 白区域的信息来逐步切分，它的速度比较快，适用于版面结构比较简单或者某种已知版 面结构的文档图像a 自底向上的方法比较费时，但是比较灵活，适用于版面结构比较复 杂且对舨面结构没有太多先验知识的情况。 也有许多的方法是自顶向下和自底向上方法的结合 4 。 2 1 3 非层次化版面分析方法 在版面分析中，非层次化的方法比较少，但是它们有一个共同的好处是可以处理非 m a n h a ；t a n 式版面。m a n h a t t a n 版面是指图像中各区域都能用一个矩形来描述，且所有的 区域的方向都是一致的。层次化的版面分析方法多数都只能处理m a n h a t t a n 版面。 4 第二章现有版面分析方法介缁 4 总结了眈较著名酌j 藩次纯方法，惫括：j a i n 等旋密静基于g a b o r 过滤嚣懿方 法，t a n g 等提出的基于分形的f r a e t a ls i g n a t u r e 方法，d o e r m a n n 提出的基于小波的多 尺度的分析方法。在 1 中掇到了s e h e r l 等提出鏊予局部属性( l o c a lp r o p e r t i e s ) 的 方法，该方法把图像划分为许多楣交的正方形小窗聪，分柝这个小窟口内的特征，基于 统讲4 的方法把这些窬口分类，再把同类的窗口合并为同质区域。这些方法都可以商接应 用于灰凄墅像，但是它们邦鸯较裹的粒闷复杂度。 2 。1 4 层次化版瞄分析方法中腭到的主要技术 由于本文使用的版面分析方法也耩于层次化方法，所以，下面介缯一下层次化方法中 用到的主要的技术。有一点要说明的是；下睡的这贱技术是非掌基本的，葭们中的一个 并不能完成版面分析的任务，一个版箍分析方法通常是在不同的处理阶段用到这熟方法 中熬巢一个。 2 1 4 1 连通体分析 连逶傣怒镀魏捐邻豹丽色蒙素( 蕉色或酝色) 斡集合，集合中的任意两个象素之鬻都 存在一条8 连通的路径。适通体是犬多数自底向上版面分析方法的基础。通过分析连通 体本身的信怠和连通体之间的几何关系，把连通体分类，稃逐步合并同类璃通体为同质 区域。 比如c l o 中，f e il i u 烨提出了基于连通体的对撮纸进行版面分析的方法。l i u 定义 了一秘凝的遣送薅之耀兹足德距裹d ：嚣令逡通薅f 窝连逶搭j 之淫瓣足褒鞭爨矗鑫，力是 连通体f 和连通体j 谯x 方向上的距离d ，( f ，) 和l ，方向上距离d ，o ，j ) 中的较大值。又定义 了遣遴体之间的会并躐离d ：两个逑逶体i 和连通体，之间的几何距离 d ( i ，) = 嘞x d # 岛。其中，吩是灏个连逶体豹赢度豹毙德，记h 必连邋体豹毫壤， 嘞。m a x 眠h ，h ，i h ) ，& 是两个连通体的游程平均长度的比值。记w 为连通体的平均 游餐长度，磊。m a x ( w i7 ，) 。在合弗阶段，每次都会并有簸小扫德的两个连通 体。 在图像上寻找连通体一般比较费时，所以在找连通体之前可以先对图像进行x y 两个 方彝上豹模糊t 期在模凝臻像中兹一令蒙素饯表愿嚣稼孛豹令璐拜令象索懿强缀区 域，稽原图中卅n 的图像区域中有个象素魁黑象索，则模糊图像巾对应的象素也怒黑 象素，搬寝瞧莸是貘凝搡络孛| l 睾嚣令参数。 5 第二章现有敝嚣分析方法奔缡 _ h _ _ w _ - _ h _ - _ _ _ _ * _ _ - _ _ _ _ h _ “_ _ 一 2 1 。4 。2 投影努耨 圈像的投影就是把二维的图像映射为一维数组，数组的值是二维图像沿某个方向的所 有象索值静幂秘。眈如：图像翰东平投影就怒凳图象静一行中疆有的象素毽瓣耪终为投影 中对应元素的值。常用的投影方向有；水平，竖直和4 5 度方向。 天津市委常委、滨海新区管 委会主任皮黔生主持会议并宣 读了全国政协副主席、中国工业 高辩技论坛组委会名誉颗翔经 叔平发来的贺信，天津市市长李 盛纛致欢萎薹谲，并在会前会觅了 ( a ) 文档图像( b ) 水平投影波形圈 f i g u r e2 - l 文字区域及其水平投影 投影对瘦着一个波形强，分援这令波形潮就毙褥副绶影爨像弱冬转蛙矮。魄懿【1 弱 中，r y u 等使用自顶向下的方法切分送域，他们通过投影来判断某区域是否是同质区域 蘩是蠢还纛簧避一多甥分。我靛知遴澍一格式懿文字送装串文字嚣豹离度帮文字费阗豹 空白区的高度都是一样的，这种性质反映在其水平或竖直投影上，就是有均匀的波蜂和 波谷。鲐f i g u r e2 - i 所示。 教学活动期闻，摹g 学棱的嬲览室、 瓣书室、蜜疑塞、徽撬室蠢学习或 畿阅有关资料而赢认为囱已没有 必要昕的澡可以承听，认挎自己漫 容堪娶骰的 霉疆冒黻幂徽。窘 1 9 9 8 年搿始至今该校槎奥林匹 克知讽竞赛串或续墼然，弗有多名 学生授详为甫缀”十馕学生”。 1 9 9 8 、l 娜年连续两年杨村一中 妁理科糍考总分擞羼零枣熊一名。 2 。o l 苹谶棱的文灌辩总分又再次 名列郊县榜首。 ( 8 ) 象戆星像 ( b ) 竖直投影波形圈 f i g u r e2 - 2 用投影选择醚城切分赢 6 垂 第二誊现有版面分析方法介绍 - _ _ * 一一 一 在 6 中，h a r a l i c k 采m y - 个自顶向下釉自底向上相结台的方法a 程自顶向下处理 部分，需要对待切分隧域确定切分点。般来讲，同质区域之间都有比同质区域内部更 宽的空白区域。h a r m i c k 就利用了该醒域的投影，把其中最窝的波谷作为切分点，如 f i g u r e2 - 2 中繇示，这毽嚣为递麴x 一￥甥分( r e c u r s i v ex - yc u t ) 的方法e 2 1 。4 。3 游稷会劳葵竣r l s a ( r u nl e n g t hs m e a r i n ga l g o r i t h m ) 在图像的一行( 或一列) 中，连续的一串黑象索稼为一个游程。假设图像中用0 表示 白色，用1 袭示黑色，那么在一萱亍或一列象索就相当于个二进制串，如f i g u r e2 - 3 中 原始图像所示。连续瓣一串l 表承个游程，那么f i g u r e2 - 3 的舔始圈像中就有轰个游 程。r l ，s a 黪法蹩把强像孛翅疑魄较逐瓣游裁连接越来，鼗奁二遂期审审，熟鬃囊个连续 的l 串之闯戆0 串比较短，鄹小予菜个阚筑e ，剿把这些0 都变艘1 。如f i g u r e2 - 3 中，我们取阑假c 为5 ，则r l s a 变换精的图像如输出图像所永： 驻始图像：0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 10 0 0 0 0 0 0 0 li 0 0 0 输蹬图像：1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 10 0 0 0 0 0 0 0 i 10 0 0 f i g u r e2 - 3r l s 矗舅法示铡( 潮篷必5 ) r l s a 算法的关键在于阈值c 的选取，选取不同的c ，就可以把文档图像中不同的部分 连接起来。比如选择的阈值间英文革词中字符的间雅相当，那么应用r l s a 算法会将单词 中静字符遗袋熬来；港蠲德与荤调之阗翡闻鼷相当，那么r l s a 算法藏会琵嗣文字行中 懿革诞都逡接越来。怒r l s a 葵法成焉子凿像翡筏，酉黻把一个文字区域内韵各个文字行 连接起来 前提是区域之阅的空巍丈予区域内部文字行之闼鼬空囊) 。凌 1 4 3 串，箨a n g 等就利用了r l s a 算法，然艨在其结果图像上找连邋体，用适通体的外接边框作为区域切 分的罄础，掇大盼简优了处壤的复杂度。 2 1 a a 最哙支撑树方法( m i n i m a ls p a n n i n gt r e em e t h o d ) 魏采撼文秽黼缘中翡秘毽组辞着戒第点，褥街瑗缀件之闯的鼯离看成节点之阎的边的 权熏值，那么文档图像裁对癍了一令带权麴爨g = 秽，基) ，其中y 爨蕊点麴集合，e 是边 的集合。节点f 和节点j 之闽的边朋勺暮表示，节点f 和节点，之阍的距魏用d 。寒表示， 8 f 的枚重e 黜l 勺= d # 。对送祥的图g ，其墩小支撑瓣( 髓i n i m a ls p a n n i 岵t r e e ) 包括 g 中的所有节点，和g 中边的子集，这个边的子集满足以下条件： ( i ) 这个予集中所有边的裰之和为所肖子集中最，j 、的； 7 第二章现有版强分析方法介绍 _hw_”_一一 ( 2 予爨中麓选能够援涯懑是遘遂鹣。 在 1 2 中，s i m o n 等在文档图像首先找出连通体，把连通体作为节点构成图g ，两个 节点之间的边的权重为两个节点之间的距离，距离的定义如下：节点i 和节点，之间的距 离d0 ，j ) 燕f 和，在x 方自上瓣躐离癌，矗，力犟鹾】，方向上距离蠢，i ，) 中数较大 蠹。s i m o n 逶 过默g 梅戏疆蠢、支撑树静避程采遮翻版蠢分耩静鼷的，褪中酶子褥就题对瘦了文楼强豫 中豹穆理缀俘。s i m o n 魏方法蒸予遮撵戆一个缓设：擎溺内郝豹闻鼷，攀键秘敬阕黪，圈 一区域文字行的间距，区域之间的阆距是逐步递增的。生成最小支撑树的方法是一个递 归的过程，在每一次递归中，在还没有使用的边的集含中选择拥有最小投重的边插入。 蚩菜次选择的逾的权重是上次送耩静逮的较重酌添倍淡上，籍表示藤次的浚交。鲐下 图中，表示稀入的边，f 袭示撩入的顺序。可驳蓉出，矗譬。磁矗。的校鍪都大褥多，它 靛豹接入藏代表了献攀运凌部豹鼹离到单运之阕鹣鼹离，荐蘩文字符之阗戆鼷离。 f i g u r e2 利翅最小支撑耱叟成攀键0 8 2 1 4 5 基予背景的分析方法 目u 面提剃的几种投术都慰通过分攒前景元素( 即黧元素) 鲍分布，来遮爨媛殛分析豹 茸的。丽基于鬻景的矜析方法是撼背黎( 即自象索) 伟为研究对象的。该方法的主攫目 的楚找到环绕蔫备区域的自象素流( w h i t es t r e a m ) ，由此究成区域切分工作。这个方 法魏好处是：它慰菲m a n h a t t a n 舨嚣器考较大穰勰是壤熬文档蚕镶窍琵鞍盎 瓣效暴，鄂 该方法并不假设灾搂嬲像中豹区域都是矩形。 1 5 中对文档图像的限制是：区域之阅的自象索流甍比区域内部的自浆索流宽。该方 法的基本恩想是：对文档图像中的每一个自象素的值改变为该位置臼象素流的宽度。例 翔：f i g u r e2 - 5 ( a ) 中豹繁2 行第2 翔的岛象素，在锪的便鬻上霹以放鬻一个3 x 3 的岛 色正方形，郧么就绘该象索赋擅为3 。处理螽结聚翅f i g u r e2 - 5 ( b ) 联示。然爱磐曩 8 塑三里塑壹堑重坌堑查整垒塑 _ h _ _ _ _ _ 一1 雕s a 算法愚慧，选取某个阖值c ，靖僮小于c 斡象豢的都斌僮先0 ，g f 棚当于把连通蒋 都连接起来。选取不同的阈值，就可以划分不同层次的物理组件。如：较大的阈值可以 用来切分区域，对每个区域用稍小的闽值即可切分文字行等。 躬黧骶絮 雌赫剩醚整蔫 ( a ) 原始图像：o 代液攥 ( b ) = ! 燕换精图像：原米的白象索 也，l 代表白色 的值转变为避犬正方形的边& f i g u r e2 - 5 自象素流窕爱分辨 7 】为了熊裘示各种形状自色区域，采用了细化算法，把白色区域用细化后的线条表 示，如f i g u r e2 - 6 ( b ) 所示。细化后的线条保持了原米白色区域的连通性，这就确保了 前景区域还是被这些线条所包鄹的。基于这种对背景的表示方法，划分区域的工作就可 班通过寻找醛绕旃景区域豹线条来宠袋。要褥到环绕藏祭送壤敬线条，簸要嬲豫郡些于 挽毪鹣线条。蓑先，弱除不成环的线条。然蜃穰器线条距离兹景元素鹃遴近和蓊景元素 的性质来删除那些被判断为是区域内部的线条。区域划分的结果如f i g u r e2 - 6 ( c ) 所 示。 ( a ) 棘虫f ! | j 6 | 像 ( b ) 背景白色区域翱f 化蚺聚 ( c ) 区域切分结果 f i g u r e2 - 6j f l l 朋背景白色区域细化避行区域切分 2 2 孛文叛巍分析发襞匏穗况 2 2 1 中文版面分析的特点 中文版面分析较英文版面分析怒步晚，国外的英文版筒分析技术比较成熟，已经达到 实用阶段，而中文版面分析还处予刚起步的阶段。虽然豳外应用于英文黝版灏分析算法 9 一釜三童鍪壹堡重坌篓壅壁垒璺 一 w m h _ _ _ _ _ _ _ - 一1 中熬诲多技术遣可以耀予串文舨瑟分臻，键是盘予中文数疆鑫赛不曩予荚文舨瓣懿特 点，中文版酾的复杂性高于英文版酾，所以距离中文版面分析技术的成熟，我们还需要 滗较长的路簧走。 与英文版面相比，中文版面的复杂性体现在以下方面： ( 1 ) 中文字符的不连通幢：不难看出，丽英文字符相比，中文字符的不连通健怒非常 显著的。汉字中属于单一连通体的字被称为独体字，在整个汉字集中的比例相当 小。而且，中文字符的不连通性同英文相比还有更大的不确定性。比如：在英文 字符斡不连通字铸都怒上下缡掏( 字德“i ，) ，焉汉字中熬不连遭字符筑缨魏比 较复融，有上下结构( 如：“二”) ，左右结构( 如：“件”) ，包宙结构 ( 魏；“国”“逮”) ，还鸯爱复杂懿，懿“嚣”，“惑”等。汉字不连逶性绘 版面分析带来了困难。 ( 2 ) 中文敝箍酶横鳌混蒜。在葵文文橙串，掰有静文字行都是攘摊熬，褥在中文文档 中，有竖排的文字，墩有横排的文字，这给版面分析带来的影响是显而易见的。 2 2 2 目前采用的主要方法 舞藏暴蟋瓣孛文舨嚣势凝大多暴雳叁底蠢嚣方法8 ”“7 凇“嘲，宠筏窭文撩蛰像中静连 通体，然后根据一定的规则含并为文字，文字行，文字区域。 【1 8 3 中绳篷一释萋子缀合特征鹣审交敝褥分拆方法。掰谓缝含特征就憝文档强像中 各物理组件的物理属性，毗及物理缎件之闯豹相关性。该方法从文档图像中的连通体着 手，逐步将避通体合并为字符。字符合并为文字行，文字彳亍含并为文本区域。在每个 合并屡次上所遵循的规则如下：若磁个物理组件之阗弱距离小予预先设定的阚值，娥舍 并这两个物瑷组件。该方法对横竖濑排的解决方案趄：当字符按照以上规则合并为文字 行矮，列叛这个文字行熬宽麓毙，蓑其毫爱远大子蒺宽菠裂潮定文字疗是骚簧 ，季瓣是 横排 在进行文本区域的合并时，横排文字与横排文字合并，竖排文字和竖排文字合 荠。 1 6 中提出的基于最近邻连接强度和行剿可信膨的版丽分析方法。该方法对文档图 像中斡每一个连逶体援妥箕t 下左右个方向的最近邻，并计算各个方向上的最远邻的 连接强度w ，w 主要l i j i 该连通体与该方向上的最近邻之间的太小差黪、距离以及中心点 的偏移决定。若菜个连通体4 个方向上的w 都小于预先设寇的阈值，则去除该连通体与 所有方向上的最近邻鲍连接；否则，取4 个方囊中竣大静连接强度必弹一，若菜个方淀 上的w 与w 。，的比值小于某个预定的阀值，则去除该方向上的连接。这样一来，横排文 1 0 第二章现有版筒分析方法介绍 m _ _ 一 字行中的连邋体一般只藕下与左右霰近邻的连接，聪整葬 文字行中静连逶体一毅哭灏下 与上f 最近邻的连接。根据送个连接关系，把文档图像中的所有连通体分别合并为候选 行和候选列中。若有连通体属于某个候选行又属于蘩个候选到，捌分别计算该候谗行和 该候选列的耐信度，保留可信发大的释一令。可信度是由行( 或列) 的宽南比( 或商宽 比) 、字符平均间距、平均偏移和字符大小的均匀程度综合决定的。根据以上方法得到 了文字行( 列) 进一步合并为横 竖) 文字隧域。 1 7 提出一种慕于数学形态学的自适应版面分析方法。该方法的主要聪想是：在同 等穗壤翡扩大文档黧豫中豹耪理组 每敬强接逑挺瑟嘏豹条传下，驻褰越遥的貔理帮舞熬 外接边框重台的可能性越大。该方法是用递归实现的在递归的每层完成以下两个工 作： ( 1 ) 把所村外接边框有重龠的物理部件进行合并； ( 2 ) 把所肖物理部件的舞接边框腻t 下左右4 个方国扩展1 个象素； 采取这棒的自适聪的会势方法，比采用繁个预先设定的仓并阈值，有相巍的优势。 2 2 3 现有中文舨箍分析方法存在的缺点 穰据第一牵孛静奔绍，瑶班憨维磁现有蔽瑟分橱方法存在韶下臻熹： ( 1 ) 可以精出现有中文版鼷分析的方法基本上都怒自底向上的，其分析基础都是文档 图像上的连通体。由中文字符的特点决定，个中文字符可能由好几个连通体组 成，所以，从文档图像上找严格意义上的8 连懑体的工作是比较耗时熟。 ( 2 ) 在进行自底向上的合并l i 于采取的规则有一定的局限性。 1 8 中采取抱预定阈值作 为合并标准，这霹予字号交织大量舨麓络稳不单一戆螬提蠡然是苓会蠢攫磐裁结 果a 1 6 中提出的为姆个最连通体计算其四个方向的最近邻和连接强度的办法 耗薅邈卡分基大，茏英在孛交澈蟊孛逡逶体数鼗本来簸琵较大酌情况下。 党全采用自底向上的分析方法会忽略了一些全局信息，比如用于分隔区域的黑线和白 线静信息，这些全局信息对版面分析裔很重簧酶意义 2 3 现有报纸板薅分析方法综述 蜘予报纸舨嚣豹复杂弦秘特殊牲，在叛瑟分羲方法戆过稷孛，一囊骞不少舒霹予报纸 版丽的研究a 在2 0 0 1 年的i c d a r 上缀织了第一届国际报纸版颟分析比赛，现将比赛中用 至l 方法大致套缮魏下： 第二肇现有版面分析方法介绍 9 】提交了个垂底囱主戆报纸敝瑟分叛方法。蘩瓷麸文秘纛始鋈缳中褥鬟p a t t e r n 兹 集合，作为版雠分析的基础。p a t t e r n 不是严格意义上的连通体，距离小于3 个象素的连 通体都合并在个p a t t e r n 中。进一步把p a t t e r n 分类为t e x t 、t i t l e 、p h o t o 、l i n e 等7 个类 蹦，通过合并棚邻的同类连通体丽得到同质区域。 9 逐提出了一种能抽敬豳与其它物理 裁臀糖连静纛线方法；只要在获取p a t t e r n 霹戆撬至l 该惠线瓣一部分，然聪褥之淘嚣蕊延 率，分桥与延体部分孝占连的p a t t e r n ，看是否可戳舔分融l i n e 豹部分。遂祥就减少了由 于l if i e 和文字粘连造成的版面分析错误。 1 0 中提出的报纸版面分析方法也是臼底向上的，它分为如下几个步骤：连通体的获 取，连通体的分类，台并同类连懑体两褥至l 区域。该方法的突出豹特点怒定义了一个特 殊戆连逶俸之瓣静距离终为台劳豹稼准。蠢2 。1 4 + l 中掰述，魏栗连逶倦之闽有壹线鞭 隔，为无穷大，盥可以看出只有棚邻的且物理性质类似的连通体有较小的躐离。 1 1 中提出了一个先切分后念弹( s p l i ta n dm e r g e ) 的方法：用获取连通体的方法 得到原始图像中的直线和图像区域，利用图像区域的边界生成新的直线，加入到直线集 合中。延长濒蠢夔壹线到文挡迭器，峦蘧茏文挡分裁麓疆磅装。分掇每一令瓣穆魏蛙 质，合并相邻弼鹰的网格，由此褥铡闭质区域。 由上可以澍如，由于报纸版面的复杂性和多变性，报纸版面分析方法多是采取自底向 上的方法。 1 2 第三章个新的版面分析方法的流程 第三章一个新的版面分析方法的流程 前面阐述了中文版面分析有别于英文版面分析，且中文版面分析还存在着许多问题， 所以本文握爨了一耪新的蠢底向上与鑫矮囱下方法穗缀合酌中文蔽蘑分橱方法，该方法 在一定程凄上豫 了襞骞敝囊分撰方法瓣鲮酸。 3 。1 对本文方法要解决的润题的界定 影响一个版面分析算法的质量的因索很多，总体上来说，包括两个方筒：图像质量和 蔽西复杂成凌。图像餍量主簧包攒图像的分辨率秘颜色( 皴：彩色，灰凄，黧自) ，餮 像静颓籍程度，黼像懿污染程度。敝覆翡复杂程魔餐摇：版甏豹祥式是攀瓣还楚多样 他的，舨嚣缝搀是麓攀豹还跫复杂豹。 图像质嫩的不同决定了版面分析需疆对图像进彳亍不同的处理。版筒分析是一个很复杂 的过程，包括很多环节，而艟一般来讲个版面分析方法不阿能对所有类型的文档图像 都有好静楚灌绪采，它存一定静逶蠲藏匿。f i g u r e3 - 1 中鼹零是一个舨藤分轿系统静基 本缍残熬分： 本文关心麴 娃鞋步骤 x l | i 泣释：r ：衮承数糍状态 一 ( 二二3 ：裘承搽俸 f i g u r ea - 1 一般版面分析流程 零文繇糖氆豹版瑟分撰方法是一个蔽瑟分孝斥系翁的一部分，这个版面分析系统包括如 9 1 8 “。8 3 1 掰示的痰商处理步骤。图像二值他t 谈辩按燕，誊警努警是舨蘧势凝豹爨要 1 3 笺兰童= 全堑堕墨亘坌翅查婆塑煎堡 h _ “_ 一r 一 组成都分，肖其专门的技术，为了简便起熙，本文袋中讨论版丽分孝厅中的区域拆分过 程，如f i g u r e3 - l 中虚线樵中所示。即本文版面分析方法有如下前提条件： ( 1 ) 二能图像； ( 2 ) 鹭缀秃掇蕊，澄经竞袋 囊裁校燕； ( 3 ) 髫像没有太大鹣污染。 下面讨论一下本文的版面分桥方法适合的版面结构。版面结构的复杂性可以体现在多 个方面，比如区域并非矩形，文档中包含艇杂的激格结构等等。本文并不解决这些问 题，本文新针对瓣复杂敝霹楚赞躐予予报纸等 蠢况e 露些舨嚣分毒厅针对菜秽特定类型熬文拶鞠豫避行舨箍分攒，对舨甄绥梅鸯糕当多豹先 验知淡，那么版嚣麴复杂稷度是捆对比较低豹；褰易赣堪，辩技文献类瓣文档的版西结 构一般来说要比报纸的版谳结构简单。本文提出的版面分析方法怒可以解决报纸等复杂 版面结构的文横。其笈杂住体现在以下凡个方面： ( 1 )中文字褥熬复杂缝豢潦熬羧錾势援熬簸杂蠖； ( 2 ) 文楼强像豹叛巍缝掬风搭不一，虽文鬻孛懿送域缀鸯魄较复杂； ( 3 ) 版面中字体字号不一； ( 4 ) 文字方向不一：可以是横排、搬排或横竖漏排。 3 。2 本文的提出靛秀法综述 本文摁窭了令懿基疯内上秘鑫矮淘下鞠结合鹃凝嚣分褥算法，采雳这榉瓣方法毽交 如下。如前所述，自顶向下方法童要适用予下面掰个情况：一是商相当多的荚于版面结 构的先验知识时，可以采用基予模型的版丽分析力法，二是当文档图像中各个物理组件 之闯青绢嚣的黧盘区时，瑟叛采鬻投影分耩的方法我委g 缀件之阉鹃空自壤，邂步留分。 显纛箍冤，缀绥豹敝疆分褥并不瓣予渡上两释情溅，繇缓，一觳麴报纸激霭分撰方法都 采臻囊底囊上戆舨蘑分辑方法。遐一方嚣，在舨瓣分掇过程串霹驳褥到努裁羲令致壤戆 的黑线白线的信息，如果能加以利用，则对区域的切分肖指导作用。 浚方法也怒先从寻找文档图像的谶通体开始，从连通体垂文字行的含并是采用的自底 蠢上戆方浚。撼登撩麓文字簿套势为骚捧豹突字隧城魄楚健溺静裔赡巍上辩方法。毽是 援捺文字嚣蠲横撵莲竣是暴璃熬鑫疆囱下静方法。 1 4 第三章个新的版面分析方法的漉程 - _ 一一 3 。3 对板蘧复杂性豢函鹌分类帮对应鹤处理方法 经过大量样张的观察，造成中文报纸等文档图像版面结构复杂的因素w 以分为4 类： ( 1 ) 中文字符的不连通性造成的困难 中文字符的不连通性对黢露分毒髫的影是比较严重的。在使爝连遥髂方法进行舨面分享厅 时找笺豹连避侮卡分零薄，耗费时漓帮存镶，磊菇缀滚透过这些连遥蒋褥褥鬟任侮有瘸 的统计信息。闭比英文版面分析相比，自底向上的中文版面分析方法蒙多个从连通体 到字符的合并过程，而且这个合并过程的规则比较复杂因为一个连通体有从上下左右 任何方翔进行合并的可能。另外，程汉字字体比较大的时候，不连通性给字符的合并造 惑了更大匏骥鼹。毙懿在稼题中撼溪豹“二”字，缀滚翔瑟这嚣个连逶 搴起蚕应该台 并。 本文提出了一个新的连通体获取算法，找到的涟溉体并不是严格意义上的8 连通的连 通体，而基本上是几个中文字符的集合。这降低连通体获取的时间消耗，减少了连通体 静数目，也裔利予降低嚣续处理熬辩阕溃耗，同时减少鹣麸连通体到字符麴食势过程。 ( 2 ) 标题逡藏靛叛面分轿麴瓣滩 在人阅读报纸时，会觉得标题的出现令版面结构甄加明晰，这是因为。人在看报纸 时，第一眼就餐到比较显眼的标题。并且在下意识嫩将标题与正文分别对特，所以，甚 至只看标题就熊大体把握整个版灏结构。丽在版面分耩中，标题无论在义字方囱还是文 字大小彝潺躐上毒| l 与委交魏文字鸯缀丈戆蘧爱。穰楚大多数懿藏瑟势爨方法并没育怒标 题和文字区剐对待，这不仅仅没肖剿用标题对版面缩 訇提纲挈领的作用，黼且还造成一 些统计信息的谈差和自底向上合并的规则的混乱。如 1 8 中的预定阈值方法，在标题之 问的字符间距棋至犬于正文中文字行的间距的时候就会出现未能充分合弗域错误合并。 翔在 1 7 3 中趱到豹区域彩获会并麴方法，在耘题移燕文黪距褰枣子耘鬈字符之阕耱距 离翡瞎凝下会必黢。 在本文提出的方法中，标题和正文会得到区别对待：在得到文档图像的连通体之后会 首先寻找标题隧域，之后再分析豫文区域的划分。这样，在通过连通体的统计信息计算 正文字符平均瀚度和平均闯距时会遐擒准确，丽且，标题区域逸会辩以薅熟区域翅分提 供毒瑗兹参考嫠惑。 ( 3 ) 文字方囱的不确定造成的版籁分析困难 文字方向的不确定性包括文档网像可能是横排文档、竖排文档、横竖混排的文档。文 字方向的不确定会增加自底向上的含并或自顶向下的切分规则的混乱和艇杂度。对此， 第三章一个耨的版面分析方法的流程 f 1 8 采取静搭施是：假设无论旗撵文字还蓬竖莽 文字，其文字行( 猁) 内帮字蓊之阕静 距离是一样的。所以对字符到文字行的合并采用了相同的阈值。在 1 6 中采取的方法 是：假设无论横排文字还是竖排文字，其文字行( 列) 内部的字符之问的距离小于文字 行( 列) 之阍